1、顺序表遗留问题

1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,使用malloc、realloc等函数拷贝数据,释放旧空间。会有不小的消耗。
3. 当我们以2倍速度增容时,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,若下次只是插入5个数据,就会浪费95个数据大小的空间。
为了改进、弥补顺序表的缺点,我们发明了链表。

2、什么是链表

概念:物理顺序:链表是一种物理存储结构上非连续、非顺序的存储结构。

           逻辑顺序:是通过链表中的指针链接次序实现的。

 

 3、接口函数以及结点的定义
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct
SListNode* next; }SListNode; //单链表打印 void SLTPrint(SListNode* phead); //尾插 void
SLTPushBack(SListNode** pphead,SLTDataType x); //创建一个新结点的函数,并将新结点的数据初始化为x
SListNode* BuySLTNode(SLTDataType x); //尾删 void SLTPopBack(SListNode** pphead);
//头插 void SLTPushFront(SListNode** pphead, SLTDataType x); //头删 void
SLTPopFront(SListNode** pphead); // 单链表查找 SListNode* SListFind(SListNode*
plist, SLTDataType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos,
SLTDataType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos);
//单链表在pos前面插入 void SListInsertBefore(SListNode** pphead, SListNode* pos,
SLTDataType x); //单链表在删除在pos位置的值 void SListErasepos(SListNode** pphead,
SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode* plist);
 为了方便,我们将链表的数据类型定义为int,同时定义一个struct ListNode*类型的指针next,用来指向下一个结点。

由于链表不需要事前申请一块连续的空间,因此不需要初始化,只需定义一个SlistNode*类型的指针phead,作为链表的头指针,指向这个链表。

4、链表的打印
//单链表打印 void SLTPrint(SListNode* phead) { SListNode* cur = phead; while (cur)
{ printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

创建一个cur指针变量指向头结点,然后用cur=cur->next来遍历,打印完data后再到下一个,直到打印完最后一个data,cur指向最后结点的next(指向NULL)。为了便于前期理解,最后打印一个NULL。下文插入操作后,演示打印效果。

5、创建(Buy)一个新结点
//创建一个新结点的函数,并将新结点的数据初始化为x SListNode* BuySLTNode(SLTDataType x) {
//建立一个新的结点,并将data初始化,next置为NULL SListNode* newnode =
(SListNode*)malloc(sizeof(SListNode)); if (NULL == newnode) { perror("malloc
fail"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode;
}

先用malloc申请一个结点大小的空间,并将其交给一个newnode指针,确认申请成功后,对newnodd进行初始化,data=x,next置为NULL,(因为不知道要指向哪里,只是申请一个新结点,next指向的问题交给调用此函数的人来完成)。

然后将newnode返回,使用的人用某个结点的next指向它,就可以链接一个新结点。

6、尾插
//尾插 void SLTPushBack(SListNode** pphead,SLTDataType x) { SListNode* tmp =
BuySLTNode(x); if (NULL == tmp) { return; } SListNode* newnode = tmp;
//分情况,原来是否为空链表 if (*pphead == NULL)//为空链表 { *pphead = newnode;//建立phead与新结点的联系
} else { //先找到原来的尾结点,然后建立其与新结点的联系 SListNode* tail = *pphead; while (tail->next
!= NULL) { tail = tail->next; } //找到原来的尾结点后 tail->next = newnode; } }
链表是为了改进顺序表中头插和中间插入效率而产生的,与顺序表是互补关系,顺序表尾插时直接插入即可,消耗很小。但链表尾插时,需要先进行找尾操作,然后再尾插新数据。

注意:第一个参数是SListNode**
pphead,用来接收头指针的地址,这是一次传址调用,可以改变phead本身的内容,由于phead是头指针,改变的就是头指针指向的内容。

第一次尾插时,phead指向NULL,利用*pphead使其指向新的第一个结点。

如果用一个SListNode*
plist来接收,只是phead的形参,即一份临时拷贝,用plist接收newnode,只是在尾插函数内部起作用,而对外部的phead无影响,结果变成尾插一大顿,phead仍然指向NULL。

若phead不为NULL,则创建一个tail指针进行找尾操作。找尾过程中,tail->next为NULL,则此时tail指向尾结点,将newnode赋给tail->next即完成尾插。

 上图为尾插1234后的结果。

还有一点要注意:assert的使用,不能见到指针就用assert,有时传入的数据就是一个NULL,比如插入第一个元素时phead就是NULL,如果使用assert(phead),就会报错导致无法插入。

而对于pphead即phead的地址,是一定不为NULL,就可以进行assert(pphead)的操作。

注意*pphead与pphead的区别

7、尾删
//尾删 void SLTPopBack(SListNode** pphead) {
assert(pphead);//先检查pphead,再检查*pphead,若pphead为NULL,*pphead就会产生错误
assert(*pphead);//若原来为空链表,则无法删除 SListNode* cur = *pphead; //分情况,原来链表中有一个 还是
多个元素 if (NULL == cur->next) { free(cur); cur = NULL; *pphead = NULL; } else//
多个元素先找到倒数第二个 { SListNode* pretail = *pphead; while (pretail->next->next !=
NULL) { pretail = pretail->next; } free(pretail->next); pretail->next = NULL; }
}
先用assert确保phead不为NULL,即确保删除的不是空链表。

如果链表只有一个元素,free后,将phead置为NULL,使其成为空链表

当链表中有多个元素时,需要先找到尾结点的前一个元素pretail,方法是遍历,直到pretail->next->next为NULL,这里通过两个next,可以找到尾结点的那个next中的NULL,因此多个元素时使用这种方法,若只有一个元素则next的next会对NULL->,产生对于野指针解引用的错误。

