荆州哪有做网站的公司,外贸公司大全,毕业网站设计代做,林业建设协会网站特点#xff1a;
结构#xff1a;指向前一结点指针数据指向后一结点指针由于循环#xff0c;尾结点的下一结点next指向头结点#xff08;哨兵结点#xff09;空的双向链表只有自循环的哨兵结点#xff08;头结点#xff09;
模拟实现双向链表
LIST.h
#define _CRT_…
特点
结构指向前一结点指针数据指向后一结点指针由于循环尾结点的下一结点next指向头结点哨兵结点空的双向链表只有自循环的哨兵结点头结点
模拟实现双向链表
LIST.h
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//定义双向链表结构
typedef int LTDataType;//链表数据类型
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化
void LTInit(LTNode** pphead);
LTNode* LTInit2();//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead);
void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL//打印链表
void 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 LTIErase(LTNode* pos);
LIST.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeLIST.h//创建结点
LTNode* buyNode(LTDataType x) {LTNode* newnode (LTNode*)malloc(sizeof(LTNode*));if (newnode NULL) {perror(malloc fail!);exit(1);}newnode-data x;newnode-next newnode-prev newnode;//初步实现双头自循环的空链表return newnode;
}
//初始化1 传参初始化
void LTInit(LTNode** pphead) {//创建一个哨兵结点头结点*pphead buyNode(-1);
}
//初始化2 返回值初始化
LTNode* LTInit2() {LTNode* phead buyNode(-1);return phead;
}//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead) {//哨兵位不能先销毁assert(pphead *pphead);LTNode* pcur (*pphead)-next;//从哨兵位的下一结点开始遍历销毁while (pcur ! (*pphead)) {LTNode* Next pcur-next;//创建pcur下一结点方便遍历销毁free(pcur);pcur Next;}//跳出循环说明哨兵位之后的全销毁了//现在释放销毁哨兵位free(*pphead);*pphead pcur NULL;
}//初次错误示范
void LTDesToryError(LTNode** pphead) {LTNode* pcur (*pphead)-next;LTNode* Next pcur-next;while (pcur!*pphead) {free(pcur);pcur Next;Next Next-next;}pcur Next NULL;
}//void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL//打印链表
void LTPrint(LTNode* phead) {LTNode* pcur phead-next;//记住第一个结点是哨兵位下一个结点while (pcur ! phead) {printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}//尾插数据
//第一个参数传一级还是二级要看pphead指向的节点会不会发生改变
//如果发生改变那么pphead的改变要影响实参传二级
//如果不发生改变pphead不会影响实参传一级
//我们通过传递的一级指针来找到头结点就可以找到之后的节点了//那么我们在插入新节点的时候受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//哨兵位 phead 新结点 newnode 尾结点pcur(phead-prev)LTNode* pcur phead-prev;LTNode* newnode buyNode(x);//newnode的指针修改prev指向上个尾节点next指向哨兵位newnode-prev pcur;newnode-next phead;//原先的尾节点next指针-哨兵位现在next-newnode//哨兵位的prev原本-尾节点,现在让prev-newnodepcur-next newnode;phead-prev newnode;
}//头插数据
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//哨兵位phead 新结点newnode 第一个结点 pcur(phead-next)LTNode* newnode buyNode(x);LTNode* pcur phead-next;//插入newnodeprev指向哨兵位next指向pcurnewnode-prev phead;newnode-next pcur;//哨兵位的next原头结点的prev分别指向newnodephead-next newnode;pcur-prev newnode;
}
//————————ERROR注意删除要检查链表是否为空——————————
//判断链表是否为空
bool LTEmpty(LTNode* phead) {assert(phead);//error!!! return phead NULL;不是判断哨兵位phead第一个结点是哨兵位下一结点phead-next!return phead-next phead;//如果哨兵位next指向自己说明是自循环的只有哨兵位的空链表
}//链表为空返回true
//尾删数据
void LTPopBack(LTNode* phead) {assert(phead);//哨兵位不得为空assert(!LTEmpty(phead));//链表不得为空//哨兵位phead 尾结点 del(phead-prev) 尾结点前一结点 del-prevLTNode* del phead-next;//删除尾结点 哨兵位的prev指向del-prev, 尾结点的前一结点的next-哨兵位del-prev-next phead;//注意这俩行代码不可调换phead-prev del-prev;//先改了头结点的指向 del也会跟着改//删除完之后释放delfree(del);del NULL;
}//头删数据
void LTPopFront(LTNode* phead) {assert(phead);assert(!LTEmpty(phead));//哨兵位phead 要删除的第一个结点del(phead-next) 新的第一结点del-nextLTNode* del phead-next;//删除结点 哨兵位的next指向新第一结点 新的第一结点的prev指向哨兵位del-next-prev phead;phead-next del-next;//释放delfree(del);del NULL;
}//查找数据
//遍历链表直至再次遇到哨兵位找一圈了没找到就是没有
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur phead-next;//记住从第一个结点不是pheadwhile (pcur ! phead) {//找到了if (pcur-data x) {return pcur;}pcur pcur-next;}//遍历循环找了一圈没找到return NULL;
}
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x) {//创建一个新结点LTNode* newnode buyNode(x);//pos newnode pos-next//先安newnodenewnode-next pos-next;newnode-prev pos;//先连接pos后面的再连pospos-next-prev newnode;pos-next newnode;
}//删除指定位置的节点
void LTIErase(LTNode* pos) {assert(pos);//传过来的位置不为空/*pos前面的节点pos-prevpos后面的节点pos-next删除pos影响这两个节点pos前面指针的节点的next指针-Pos后面的节点pos后面的节点的prev指针就-pos前面的节点*///pos-prev pos pos-nextpos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}
