线性结构之链表

离散存储[链表]：
  定义：
    n个结点的离散分配
    彼此通过指针相连
    每个结点只有一个前续结点
    每个结点只有一个后续结点
    首结点没有前续结点
    尾结点没有后续结点
  专业术语：
    首结点：第一个有效结点，存放第一个有效数据
    尾结点：最后一个有效结点，存放最后一个有效数据
    头结点：在首结点之前的一个结点，既不存放有效数据，也不存放有效结点的个数，加头结点的主要目的是为了方便对链表的操作，头结点的数据类型和其他结点的数据类型是一样的
    头指针：指向头结点的指针变量，存放了头结点的地址
    尾指针：指向尾结点的指针变量，存放了尾结点的地址
  确定一个链表至少需要哪些参数：
    只需要一个参数：头指针
    因为我们通过头指针就可以推出链表的其他所有信息
  链表的分类：
    单链表：每一个结点只有一个指针域
    双链表：每一个结点有两个指针域
    循环链表：能通过任何一个结点找到其他所有的结点
    非循环链表
 
  算法：
    狭义的算法是与数据存储方式密切相关的
    广义的算法与数据存储方式无关
    泛型：你用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

1. /*
2. @file      main.c
3. @brief     线性结构之链表
4. @author    EricsT (EricsT@163.com)
5. @version   v1.0.0
6. @date      2025-09-21
7. @history   2025-09-21 EricsT - 新建文件
8.            2025-09-22 EricsT - 新增 CreateList\TraverseList
9.            2025-09-22 EricsT - 新增 isEmptyList\GetLenthList\InsertList\DeleteList\SortList
10. */
12. #include <stdio.h>
13. #include <malloc.h>
14. #include <stdlib.h>
16. typedef struct Node
17. {
18.         int data;//数据域
19.         Node* ptrNext;//指针域
20. }* PtrNode, NODE;//NODE 相当于 Node NODE//ptrNode 相当于 Node* ptrNode
22. PtrNode CreateList();//创建链表
23. void TraverseList(const PtrNode ptrNode);//遍历链表
24. bool isEmptyList(const PtrNode ptrNode);//是否为空
25. int GetLenthList(const PtrNode ptrNode);//获取链表长度
26. bool InsertList(PtrNode ptrNode, int insertPos, int insertData);//插入结点
27. bool DeleteList(PtrNode ptrNode, int deletePos);//删除结点
28. void SortList(PtrNode ptrNode);//排序
30. int main(void)
31. {
32.         PtrNode ptrNode = NULL;
33.         ptrNode = CreateList();
34.         TraverseList(ptrNode);
36.         if (isEmptyList(ptrNode))
37.                 printf("链表为空\n");
38.         else
39.                 printf("链表非空\n");
41.         printf("链表长度为：%d\n", GetLenthList(ptrNode));
43.         int insertPose;
44.         printf("请输入插入位置");
45.         scanf("%d", &insertPose);
47.         int insertValue;
48.         printf("请输入插入数值");
49.         scanf("%d", &insertValue);
51.         InsertList(ptrNode, insertPose, insertValue);
53.         TraverseList(ptrNode);
55.         int deletePose;
56.         printf("请输入删除位置");
57.         scanf("%d", &deletePose);
59.         DeleteList(ptrNode, deletePose);
61.         TraverseList(ptrNode);
63.         SortList(ptrNode);
65.         TraverseList(ptrNode);
67.         return 0;
68. }
70. PtrNode CreateList()
71. {
72.         int len;
74.         printf("请输入结点个数len = ");
75.         scanf("%d", &len);
77.         int addr = 0;
79.         PtrNode ptrNodeFirst = (PtrNode)malloc(sizeof(NODE));//头结点
80.        
81.         if (NULL == ptrNodeFirst)
82.         {
83.                 printf("分配失败\n");
84.                 exit(-1);
85.         }
87.         PtrNode ptrNodeLast = ptrNodeFirst;//尾结点
88.         ptrNodeLast->ptrNext = NULL;
90.         for (int i = 0; i < len; ++i)
91.         {
92.                 PtrNode ptrNode = (PtrNode)malloc(sizeof(PtrNode));//新的尾结点
93.                 if (NULL == ptrNodeFirst)
94.                 {
95.                         printf("分配失败\n");
96.                         exit(-1);
97.                 }
99.                 ptrNodeLast->ptrNext = ptrNode;//新的尾结点挂在旧的尾结点后面
101.                 printf("请输入%d个结点的数值", i + 1);
102.                 scanf("%d", &ptrNode->data);
103.                 ptrNode->ptrNext = NULL;
105.                 ptrNodeLast = ptrNode;//更新尾结点
106.         }
108.         return ptrNodeFirst;
109. }
111. void TraverseList(const PtrNode ptrNode/*头结点*/)
112. {
113.         PtrNode ptrNode_ = ptrNode->ptrNext;//首节点
114.        
115.         while (NULL != ptrNode_)//结点为空，则是尾结点
116.         {
117.                 printf("%d ", ptrNode_->data);
118.                 ptrNode_ = ptrNode_->ptrNext;//下一结点
119.         }
121.         printf("\n");
122. }
124. bool isEmptyList(const PtrNode ptrNode)
125. {
126.         PtrNode ptrNode_ = ptrNode->ptrNext;//首节点
128.         if (NULL == ptrNode->ptrNext)
129.                 return true;
131.         return false;
132. }
134. int GetLenthList(const PtrNode ptrNode)
135. {
136.         int iLen = 0;
137.         PtrNode ptrNode_ = ptrNode->ptrNext;//首节点
139.         while (NULL != ptrNode_)//结点为空，则是尾结点
140.         {
141.                 ptrNode_ = ptrNode_->ptrNext;//下一结点
142.                 iLen++;
143.         }
145.         return iLen;
146. }
148. bool InsertList(PtrNode ptrNode, int insertPos, int insertData)
149. {
150.         if (insertPos < 1)
151.                 return false;
153.         if (insertPos > (GetLenthList(ptrNode) + 1))
154.                 return false;
156.         PtrNode ptrNodeInsert = (PtrNode)malloc(sizeof(Node));
158.         ptrNodeInsert->data = insertData;
160.         PtrNode ptrNodeCur = ptrNode;
161.         for (int i = 1; i < insertPos; ++i)
162.                 ptrNodeCur = ptrNodeCur->ptrNext;
164.         ptrNodeInsert->ptrNext = ptrNodeCur->ptrNext;
165.         ptrNodeCur->ptrNext = ptrNodeInsert;
167.         return true;
168. }
170. bool DeleteList(PtrNode ptrNode, int deletePos)
171. {
172.         if (deletePos < 1)
173.                 return false;
175.         if (deletePos > GetLenthList(ptrNode))
176.                 return false;
178.         PtrNode ptrNodeCur = ptrNode;
179.         for (int i = 1; i < deletePos; ++i)
180.                 ptrNodeCur = ptrNodeCur->ptrNext;
182.         ptrNodeCur->ptrNext = ptrNodeCur->ptrNext->ptrNext;
183.         return true;
184. }
186. void SortList(PtrNode ptrNode)
187. {
188.         int iLen = GetLenthList(ptrNode);
190.         PtrNode ptrNodeCur = ptrNode;//头结点
192.         for (int i = 0; i < iLen; ++i)
193.         {
194.                 ptrNodeCur = ptrNodeCur->ptrNext;
196.                 PtrNode ptrNodeNext = ptrNodeCur->ptrNext;
198.                 while (NULL != ptrNodeNext)
199.                 {
200.                         if (ptrNodeCur->data > ptrNodeNext->data)
201.                         {
202.                                 int temp = ptrNodeCur->data;
203.                                 ptrNodeCur->data = ptrNodeNext->data;
204.                                 ptrNodeNext->data = temp;
205.                         }
207.                         ptrNodeNext = ptrNodeNext->ptrNext;
208.                 }
209.         }
210. }

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！