网站建设待遇,shopify做国内网站,建网站的流程和费用,中企动力科技股份有限公司做网站链表的分类实现带有哨兵位的双向的循环链表**定义节点的结构**初始化单个节点初始化带有哨兵位的双向循环链表打印链表销毁链表尾插尾删头插头删find函数在任意位置之前插入任意位置的删除全部代码list.hlist.ctest.c 链表和顺序表的区别 链表的分类
如下 根据上述的三种组合… 链表的分类实现带有哨兵位的双向的循环链表**定义节点的结构**初始化单个节点初始化带有哨兵位的双向循环链表打印链表销毁链表尾插尾删头插头删find函数在任意位置之前插入任意位置的删除全部代码list.hlist.ctest.c 链表和顺序表的区别 链表的分类
如下 根据上述的三种组合一共分为8类
实现带有哨兵位的双向的循环链表
定义节点的结构
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;初始化单个节点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode(LTNode*)malloc(sizeof(LTNode));if (newnodeNULL){perror(malloc fail);}newnode-next NULL;newnode-prev NULL;newnode-data x;return newnode;
}初始化带有哨兵位的双向循环链表
作用使链表在无数据的情况下就具有循环的特点
LTNode* LTInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
}打印链表
哨兵位phead一定不能为空否则无法连接下面的节点
void LTPrint(LTNode* phead)
{assert(phead);printf(head);LTNode* cur phead-next;while (cur!phead){printf(%d,cur-data);cur cur-next;}printf(\n);
}销毁链表
void LPDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur!phead){LTNode* next cur-next;free(cur);cur next;}free(phead);}尾插
需要三个节点即可布置好顺序 顺序为tail newnode phead
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;}尾删
增加一个函数用于判断除哨兵位以外是否有其它的节点 bool类型只有两个取值true和false 需要三个节点顺序为tailprevtailphead
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail phead-prev;LTNode* tailprev tail-prev;tailprev-next phead;phead-prev tailprev;free(tail);
}头插
需要三个节点即可布置好顺序 顺序为phead newnode first void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;
}头删
增加一个函数用于判断除哨兵位以外是否有其它的节点 bool类型只有两个取值true和false 需要三个节点顺序为pheadtailtailnex
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail phead-next;LTNode* tailnex tail-next;phead-next tailnex;tailnex-prev phead;free(tail);
}find函数
从哨兵位的下一个节点开始遍历直至找到该元素或者遍历到哨兵位结束
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur!phead){if (cur-datax){return cur;}cur cur-next;}return NULL;
}在任意位置之前插入
任意位置之前的插入需要搭配find函数来使用需要三个节点顺序为posprevnewnodepos 可以使用它来进行头插和尾插分别可以表示为LTInsert(phead-next, x) LTInsert(phead, x)
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyListNode(x);LTNode* posprev pos-prev;newnode-next pos;pos-prev newnode;posprev-next newnode;newnode-prev posprev;
}任意位置的删除
道理同任意位置的插入
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnex pos-next;posprev-next posnex;posnex-prev posprev;free(pos);
}结果如下
全部代码
list.h
#pragma once
#include stdlib.h
#include stdio.h
#include assert.h
#include stdbool.htypedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;//创建单个的节点
LTNode* BuyListNode(LTDataType x);
//初始化
LTNode* LTInit();
//
void LTPrint(LTNode* phead);
void LPDestroy(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);//任意位置之前的插入
void LTInsert(LTNode* pos, LTDataType x);
//任意位置的删除
void LTErase(LTNode* pos);list.c
#define _CRT_SECURE_NO_WARNINGS 1
#include list.hLTNode* BuyListNode(LTDataType x)
{LTNode* newnode(LTNode*)malloc(sizeof(LTNode));if (newnodeNULL){perror(malloc fail);}newnode-next NULL;newnode-prev NULL;newnode-data x;return newnode;
}LTNode* LTInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
}void LTPrint(LTNode* phead)
{assert(phead);printf(head);LTNode* cur phead-next;while (cur!phead){printf(%d,cur-data);cur cur-next;}printf(\n);
}void LPDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur!phead){LTNode* next cur-next;free(cur);cur next;}free(phead);}
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;}bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail phead-prev;LTNode* tailprev tail-prev;tailprev-next phead;phead-prev tailprev;free(tail);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* first phead-next;newnode-next first;first-prev newnode;phead-next newnode;newnode-prev phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail phead-next;LTNode* tailnex tail-next;phead-next tailnex;tailnex-prev phead;free(tail);
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur!phead){if (cur-datax){return cur;}cur cur-next;}return NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyListNode(x);LTNode* posprev pos-prev;newnode-next pos;pos-prev newnode;posprev-next newnode;newnode-prev posprev;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnex pos-next;posprev-next posnex;posnex-prev posprev;free(pos);
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include list.h
void Test1()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPopBack(plist);LTPrint(plist);
}void Test2()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushFront(plist, 100);LTPushFront(plist, 200);LTPushFront(plist,300);LTPrint(plist);LTPopFront(plist);LTPrint(plist);}
void Test3()
{LTNode* plist LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTNode* posLTFind(plist, 3);if (posNULL){perror(pos NULL);}LTInsert(pos, 100);LTPrint(plist);LTErase(pos);LTPrint(plist);
}
int main()
{//Test1();//Test2();Test3();return 0;
}链表和顺序表的区别 局部性原理加载指定的数据可能会把与其物理内存之后的数据加载上去。 根据局部性原理顺序表在载入缓存中时可能会把与之相邻的数据一同载入但是链表的地址并不是相邻的在载入相应的链表的时候不会把相邻的链表载入缓存。 因此顺序表的缓存利用率比较高。
