1 链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
从以上图片可以看出:
1.链式结构在逻辑上是连续的,但在物理上不一定是连续的。
2.现实中的节点一般是在堆上申请出来的。
3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,可能不连续。
2 链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
2.1单向或双向
2.2带头或者不带头
2.3循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。
3 单向无头链表的实现
在头文件中包含一些函数的声明。
因为每个节点都是一个结构体,所以每个节点都要存放一个结构体的指针,指向下一个节点。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; SLTNode* BuyListBNode(SLTDataType x); void PrintSList(SLTNode* phead); void SLTPushBcak(SLTNode** pphead,SLTDataType x);//尾插 void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插 void SLTPopback(SLTNode** pphead);//尾删 void SLTPopFront(SLTNode** pphead,SLTDataType x);//头删 void SLTFind(SLTNode* pphead,SLTDataType x);//查找 //在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos之后插入x void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos);
3.1打印链表
打印链表首先要遍历链表,那么循环的条件就是走到空。所以我们创建一个临时变量cur代替头节点用来遍历,这样就可以不用动头节点,打印就是将节点中的数据打印出来,所以先将各个节点的数据打印出来,再指向下一个节点,需要注意的是next就是下一个节点的地址,所以将cur->next赋给cur就可以拿到下一个节点的地址了,拿到地址就可以继续访问下一个节点了。
void PrintSList(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
3.2创建节点
这里malloc一个节点出来就行了,然后判断是否malloc成功,将需要的数据存进data中就行了,然后将next置为NULL,然后返回这个节点。
SLTNode* BuyListBNode(SLTDataType x) { SLTNode* newnode = (SLTNode*) malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
3.3尾插节点
这个函数的第一个参数是一个二级指针,目的是为了修改结构体,尾插节点首先需要创建一个节点,然后·判断一下当前链表是否为空,如果为空则将这个节点设置为头节点,所以解引用这个二级指针,拿到一级指针的地址,就可以修改了。如果不为空,则创建一个临时变量来保存头节点的地址,然后使用这个变量来遍历链表找到尾节点,循环的结束条件就是tail的next为空,因为尾节点的next是NULL,循环结束之后tail就走到了尾节点的位置,然后将新节点赋给tail的next即可。
void SLTPushBcak(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuyListBNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
3.4头插节点
尾插节点还是需要创建一个节点,然后将这个节点的next指向这个头节点,但是头插之后头节点就是新插入的这个节点,所以需要使用二级指针,最后将新节点newnode赋给*pphead,这样头节点就更新了。
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuyListBNode(x); newnode->next = *pphead; *pphead = newnode; }
3.4尾删节点
尾删需要分很多种情况:
1.没有节点,这种情况就直接暴力检查,没有节点是删除不了的,直接assert即可。
2.一个节点,如果是一个节点的话,这个节点的next一定是NULL,所以使用if判断*pphead->next是否为NULL,如果是的话直接free掉这个节点然后置为空就行了。
3.如果是多个节点的话创建一个临时变量来遍历链表找到尾,需要注意的是,这个循环的结束条件是tail->next->next为空。下面这段代码就是错误的,因为free(tail)的本质是将tail指向的节点free,再将tail置为空相当于给tail赋值0x00000000,局部变量出了作用域就销毁了,但是前一个节点还是野指针,next虽然还是指向这个节点,但是这个节点已经free了。所以解决的方法就是找到tail的前一个节点,然后free掉tail->next,再置空。
正确的方法:
void SLTPopback(SLTNode** pphead) { assert(*pphead); //一个节点 if ((*pphead)->next = NULL) { free(*pphead); *pphead = NULL; } else//多个节点 { SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
3.5头删节点
头删也需要用到二级指针,然后暴力检查链表是否为空,不为空则创建一个变量newnode来保存头节点的next,然后free掉头节点,再将newnode赋给*pphead。
void SLTPopFront(SLTNode** pphead) { assert(pphead); SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
3.6查找节点
这个函数很简单,找到data就行,然后返回节点。
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
3.6在pos位置之前插入节点
pos的位置也需要分情况:
1.暴力检查
2.如果是头插,直接调用头插函数。
3.正常情况,创建一个结构体变量来遍历链表寻找pos节点,但是循环的结束条件设置成pre->next=pos最合适,因为我们需要保存pos的前一个节点,所以循环结束后pre就是pos的前一个节点,此时创建一个需要插入的节点newnode,将pre的next指向newnode,再将newnode的next指向pos,就完成链接了。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); if (*pphead == pos) { SLTPopFront(pphead,x); } else { SLTNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } SLTNode* newnode = BuyListBNode(x); pre->next = newnode; newnode->next = pos; } }
3.7在pos位置之后插入节点
首先暴力检查,再创建一个新节点newnode,插入需要注意的是以下这种写法是错误的,因为当我们将pos的next指向newnode的时候,就与后面的节点完全断开了,然后newnode的next又指向pos的next相当于形成了一个死循环。正确的方法应该是pos的next指向newnode的next,相当于先将newnode的next指向pos的后一个节点形成newnode的尾部链接,再将pos的next指向newnode完成newnode的头部链接。
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuyListBNode(x); newnode->next = pos->next; pos->next = newnode; }
3.8删除pos位置的节点
首先暴力检查,再判断pos是不是头删,正常删除就是创建一个变量遍历链表,pos的next为空作为循环的结束条件,循环结束之后pre就是pos的前一个节点,这个时候将pre的next指向pos的next也就是pos的下一个节点就行了,然后frre掉pos,这时候就不需要置空了。
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pos); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } pre->next = pos->next; free(pos); } }
3.9删除pos位置之后的节点
首先暴力检查,然后再检查是否为尾节点。创建一个变量posNext保存pos的下一个节点,然后即将pos的下一个节点指向pos的下下个节点即可。然后free掉posNext。
void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next);//检查是否是尾节点 SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); }