【优秀题解】问题 1678: 算法2-18~2-19：双向循环链表

解题思路:

双链表插入过程

以下介绍的是头插法

截取双向链表某一段

在p 后面插入元素 s

假如p->next指向下一个元素x

注意：先把后元素连接 再将前元素连接

第一步：（这一步千万不要倒过来 否则会出错）先把p->next元素（用x 元素代替），

x->prior指针指向x->prior=s （ p->next->prior=s）

x->next(即p->next->next)指针不需要改变

第二步：s->next=x; 到了这一步就实现了p元素与x元素的连接，就不需要再对x进行操作

第三步：p->next=s; 此时p->next不再指向x元素 第三步：p->next=s; 此时p->next不再指向x元素

第四步：s->prior=p; 最后实现了双向链表的插入与连接

双向链表的删除过程

首先先找到要删除的位置

例如p就是要删除的位置

只要将p的前后元素相连 再把p元素释放掉即可删除x

第一步：获取p的前驱元素s=p->prior;

第二步： s->next=p->next;

第三步：p->next->prior=s;

p->next=NULL

p->prior=NULL

free(p);

注意事项:使用c++提交，c提交编译不通过。也不知道是啥原因 参考代码:

#include <stdio.h>

#include <stdlib.h>

/*

解题的方法不用于题目，

插入时使用的是头插法

所以删除，输出操作与题目也不一致

*/

typedef int ElemType;

typedef struct DuLNode{

ElemType data;

struct DuLNode *next;

struct DuLNode *prior;

}DuLNode,*DuLinkList;

void Int_List (DuLinkList &L){

L=(DuLinkList)malloc(sizeof(DuLNode));

L->next=L;

L->prior=L;

}

void printf1(DuLinkList L)//输出的是也要反过来

{

DuLinkList p;

p=L;

while(p->prior!=L)

{

p=p->prior;

printf("%d ",p->data);

}

printf("\n");

}

DuLinkList DuLinkList_getELemp1(DuLinkList L,int i)//寻找删除的元素位置

{

DuLinkList p;

int j=1;

p=L->prior;

while(p!=L && j<i)

{

p=p->prior;

j++;

}

if(p==L && j<i)//位置不合法

return 0;

else

return p;

}

int LinsInsert_DuL(DuLinkList &L,int i,ElemType e)//插入操作 头插法

{

DuLinkList p,s;

p=DuLinkList_getELemp1(L,i);//获取插入位置

if(!p) return 0;//插入的位置不合法

s=(DuLinkList)malloc(sizeof(DuLNode));

if(!s) return 0;

s->data=e;

p->next->prior=s;//第一步操作

s->next=p->next;//第二步

p->next=s;//第三步

s->prior=p;//第四步

return 1;

}

int LinkListdelete_DuL( DuLinkList &L,int i)

{

DuLinkList p,s;

p=DuLinkList_getELemp1(L,i);

if(!p) return 0; //删除的位置不合法

s=p->prior;//获取删除位置的前驱元素 (第一步)

s->next=p->next;//s->next指向p的下一个元素（第二步）

p->next->prior=s;//p的上一个元素指向s（第三步）

p->next=NULL;

p->prior=NULL;

free(p);//释放内存

return 1;

}

int main (){

int a,i,e;

DuLinkList L;

Int_List(L);

while(scanf("%d",&a)!=EOF){

if(a==0)//输出

{

printf1(L);

}

else if(a==1){//插入

scanf("%d %d",&i,&e);

LinsInsert_DuL(L,i,e);

}

else if(a==2){//删除

scanf("%d",&i);

LinkListdelete_DuL(L,i);

}

}

free(L);

return 0;

} 点击“http://www.dotcpp.com/blog/9013.html”去撩原作者。