若有一个无序顺序表r1和递增有序顺序表r2,它们均含有n个元素,且可能存在相同关键字的元素。设计两个算法分别输出r1和r2中第一个关键字为k的元素位置,并分析成功查找的平均查找长度。
时间: 2023-05-03 18:00:15 浏览: 75
题目描述:给定两个无序顺序表r1和r2,它们均含有n个元素,并可能存在相同关键字的元素。设计两个算法分别输入r1和r2中第一个关键字为k的元素位置,并分析成本查找的平均查找长度。
答案:
该题考查的是查找算法。
算法一:顺序查找
该算法是从表的第一个元素开始顺序地对每一个元素进行比较,直到找到关键字等于k的元素为止。
该算法的成本是:
当查找到目标元素在待查找表的前面时,需要进行n次比较,查找成本为(n+1)/2。
当查找到目标元素在待查找表的后面时,需要进行n次比较,查找成本为n。
当目标元素不存在时,需要进行n次比较,查找成本为(n+1)/2。
因此平均查找长度为:
(n+(n+1)/2)/n= (3n+1)/4
算法二:折半查找
该算法是利用顺序表有序的特点,先将表分成两个部分,然后取中间位置的元素与关键字进行比较,如果相等,直接返回;如果中间位置的元素大于关键字,则在左半部分中继续查找;否则在右半部分中继续查找。
该算法的成本是:
当查找到目标元素时,需要进行k次比较,查找成本为log2n。
当目标元素不存在时,需要进行k次比较,查找成本为log2(n+1)
因此平均查找长度为:
[(log2n+1)/n ]+[(log2(n+1)+1)/n]
=([log2n+log2(n+1)+2]/n)
知识拓展:
平均查找长度是评价查找算法的一个重要指标,它反映了查找算法的效率。在某种意义上,它反映了查找数据所需的平均操作次数。它越小,则说明查找算法越优秀。
相关问题
设顺序表 a,其数据元素值无序且重复 按照顺序表 a 生成一个升序有序且不含重复值的单向链表
好的,针对您的问题,我可以提供以下思路:
1. 首先创建一个空的单向链表,用来存放升序有序且不含重复值的元素。
2. 遍历顺序表 a 中的每一个元素,对每个元素进行如下操作:
a. 如果链表为空,则将该元素插入链表头部。
b. 如果链表不为空,则从链表头部开始遍历,找到第一个大于等于该元素值的节点,并将该元素插入该节点之前。
c. 如果链表中已经存在该元素,则不进行插入操作。
3. 遍历完顺序表 a 中的所有元素后,得到的就是一个升序有序且不含重复值的单向链表。
以下是一个示例代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def create_linked_list(a):
head = None
for val in a:
if not head:
head = Node(val)
else:
if val == head.val:
continue
if val < head.val:
node = Node(val)
node.next = head
head = node
else:
prev = head
curr = head.next
while curr and curr.val < val:
prev = curr
curr = curr.next
if curr and curr.val == val:
continue
node = Node(val)
node.next = curr
prev.next = node
if not curr:
break
return head
```
这个函数接收一个顺序表 a 作为参数,返回一个升序有序且不含重复值的单向链表头节点。您可以将需要排序的顺序表作为参数传入该函数中。
用c语言写一个程序:创建顺序表,输入顺序表中的元素,判断元素是否有序
以下是一个示例 C 语言程序,它创建了一个顺序表,输入元素,并判断元素是否有序:
```
#include <stdio.h>
#define MAX_SIZE 100
int main() {
int list[MAX_SIZE];
int n, i, isSorted = 1;
printf("请输入顺序表的大小: ");
scanf("%d", &n);
printf("请输入顺序表中的元素: ");
for (i = 0; i < n; i++) {
scanf("%d", &list[i]);
}
for (i = 1; i < n; i++) {
if (list[i] < list[i-1]) {
isSorted = 0;
break;
}
}
if (isSorted) {
printf("顺序表中的元素有序\n");
} else {
printf("顺序表中的元素无序\n");
}
return 0;
}
```
这段程序首先声明了一个名为 "list" 的整型数组,并使用宏定义 MAX_SIZE 设置了数组的最大长度。 然后在 main() 函数中,程序请求用户输入顺序表的大小和顺序表中的元素。 之后程序使用一个 for 循环来检查顺序表中的元素是否有序。如果顺序表中的元素是有序的,程序将打印一条消息,告诉用户顺序表中的元素有序。否则,程序将打印一条消息,告诉用户顺序表中的元素无序。