营销型网站主页定制,建筑模板木板,大气的金融网站,wordpress 4链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的 我们在上一篇文章所学习的顺序表是连续存储的 例如#xff1a; 顺序表就好比火车上的一排座位#xff0c;是连续的 而链表就好比是火车…链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 我们在上一篇文章所学习的顺序表是连续存储的 例如 顺序表就好比火车上的一排座位是连续的 而链表就好比是火车的各节车厢中间有东西将其互相连接的 链表的基本结构图如下 有一个指针指向下一个节点
链表的概念及结构
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 链表可以是单向和双向循环和不循环带头和不带头这样一组合就会出现八种类型的列表 单向的列表如下 双向列表 相比较单向双向的增删查改较为容易他会自带一个prev的节点能顾标记当前节点的前一个节点 循环列表 其实循环列表就是最后一个节点指向了开头节点 带头和不带头 头节点我们可以称其为哨兵位它是不会在链表中存储有效的数据的 其实八种链表我们最常用的只有两种 无头单向非循环链表 带头双向循环列表
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是后面的学习中你会发现其实他是比较简单的
链表的实现
首先我们要了解的就是单链表的实现 头文件如下
#includestdio.h
#includeassert.h
#includectype.h
#includestring.h
#includestdlib.h
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** plist);新节点的创建 我们要创建一个节点首先就是要为他动态开辟一个空间 然后再将这个新节点newnode的值赋予x并且将他的next置为空然后函数返回这个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}链表的打印 打印链表是我们可以用一个符号-来代替空格但是链表实际上是没有这个符号的 我们可以首先定义cur从链表的第一个节点开始遍历知道cur为空时就不会打印了并且打印一次cur的datacur要等于cue的next
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}单链表的尾插 这里我们要注意的是要记得用二级指针因为当链表为空时我们要改变的是节点的地址而我们要改变地址就要用地址的地址也就是二级指针 首先需要插入一个节点我们要做的就是创建一个新节点我们之前定义了的一个函数直接使用 然后我们创建一个tail指针让他从链表的第一个位置开始遍历一直遍历到最后一个节点此时令tail的next等于newnode即可
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);/*assert(*pplist);*///链表为空时可以尾插SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;}else{SListNode* tail *pplist;while (tail-next){tail tail-next;}tail-next newnode;}
}单链表的头插 头插比较简单我们直接将新节点的next等于链表的第一个节点即可也就是*pplist我们传进来的是**pplist是节点地址的地址所以我们需要解引用一次才能将地址给newnode的next
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}单链表的尾删 尾删的情况我们要分为两种 1.只有一个节点时 只有一个节点时我们直接free掉这个节点其次为了防止野指针我们要将其置空 2.当有多个节点时 我们创建一个tail和prev然后用循环将tail遍历到最后一个节点循环的终止条件时tail-next为空条件满足时就将tail赋予prev当跳出循环时prev就是尾节点的前一个节点我们直接将tail给free掉将其置空这样尾节点就被删除了
void SListPopBack(SListNode** pplist)
{assert(*pplist);//链表为空时不能再删暴力检查 if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* prev NULL;SListNode* tail *pplist;while (tail-next){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}单链表的头删 头删就很简单了首先定义一个tail存入第一个节点的位置然后将第一个节点的位置移动到他的next注意记得将临时存储第一个节点位置的指针给free掉避免出现野指针的问题
void SListPopFront(SListNode** pplist)
{assert(*pplist);//链表为空时不能再删暴力检查SListNode* tail *pplist;*pplist (tail)-next;free(tail);
}节点的查找 节点的查找也比较容易直接用while循环遍历如果cur的data和x相等就返回cur否则就是没有这个节点返回null
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur-next){if (cur-data x){return cur;//break;}cur cur-next;}return NULL;
}在一个节点之后插入节点 需要插入节点首先要做的就是创建一个新节点 然后首先要做的是将newnode的next连接到要插入位置pos的next 再将pos的next置为newnode 这里注意位置不能颠倒不然newnode的next就找不到了
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}删除一个节点之后的节点 要删除节点之后的一个节点首先这个节点之后一定要有一个节点所以要对pos-next进行断言 我们将pos-next存储到next中然后将pos-next直接指向next-next即可也就是把pos-nextpos-next-next
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//pos-next pos-next-next;SListNode* next pos-next;pos-next next-next;free(next);
}单链表的销毁 直接将pplist置空即可
void SListDestroy(SListNode** pplist)
{SListNode* node *pplist;node NULL;free(node);
}好了今天的分享到这里就结束了感谢大家的支持 完整代码如下
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);/*assert(*pplist);*///链表为空时可以尾插SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;}else{SListNode* tail *pplist;while (tail-next){tail tail-next;}tail-next newnode;}
}void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}void SListPopBack(SListNode** pplist)
{assert(*pplist);//链表为空时不能再删暴力检查 //SListNode* tail pplist;//while (tail-next-next)//{// tail tail-next;//}//free(tail-next);//tail-next NULL;if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* prev NULL;SListNode* tail *pplist;while (tail-next){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}void SListPopFront(SListNode** pplist)
{assert(*pplist);//链表为空时不能再删暴力检查SListNode* tail *pplist;*pplist (tail)-next;free(tail);
}SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur-next){if (cur-data x){return cur;//break;}cur cur-next;}return NULL;
}void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//pos-next pos-next-next;SListNode* next pos-next;pos-next next-next;free(next);
}void SListDestroy(SListNode** pplist)
{SListNode* node *pplist;node NULL;free(node);}
