重生之我在异世界学编程之数据布局与算法：单链表篇 ...

各人好，这里是小编的博客频道
小编的博客：就爱学编程
    很高兴在CSDN这个各人庭与各人相识，希望能在这里与各人共同进步，共同劳绩更好的本身！！！
  
  
引言

在C语言中，数据布局的掌握对于高效编程至关重要。此中，单链表作为一种底子且常用的数据布局，具有独特的上风和应用场景。下面将对单链表进行具体介绍，并概述实在现方法。一起来看看吧！！！

---

   那接下来就让我们开始遨游在知识的海洋！
  正文

---

一、单链表的概念与布局

   

• 单链表（Singly Linked List）是链式存取的数据布局的一种，它用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以节点（Node）来表示的，每个节点包含两部分：数据域和[指针域。数据域用于存储数据元素，而指针域则用于指向下一个节点的地址。末了一个节点的指针域指向NULL，表示链表的末了。
  

  具体来说，单链表的布局可以定义如下：

2. typedef int SLLDataType; // 单链表存贮的数据类型
4. typedef struct SLLNode {
5.     SLLDataType data;      // 数据域
6.     struct SLLNode* next;  // 指针域，指向下一个节点的地址
7. } Node;

复制代码

---

二、单链表的上风与应用

相较于顺序表（即数组），单链表具有以下上风：
   插入和删除操作高效：在顺序表中插入或删除数据需要移动大量元素，而在单链表中，只需改变相关节点的指针域即可，时间复杂度较低。
    动态分配内存：单链表可以根据需要动态申请或开释内存空间，避免了顺序表因巨细固定而造成的内存浪费或不敷标题。
    灵活性强：单链表适用于各种复杂的数据处理场景，如循环链表、双向链表等都是由单链演出变而来的。
  

• 单链表广泛应用于各种数据处理场景中，如实现队列、栈等抽象数据类型，以及办理图论、排序等标题。
  

---

三、单链表的实现概述

单链表的实现主要包括以下几个关键步骤：
在C语言中，单链表是一种常见的数据布局，它由一系列节点（Node）组成，每个节点包含数据部分和指向下一个节点的指针。下面我将具体讲解怎样用C语言实现单链表的关键部分，包括节点定义、创建链表、插入节点、删除节点以及遍历链表等操作。

---

1. 定义节点布局

首先，我们需要定义一个布局体来表示链表的节点：

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 定义节点结构
5. typedef struct Node {
6.     int data;           // 数据域
7.     struct Node* next;  // 指针域，指向下一个节点
8. } Node;

复制代码

---

2. 创建链表

创建一个空链表通常意味着初始化一个头指针为NULL：

1. Node* createList() {
2.     return NULL;  // 空链表的头指针为NULL
3. }

复制代码

---

3. 在链表头部插入节点

在链表头部插入一个新节点是一个常见的操作。我们首先需要为新节点分配内存，然后设置其数据和指针，末了更新头指针。

1. void insertAtHead(Node** head, int newData) {
2.     // 为新节点分配内存
3.     Node* newNode = (Node*)malloc(sizeof(Node));
4.     if (!newNode) {
5.         printf("Memory allocation error
6. ");
7.         return;
8.     }
10.     // 设置新节点的数据
11.     newNode->data = newData;
13.     // 将新节点的next指针指向当前的头节点
14.     newNode->next = *head;
16.     // 更新头指针
17.     *head = newNode;
18. }

复制代码

---

4. 删除指定值的节点

删除指定值的节点需要遍历链表并找到目标节点的前一个节点，然后修改前一个节点的next指针以跳过目标节点。同时，别忘了开释被删除节点的内存。

1. void deleteNode(Node** head, int key) {
2.     // 存储临时头指针，用于处理头节点被删除的情况
3.     Node* temp = *head;
4.     Node* prev = NULL;
6.     // 如果头节点就是要删除的节点
7.     if (temp != NULL && temp->data == key) {
8.         *head = temp->next;   // 改变头指针
9.         free(temp);           // 释放旧头节点
10.         return;
11.     }
13.     // 查找要删除的节点，保持对前一个节点的引用
14.     while (temp != NULL && temp->data != key) {
15.         prev = temp;
16.         temp = temp->next;
17.     }
19.     // 如果没有找到该值的节点
20.     if (temp == NULL) return;
22.     // 从链表中断开节点，并释放内存
23.     prev->next = temp->next;
24.     free(temp);
25. }

复制代码

---

5. 遍历链表

遍历链表意味着重新节点开始，依次访问每一个节点直到碰到NULL指针。

1. void printList(Node* node) {
2.     while (node != NULL) {
3.         printf("%d -> ", node->data);
4.         node = node->next;
5.     }
6.     printf("NULL
7. ");
8. }

复制代码

---

6. 主函数示例

以下是一个简单的主函数示例，展示了怎样使用上述函数来操作单链表：

1. int main() {
2.     Node* head = createList();
4.     insertAtHead(&head, 1);
5.     insertAtHead(&head, 2);
6.     insertAtHead(&head, 3);
8.     printf("Created linked list: ");
9.     printList(head);
11.     deleteNode(&head, 2);
12.     printf("
13. Linked list after deleting 2: ");
14.     printList(head);
16.     return 0;
17. }

复制代码

总结

• 以上代码展示了怎样在C语言中实现和操作一个简单的单链表。关键部分包括节点布局的定义、链表的创建、节点的插入与删除以及链表的遍历。这些基本操作是单链表实现的底子，也是理解和扩展更复杂数据布局的重要步骤。
  

---

四、源码

   注意：这是小编本身写的，可能有不敷之处，仅供参考！！！
  （1）SLT.h

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<assert.h>
5. typedef int SLTDateType;
6. typedef struct SListNode
7. {
8.         SLTDateType data;
9.         struct SListNode* next;
10. }SListNode;
12. // 动态申请一个节点
13. SListNode* BuySListNode(SLTDateType x);
15. // 单链表打印
16. void SListPrint(SListNode* plist);
18. // 单链表尾插
19. void SListPushBack(SListNode** pplist, SLTDateType x);
21. // 单链表的头插
22. void SListPushFront(SListNode** pplist, SLTDateType x);
24. // 单链表的尾删
25. void SListPopBack(SListNode** pplist);
27. // 单链表头删
28. void SListPopFront(SListNode** pplist);
30. // 单链表查找
31. SListNode* SListFind(SListNode* plist, SLTDateType x);
33. // 单链表在pos位置之后插入x
34. // 分析思考为什么不在pos位置之前插入？
35. void SListInsertAfter(SListNode* pos, SLTDateType x);
37. // 单链表删除pos位置之后的值
38. // 分析思考为什么不删除pos位置？
39. void SListEraseAfter(SListNode* pos);
41. // 在pos的前面插入
42. void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
44. // 删除pos位置
45. void SLTErase(SListNode** pphead, SListNode* pos);
47. //销毁链表
48. void SLTDestroy(SListNode** pphead);

复制代码

---

（2）SLT.c

1. #include"SLT.h"
3. // 动态申请一个节点
4. SListNode* BuySListNode(SLTDateType x) {
5.         SListNode* ptr = (SListNode*)malloc(sizeof(SListNode));
6.         if (ptr == NULL) {
7.                 return NULL;
8.         }
9.         ptr->data = x;
10.         ptr->next = NULL;
11.         return ptr;
12. }
14. // 单链表打印
15. void SListPrint(SListNode* plist) {
16.         SListNode* cur = plist;
17.         while (cur) {
18.                 printf("%d->", cur->data);
19.                 cur = cur->next;
20.         }
21.         printf("NULL");
22.         printf("\n");
23. }
25. // 单链表的头插
26. void SListPushFront(SListNode** pplist, SLTDateType x)
27. {
28.         SListNode* newnode = BuySListNode(x);
29.         newnode->next = *pplist;
30.         *pplist = newnode;
31. }
33. // 单链表尾插
34. void SListPushBack(SListNode** pplist, SLTDateType x) {
35.         assert(pplist);
36.         if (NULL == *pplist) {
37.                 SListPushFront(pplist, x);
38.                 return;
39.         }
40.         SListNode* newnode = BuySListNode(x);
41.         SListNode* fail = *pplist;
42.         while (fail->next) {
43.                 fail = fail->next;
44.         }
45.         fail->next = newnode;
46. }
48. // 单链表的尾删
49. void SListPopBack(SListNode** pplist) {
50.         //一个节点和多个节点
51.         assert(pplist && *pplist);
52.         //一个节点
53.         if ((*pplist)->next == NULL) {
54.                 free(*pplist);
55.                 *pplist = NULL;
56.         }
57.         //多个节点
58.         SListNode* fail = *pplist;
59.         SListNode* perv = *pplist;
60.         while (fail->next) {
61.                 perv = fail;
62.                 fail = fail->next;
63.         }
64.         free(fail);
65.         //fail = NULL;               //这一步不会把删除后的最后一个节点的next指针改为NULL，这就要对于变量赋值和改值要有理解。
66.         perv->next = NULL;
67. }
69. // 单链表头删
70. void SListPopFront(SListNode** pplist) {
71.         assert(pplist && *pplist);
72.         SListNode* cur = *pplist;
73.         *pplist = cur->next;
74.         free(cur);
75. }
77. // 单链表查找
78. SListNode* SListFind(SListNode* plist, SLTDateType x) {
79.         assert(plist);
80.         SListNode* cur = plist;
81.         while (cur) {
82.                 if (cur->data == x)
83.                         return cur;
84.         }
85.         printf("找不到\n");
86.         return NULL;
87. }
89. // 单链表在pos位置之后插入x
90. // 分析思考为什么不在pos位置之前插入？
91. void SListInsertAfter(SListNode* pos, SLTDateType x) {
92.         assert(pos);
93.         SListNode* cur = BuySListNode(x);
94.         cur->next = pos->next;
95.         pos->next = cur;
96. }
98. // 单链表删除pos位置之后的值
99. // 分析思考为什么不删除pos位置？
100. void SListEraseAfter(SListNode* pos) {
101.         assert(pos && pos->next);
102.         SListNode* temp = pos->next->next;
103.         free(pos->next);
104.         pos->next = temp;
105. }
107. // 在pos的前面插入
108. void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {
109.         assert(pphead && *pphead);
110.         SListNode* ptr = BuySListNode(x);
111.         SListNode* cur = *pphead;
112.         if (cur == pos) {
113.                 SListPushFront(pphead, x);
114.                 return;
115.         }
116.         while (cur->next != pos && cur->next) {
117.                 cur = cur->next;
118.         }
119.         if(cur->next == pos){
120.                 cur->next = ptr;
121.                 ptr->next = pos;
122.                 return;
123.         }
124.         else assert(cur->next);
125. }
126.        
127. // 删除pos位置
128. void SLTErase(SListNode** pphead, SListNode* pos) {
129.         assert(pphead && *pphead);
130.         if (*pphead == pos) {
131.                 SListPopFront(pphead);
132.                 return;
133.         }
134.         SListNode* cur = *pphead;
135.         while (cur->next != pos && cur->next) {
136.                 cur = cur->next;
137.         }
138.         assert(cur->next);
139.         cur->next = pos->next;
140.         free(pos);
141. }
143. //销毁链表
144. void SLTDestroy(SListNode** pphead) {
145.         SListNode* cur = *pphead;
146.         while (cur) {
147.                 SListNode* temp = cur->next;
148.                 free(cur);
149.                 cur = temp;
150.         }
151.         *pphead = NULL;
152. }

复制代码

---

（3）Test.c

1. #include"SLT.h"
2. void test3() {
3.         SListNode* n1 = BuySListNode(1);
4.         SListNode* n2 = BuySListNode(2);
5.         n1->next = n2;
6.         n2->next = NULL;
8.         SListInsertAfter(n1, 3);
9.         SListInsertAfter(n2, 4);
11.         SListPrint(n1);
13.         SListEraseAfter(n1);
14.         SListEraseAfter(n2);
16.         SListPrint(n1);
18.         SLTInsert(&n1, n2, 5);
20.         SListPrint(n1);
22.         SLTErase(&n1, n2);
24.         SListPrint(n1);
26.         /*SLTErase(&n1, n1);
27.         SListPrint(n1);*/
29.         SLTDestroy(&n1);
30. }
33. void test2() {
34.         SListNode* n1 = BuySListNode(1);
35.         SListNode* n2 = BuySListNode(2);
36.         n1->next = n2;
37.         n2->next = NULL;
39.         SListPushBack(&n1, 3);
40.         SListPushBack(&n1, 4);
42.         SListPrint(n1);
44.         SListPopBack(&n1);
45.         SListPopBack(&n1);
47.         SListPrint(n1);
49.         SListPopFront(&n1);
51.         SListPrint(n1);
53.         SLTDestroy(&n1);
54. }
55. void test1() {
56.         SListNode* n1  = BuySListNode(1);
57.         SListNode* n2  = BuySListNode(2);
58.         n1->next = n2;
59.         n2->next = NULL;
61.         SListPrint(n1);
63.         SLTDestroy(&n1);
64. }
66. int main() {
67.         test3();
68.         return 0;
69. }

复制代码

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！


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