数据结构第一轮复习--第七章查找（包罗课程代码）

基于数组实现次序查找代码

1. //顺序查找的实现
2. typedef struct{                //查找表的数据结构（顺序表）
3.         ElemType *elem;        //指向开辟的动态数组基址 （起始地址）
4.         int TableLen;        //表的长度
5. }SSTable;
6. //顺序查找
7. int Search_Seq(SSTable ST,ElemType key){
8.         int i;
9.         for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
10.         //查找成功，则返回元素下标；查找失败，则返回-1
11.         return i==SSTable? -1 : i;
12. }

复制代码

基于链表实现次序查找代码

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义链表节点的数据类型
5. typedef int ElemType;
7. // 定义链表节点结构
8. typedef struct Node {
9.     ElemType data;       // 数据域，存储节点的值
10.     struct Node* next;   // 指针域，指向下一个节点
11. } Node;
13. // 定义链表结构
14. typedef struct {
15.     Node* head;          // 指向链表的头节点
16. } LinkedList;
18. // 创建链表（假设链表是带头节点的单链表）
19. LinkedList* CreateLinkedList() {
20.     // 分配内存空间给链表结构
21.     LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
22.     if (list == NULL) {
23.         printf("Memory allocation failed for LinkedList.\n");
24.         return NULL; // 如果分配失败，返回NULL
25.     }
27.     // 分配内存空间给头节点
28.     list->head = (Node*)malloc(sizeof(Node));
29.     if (list->head == NULL) {
30.         free(list); // 如果头节点分配失败，释放之前分配的链表结构内存
31.         printf("Memory allocation failed for head node.\n");
32.         return NULL;
33.     }
35.     // 初始化头节点，头节点不存储实际数据，其next指针初始化为NULL
36.     list->head->next = NULL;
37.     return list; // 返回创建好的链表
38. }
40. // 向链表中插入节点（在链表尾部插入）
41. void InsertNode(LinkedList* list, ElemType value) {
42.     // 分配内存空间给新节点
43.     Node* newNode = (Node*)malloc(sizeof(Node));
44.     if (newNode == NULL) {
45.         printf("Memory allocation failed for new node.\n");
46.         return; // 如果分配失败，直接返回
47.     }
49.     // 设置新节点的数据域和指针域
50.     newNode->data = value;
51.     newNode->next = NULL;
53.     // 从头节点开始，找到链表的尾部节点
54.     Node* current = list->head;
55.     while (current->next != NULL) { // 当前节点的next不为NULL，说明不是尾部节点
56.         current = current->next; // 移动到下一个节点
57.     }
59.     // 将新节点链接到链表尾部
60.     current->next = newNode;
61. }
63. // 顺序查找（基于链表）
64. int Search_Seq(LinkedList* list, ElemType key) {
65.     // 从头节点的下一个节点开始（跳过头节点，从第一个实际节点开始）
66.     Node* current = list->head->next;
67.     int index = 0; // 用于记录当前节点的索引，从0开始
69.     // 遍历链表
70.     while (current != NULL) {
71.         if (current->data == key) { // 如果当前节点的数据等于目标值
72.             return index; // 返回当前节点的索引
73.         }
74.         current = current->next; // 移动到下一个节点
75.         index++; // 索引加1
76.     }
78.     // 如果遍历完整个链表都没有找到目标值，返回-1
79.     return -1;
80. }
82. // 释放链表内存
83. void FreeLinkedList(LinkedList* list) {
84.     // 从头节点开始释放链表内存
85.     Node* current = list->head;
86.     while (current != NULL) {
87.         Node* temp = current; // 保存当前节点
88.         current = current->next; // 移动到下一个节点
89.         free(temp); // 释放当前节点的内存
90.     }
91.     free(list); // 最后释放链表结构的内存
92. }
94. // 测试代码
95. int main() {
96.     // 创建链表
97.     LinkedList* list = CreateLinkedList();
98.     if (list == NULL) {
99.         return -1; // 如果链表创建失败，退出程序
100.     }
102.     // 向链表中插入一些数据
103.     InsertNode(list, 10);
104.     InsertNode(list, 20);
105.     InsertNode(list, 30);
106.     InsertNode(list, 40);
108.     // 测试顺序查找
109.     int key = 30; // 要查找的目标值
110.     int result = Search_Seq(list, key); // 调用顺序查找函数
111.     if (result != -1) {
112.         printf("Element %d found at index %d.\n", key, result); // 找到目标值，输出索引
113.     } else {
114.         printf("Element %d not found.\n", key); // 没有找到目标值
115.     }
117.     // 释放链表内存
118.     FreeLinkedList(list);
119.     return 0; // 程序正常结束
120. }

复制代码

 次序查找的实现（哨兵）

1. //顺序查找（哨兵）
2. typedef struct{                //查找表的数据结构（顺序表）
3.         ElemType *elem;        //指向开辟的动态数组基址 （起始地址）
4.         int TableLen;        //表的长度
5. }SSTable;
6. //顺序查找
7. int Search_Seq(SSTable ST,ElemType key){
8.         ST.elem[0]=key;                //哨兵
9.         int i;
10.         for(i=ST.TableLen; ST.elem[i]!=key;--i);        //从后往前找
11.         //查找成功，则返回元素下标；查找失败，则返回0
12.         return i；
13. }

复制代码

折半查找的实现（二分查找）

1. //折半查找的实现（二分查找）
2. typedef struct{                //查找表的数据结构（顺序表）
3.         ElemType *elem;        //指向开辟的动态数组基址 （起始地址）
4.         int TableLen;        //表的长度
5. }SSTable;
6. //折半查找
7. int Binary_Search(SSTable L,ElemType key){
8.         int low=0,high=L.TableLen-1,mid;
9.         while(low<=high){
10.                 mid=(low+high)/2;        //取中间位置
11.                 if(L.elem[mid]==key)
12.                         return mid;                //查找成功则返回所在位置
13.                 else if(L.elem[mid]>key)
14.                         high=mid-1;                //从前半部分继续查找
15.                 else
16.                         low=mid+1;                //从后半部分继续查找
17.         }
18.         return -1;                                //查找失败，返回-1
19. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。