数据结构:请编程实现一个对双向链表进行基本操作的系统，主要包括链表的创建，查询，插入，删除，销毁等_百度知道
数据结构:请编程实现一个对双向链表进行基本操作的系统，主要包括链表的创建，查询，插入，删除，销毁等
数据结构:请编程实现一个对双向链表进行基本操作的系统，主要包括链表的创建，查询，插入，删除，销毁等操作（要求：可采用带头结点和不带头结点的双向链表）
我有更好的答案
数据结构:请编程实现一个对双向链表进行基本操作的系统，主要包括链表的创建，查询，插入，删除，销毁等操作（要求：可采用带头结点和不带头结点的双向链表）struct DBLNode{
DBLNode *};//创建DBLNode *create(){
DBLNode *head=NULL;
DBLNode *p,*q;
p=new DBLN
p-&data=d;
p-&pre=p-&next=NULL;
if(head==NULL)
p-&next=p;
}while(true);}//插入DBLNode *insert(DBLNode *h,int d,int b){
DBLNode *p,*q;
if (h==NULL)
cout&&&空链表中不能插入数据&；
while(p!=NULL && p-&data!=d)
if(p==NULL)
cout&&&没有找到插入点&;
if(p-&data==d)
q=new DBLN
q-&data=b;
q-&pre=q-&next=NULL;
q-&next=p;
q-&pre=p-&
q-&pre-&next=q;
q-&next=p;
}}//查询很简单，不写了//删除和插入基本相似//销毁void cast（DBLNode *h）{ }
采纳率：32%
来自团队：
为您推荐：
其他类似问题
双向链表的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。【图文】双向链表插入删除基本操作演示_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
双向链表插入删除基本操作演示
阅读已结束，下载本文到电脑
想免费下载本文？
登录百度文库，专享文档复制特权，积分每天免费拿！
你可能喜欢C语言（数据结构） - 双向链表的基本操作
/*dlist.h*/
#ifndef DList_H
#define DList_H
typedef struct Node * PN
//节点指针
typedef PNode P
//节点位置
/*定义节点类型*/
typedef struct Node
/*数据域*/
PN /*指向前驱*/
/*指向后继*/
/*定义链表类型*/
typedef struct
/*指向头节点*/
/*指向尾节点*/
//链表长度
/*分配值为i的节点，并返回节点地址*/
Position MakeNode(Item i);
/*释放p所指的节点*/
void FreeNode(PNode p);
/*构造一个空的双向链表*/
DList* InitList();
/*删除一个双向链表*/
void DestroyList(DList *plist);
/*将一个链表置为空表，释放原链表节点空间*/
void ClearList(DList *plist);
/*返回头节点地址*/
Position GetHead(DList *plist);
/*返回尾节点地址*/
Position GetTail(DList *plist);
/*返回链表大小*/
int GetSize(DList *plist);
/*返回p的直接后继位置*/
Position GetNext(Position p);
/*返回p的直接前驱位置*/
Position GetPrevious(Position p);
/*将pnode所指节点插入第一个节点之前*/
PNode InsFirst(DList *plist,PNode pnode);
/*将链表第一个节点删除并返回其地址*/
PNode DelFirst(DList *plist);
/*获得节点的数据项*/
Item GetItem(Position p);
/*设置节点的数据项*/
void SetItem(Position p,Item i);
/*删除链表中的尾节点并返回其地址，改变链表的尾指针指向新的尾节点*/
PNode Remove(DList *plist);
/*在链表中p位置之前插入新节点S*/
PNode InsBefore(DList *plist,Position p,PNode s);
/*在链表中p位置之后插入新节点s*/
PNode InsAfter(DList *plist,Position p,PNode s);
/*返回在链表中第i个节点的位置*/
PNode LocatePos(DList *plist,int i);
/*依次对链表中每个元素调用函数visit()*/
void ListTraverse(DList *plist,void (*visit)());
/*打印data*/
void print(Item data);
/*dlist.c*/
#include&dlist.h&
/*分配值为i的节点，并返回节点地址*/
Position MakeNode(Item i)
//创建节点，并设置数据i
PNode p = NULL;
//定义一个节点p指向空
p = (PNode)malloc(sizeof(Node));
//为该节点分配Ｎode结构体大小的空间
if(p!=NULL) //分配成功后
//设置数据域为i
p-&previous = NULL;//节点p前继指针指向空
p-&next = NULL; //节点p后继指针指向空
//返回创建好的p节点指针地址
/*释放p所指的节点*/
void FreeNode(PNode p)
/*构造一个空的双向链表*/
DList * InitList()
DList *plist = (DList *)malloc(sizeof(DList));//为新的双向链表分配DList结构体大小的空间
PNode head = MakeNode(0);
//调用上面的MakeNode（）函数创建数据域为0的头指针指向头节点
if(plist!=NULL)//成功分配新链表空间后
if(head!=NULL) //头指针不为空
plist-&head =//新链表的头指针指向头节点
plist-&tail = //先链表的尾指针也指向头节点
plist-&size = 0; //链表长度为0
return NULL; //头指针创建失败
//返回创建好的空链表
/*删除一个双向链表*/
void DestroyList(DList *plist)
ClearList(plist); //因为 DList *plist = (DList *)malloc(sizeof(DList))为链表分配了空间，所以必须调用清空链表函数，释放链表节点的空间
free(GetHead(plist)); //因为 PNode head = MakeNode(0)为头节点分配了空间，所以必须调用GetHead（）函数获取当前链表的头节点地址然后进行释放
free(plist);
/*判断链表是否为空表*/
int IsEmpty(DList *plist)
if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist)) //如果调用 GetSize（）函数获取的链表大小为0并且调用GetTail函数获取的尾节点和调用
//GetHead函数获取的头节点指向同一个地址，那么就是空表
/*将一个链表置为空表，释放原链表节点空间*/
void ClearList(DList *plist) //清空链表
PNode temp,p;
p = GetTail(plist); //将节点指针p指向尾指针指向的节点地址
while(!IsEmpty(plist))
//如果该链表不为空
temp = GetPrevious(p); //将节点指针temp指向p指针的前继指针所指向的地址
free(p); //将 p指针指向的尾节点释放
p = //p指针重新指向刚才释放的尾节点的前一个节点
plist-&tail = //尾指针重新指向刚才释放的尾节点的前一个节点
plist-&size--;
//从后往前一个一个释放节点空间，释放一个链表大小就减1
/*返回头节点地址*/
Position GetHead(DList *plist)
return plist-&
/*返回尾节点地址*/
Position GetTail(DList *plist)
return plist-&
/*返回链表大小*/
int GetSize(DList *plist)
return plist-&
/*返回p的直接后继位置*/
Position GetNext(Position p)
return p-&
/*返回p的直接前驱位置*/
Position GetPrevious(Position p)
return p-&
/*在第一个节点前插入新节点pnode*/
PNode InsFirst(DList *plist,PNode pnode)
Position head = GetHead(plist);//获取头节点位置
if(IsEmpty(plist))
//若链表为空，链表的尾指针就指向pnode节点，直接插入新节点
plist-&tail =
plist-&size++;//链表大小加1,给新加的pnode节点
pnode-&next = head-& //新加的pnode节点的后继指针指向头节点指向的第一个节点
pnode-&previous =//新加的pnode节点的前继指针指向头节点
if(head-&next!=NULL)
//如果第一个节点不为空
head-&next-&previous =
//第一个节点的前继指针就指向新加的pnode节点
head-&next = //头节点的后继指针指向新加的pnode节点
/*删除第一个节点,返回该节点的地址*/
PNode DelFirst(DList *plist)
Position head = GetHead(plist);//获取头节点位置
Position p=head-& //获取第一个节点位置
if(p!=NULL)
//第一个节点存在
if(p==GetTail(plist))
//若第一个节点就是尾节点
plist-&tail = p-& //尾指针直接指向第一个节点的前继节点即头节点
head-&next = p-& //头节点的后继指针直接指向第一个节点的后一个节点也就是第二个节点
head-&next-&previous = //第二个节点的前继指针指向头节点
plist-&size--;
//删除第一个节点后链表大小减1
/*获得节点的数据项*/
Item GetItem(Position p)
return p-&
/*设置节点的数据项*/
void SetItem(Position p,Item i)
/*删除链表中的尾节点并返回地址，改变链表的尾指针指向新的尾节点*/
PNode Remove(DList *plist)
Position p=NULL;
if(IsEmpty(plist))
return NULL;
p = GetTail(plist);
//让p指向尾节点
p-&previous-&next = p-&//p的前一个节点的后继指针也就是指向尾节点的指针跳过原尾节点指向头节点
plist-&tail = p-&
//尾指针重新指向原尾节点的前一个节点
plist-&size--;//删除尾节点后链表大小减1
/*在链表中p位置之前插入新节点s*/
PNode InsBefore(DList *plist,Position p,PNode s)
s-&previous = p-& //s节点的前继指针指向 p节点的前一个节点
s-&next = //s节点的后继指针指向p节点
p-&previous-&next = //原p节点的前一个节点的后继指针指向s节点
p-&previous = //p节点的前继指针指向s节点
plist-&size++; //插入新节点s后，链表大小加1
/*在链表中p位置之后插入新节点s*/
PNode InsAfter(DList *plist,Position p,PNode s)
s-&next = p-&
//s节点的后继指针原p节点的下一个节点
s-&previous =
//s节点的前继指针指向p节点
if(p-&next != NULL)
//原p节点下一个节点存在
p-&next-&previous =
//原p节点下一个节点的前继指针指向新加的s节点
p-&next =//原p节点的后继指针指向s节点
if(p = GetTail(plist)) //如果p是尾节点
plist-&tail =
//那么尾指针重新指向新加的s节点，让s节点作为尾节点
plist-&size++; //插入新节点s后，链表大小加1
/*返回在链表中第i个节点的位置*/
PNode LocatePos(DList *plist,int i)
int cnt = 0;
Position p = GetHead(plist); //p指向头节点
if(i&GetSize(plist)||i&1)
//判断i大小是否在链表大小之间
return NULL;
while(++cnt&=i) //p指针位置从头节点开始往后移动，直至第i个节点的位置
//p最后指向的位置就是所求的第i个节点的位置
/*依次对链表中每个元素调用函数visit()打印链表元素值*/
void ListTraverse(DList *plist,void (*visit)())
Position p = GetHead(plist);//p指向头节点
if(IsEmpty(plist))
//空链表无数据就退出
printf(&NULL&);
while(p-&next!=NULL)
//p不断往下遍历输出元素值
visit(p-&data);
/*打印data*/
void print(Item data)
printf(&%d &,data);
/*test.c*/
#include&dlist.h&
#include&dlist.c&
DList *plist = NULL;
PNode p = NULL;
printf(&开始创建空双向链表。。。。。\n&);
plist = InitList();
//创建双向链表
system(&sleep 2&);
printf(&创建空双向链表完成！\n&);
printf(&请输入你想创建的节点数目:&);
scanf(&%d&,&n);
printf(&空表不能进行任何操作！\n&);
printf(&开始创建头节点。。。。。。\n&);
printf(&请输入头节点的数据（空头节点请写0继续）:&);
scanf(&%d&,&a[0]);
printf(&正在创建头节点。。。。。。\n&);
p = InsFirst(plist,MakeNode(a[0]));
printf(&头节点创建完成！数据为：%d\n&,a[0]);数据结构——双向链表实现，基本操作的C++版
对于循环双向链表
判断一个链表是否为空的条件为：head-&next==head (头指针)
判断*p为最后一个节点的条件为：p-&next=head
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！双向链表基本操作以及优化可能 - Stultz_Lee - 博客园
随笔 - 26, 文章 - 0, 评论 - 0, 引用 - 0
面试时面试官要求手写双向链表的 删除操作，当时没有考虑到边界条件，导致被刷；
现在 列举下代码以及优化，作为事后反思：
双向链表的结构定义
typedefstruct doubleLink
struct doubleLink *
struct doubleLink *
}DOUBLE_LINK;
创建一个双向链表
/*创建一个双链表*/
DOUBLE_LINK *createDoubleLink()
DOUBLE_LINK *head = NULL;
head =(DOUBLE_LINK*)malloc(sizeof*head);
head-&prior = NULL;
head-&suffix = NULL;
/*插入节点*/
bool insertNode(DOUBLE_LINK*head,int data)
if(head == NULL)
DOUBLE_LINK *currNodep = NULL;
DOUBLE_LINK *nextp = NULL;
DOUBLE_LINK *newNodep = NULL;
for(currNodep =(nextp = currNodep-&suffix)!= NULL; currNodep = nextp)
if(nextp-&data == data)
if(nextp-&data & data)
newNodep =(DOUBLE_LINK*)malloc(sizeof*newNodep);
if(newNodep == NULL)
newNodep-&data =
/*需要插入双向链表时，遍历到需要插入的位置，开始对待插入的节点，前驱指针和后驱指针赋值，
后驱指针固定指向下一个节点指针，前驱需要区分 前指针是否是 头节点。
再对 当前节点的前驱指针赋值，需要区分待插入的点是不是 尾节点*/
//1.当前节点的后驱指针
currNodep-&suffix = newN
//2.新节点的前驱指针
if(currNodep == head)
newNodep-&prior = NULL;
newNodep-&prior = currN
//3.新节点的后驱指针
newNodep-&suffix =
//4.下一个节点的前驱指针
if(nextp == NULL)//到了尾节点处，则将头节点的前驱指向该尾节点，这是双向链表的结构精髓所在
head-&prior = newN
nextp-&prior = newN
if(nextp != NULL)
//one not in the tail
newNodep-&suffix =
currNodep-&suffix = newN
if(currNodep != head)// not the head
newNodep-&prior = currN
else// currnode is head
newNodep-&prior = NULL;
nextp-&prior = newN
//in the tail
currNodep-&suffix = newN
if(currNodep != head)//not the head
newNodep-&prior = currN
else//is the head
head-&prior = newN
newNodep-&prior = NULL;
newNodep-&suffix = NULL;
删除某个节点
/*删除某个节点*/
bool deleteNode(DOUBLE_LINK *head, DOUBLE_LINK *item)
_ASSERT(head != NULL);
_ASSERT(item != NULL);
DOUBLE_LINK *currentNodep = NULL;
DOUBLE_LINK *nextp = NULL;
for(currentNodep =(nextp = currentNodep-&suffix)!= NULL; currentNodep = nextp)
if(nextp == item)
/*当前节点为头结点时，这一点很重要*/
if(currentNodep == head)// the head
currentNodep-&prior = NULL;
currentNodep-&suffix = nextp-&
free(nextp);
nextp = NULL;
//最后一个节点时
elseif(nextp-&suffix == NULL)// the tail
currentNodep-&suffix = NULL;
free(nextp);
nextp = NULL;
else// the mid
DOUBLE_LINK *tmp = nextp-&
currentNodep-&suffix = nextp-&
nextp-&prior = currentN
free(nextp);
删除节点函数优化
bool deleteNode_opt(DOUBLE_LINK *head, DOUBLE_LINK *item)
_ASSERT(head != NULL);
_ASSERT(item != NULL);
//要删除第一个节点
if(item == head-&suffix)
head-&suffix = item-&
item-&suffix-&prior = NULL;
//要删除最后一个节点
elseif(item == head-&prior)
head-&prior = item-&
item-&prior-&suffix = NULL;
item-&prior-&suffix = item-&
item-&suffix-&prior = item-&
free(item);
item = NULL;
void printAllNode(DOUBLE_LINK *head)
_ASSERT(head != NULL);
DOUBLE_LINK *currentNodep = NULL;
DOUBLE_LINK *nextNodep = NULL;
std::cout &&"Node data is: ";
for(currentNodep =(nextNodep = currentNodep-&suffix)!= NULL; currentNodep = nextNodep)
std::cout && nextNodep-&data&&" ";
std::cout && std::