本操作

概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

结构链表是有各个节点通过指针连接在一起的每个节点分为数据域和指针域每个节点的指针域指向下一个节点的地址最后一个节点的指针域为空。

逻辑结构如下图所示

物理结构逻辑结构看起来是连续的但是由于链表的节点是在堆上开辟的地址可能连续也可能不连续

1.单向和双向

通过上面三种分类我们可以得知组合起来链表总共有8中结构但是我们经常使用的不带头无循环单链表和带头双向循环链表此篇文章暂时只讨论第一种结构的基本操作

单链表的基本操作有尾插、尾删、头插、头删、指定位置插入、指定位置删除、查找、销毁等操作下面我们来实现这些操作

1、无头单向非循环链表增删查改实现

链表和顺序表一样依然是使用结构体来实现然后利用动态内存管理函数开辟相应的空间结构体含有一个数据变量和指针变量

SListNode*

(SListNode*)malloc(sizeof(SListNode));//开辟一个节点if

(newnode

NULL)//检查是否开辟成功{perror(SLTBynode

error);return

打印链表和打印顺序表思想相似从前到后一次遍历每个节点并打印数据变量链表访问下一个节点需要找到下一个节点的地址而下一个的地址存储在当前指针指向的节点的指针域所以要使指针的值改为当前节点的指针域此时指针便指向了下一个节点了即curcur-next,使指针指向下一个节点

void

plist;//定义一个临时指针进行遍历最好不要动头结点while

(cur)//指针进行遍历直到指针指向空即遍历结束{printf(%d-,

cur-next;//指针指向下一个节点}printf(NULL\n);

3.尾插

尾插即将新节点插入到链表的尾部插入过程先调用开辟节点的函数开辟一个新节点如果链表为空则直接将头指针指向新节点如果非空链表的最后一个节点指针域通常为空所以我们需要一个临时指针找到链表的最后一个节点然后将最后的节点指针域指向新节点如图所示

void

newnode;//如果链表是空则直接将头结点指向新节点}else{SListNode*

cur

链表的头插即将新节点插入到链表最前面成为链表的第一个节点插入过程先调用开辟节点的函数创建一个新节点若链表为空则直接将头结点直接指向新节点若非空将新节点的指针域指向第一个节点然后将链表的头指针指向新节点如图所示

void

newnode;//若链表为空表则直接将头指针指向新节点}else{newnode-next

5.尾删

链表的尾删即删去链表的最后一个节点删除过程先判断链表是否为空为空则不能删除我们用assert断言函数检查链表是否为空表若非空如果只有一个节点我们只需要删除这个节点然后将头指针置空如果不止一个节点我们需要找到最后一个节点的前面的一个几点然后通过前一个的节点指针域释放最后一个节点此时前一个节点变成新的最后一个节点因此我们需要将其指针域置空如图所示

void

{assert(*pplist);//判断链表是否为空SListNode*

cur

*pplist;//定义临时指针,用来找到最后一个节点的前一个节点if

((*pplist)-next

NULL)//判断是否只有一个节点{free(*pplist);//删除这个节点*pplist

(cur-next-next)//遍历到最后一个节点的前一个节点{cur

cur-next;}free(cur-next);//删除最后一个元素cur-next

6.头删

链表的头删即删去链表的第一个节点删除过程先判断链表是否为空为空则不能删除直接退出函数如果只有一个节点则直接将该节点删除然后将头指针置空如果不止一个节点则需要一个临时指针指向第二个节点通过头指针将第一个元素删除此时第二个节点成为新的第一个节点然后将头指针指向临时指针即头指针指向新的第一个节点如图所示

void

{assert(*pplist);//判断链表是否为空SListNode*

cur

NULL)//判断是否只有一个节点{free(*pplist);//删除该节点*pplist

cur-next;//临时指针指向第二个节点free(*pplist);//删除第一个节点*pplist

cur;//头指针指向第二个节点}

链表的查找和顺序表思想相似从前往后遍历每个节点的数据与查找的数据相比较相等则返回该节点的地址找不到则返回NULL

