vs2017做网站,第一个做电子商务的网站,武昌网站建设制作,用wordpress建站会不会显得水平差链表的分类
链表的结构⾮常多样#xff0c;以下情况组合起来就有8种#xff08;2 x 2 x 2#xff09;链表结构#xff1a; 虽然有这么多的链表的结构#xff0c;但是我们实际中最常⽤还是两种结构#xff1a;单链表和双向带头循环链表
1.⽆头单向⾮循环链表#xff1a…链表的分类
链表的结构⾮常多样以下情况组合起来就有8种2 x 2 x 2链表结构 虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构单链表和双向带头循环链表
1.⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构如哈希表、图的邻接表等等。
2.带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带来很多优势实现反⽽简单了。
双向链表
概念与结构 注意这⾥的“带头”跟前⾯我们说的“头结点”是两个概念实际前⾯的在单链表阶段称呼不严谨但是为了同学们更好的理解就直接称为单链表的头结点。 带头链表⾥的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这⾥“放哨 的”
链表的实现
首先我们来看看它的具体声明用一个头文件来简述
//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//为了保持接口的一致性优化接口都为一级指针
//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//销毁
void LTDesTroy(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//传一级需要手动将plist置为NULLvoid LTPrint(LTNode* phead);//插入
//第一个参传一级还是二级要看pphead指向的节点会不会发生改变
//如果发生改变那么pphead的改变要影响实参传二级
//如何不发生改变pphead不会影响实参传一级
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//删除
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);bool LTEmpty(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置节点
void LTErase(LTNode* pos);
接下来我们创建一个List.c文件来一一实现上述声明
新结点的创建
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;//prev nextnewnode-next newnode-prev newnode;return newnode;
}
结点的初始化
//初始化
//void LTInit(LTNode** pphead)
//{
// //创建一个头结点哨兵位
// *pphead LTBuyNode(-1);
//}
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}
尾插与头插 //尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead phead-prev newnodenewnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-next(d1)newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}
打印与置空
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}
尾删与头删
尾删示意图 头删示意图 //尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead prev(del-prev) del(phead-prev) LTNode* del phead-prev;LTNode* prev del-prev;prev-next phead;phead-prev prev;free(del);del NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//phead del(phead-next) del-nextLTNode* del phead-next;del-next-prev phead;phead-next del-next;free(del);del NULL;
}
查找指定结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
在指定结点之后插入结点
示意图 //在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
删除指定位置结点
示意图本处就d2、d3两处结点分别讨论删除后的next与prev指针指向 //删除指定位置节点
void LTErase(LTNode* pos)
{assert(pos);// pos-prev pos pos-nextpos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}
销毁链表
示意图 //销毁
void LTDesTroy(LTNode** pphead)
{assert(pphead *pphead);LTNode* pcur (*pphead)-next;while (pcur ! *pphead){LTNode* Next pcur-next;free(pcur);pcur Next;}//销毁哨兵位结点free(*pphead);*pphead NULL;pcur NULL;
}
//优化代码
void LTDesTroy2(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* Next pcur-next;free(pcur);pcur Next;}free(phead);phead pcur NULL;
} 总结
学完了顺序表与链表相信大家或多或少对线性表有了自己的看法下面我们来就顺序表与链表做一个简单的比较 总的来说顺序表与链表没有优劣之分存在即合理。它们在解决我们不同问题的过程中都有着重要的作用。以上便是本期的分享感谢您的观看
