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

编写程序，演示在双向链表上的插入和删除算法。问题分析：1、在双向链表上操作首先要生成一个双向链表： 1节点定义struct DuLNode ElemType data; 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-data=e;q-prior=p-prior; q-next=p;p-prior-next=q;p-prior=q; 4、 对双向链表进行删除操作算法 删除给定节点p得到的代码如下：#include#include#define OK 1#define ERROR 0using namespace std;typedef int ElemType;typedef int status;struct DuLNode ElemType data; DuLNode *prior; DuLNode *next;typedef DuLNode *DuLinkList;status DuListInsert_L(DuLinkList L,int i , ElemType e)/插入函数DuLinkList p=L; /定义两个指向头节点的指针DuLinkList q=L;int j=0;while(p-next!=L&jnext;j+;if(p-next=L|jdata=e;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;return OK;status DuListDelete_L(DuLinkList L,int i , ElemType &e)/删除 DuLinkList p=L;int j=0;while(p-next!=L&jnext;j+;if(p-next=L|jprior-next=p-next;p-next-prior=p-prior;e=p-data;free(p);return OK;int main() /初始化双向循环链表L DuLinkList L; L=(DuLinkList)malloc(sizeof(DuLNode); /创建空双列表 头结点L-next=L-prior=L;DuLNode *p,*q;ElemType e; /给L赋初始值 p=L;q=L;while(cine)p-next=(DuLNode*)malloc(sizeof(DuLNode);/分配新的节点 q=p;p=p-next; /p指向新的节点p-data=e; /新结点的数据域为刚输入的e p-next=L; /新结点的指针域为头结点，表示这是单链表的最后一个结点 p-prior=q;L-prior=p; /p指向头指针，逐一输出链表的每个结点的值 p=L;while(p-next!=L) /输出原列表 coutnext-datanext;cin.clear(); /清除上一个cin的错误信息 cin.ignore(); /清空输入流int i;coute;couti;if(DuListInsert_L(L,i,e)coutnext!=L) coutnext-datanext; printf(n);p=L; while(p-next!=L) /输出列表 coutnext-datanext;int k;cin.clear(); /清除上一个cin的错误信息 cin.ignore(); /清空输入流 coutk;if(DuListDelete_L(L,k,e) cout被删除的元素为：eendl; coutnext!=L) /输出删除后的列表