022+-链表基础及基本操作

moc

1、链表基本概念
链表：是一种物理存储单元上非连续的存储结构，由一系列结点（链表中每一个元素称为结点）组成，结点动态生成，结点与结点之间通过指针链接。
                每个结点包括两个部分：一部分是存储数据元素的数据域，另一部分是存储下一个结点地址的指针域。
链表的特点：
        1 链表是一种常用的数据结构，它通过指针将一些列数据结点，连接成一个数据链。相对于数组，链表具有更好的动态性。
        2 数据域用来存储数据，指针域用于建立与下一个结点的联系。
        3 建立链表时无需预先知道数据总量的，可以随机的分配空间，可以高效的在链表中的任意位置实时插入或删除数据。
        4 链表的开销，主要是访问顺序性和组织链的空间损失。
约定：
        •头结点、当前结点、前趋结点、后继结点  新建结点
        •pHead、pCurrent、 pPrior、    pNext、     pMalloc
链表编程关键点：
        1、指针指向谁，就把谁的地址赋给指针
        2、辅助指针变量&操作逻辑的关系
2、静态链表
        手工依次为各结点建立指向关系，不能动态增加或减少结点，应用范围小。

1. struct AdvTeacher
   
2. {
   
3.         char name[64];
   
4.         int age;
   
5.         struct AdvTeacher *next;
   
6. };
   
7.         struct AdvTeacher t1, t2, t3;
   
8.         struct AdvTeacher *p;
   
9. 
   
10.         t1.age = 10;
    
11.         t2.age = 20;
    
12.         t3.age = 30;
    
13. 
    
14.         t1.next = &t2;  //建立结点之间的指向
    
15.         t2.next = &t3;
    
16.         t3.next = NULL;
    
17.         //遍历链表
    
18.         while (p)
    
19.         {
    
20.                 printf("age:%d\n", p->age);
    
21.                 p = p->next;
    
22.         }

复制代码

3、带头结点的单项链表

        头结点作为链表的开始，第一个结点为业务结点的开始，在进行接口的封装和设计时，链表的对外属性只有指向头结点的指针，其余的操作通过封装好的函数进行。
1.创建链表
        创建链表的头结点，需要在函数内申请内存空间，返回内存空间的首地址（指针函数，二级指针做输出）。
2.循环打印链表
        通过辅助指针记录当前位置，在链表中循环。
3. 指定结点前插入结点，如果没找到指定结点插到最后
        建立要插入的结点，建立两个辅助指针变量，一个指向当前结点，一个指向当前结点的前一个结点，循环每个结点，如果找到指定结点break，最后新结点链到当前结点，前一个结点链到新结点。
4.删除指定的结点
        循环每个结点，找到指定结点后删除并返回。
5.链表的逆置操作

        1.当链表只有头结点或只有一个业务结点不需要逆置，直接返回即可。
        2.准备环境：p保存第一个结点，q保存第二个结点
        3.从第二个结点开始操作，先缓存q的下一个结点，然后逆置（让第二个结点指向第一个结点），然后p,q各向后移一个对第三个结点做同样操作，知道q的指向NULL.
        4.最后把原先的第一个结点指向NULL,头结点指向p即可。
示例代码：

1. #include "stdlib.h"
   
2. #include "stdio.h"
   
3. #include "string.h"
   
4. #define _CRT_SECURE_NO_WARNINGS
   
5. 
   
6. typedef struct Node
   
7. {
   
8.         int data;
   
9.         struct Node *pNext;
   
10. }SLIST;
    
11. 
    
12. SLIST *Creat_SList()
    
13. {
    
14.         int data = 0;
    
15. 
    
16.         // 1建立头结点并初始化
    
17.         SLIST *pHead = NULL, *pm = NULL, *pCur = NULL;
    
18.         pHead = (SLIST*)malloc(sizeof(SLIST));
    
19.         if (pHead == NULL)
    
20.         {
    
21.                 return -1;
    
22.         }
    
23.         pHead->data = 0;
    
24.         pHead->pNext = NULL;
    
25.         pCur = pHead;
    
26. 
    
27.         // 2循环建立结点，结点中的数据域由键盘输入
    
28.         printf("\n Please enter the data of node(-1:quit):");
    
29.         scanf("%d", &data);
    
30. 
    
31.         while (data != -1)
    
32.         {
    
33.                 // 不断的malloc新结点， 并为数据域赋值
    
34.                 pm = (SLIST*)malloc(sizeof(SLIST));
    
35.                 if (pm == NULL)
    
36.                 {
    
37.                         SList_Destory(pHead);
    
38.                         return NULL;
    
39.                 }
    
40.                 pm->data = data;
    
41.                 pm->pNext = NULL;
    
42. 
    
43.                 // 新结点加入链表
    
44.                 pCur->pNext = pm;
    
45.                 pCur = pm;
    
46. 
    
47.                 printf("\n Please enter the data of node(-1:quit):");
    
48.                 scanf("%d", &data);
    
49.         }
    
50. 
    
51.         return pHead;2.
    
52. }
    
