链表基本操作

这里我们来看看链表的基本操作:

  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 }

代码相当简单,就不再多叙述了。来看看运行效果:

链表基本操作

 

上一篇:线性表的链式存储--单链表


下一篇:C/C++编程笔记:图书管理系统(C语言链表),项目源码献上