SListNode*

链表指定位置一般是在指定位置后面插入元素插入元素过程先判断位置是否合法在创建一个新节点然后通过给定位置的next找到后面一个节点然后将新节点的指针域指向后面一个节点然后指定位置指针域指向新节点如图所示

特别值得注意的是图中的1和2顺序不能倒过来如果倒过来即先让指定位置指针域先指向新指针就找不到指定位置的后一个节点了

void

{assert(pos);//判断位置是否合法SListNode*newnodeBuySListNode(x);//创建新节点newnode-next

pos-next;//新节点指针域指向指定位置后一个节点pos-next

9.指定位置删除

链表的指定位置删除一般是删除指定位置之后的节点删除过程先判断位置是否合法然后需要定义一个临时指针找到给定位置的后一个节点然后将指定位置指针域指向要删除的节点后一个节点然后再删除指定位置后一个节点如图所示

void

{assert(pospos-next);//判断位置是否合法SListNode*

cur

pos-next;//定义临时指针指向指定位置的后一个节点pos-next

pos-next-next;//让指定位置指针域指向要删除节点的后一个接地那free(cur);//删除指定位置后一个节点

10.销毁

单链表的销毁需要两个临时指针第一个指针指向前面一个元素第二个指针指向后一个元素依次从前往后遍历删除掉第一个指针指向的节点然后第一个指针指向第二个指针指向的节点第二个指针往后走一个节点然后继续删除掉第一个指针指向的节点知道第二指针指向为空此时第一个指针指向最后一个节点再继续删除掉第一个指针指向的节点即全部删除完成

void

plist;//定义第一个临时指针指向相对前一个节点SListNode*

next

plist;//定义第二个临时指针指向相对前一个节点while

next;next

(SListNode*)malloc(sizeof(SListNode));//开辟一个节点if

(newnode

NULL)//检查是否开辟成功{perror(SLTBynode

error);return

plist;//定义一个临时指针进行遍历最好不要动头结点while

(cur)//指针进行遍历直到指针指向空即遍历结束{printf(%d-,

cur-next;//指针指向下一个节点}printf(NULL\n);

void

newnode;//如果链表是空则直接将头结点指向新节点}else{SListNode*

cur

newnode;//若链表为空表则直接将头指针指向新节点}else{newnode-next

void

{assert(*pplist);//判断链表是否为空SListNode*

cur

*pplist;//定义临时指针,用来找到最后一个节点的前一个节点if

((*pplist)-next

NULL)//判断是否只有一个节点{free(*pplist);//删除这个节点*pplist

(cur-next-next)//遍历到最后一个节点的前一个节点{cur

cur-next;}free(cur-next);//删除最后一个元素cur-next

void

{assert(*pplist);//判断链表是否为空SListNode*

cur

NULL)//判断是否只有一个节点{free(*pplist);//删除该节点*pplist

cur-next;//临时指针指向第二个节点free(*pplist);//删除第一个节点*pplist

cur;//头指针指向第二个节点}

{assert(pos);//判断位置是否合法SListNode*newnodeBuySListNode(x);//创建新节点newnode-next

pos-next;//新节点指针域指向指定位置后一个节点pos-next

void

{assert(pospos-next);//判断位置是否合法SListNode*

cur

pos-next;//定义临时指针指向指定位置的后一个节点pos-next

pos-next-next;//让指定位置指针域指向要删除节点的后一个接地那free(cur);//删除指定位置后一个节点

void

plist;//定义第一个临时指针指向相对前一个节点SListNode*

next

plist;//定义第二个临时指针指向相对前一个节点while

next;next

0);SListPopBack(node);SListPopFront(node);SListNode*

posSListFind(node,

3);SListPrint(node);//SListInsertAfter(pos,100);//SListPrint(node);SListEraseAfter(pos);SListPrint(node);SListDestroy(node);

int

写是为了不停地思考创作是为了更好地思考种一棵树最好的时间是十年前其次是现在。

单链表就暂时学到这啦如果对您有所帮助欢迎一键三连~