1. 认识链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
- 和顺序表相比，链表的优势体现在哪？
- 顺序表中存在扩容问题，扩容扩大了，而数据没占满，则会浪费数据，链表是一个数据占一个空间，这样就不会出来空间浪费问题
2. 无哨兵位单向非循环链表结构
一个结构存放数据和关系，那么就有如下结构：
typedef int SLLDataType; typedef struct SingleLinkListNode { int data; //数据 struct SingleLinkListNode* next; //指向下一个结点 }SLLNode;
3. 生成一个结点
SLLNode* BuySLLNode(SLLDataType x) { SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode)); if (newnode == NULL) { perror("BuySLLNode:malloc:"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
- 问题一：为什么要使用malloc去申请空间，而不是用结构体类型变量？
SLLNode BuySLLnode1(SLLDataType x) { SLLNode newnode; newnode.data = x; newnode.next = NULL; return newnode; } //问什么不能使用这种方式开辟结点空间？
原因：malloc申请的空间是在堆区中开辟的，堆区中的空间出了函数栈帧数据仍然存在，但是用结构类型变量，出了函数栈帧就销毁了，并不能存储数据
- 问题二：为什么开始的时候要使newnode指向NULL？
原因：在后面插入时，如果起初不指向NULL，而是指向别的地址，那么最后尾部还要对其做一步指向NULL的操作
4. 打印链表
void PrintSLLNode(SLLNode* phead) { SLLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
问题：为什么限制条件是cur != NULL而不是cur->next != NULL?
5. 创建len长度的链表
SLLNode* GreateSLLNode(int len) { SLLNode* head = NULL; SLLNode* tail = NULL; for (int i = 0; i < len; ++i) { //创建一个新结点 SLLNode* newnode = BuySLLNode(i); //检查第一步head if (head == NULL) { head = tail = newnode; } else { //变动tail tail->next = newnode; tail = newnode; } } return head; }
问题：为什么要区分第一步head == NULL?
新链表中返回的是头节点地址，不可能头节点为NULL吧，所以要区分，对其进行改变
6. 尾插
void SLLPushBack(SLLNode** pphead, SLLDataType x) { SLLNode* newnode = BuySLLNode(x); if (*pphead == NULL) { //*phead拿到的是head *pphead = newnode; } else { SLLNode* tail = *pphead; //找尾 while (tail->next != NULL) { tail = tail->next; } //找到尾部 tail->next = newnode; } }
- 问题一：为什么不需要断言？
空链表也可以插入数据无需断言
- 问题二：为什么是传二级指针，而不是一级指针？
考虑传二级指针是针对*pphead == NULL时，要改变head指向的位置，改变指针所指向的位置就要传指针的指针(尾插、头插、尾删、头删都需要传二级都是这个原因)
7. 尾删
void SLLPopBack(SLLNode** pphead) { //写法一 assert(*pphead); //如果结点只有一个要单独处理 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLLNode* pre = *pphead; SLLNode* tail = *pphead; //找尾 while (tail->next != NULL) { pre = tail; tail = tail->next; } //释放 free(tail); pre->next = NULL; } }
void TestSLLPopBack(SLLNode** pphead) { //写法二 //链表为空不能删除 assert(*pphead); //只有一个结点的时候是不能使用的，NULL不能NULL->next if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLLNode* tail = *pphead; //找尾 while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
问题：下面这种写法对吗？
void SLLPopBack(SLLNode* phead) { SLLNode* tail = phead; //找尾 while (tail->next != NULL) { tail = tail->next; } free(tail); tail = NULL; }
为什么不行？
8. 头插
void SLLPushFront(SLLNode** pphead, SLLDataType x) { //创建结点 SLLNode* newnode = BuySLLNode(x); //链接 newnode->next = *pphead; //改变头结点指针位置,所以传二级指针 *pphead = newnode; }
9. 头删
void SLLPopFront(SLLNode** pphead) { assert(*pphead); //先调整头结点指针,所以传二级指针 SLLNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
10. 查找
SLLNode* SLLFind(SLLNode* phead, SLLDataType x) { //好的习惯 SLLNode* cur = phead; //找到返回结点位置，没找到返回NULL，同时如果链表为NULL，也返回NULL while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
11. 在pos位置之后插入数据
void SLLInsertAfter(SLLNode* pos, SLLDataType x) { assert(pos); 写法一 //SLLNode* nextnode = pos->next; //SLLNode* newnode = BuySLLNode(x); //pos->next = newnode; //newnode->next = nextnode; //写法二 SLLNode* newnode = BuySLLNode(x); newnode->next = pos->next; pos->next = newnode; }
为什么断言？
我们没找到的话就返回NULL，所以需要断言
之后插入数据为什么可以不记录pos后面的结点？
因为单链表是单向的，可以通过pos位置找到后一个结点，所以可以不用记录
12. 在pos位置之前插入数据
void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x) { //可能是head链表不为空，但是pos为空的情况则需断言 assert(pos); //head为空也可以插入 //head == pos时可以插入 if (*pphead == pos) { SLLPushFront(pphead, x); } //不是头部插入 else { SLLNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } SLLNode* newnode = BuySLLNode(x); pre->next = newnode; newnode->next = pos; } }
为什么传二级指针？
因为链表为NULL时头插要改变head的指向
为什么这里必须记录上一个结点？
因为单链表是单向的，通过此结点不能直接访问上一个结点，所以必须记录上一个结点连接时使用
13. 删除pos位置之后的数据
void SLLEraseAfter(SLLNode* pos) { //断言pos,不然pos->next会有错误 assert(pos); if (pos->next == NULL) { perror("warining:已经在尾部，不可对后面删除!"); } else { SLLNode* nextnode = pos->next; pos->next = nextnode->next; free(nextnode); } }
为什么free后可以无需置空？
因为nextnode是局部变量，出了函数栈帧销毁
14. 删除pos位置数据
void SLLErase(SLLNode** pphead, SLLNode* pos) { assert(pos); //链表为空不能删除 assert(*pphead); if (*pphead == pos) { SLLPopFront(pphead); } else { SLLNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } pre->next = pos->next; free(pos); //无需置空，lastnode为局部变量，出栈帧自动销毁 } }
为什么传二级？
因为head = NULL时，要改变head指向
15. 销毁链表
void SLLDestroy(SLLNode** pphead) { //链表为NULL时断言 assert(*pphead); SLLNode* cur = *pphead; while (cur != NULL) { SLLNode* nextnode = cur->next; free(cur); cur = nextnode; } *pphead = NULL; }
为什么要最后*pphead = NULL，可以不置空吗？
循环中已经对链表释放完了，但是* pphead依然指向的是头结点的位置，但是头节点的空间已经释放，还给操作系统了，这里的*pphead就是野指针，所以必须置空
重要的要点已经指出，感性大家支持！
