中海外交通建设有限公司网站,网站建设书籍,wordpress query_vars,国外网站需要备案吗个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》 文章目录 前言 一、实现思路1.节点的结构(ListNode)2.新节点的创建(BuyListNode)3.头结点的创建(ListCreate)4.双向链表的销毁(ListDestroy)5.双向链表的打印(ListPrint)6.双向链表的尾插(ListPu… 个人主页 个人主页 个人专栏 《数据结构》 《C语言》 文章目录 前言 一、实现思路1.节点的结构(ListNode)2.新节点的创建(BuyListNode)3.头结点的创建(ListCreate)4.双向链表的销毁(ListDestroy)5.双向链表的打印(ListPrint)6.双向链表的尾插(ListPushBack)7.双向链表的尾删(ListPopBack)8.双向链表的头插(ListPushFront)9.双向链表的头删(ListPopFront)10.双向链表的查找(ListFind)11.双向链表在pos前插入(ListInsert)12.双向链表删除pos位置处的节点(ListErase) 二、代码实现总结 前言
本篇博客将要实现的是带头双向循环链表该结构实现尾插尾删只需要O(1)的时间复杂度。 其结构如下所示 一、实现思路
1.节点的结构(ListNode)
既然要实现的链表是双向循环的那么对于指针域我们就需要指向节点上一个的指针和指向节点下一个的指针。至于双向循环我们只需要尾节点的next指向头结点头结点的prev指向尾节点即可实现双向循环。 如下
typedef int LTDataType;//方便以后修改数据类型typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;2.新节点的创建(BuyListNode)
动态开辟一块空间使该节点的prevnext都指向自己(方便头结构的创建)再为data赋值返回该空间地址。 //创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next newnode;newnode-prev newnode;return newnode;
}3.头结点的创建(ListCreate)
复用BuyListNode函数使头结点的data为无效数据(这里即为-1)。
//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}4.双向链表的销毁(ListDestroy)
要销毁链表我们就要遍历链表那么如何遍历链表
以遍历到头节点为结束条件从头结点的下一个节点开始遍历
如上我们就可以循环遍历链表。 销毁节点我们需要两指针变量一个记录要free的节点(cur)一个记录要free的节点的下一个节点(curNext)。每次free(cur)使cur curNext。
//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){ListNode* curNext cur-next;free(cur);cur curNext;}free(pHead);
}5.双向链表的打印(ListPrint)
我们只有遍历打印链表即可。
以遍历到头节点为结束条件从头结点的下一个节点开始遍历
//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;printf(head);while (cur ! pHead){printf(%d, cur-data);cur cur-next;}printf(head\n);
}6.双向链表的尾插(ListPushBack)
我们只需要让尾节点(tail)的next指向newnodenewnode的prev指向尾节点(tail)newnode的next指向头结点头结点的prev指向newnode. 我们知道该链表是双向循环的那么头结点的上一个节点就是尾节点。(与单链表相比该链表实现尾插并不需要遍历找尾时间复杂度是O(1) )。
//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode BuyListNode(x);ListNode* tail pHead-prev;tail-next newnode;newnode-prev tail;pHead-prev newnode;newnode-next pHead;
}7.双向链表的尾删(ListPopBack)
我们只需要两个指针tail (指向尾节点)tailPrev (指向尾节点的上一个节点)。 free掉tail使tailPrev的next指向头结点头结点的prev指向tailPrev。
注意head-next head 时链表无有效数据不能尾删数据。 //双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead-next pHead时链表没有元素assert(pHead-next ! pHead);ListNode* tail pHead-prev;ListNode* tailPrev tail-prev;pHead-prev tailPrev;tailPrev-next pHead;free(tail);
}8.双向链表的头插(ListPushFront)
我们只需要一个指针 first (头结点的下一个节点)使first的prev指向newnodenewnode的next指向firsthead的next指向newnodenewnode的prev指向head。 head节点是哨兵位不存储有效数据。
//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode BuyListNode(x);ListNode* first pHead-next;newnode-next first;first-prev newnode;newnode-prev pHead;pHead-next newnode;
}9.双向链表的头删(ListPopFront)
我们需要两个指针frist (指向头结点的下一个节点)second (指向头结点的下一个的下一个节点)。 free掉first使second的prev指向头结点头结点的next指向second。
注意如果head-next head表示链表为空不能头删。 //双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead);ListNode* first pHead-next;ListNode* second first-next;second-prev pHead;pHead-next second;free(first);
}10.双向链表的查找(ListFind)
我们需要遍历链表比较链表元素是否是要查找对象。如果找到了返回该节点的地址。如果找不到返回NULL。
//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x)return cur;cur cur-next;}return NULL;
}11.双向链表在pos前插入(ListInsert)
我们需要一个指针 posPrev (指向pos前一个节点)。 pos的prev指向newnodenewnode的next指向posposPrev的next指向newnodenewnode的prev指向posPrev。
如果pos指向头结点(哨兵位)那么ListInsert相当与完成尾插。如果pos指向头结点(哨兵位)的下一个节点那么ListInsert相当于头插。 //双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode BuyListNode(x);ListNode* posPrev pos-prev;newnode-prev posPrev;posPrev-next newnode;newnode-next pos;pos-prev newnode;
}12.双向链表删除pos位置处的节点(ListErase)
我们需要两个指针posPrev(记录pos的上一个节点的地址)posNext(记录pos的下一个节点的地址)。free掉pos使posNext的prev指向posPrevposPrev的next指向posNext。
如果pos指向头结点的下一个那么ListErase相当于头删。如果pos指向头结点的上一个(也就是尾节点)那么ListErase相当于尾删。 //双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext pos-next;ListNode* posPrev pos-prev;posPrev-next posNext;posNext-prev posPrev;free(pos);
}二、代码实现
对于头插尾插函数我复用了ListInsert函数。 对于头删尾删函数我复用了ListErase函数。
//Lish.h 文件#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;//创建返回链表的头结点
ListNode* ListCreate();//创建新节点
ListNode* BuyListNode(LTDataType x);//双向链表的销毁
void ListDestroy(ListNode* pHead);//双向链表的打印
void ListPrint(ListNode* pHead);//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x);//双向链表的尾删
void ListPopBack(ListNode* pHead);//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x);//双向链表的头删
void ListPopFront(ListNode* pHead);//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x);//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x);//双向链表删除pos位置的节点
void ListErase(ListNode* pos); //Lish.c 文件#include List.h//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next newnode;newnode-prev newnode;return newnode;
}//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;printf(head);while (cur ! pHead){printf(%d, cur-data);cur cur-next;}printf(head\n);
}//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode BuyListNode(x);ListNode* tail pHead-prev;tail-next newnode;newnode-prev tail;pHead-prev newnode;newnode-next pHead;*/ListInsert(pHead, x);
}//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead-next pHead时链表没有元素assert(pHead-next ! pHead);/*ListNode* tail pHead-prev;ListNode* tailPrev tail-prev;pHead-prev tailPrev;tailPrev-next pHead;free(tail);*/ListErase(pHead-prev);
}//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode BuyListNode(x);ListNode* first pHead-next;newnode-next first;first-prev newnode;newnode-prev pHead;pHead-next newnode;*/ListInsert(pHead-next, x);
}//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-next ! pHead);/*ListNode* first pHead-next;ListNode* second first-next;second-prev pHead;pHead-next second;free(first);*/ListErase(pHead-next);
}//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x)return cur;cur cur-next;}return NULL;
}//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode BuyListNode(x);ListNode* posPrev pos-prev;newnode-prev posPrev;posPrev-next newnode;newnode-next pos;pos-prev newnode;
}//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext pos-next;ListNode* posPrev pos-prev;posPrev-next posNext;posNext-prev posPrev;free(pos);
}//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){ListNode* curNext cur-next;free(cur);cur curNext;}free(pHead);
}总结
以上就是双向链表的实现 文章转载自： http://www.morning.rpljf.cn.gov.cn.rpljf.cn http://www.morning.fbxlj.cn.gov.cn.fbxlj.cn http://www.morning.tjmfz.cn.gov.cn.tjmfz.cn http://www.morning.hrjrt.cn.gov.cn.hrjrt.cn http://www.morning.yhxhq.cn.gov.cn.yhxhq.cn http://www.morning.mcndn.cn.gov.cn.mcndn.cn http://www.morning.nkyc.cn.gov.cn.nkyc.cn http://www.morning.mrttc.cn.gov.cn.mrttc.cn http://www.morning.plpqf.cn.gov.cn.plpqf.cn http://www.morning.fssjw.cn.gov.cn.fssjw.cn http://www.morning.wmcng.cn.gov.cn.wmcng.cn http://www.morning.bcngs.cn.gov.cn.bcngs.cn http://www.morning.ltzkk.cn.gov.cn.ltzkk.cn http://www.morning.wlsrd.cn.gov.cn.wlsrd.cn http://www.morning.kpgbz.cn.gov.cn.kpgbz.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.ksgjn.cn.gov.cn.ksgjn.cn http://www.morning.zxqxx.cn.gov.cn.zxqxx.cn http://www.morning.rzbgn.cn.gov.cn.rzbgn.cn http://www.morning.ztdlp.cn.gov.cn.ztdlp.cn http://www.morning.lmctj.cn.gov.cn.lmctj.cn http://www.morning.osshjj.cn.gov.cn.osshjj.cn http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.sgfpn.cn.gov.cn.sgfpn.cn http://www.morning.jjhng.cn.gov.cn.jjhng.cn http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.gyqnc.cn.gov.cn.gyqnc.cn http://www.morning.jgnst.cn.gov.cn.jgnst.cn http://www.morning.qgtbx.cn.gov.cn.qgtbx.cn http://www.morning.spbp.cn.gov.cn.spbp.cn http://www.morning.rnnwd.cn.gov.cn.rnnwd.cn http://www.morning.rpwht.cn.gov.cn.rpwht.cn http://www.morning.xhkgl.cn.gov.cn.xhkgl.cn http://www.morning.qmzhy.cn.gov.cn.qmzhy.cn http://www.morning.xqltq.cn.gov.cn.xqltq.cn http://www.morning.pqjpw.cn.gov.cn.pqjpw.cn http://www.morning.mytmn.cn.gov.cn.mytmn.cn http://www.morning.ahscrl.com.gov.cn.ahscrl.com http://www.morning.lzzqz.cn.gov.cn.lzzqz.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.plgbh.cn.gov.cn.plgbh.cn http://www.morning.bsjpd.cn.gov.cn.bsjpd.cn http://www.morning.diuchai.com.gov.cn.diuchai.com http://www.morning.jwtwf.cn.gov.cn.jwtwf.cn http://www.morning.klyzg.cn.gov.cn.klyzg.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.hmhdn.cn.gov.cn.hmhdn.cn http://www.morning.fwkq.cn.gov.cn.fwkq.cn http://www.morning.lkcqz.cn.gov.cn.lkcqz.cn http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.clyhq.cn.gov.cn.clyhq.cn http://www.morning.yccnj.cn.gov.cn.yccnj.cn http://www.morning.cljpz.cn.gov.cn.cljpz.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.lrmts.cn.gov.cn.lrmts.cn http://www.morning.hwnnm.cn.gov.cn.hwnnm.cn http://www.morning.pdghl.cn.gov.cn.pdghl.cn http://www.morning.tsrg.cn.gov.cn.tsrg.cn http://www.morning.hbqfh.cn.gov.cn.hbqfh.cn http://www.morning.bygyd.cn.gov.cn.bygyd.cn http://www.morning.gyfwy.cn.gov.cn.gyfwy.cn http://www.morning.mnwsy.cn.gov.cn.mnwsy.cn http://www.morning.twdkt.cn.gov.cn.twdkt.cn http://www.morning.monstercide.com.gov.cn.monstercide.com http://www.morning.ywpwq.cn.gov.cn.ywpwq.cn http://www.morning.rjznm.cn.gov.cn.rjznm.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.qgdsd.cn.gov.cn.qgdsd.cn http://www.morning.rmdwp.cn.gov.cn.rmdwp.cn http://www.morning.mjzcp.cn.gov.cn.mjzcp.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.mhsmj.cn.gov.cn.mhsmj.cn http://www.morning.rwpfb.cn.gov.cn.rwpfb.cn http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.c7630.cn.gov.cn.c7630.cn
