动态顺序表的缺陷
- 尾部插入效率还不错，但是头部 和随机删除和随机插入效率很低
- 容量满了就要扩容。扩容分为两种，一种为原地扩容，一种为异地扩容（效率低下），扩容一般都会存在一定的空间浪费，（一次扩大50，而使用就使用一两个）
动态顺序表的优点
- 连续存储说明只需要知道一个地址就可以访问剩下的元素
链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
这个图是我们想象出来的，图中的方框就是一个节点
为了解决这个问题，前面的大佬就想到了通过地址访问空间，每一个节点存放下一个节点的地址
用plist存放第一个节点的地址，然后通过遍历一一访问
注意:
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续般都是从堆上申请出来的
2.现实中的结点一般都是在堆上申请出来的（动态开辟）
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
服设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表
链表的分类
链表有8种，下面我来一一介绍
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
8种链表就是这么来的
单向链表
单向链表是链表中最常用的一种，一个列表节点有两个字段，即数据域和指针域。在单向链表中，指向第一个节点的节点称为“头结点”，最后一个节点的指针域设为null。
单项链表的操作
单链表的结构体
typedef int SLDataType; //链表元素 typedef struct SListNode { SLDataType val; struct SListNode *next; //这里只是一个指针,大小是4/8个大小,如果是定义成结构体变量就会出错 }SListNode;
这里要注意的就是struct SListNode next不能写成SListNodenext
打印输出
思路图：
//输出链表内容 void SLPrint(SListNode* phead) { assert(phead); //防止phead的值改变 SListNode* cur = phead; while (cur!= NULL) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
这里很容易搞混，一些写出的错误可能就是链表的结尾和地址搞不明白很容易混淆
错误写法：
void SLPrint(SListNode* phead) { assert(phead); //防止phead的值改变 SListNode* cur = phead; while (cur->next!= NULL) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
这种情况就会导致最后一个无法打印出来
创建节点
//创建节点(动态开辟,防止出作用域销毁) SListNode* CreateNode(SLDataType elemest) { SListNode* p = (SListNode*)malloc(sizeof(SListNode)); if (p == NULL) { perror("CreateNode -malloc"); return; } p->next = NULL; p->val = elemest; return p; }
尾插数据
思路： 我们要判断传入的链表中是不是空链表，空链表就是phead =NULL，如果是空链表，我们只需要phead指向插入数据的地址就行，如果不是，我们就要找到最后一个节点，把该节点的成员next的值是该数据的地址，然后把该数据的next改为NULL
void SLPushBack(SListNode** pphead, SLDataType elemest) { //创建一个节点 SListNode* Node = CreateNode(elemest); //找到最后一个节点,判断phead是否是NULL if (*pphead) { SListNode* stall = *pphead; while (stall->next != NULL) { stall = stall->next; } //插入 stall->next = Node; } else { *pphead = Node; } }
这里我们要判断两种情况的过程中有一些人可能会写成以下错误：
1.
这个错误就是让stall的地址指向的不是最后一个节点了
2.
就是这里是传值调用，无法更改phead 的值，有很多就误以为更改这个形参就会更改实参了，所以我们要传入phead的地址，改变外面结构体的指针（phead）就要用二级指针
链表头插
思路图：
思路：让phead指向节点2
//头插 void SLPushFront(SListNode** pphead, SLDataType elemest) { //创建节点 SListNode* Node = CreateNode(elemest); //插入 SListNode* tail = *pphead; *pphead = Node; (*pphead)->next = tail; }
尾删
思路:
我们要分三种情况
一种是空链表 : 直接判断*phead
一种是只有一个节点 :判断(*pphead)->next 是否是 NULL
一种是多个节点:
思路:只要tail->next不是NULL,prev=tail,然后 tail指向下一个节点,否则free(tail),然后把prev->next =NULL
//尾删 void SLPopBack(SListNode** pphead) { assert(*pphead && pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//多个节点 { SListNode* prev = *pphead; SListNode* tail = (*pphead)->next; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail == NULL; prev->next = NULL; } }
或者这样写
//尾删 void SLPopBack(SListNode** pphead) { assert(*pphead && pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//多个节点 { SListNode* tail = *pphead; while (tail->next ->next != NULL) { tail = tail->next; } free(tail ->next); tail->next = NULL; } }
错误写法:
这种写法就是一个大错误,主要是分不清prev和tail都是指向同一块空间,且没有考虑一个节点的情况
头删
思路图:
//头删 void SLPopFront(SListNode** pphead) { assert(pphead && *pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode* p = (*pphead)->next; free(*pphead); *pphead = p; } }
或者这样写
//头删 void SLPopFront(SListNode** pphead) { assert(pphead && *pphead); SListNode* p = (*pphead)->next; free(*pphead); *pphead = p; }
这里我们主要还是要区分
pphead = NULL （存储的是空地址）
*pphead = NULL （phead存储的是NULL，但是phead有地址,代表空链表）
（*pphead)->next = NULL(代表的是当前节点是尾节点)
链表查找
思路: 遍历一遍链表,找到就返回地址,找不到就返回NULL
void* SLFind(SListNode* phead, SLDataType elemest) { assert(phead); SListNode* tail = phead; while (tail != NULL) { if (tail->val == elemest) { return tail; } tail = tail->next; } return NULL; }
链表的地址前插入
这里我们要清楚,传入的地址是否为NULL
思路: 插入分两种情况,一种是头插 一种是插入到多个之间
// 插入pos前面 void SLTInsert(SListNode** pphead, SListNode* pos, SLDataType elemest) { //两者不为NULL assert(pphead && pos && *pphead); SListNode* tail = *pphead; // 创建节点 SListNode* newnode = CreateNode(elemest); if (tail == pos) { //头插 newnode->next = pos; *pphead = newnode; } else { while (tail->next != pos) { tail = tail->next; } tail->next = newnode; newnode->next = pos; } }
这里的断言主要分三种情况 一种是 *phead和pos都可以为NULL,相当于空链表插入 ,一种是两者都不为NULL,一种是同时满足,这个要看自己来规定,这里我规定的是两个不能为空
链表的地址后插入
这里我们还是一样要考虑和前面的一样,
// 插入pos后面 void SLBInsert(SListNode** pphead, SListNode* pos, SLDataType elemest) { assert(pphead && pos); //创建节点 SListNode* newnode = CreateNode(elemest); //插入 SListNode* tail = pos->next; pos->next = newnode; newnode->next = tail; }
删除
思路:主要分析只要第一个节点(只有一个和多个)和多个节点
//删除 void SLErase(SListNode** pphead, SListNode* pos) { assert(pphead && pos && *pphead); //写法1 一个节点 //if ((*pphead)->next == NULL) //{ // if (pos == *pphead) // { // free(pos); // pos = NULL; // *pphead = NULL; // } //} //else //多个 //{ // SListNode* tail = *pphead; // if (pos == tail) // { // *pphead = (*pphead)->next; // free(pos); // pos = NULL; // } // else if (pos->next == NULL) // { // while (tail->next != pos) // { // tail = tail->next; // // } // tail->next = NULL; // free(pos); // pos = NULL; // } // else // { // while (tail->next != pos) // { // tail = tail->next; // } // if (pos = tail->next) // { // SListNode* prev = pos->next; // tail->next = prev; // free(pos); // pos = NULL; // } // } //} //写法2 SListNode* tail = *pphead; if (pos == tail) { //头删 SLPopFront(pphead); } else { //这个无法释放第一个节点 while (tail->next != pos) { tail = tail->next; } tail->next = pos->next; free(pos); pos = NULL; } }
链表的其他操作
//不传head ,在pos后面插入 void SLTInsertAfter(SListNode* pos, SLDataType elemest) { assert(pos); //创建节点 SListNode* newnode = CreateNode(elemest); newnode->next = pos->next; pos->next = newnode; } //不传head ,在pos前面插入,(交换值) void SLTInsertFort(SListNode* pos, SLDataType elemest) { assert(pos); //创建节点 SListNode* newnode = CreateNode(elemest); newnode->next = pos->next; pos->next = newnode; //交换值 SLDataType val = newnode->val; newnode->val = pos->val; pos->val = val; } //不传head ,在pos后面删除 void SLTEraseAfter(SListNode* pos) { //删除尾节点会报错 assert(pos &&pos->next); SListNode* prev = pos->next->next; free(pos->next); pos->next = prev; }