总结:链表进行尾插尾删操作时,要先进行找尾,此过程需要遍历,效率较低,因此进行尾部操作时不如顺序表。

删除空链表时会报错。 

8、头插
//头插 void SLTPushFront(SListNode** pphead, SLTDataType x) { //先创造一个新结点
SListNode* tmp = BuySLTNode(x); if (NULL == tmp) { return; } SListNode* newnode
= tmp; //分情况讨论,原来链表是否为空 //if (NULL == *pphead) //{ // //如果为空,直接将phead与新结点连接即可
// *pphead = newnode; //} //else //{ // //不为空,建立新结点与原来头结点的联系 //
//将phead与原来头结点的联系变为与新结点的联系 // //原来A->B,现在A->C->B,先建立C->B,再建立A->C //
newnode->next = *pphead; // *pphead = newnode; //}
//是否为空都按不为空处理,next要么存原来头结点地址,要么为 NULL newnode->next = *pphead; *pphead =
newnode; }
链表的头插很简单,先buy一个新结点,然后将newnode->next指向原来的头结点,无论原来是否为NULL,再用phead指向这个新结点。

9、头删
//头删 void SLTPopFront(SListNode** pphead) { assert(*pphead); SListNode* first
= *pphead; *pphead = (*pphead)->next; free(first); first = NULL; }
创建first指针指向头结点,然后将phead指向下一个结点,不论是否为NULL,然后free掉first。

10、查找 
// 单链表查找 SListNode* SListFind(SListNode* phead, SLTDataType x) { SListNode*
cur = phead; while (NULL != cur) { if (cur->data == x) { return cur; } cur =
cur->next; } return NULL; }
利用cur遍历链表,如果找到x就返回cur,即存有x的结点的地址,没找到就继续遍历,cur==NULL时仍然未找到,则返回NULL。

 11、指定位置pos后方插入数据
// 单链表在指定位置后方插入 不用遍历 void SListInsertAfter(SListNode* pos,SLTDataType x) {
assert(pos); SListNode* newnode = BuySLTNode(x); if (NULL == newnode) {
perror("ButSLTNode fail"); return; } newnode->next = pos->next; pos->next =
newnode; }

将newnode->next连接pos的next,不论正负,然后将newnode赋给pos的next,此过程中不需要遍历,解决了顺序表在中间位置插入效率低的问题。

12、删除指定位置pos后方的数据
// 删除后面的 不用遍历 void SListEraseAfter(SListNode* pos) { assert(pos);
assert(pos->next != NULL); SListNode* del = pos->next; pos->next = del->next;
free(del); del = NULL;//del为形参,是否置空影响不大,到函数外自动销毁,一般由使用者进行置空 }
必须保证pos->next不为NULL,因为是删除pos位置的下一个元素,则至少有2个元素,若只有一个,next为NULL,再解引用会变为野指针。

用del保存要删除的位置,将pos的next与要删除元素的下一个元素连接,不论是否为NULL,然后free掉del,完成删除,也不需要遍历。

总结:链表的优点在于头部以及中间位置的插入和删除不需要遍历,这里中间位置,实际是pos的下一个元素。

任意位置后方进行插入/删除,不涉及phead的改变,因此只需要传入phead即可。

 13、在指定位置pos的前方插入元素

在前方插入删除涉及phead,因此传入&phead
//单链表指定位置之前插入元素,需要找prev void SListInsertBefore(SListNode** pphead,SListNode*
pos,SLTDataType x) { assert(*pphead);//不能为空,否则Find找不到pos assert(pos);
SListNode* newnode = BuySLTNode(x); SListNode* prev = *pphead; if (pos ==
*pphead) { newnode->next = pos; *pphead = newnode; } else//找到pos前一个位置 {
SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; }
newnode->next = pos; prev->next = newnode; } }
若链表中只有一个元素,则会改变phead的指向,这里调用头插SLTPushFront也可以。

>=2个元素时,先找到prev,然后插入。

需要进行遍历找到prev。 

如果要找的位置pos是NULL,直接报错即可,是使用该函数的人的问题,函数只要完成应该完成的任务即可。

注意:假设传入的是plist,而不是它的地址,仍然用pphead接收,后续*pphead就会发生错误。因此可assert(pphead)。pphead实际上一定不为空,因此只要传入plist地址就要assert

14、删除指定位置pos的数据
//在指定位置pos的删除 void SListErasepos(SListNode** pphead, SListNode* pos) {
assert(pphead); assert(*pphead); assert(pos); SListNode* cur = *pphead; if (cur
== pos) { *pphead = pos->next; free(cur); cur = NULL; } else { SListNode* prev
= *pphead; while (prev->next != pos) { prev = prev->next; } prev->next =
pos->next; free(pos); } }
 

 如果pos指向第一个结点,即为头删,也可以使用SLTPopFront头删函数

接收Find的ret在erase后可以置为NULL,在函数外部完成,内部为形参。在内部改变需要传pos的二级指针。

而对于pphead则只能传二级指针,在函数内部修改phead的指向。

销毁时,利用tmp指针变量销毁当前位置,然后next找到下一个位置,遍历销毁。

总结:尾插尾删头插头删都需要pphead,insertafter和eraseafter仅需要pos,查找和打印仅需要phead,insertbefore、erasepos需要pphead、pos。

pos  phead  pphead  *pphead 的assert问题。

链表的优点缺点,某些位置是否需要遍历。

面试题:不告知phead,只知道pos,怎么在pos指向的数据之前插入数据?

例如原来为  1   2,pos指向2,可以在2的位置后插入3,然后将2、3两个data交换,结果为132,当然,此时pos指向的是3。

如果是删除不给phead删除pos当前位置,则将pos位置的值改为下一个位置的值,然后删除掉下一个位置的数据。(不能删除尾结点)

技术
今日推荐
阅读数 169685
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信