53. //打印链表中的每一个值
    
54. int SList_Print(SLIST *pHead)
    
55. {
    
56.         SLIST *pCur = NULL;
    
57.         if (pHead == NULL)
    
58.         {
    
59.                 return -1;
    
60.         }
    
61.         // 准配环境
    
62.         pCur = pHead->pNext;
    
63.         printf("\nBegin   ");
    
64.         while (pCur)
    
65.         {
    
66.                 printf("%d ", pCur->data);
    
67.                 pCur = pCur->pNext;
    
68.         }
    
69.         printf("End  \n ");
    
70. 
    
71. }
    
72. 
    
73. // 在结点数值为x的前面插入y,如果没找到加到最后
    
74. int SList_NodeInsert(SLIST *pHead, int x, int y)
    
75. {
    
76.         SLIST *pCur = pHead, *pPre = NULL, *pTemp = NULL;
    
77.         if (pHead == NULL)
    
78.         {
    
79.                 return -1;
    
80.         }
    
81.         pTemp = (SLIST*)malloc(sizeof(SLIST));
    
82.         if (pTemp == NULL)
    
83.         {
    
84.                 return -2;
    
85.         }
    
86.         pTemp->data = y;
    
87.         while (pCur)   // 查找值为x结点的前一个结点
    
88.         {
    
89.                 if (pCur->data == x)
    
90.                 {
    
91.                         break;
    
92.                 }
    
93.                 pPre = pCur;
    
94.                 pCur = pCur->pNext;
    
95.         }
    
96.         // 新结点链接到后继结点
    
97.         pTemp->pNext = pPre->pNext;
    
98.         // 让前驱结点链接到pTemp
    
99.         pPre->pNext = pTemp;
    
100. 
     
101.         return 0;
     
102. }
     
103. 
     
104. // 删除值为y的结点,如果不存在则打印删除结点不存在
     
105. int SList_NodeDel(SLIST *pHead, int y)
     
106. {
     
107.         SLIST *pCur = pHead, *pPre = NULL;
     
108.         if (pHead == NULL)
     
109.         {
     
110.                 return -1;
     
111.         }
     
112.         while (pCur)
     
113.         {
     
114.                 if (pCur->data == y)
     
115.                 {
     
116.                         pPre->pNext = pCur->pNext;
     
117.                         free(pCur);
     
118.                         return 0;
     
119.                 }
     
120.                 pPre = pCur;
     
121.                 pCur = pCur->pNext;
     
122.         }
     
123.         printf("值为%d结点不存在！\n", y);
     
124. 
     
125. }
     
126. 
     
127. // 链表逆置操作   //从第二个结点开始逆置
     
128. int SList_revse(SLIST *pHead)
     
129. {
     
130.         SLIST *p = NULL, *q = NULL, *t = NULL;
     
131.         if (pHead == NULL)
     
132.         {
     
133.                 return -1;
     
134.         }
     
135.         if (pHead->pNext == NULL || pHead->pNext->pNext == NULL)
     
136.         {
     
137.                 return 0;
     
138.         }
     
139.         // 准备环境
     
140.         p = pHead->pNext;
     
141.         q = pHead->pNext->pNext;
     
142.         while (q != NULL)
     
143.         {
     
144.                 //1. 逆置之前做个缓存
     
145.                 t = q->pNext;
     
146.                 //2.开始逆置
     
147.                 q->pNext = p;
     
148.                 //3.p,q分别后移
     
149.                 p = q;
     
150.                 q = t;
     
151.         }
     
152. 
     
153.         // 扫尾工作
     
154.         pHead->pNext->pNext = NULL;
     
155.         pHead->pNext = p;
     
156.         return 0;
     
157. 
     
158. }
     
159. 
     
160. // 销毁整个链表
     
161. int SList_Destory(SLIST *pHead)
     
162. {
     
163.         SLIST *pCur = pHead, *pTemp = NULL;
     
164.         if (pHead == NULL)
     
165.         {
     
166.                 return -1;
     
167.         }
     
168.         while (pCur)
     
169.         {
     
170.                 // 缓存后继结点
     
171.                 pTemp = pCur->pNext;
     
172.                 // 删除当前结点
     
173.                 free(pCur);
     
174.                 // 当前结点下移
     
175.                 pCur = pTemp;
     
176. 
     
177.         }
     
178.         return 0;
     
179. }
     
180. 
     
181. void main()
     
182. {
     
183.         SLIST *pHead = NULL;
     
184.         pHead = Creat_SList();
     
185.         SList_Print(pHead);
     
186.         SList_NodeInsert(pHead, 20, 19);
     
187.         SList_Print(pHead);
     
188.         SList_NodeDel(pHead, 20);
     
189.         SList_Print(pHead);
     
190.         SList_revse(pHead);
     
191.         SList_Print(pHead);
     
192.         SList_Destory(pHead);
     
193.         system("pause");
     
194. }

复制代码