单链表 就好比火车
火车头-->链表头部
火车尾-->链表尾部
火车厢-->链表的节点
火车厢连接的部分-->指针
火车中的内容-->链表节点的的数据
链表节点包含数据域和指针域
数据域存放数据
指针域存放要连接的节点的首地址
在造火车的时候 先是火车头 然后是车厢
--->链表的首节点和之后的节点
先从内存中申请头结点的存储空间
--->PLTST phead=(PLTST)malloc(sizeof(LTST));
首节点在创建时会让指针域指向空
--->既链表的初始化
链表连接的规则，要先连接后断开
对于单链表的插入有两种方法
1、头插法
2、尾插法（比较简单的）
尾插法 申请好一个新的节点后将链表的最后一个节点的指针域指向新节点
头插法 首先创建新节点，找到链表头节点，将指针指向新节点，将新节点指针指向第二节点
单链表测试代码笔记如下：
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("头结点的内存申请失败! "); 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("结点内存申请失败! "); 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 "); 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 }
附：
