这里我们来看看链表的基本操作:
1 #define _CRT_SECURE_NO_WARNINGS 1 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 struct Node { 6 int data; 7 struct Node* next; 8 }; 9 10 struct Node* CreateList() //创建链表的函数 11 { 12 struct Node* headNode = (struct Node*)malloc(sizeof(struct Node)); 13 headNode->next = NULL; 14 return headNode; 15 } 16 17 struct Node* CreateNode(int data) //创建节点 18 { 19 struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); 20 newNode->data = data; 21 newNode->next = NULL; 22 return newNode; 23 } 24 25 int ListLength(struct Node* headNode) //获取链表长度 26 { 27 int len = 0; 28 while (headNode) 29 { 30 headNode = headNode->next; 31 len++; 32 } 33 return len; 34 } 35 36 int GetData(struct Node* headNode, int data) //查找函数 37 { 38 if (headNode == NULL) { 39 return NULL; 40 } 41 struct Node* posNode = headNode->next; 42 int j = 1; 43 while (posNode) 44 { 45 if (posNode->data == data) { 46 return j; 47 } 48 posNode = posNode->next; 49 j++; 50 } 51 return -1; 52 } 53 54 void DeleteNodeInOneMinute(struct Node* headNode, struct Node* target) //在O(1)的时间复杂度内删除结点 55 { 56 if (headNode->next == NULL) { //只有一个节点 57 return; 58 } 59 if (target->next == NULL) { //要删除结点是尾结点 60 if (headNode->next == target) { //头结点下一个结点即尾结点 61 headNode->next = NULL; 62 free(target); 63 } 64 else { 65 struct Node* pMove = headNode->next; //控制pMove指针不断向前移动 66 while (pMove->next != target) 67 { 68 pMove = pMove->next; 69 } 70 pMove->next = NULL; 71 free(target); 72 } 73 return; 74 } 75 struct Node* temp = target->next; 76 target->data = temp->data; 77 target->next = temp->next; 78 free(temp); 79 } 80 81 82 void deleteNodeByPosition(struct Node* headNode, int num) //删除某个节点 83 { 84 struct Node* posNodeFront = headNode; //当前节点的前面一个节点是头结点 85 struct Node* posNode = headNode->next; // 当前节点从头结点下一个开始 86 if (posNode == NULL) { 87 printf("链表为空,无法删除!\n"); 88 } 89 else { 90 while (posNode->data != num) //这个循环用来控制指针不断往前移,直到找到num 91 { 92 posNodeFront = posNode; //如果不是要找的节点,就推动当前节点往前走 93 posNode = posNode->next; 94 if (posNode == NULL) //如果一直找遍了链表都没找到的话 95 { 96 printf("未找到相关信息!\n"); 97 return; //直接使函数返回 98 } 99 } 100 posNodeFront->next = posNode->next; 101 free(posNode); //一定要记得释放被删除的节点 102 } 103 } 104 105 void InsertNode(struct Node* headNode,int index, int data) //在指定位置插入节点 106 { 107 if (!headNode || index<=0 || index>ListLength(headNode)) { //未找到返回-1 108 return -1; 109 } 110 else if (index == 1) { //单独考虑第一个位置的插入情况 111 struct Node* newNode = CreateNode(data); 112 newNode->next = headNode->next; 113 headNode->next = newNode; 114 } 115 else { 116 struct Node* temp = headNode; 117 for (int i = 0; i < index-1; i++) { //控制temp指针一直移动 118 temp = temp->next; 119 } 120 struct Node* newNode = CreateNode(data); 121 newNode->next = temp->next; 122 temp->next = newNode; 123 } 124 } 125 126 void purge(struct Node* headNode) //去重函数 127 { 128 struct Node* p, * q, * succ, * cur; 129 p = headNode->next; 130 headNode->next = NULL; 131 while (p != NULL) 132 { 133 succ = p->next; // 记下结点p的后继 134 q = headNode->next; //q指向新表的第一个结点 135 cur = headNode; //这里cur指针必须先初始化,否则会报错 136 while (q && p->data != q->data) //检查的时候必须从第一个结点开始检查 137 { 138 cur = q; //记录下q的前一个结点 139 q = q->next; //控制q指针后移 140 } 141 if (!q) { 142 cur->next = p; 143 p->next = NULL; 144 } 145 else { 146 free(p); //重复结点就抛弃,一定要记得释放! 147 } 148 p = succ; 149 } 150 } 151 152 void printList(struct Node* headNode) //打印链表 153 { 154 struct Node* pMove = headNode->next; //打印链表应该从头节点下一个开始 155 while (pMove != NULL) //为空的话肯定就不能打印 156 { 157 printf("%d ", pMove->data); 158 pMove = pMove->next; 159 } 160 printf("\n"); 161 } 162 163 int main(void) 164 { 165 struct Node* List = CreateList(); //创建链表 166 int i, data, pos; 167 while (1) 168 { 169 printf("1.在指定位置处插入数据;2.查找某个数据;3.删除某个数据;4.打印链表;5.链表去重;6.退出;请输入你的选择:"); 170 scanf("%d", &i); 171 if (i == 1) { 172 printf("请输入你想要添加的位置:"); 173 scanf("%d", &pos); 174 printf("请输入你想要添加的数据:"); 175 scanf("%d", &data); 176 InsertNode(List, pos, data); 177 } 178 else if (i == 2) { 179 printf("请输入你想要查询的数据:"); 180 scanf("%d", &data); 181 pos = GetData(List, data); 182 printf("你查找的数据的位置在:%d", pos); 183 printf("\n"); 184 } 185 else if (i == 3) { 186 printf("请输入你想要删除的数据:"); 187 scanf("%d", &data); 188 deleteNodeByPosition(List, data); 189 } 190 else if (i == 4) { 191 printList(List); 192 } 193 else if (i == 5) { 194 purge(List); 195 } 196 else if (i == 6) { 197 break; 198 } 199 } 200 return 0; 201 }
代码相当简单,就不再多叙述了。来看看运行效果: