单链表相关操作(基于C语言)

单链表界说

1. typedef struct node
2. {
3.         int data;
4.         struct node* next;
5. }LinkNode,*LinkList;

复制代码

版本一(可自己选择是否含头节点)

创建单链表

1. /**
2. * @brief 创建单链表
3. * @param head 单链表存储位置
4. * @param data 存储单链表的整数数组
5. * @param size 数组大小
6. * @param is_have_head 是否创建头节点，是为1，否则为0
7. */
8. LinkList CreateList(int data[], int size, int is_have_head) {
9.         LinkList head = NULL;
10.         LinkNode* p = NULL;
11.        
12.         head = (LinkNode*)malloc(sizeof(LinkNode));  // 创建头结点
13.         head->next = NULL;
14.         p = head;
16.         for (int i = 0; i < size; i++) {
17.                 LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
18.                 newNode->data = data[i];
19.                 newNode->next = NULL;
21.                 if (head == NULL) {
22.                         head = newNode;
23.                         p = head;
24.                 }
25.                 else {
26.                         p->next = newNode;
27.                         p = p->next;
28.                 }
29.         }
31.         if (!is_have_head && head != NULL) {  // 删除头结点
32.                 LinkNode* temp = head;
33.                 head = head->next;
34.                 free(temp);
35.         }
37.         return head;
38. }

复制代码

打印单链表

1. /**
2. * @brief 打印单链表
3. * @param head 单链表指针
4. * @param is_have_head 是否含头节点，是为1，否则为0
5. */
6. void PrintList(LinkList head, int is_have_head) {
7.         LinkNode* p = head;
8.         if (is_have_head) p = p->next;
9.         if (!p) printf("空链表！\a\n");
10.         else {
11.                 while (p) {
12.                         printf("%d->", p->data);
13.                         p = p->next;
14.                 }
15.                 printf("NULL\n");
16.         }
17. }

复制代码

对单链表举行冒泡排序

1. /**
2. * @brief 对单链表进行冒泡排序
3. * @param L 单链表指针L
4. * @param is_have_head 是否含头节点，是为1，否则为0
5. */
6. void LinkBubbleSort(LinkList L, int is_have_head) {
7.         LinkNode* head = L;
8.         if (is_have_head) head = head->next;
9.         LinkNode* p = head, * q = p->next, * last = NULL;
10.         if (p == NULL || q == NULL) return;
11.         while (head->next != last) {
12.                 while (q && q != last ) {
13.                         if (p->data > q->data) {
14.                                 int temp = p->data;
15.                                 p->data = q->data;
16.                                 q->data = temp;
17.                         }
18.                         p = q;
19.                         q = q->next;
20.                 }
21.                 last = p;
22.                 p = head;
23.                 q = p->next;
24.         }
25. }

复制代码

删除单链表中值为key的节点

1. /**
2. * @brief 删除单链表中值为key的节点
3. * @param L 单链表L
4. * @param key 目标值key
5. * @param is_have_head 是否含头节点，是为1，否则为0
6. * @return 删除成功返回true，否则返回false
7. */
8. bool ListDeleteNode(LinkList L, int key, int is_have_head) {
9.         LinkNode* p = L, * pre = NULL;
10.         if (is_have_head) {
11.                 pre = p;
12.                 p = p->next;
13.         }
14.         while (p && p->data != key) {
15.                 pre = p;
16.                 p = p->next;
17.         }
18.         if (!p) return false;
19.         pre->next = p->next;
20.         free(p);
21.         return true;
22. }

复制代码

求单链表表长

2. /**
3. * @brief 求链表长度
4. * @param L 表头指针
5. * @param is_have_head 是否含头结点，是为1，否则为0
6. * @return 返回单链表的长度(不含头结点)，空表返回0
7. */
8. int GetListSize(LinkList L, int is_have_head) {
9.         LinkNode* p = L;
10.         if (p == NULL) return 0;
11.         if (is_have_head) p = p->next;
13.         int count = 0;
14.         while (p) {
15.                 count++;
16.                 p = p->next;
17.         }
18.         return count;
19. }

复制代码

在单链表位序为i的位置插入新元素e

1. /**
2. * @brief 在单链表位序为i的位置插入新元素e
3. * @param L 表头指针
4. * @param i 插入位置(1<=i<=GetListSize(L)+1)
5. * @param e 待插入元素e
6. * @param is_have_head 是否含头结点，是为1，否则为0
7. * @return 插入成功返回1，否则返回0
8. */
9. int ListInsert(LinkList L, int i, int e, int is_have_head) {
10.         int list_size = GetListSize(L, is_have_head);
11.         if (i < 1 || i > list_size + 1) return 0;  // 位序非法
13.         LinkNode* p = L, * pre = NULL;
14.         int cur = 1;
15.         if (is_have_head) {
16.                 pre = p;
17.                 p = p->next;
18.         }
20.         while (cur < i) {
21.                 pre = p;
22.                 p = p->next;
23.                 cur++;
24.         }
26.         LinkNode* new_node = (LinkNode*)malloc(sizeof(LinkNode));
27.         new_node->data = e;
28.         if (pre == NULL) { // 第一个位置插入
29.                 new_node->next = L;
30.                 L = new_node;
31.         }
32.         else {
33.                 new_node->next = p;
34.                 pre->next = new_node;
35.         }
36.         return 1;
37. }

复制代码

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