C++学习（三十五）（C语言部分）之 单链表
单链表测试代码笔记如下：
1 #include<stdio.h>
2 #include <stdlib.h> //malloc 要用到
3
4 typedef struct Node
5 {
6 int data; //数据域：用来存放数据
7 struct Node* pNext; //指针域：用来存储下一个结点地址
8 }LIST,*PLIST;
9
10 //1. 创建一个火车头. 相当于创建链表 =用函数来创建一个链表的头部
11 //创建链表的头部
12 PLIST CreateListHead()
13 {
14 //1.1 申请内存
15 PLIST phead = (PLIST)malloc(sizeof(LIST));
16 //1.2 判断是否申请成功
17 if (NULL == phead)
18 {
19 printf("头结点的内存申请失败!\n");
20 return NULL;
21 }
22 phead->pNext = NULL;
23 //phead->data 可以赋值也可以不赋值,因为头结点不存储数据
24 //.它只是用来标记链表的头部
25 //有表头的链表头结点都不存储数据,只是用来标记链表的头部
26 return phead;
27 }
28
29 //2.写一个创建结点的函数,用来申请结点内存
30 PLIST CreateListNode(int data)
31 {
32 PLIST newNode = (PLIST)malloc(sizeof(LIST));
33 if (NULL == newNode)
34 {
35 printf("结点内存申请失败!\n");
36 return NULL;
37 }
38 newNode->pNext = NULL;
39 newNode->data = data;
40 return newNode;
41 }
42
43 //3.插入一个结点 头部插入 指定位置插入 尾部插入
44 void InsertListHead(PLIST p_list, int data)//1. 要说明要插入的链表是哪一个 2.要插入的数据
45 {
46 //3.1 申请一个结点
47 PLIST node = CreateListNode(data);
48 //先连接后断开
49 node->pNext = p_list->pNext;
50 p_list->pNext = node;
51 }
52
53 //4. 尾插法
54 void InsertListTail(PLIST p_list, int data)
55 {
56 //4.1 申请结点内存
57 PLIST node = CreateListNode(data);
58 //我们只知道链表的头部 尾部就要去遍历得到
59 PLIST p_Temp = p_list;
60 //遍历找到尾结点
61 while (p_Temp->pNext!=NULL) // 表达式非0就是真
62 {
63 p_Temp = p_Temp->pNext;
64 }
65 //循环结束 就是找到了最后一个结点
66 node->pNext = NULL;
67 p_Temp->pNext = node;
68 }
69
70 //在链表p_list中的pos位置插入data
71 void InsertListAppoint(PLIST p_list, int pos, int data)
72 {
73 PLIST node = CreateListNode(data);
74 PLIST p_Temp1 = p_list;
75 PLIST p_Temp2 = p_list;
76 for (int i = 0; i < pos; i++)
77 {
78 if (p_Temp1->pNext != NULL)
79 {
80 p_Temp1 = p_Temp1->pNext;
81 if (i>0)
82 p_Temp2 = p_Temp2->pNext;
83 }
84 else
85 { //如果pos大于链表结点的个数,就插入到尾部
86 p_Temp1->pNext = node;
87 node->pNext = NULL;
88 return; //退出函数 不往下执行
89 }
90 }
91 //循环结束 --> 说明我找到了我要插入的位置
92 node->pNext = p_Temp1;
93 p_Temp2->pNext = node;
94
95 }
96
97 // 遍历链表的每一个结点
98 void PrintList(PLIST p_list)
99 {
100 PLIST p_Temp = p_list->pNext; //从头部的下一个结点开始输出里面的数据
101 while (p_Temp)
102 {
103 printf("%d -> ", p_Temp->data);//打印结点里面的数据
104 p_Temp = p_Temp->pNext;
105 }
106 printf("NULL\n");
107 }
108 //删除 删除头结点 指定位置删除 尾部删除
109 //知道这个逻辑 多画图 多写代码
110 //后面还会有双向循环链表 要处理四个指针 现在只需要处理两个 双向循环链表不画图很难理解
111 //画图之后会发现很简单 只需要照着画的图去链接各个指针就OK了
112 void DeleteListHead(PLIST p_list) //PLIST p_list=head.
113 {
114 PLIST p_Temp = p_list->pNext;
115 //先链接还是先释放
116 p_list->pNext = p_Temp->pNext; //连接
117 free(p_Temp);
118 }
119
120 //不用循环 删除所有结点
121 void DeleteList(PLIST p_list)//函数会执行5 5 4 3 2 1
122 {
123 //满足条件的情况下 自己调用自己
124 if (p_list->pNext!=NULL) //if括号里面不是0就是成立
125 {
126 DeleteList(p_list->pNext);
127 }
128 free(p_list);
129
130 }
131
132 int fun(int n)
133 {
134 if (n == 1)
135 {
136 return 1;
137 }
138 else
139 {
140 return n + fun(n - 1);
141 } //5 +4+3+2+1 //函数嵌套调用
142 for (int i = 0; i < 5; i++)
143 {
144 for (int j = 1; j < 5; j++)
145 {
146 ///内循环结束又回到了外循环
147 }
148 }
149 }
150
151 int main()
152 {
153 PLIST head = CreateListHead(); //创建头部 把堆内存的首地址返回给head
154 for (int i = 1; i <= 5; i++)
155 InsertListHead(head, i);
156 PrintList(head);
157
158 ////尾插法
159 //InsertListTail(head, 98);
160 //PrintList(head);
161
162 ////指定位置插入
163 //InsertListAppoint(head, 2, 520);
164 //PrintList(head);
165 //InsertListAppoint(head, 88, 520);
166 //PrintList(head);
167 //DeleteListHead(head);
168 //PrintList(head);
169
170 DeleteList(head);
171 PrintList(head);
172 head = NULL;
173 return 0;
174 }