单链表知识点

1. #pragma once
2. #include <stdio.h>
3. #include <assert.h>
4. #include <stdlib.h>
5. #include <string.h>
6. 
7. 
8. typedef int SLTDateType;
9. 
10. //单链表中，定义一个结构体，结构体里面有两个结构体成员，一个是数据，一个是指针(指针指向一个结构体)，
11. // 这个指针的类型是一个结构体,这个结构体又和自己类型一样，所以结构体有的自引用
12. typedef struct SListNode
13. {
14.   SLTDateType date;//数据
15.   struct SListNode* next;//储存下一个节点的地址
16. }SListNode;
17. //知识点结构体的自引用方式
18. 
19. //单链表不需要初始化，因为单链表刚开始只有一个指针
20. void SListPrint(SListNode* phead);//打印
21. //尾插
22. void SListPushBack(SListNode** pphead, SLTDateType x);
23. //头插
24. void SListPushFront(SListNode** pphead, SLTDateType x);
25. //尾删
26. void SListPopBack(SListNode** pphead);//需要传递的是头部结构体的地址的地址，当尾删的时候，如果单链表就有一个值，那么进行尾删的时候，需要改变头部结构体地址
27. //头删
28. void SListPopFront(SListNode** pphead);
29. //查找
30. SListNode* SListFind(SListNode* phead, SLTDateType x);
31. //前插入
32. void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
33. //后插入
34. void SListInsertAfter(SListNode* pos, SLTDateType x);
35. //删除
36. void SListErase(SListNode** pphead, SListNode* pos);
37. //删除后面
38. void SListEraseAfter(SListNode** pphead);
39. //销毁
40. void SListDestory(SListNode** pphead);

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "SList.h"
3. 
4. 
5. //打印
6. void SListPrint(SListNode* phead)
7. {
8.  //assert(phead);//这里不需要断言，因为单链表可能是空链表
9.  SListNode* cur = phead;
10.   while (cur != NULL)
11.   {
12.     printf("%d->", cur->date);
13.     cur = cur->next;
14.   }
15.   printf("NULL\n");
16. }
17. 
18. //一个节点的创建
19. SListNode* BuySListNode(SLTDateType x)
20. {
21.   SListNode* newnode = (SListNode*)malloc(sizeof(SLTDateType));
22.   if (newnode == NULL)
23.   {
24.     printf("malloc fail\n");
25.     exit(-1);
26.   }
27.   else
28.   {
29.     newnode->date = x;
30.     newnode->next = NULL;
31.   }
32.   return newnode;
33. }
34. 
35. //尾插
36. void SListPushBack(SListNode** pphead, SLTDateType x)//当链表是空的时候，尾插，相当于头插，需要改变头部的地址，改变地址，需要传递头部地址的地址【形参的改变不影响实参】
37. //需要改变谁，就需要传谁的地址
38. {
39.   assert(pphead);
40.   SListNode* newnode = BuySListNode(x);
41.   if (*pphead == NULL)
42.   {
43.     *pphead = newnode;
44.   }
45.   else
46.   {
47.     SListNode* tail = *pphead;
48.     while (tail->next != NULL)
49.     {
50.       tail = tail->next;
51.     }
52.     tail->next = newnode;
53.   }
54. }
55. //头插//改变头部地址就需要传二级指针
56. void SListPushFront(SListNode** pphead, SLTDateType x)
57. {
58.   assert(pphead);
59.   SListNode* newnode = BuySListNode(x);
60.   newnode->next = *pphead;
61.   *pphead = newnode;
62. }
63. 
64. 
65. //尾删//要把倒数第二个值的next变成NULL，所以需要倒数第二个结构体的地址，才能改变(形参的改变，不改变实参)【每一个结构体，相当于结构体传参】
66. //没有节点，一个节点，许多节点
67. void SListPopBack(SListNode** pphead)
68. {
69.   assert(pphead);
70.   if (*pphead == NULL)//空
71.   {
72.     return;
73.   }
74.   else if ((*pphead)->next == NULL)
75.   {
76.     free(*pphead);
77.     *pphead = NULL;
78.   }
79.   else
80.   {
81.     SListNode* prev = NULL;
82.     SListNode* tail = *pphead;
83.     while (tail->next != NULL)
84.     {
85.       prev = tail;//倒数第二个
86.       tail = tail->next;//倒数第一个
87.     }
88.     free(tail);
89.     tail = NULL;
90.     prev->next = NULL;
91.   }
92. }
93. //头删
94. void SListPopFront(SListNode** pphead)
95. {
96.   assert(pphead);
97.   if (*pphead == NULL)
98.   {
99.     return;
100.  }
101.  else//一个值和很多值
102.  {
103.    SListNode* front = NULL;
104.    front = (*pphead)->next;
105.    free(*pphead);
106.    *pphead = front;
107.  }
108. }
109. 
110. //查找
111. SListNode* SListFind(SListNode* phead, SLTDateType x)
112. {
113.  SListNode* cur = phead;
114.  while (cur != NULL)
115.  {
116.    if (cur->date == x)
117.    {
118.      return cur;
119.    }
120.    cur = cur->next;
121.  }
122.  return NULL;
123. }
124. 
125. //插入,在某个数字前插入//首先用find找某个数的地址，然后再在地址处插入。,
126. void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
127. {
128.  assert(pphead);
129.  assert(pos);
130.  if (*pphead == pos)
131.  {
132.    SListPushFront(pphead, x);
133.  }
134.  else
135.  {
136.    SListNode* prev = *pphead;
137.    while (prev->next != pos)
138.    {
139.      prev = prev->next;
140.    }
141.    SListNode* newnode = BuySListNode(x);
142.    prev->next = newnode;
143.    newnode->next = pos;
144.  }
145. }
146. //在insert之后插入
147. void SListInsertAfter(SListNode* pos, SLTDateType x)
148. {
149.  assert(pos);
150.  SListNode* next = pos->next;
151.  SListNode* newnode = BuySListNode(x);
152.  pos->next = newnode;
153.  newnode->next = next;
154. }
155. 
156. //删除
157. void SListErase(SListNode** pphead, SListNode* pos)
158. {
159.  assert(pphead);
160.  assert(pos);
161.  if (*pphead == pos)
162.  {
163.    SListPopFront(pphead);
164.  }
165.  else
166.  {
167.    SListNode* prev = *pphead;
168.    while (prev->next != pos)
169.    {
170.      prev = prev->next;
171.    }
172.    prev->next = pos->next;
173.    pos = NULL;
174.    free(pos);
175.  }
176. }
177. 
178. //删除后面
179. void SListEraseAfter(SListNode* pos)
180. {
181.  assert(pos);
182.  if (pos->next == NULL)
183.  {
184.    return;
185.  }
186.  else
187.  {
188.    SListNode* next = pos->next;
189.    pos->next = next->next;
190.    free(next);
191.    next = NULL;
192.  }
193. }
194. 
195. //销毁
196. void SListDestory(SListNode** pphead)
197. {
198.  assert(pphead);
199.  SListNode* cur = *pphead;
200.  SListNode* next = NULL;
201.  while (cur->next != NULL)
202.  {
203.    next = cur->next;
204.    free(cur);
205.    cur = NULL;
206.  }
207.  *pphead = NULL;
208. }
209. 
210.