双向链表上的插入和删除算法

《双向链表上的插入和删除算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编写程序，演示在双向链表上的插入和删除算法。问题分析：1、在双向链表上操作首先要生成一个双向链表：1>节点定义structDuLNode{ElemTypedata;DuLNode*prior;DuLNode*next;};2.>创建双列表L=(DuLinkList)malloc(sizeof(DuLNode));L->next=L->prior=L;3>输入链表数据；2、3、对向链表进行插入操作算法：在节点p的前面加入一个新的节点q：q=(DuLinkList)malloc(sizeof(DuLNode));q->da

2、ta=e;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;4、对双向链表进行删除操作算法删除给定节点p得到的代码如下：#include#include#defineOK1#defineERROR0usingnamespacestd;typedefintElemType;typedefintstatus;structDuLNode{ElemTypedata;DuLNode*prior;DuLNode*next;};ty

3、pedefDuLNode*DuLinkList;statusDuListInsert_L(DuLinkListL,inti,ElemTypee)//插入函数{DuLinkListp=L;//定义两个指向头节点的指针DuLinkListq=L;intj=0;while(p->next!=L&&jnext;j++;}if(p->next==L

4、

5、j

6、建新节点q，数据为e，指针为nullq=(DuLinkList)malloc(sizeof(DuLNode));q->data=e;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;returnOK;}statusDuListDelete_L(DuLinkListL,inti,ElemType&e)//删除{DuLinkListp=L;intj=0;while(p->next!=L&&jnext;j++;}if(p->next==L

7、

8、j<

9、i){returnERROR;}p->prior->next=p->next;p->next->prior=p->prior;e=p->data;free(p);returnOK;}intmain(){//初始化双向循环链表LDuLinkListL;L=(DuLinkList)malloc(sizeof(DuLNode));//创建空双列表头结点L->next=L->prior=L;DuLNode*p,*q;ElemTypee;//给L赋初始值p=L;q=L;while(cin>>e){p->next=(DuLNode

10、*)malloc(sizeof(DuLNode));//分配新的节点q=p;p=p->next;//p指向新的节点p->data=e;//新结点的数据域为刚输入的ep->next=L;//新结点的指针域为头结点，表示这是单链表的最后一个结点p->prior=q;L->prior=p;}//p指向头指针，逐一输出链表的每个结点的值p=L;while(p->next!=L)//输出原列表{cout<next->data<<'';p=p->next;}cin.clear();//清除上一个cin的错误信息cin.ig

11、nore();//清空输入流inti;cout<<"输入待插入的元素e：";cin>>e;cout<<"输入待插入的位置i：";cin>>i;if(DuListInsert_L(L,i,e)){cout<<"插入后的双链为：";p=L;while(p->next!=L){cout<next->data<<'';p=p->next;}}printf("");p=L;while(p->next!=L)//输出列表{cout<next->data<<'';p=p->next;}intk;cin.clear

12、();//清除上一个cin的错误信息cin.ignore();//清空输入流cout<<"要删除第几个节点k:";cin>>k;if(DuListDelete_L(L,k,e)){cout<<"被删除的元素为："<next!=L)//输出删除后的列表{c