实验三 链式存储结构(二)----双向链表的有关操作

1、实验三 链式存储结构（二）-双向链表的有关操作姓名王艳青学号520713130135日期2009.12.8实验题目双向链表的有关操作实验内容利用尾插法建立一个双向链表。遍历双向链表。实现双向链表中删除一个指定元素。在非递减有序双向链表中实现插入元素e仍有序算法。判断双向链表中元素是否对称若对称返回1否则返回0。设元素为正整型,实现算法把所有奇数排列在偶数之前。在主函数中设计一个简单的菜单调试上述算法。双向链表的类型定义typedef int ElemType；/元素类型typedef struct DuLNodeElemType data;struct DuLNode *prior,*next

2、;DuLNode,*DuLinkList;实验说明1类型定义#include typedef int ElemType；/元素类型typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;2为了算法实现简单，最好采用带头结点的单向链表。实验源代码头文件#pragma once#define WIN32_LEAN_AND_MEAN / 从Windows 头中排除极少使用的资料#include #include List文件#include #include #define TRUE 1#define OK 1#def

3、ine FALSE 0#define ERROR 0#define NULL 0#define OVERFLOW 0typedef int ElemType;typedef int Status;typedef struct DuLNode ElemType data;DuLNode *prior,*next;DuLNode,*DuLinkList;/函数声明void InitList(DuLinkList &L;/初始化链表void ClearList(DuLinkList L;/清空表void DestroyList(DuLinkList &L;/销毁双向链表Status

4、ListEmpty(DuLinkList L;/判断表是否为空int ListLength(DuLinkList L;/判断表的长度Status GetElem(DuLinkList L,int i,ElemType &e;/返回第i个元素的值int LocateElem(DuLinkList L,ElemType e,Status(*compare(ElemType,ElemType;/返回L中第个与e满足关系compare(的数据元素的位序Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e;/前驱判断St

5、atus NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e;/后继判断DuLinkList GetElem(DuLinkList L,int i;/返回第i个元素的地址Status ListInsert(DuLinkList L,int i,ElemType e;/在表的第i个位置之前插入元素eStatus ListDelete(DuLinkList L,ElemType &e;/删除表中第i个元素void ListTraverse(DuLinkList L,void(*visit(ElemType;/正序对每个元素调用

6、函数visit(void ListTraverseBack(DuLinkList L,void(*visit(ElemType;/逆序对每个元素调用函数visit(void print(ElemType e;/函数文件b02_7.cpp#include #include"c2_4.h"void InitList(DuLinkList &L/产生空间的双向循环链表L=(DuLinkListmalloc(sizeof(DuLNode;if(LL->next=L->prior=L;elseexit(OVERFLOW;void ClearList(DuLinkL

7、ist L /清空链表DuLinkList p=L->next;/p指向第一个结点while(p!=L p=p->next;free(p->prior;L->next=L->prior=L;/头结点的两个指针域指向其身void DestroyList(DuLinkList &L ClearList(L;/将L清空free(L;L=NULL;Status ListEmpty(DuLinkList L /判断表是否为空if(L->next=L&&L->prior=Lreturn TRUE;elsereturn FALSE;int L

8、istLength(DuLinkList L /返回表的长度int i=0;DuLinkList p=L->next;/p指向第一个结点while(p!=L i+;p=p->next;return i;Status GetElem(DuLinkList L,int i,ElemType &e /当第i个元素存在，将值赋给eint j=1;DuLinkList p=L->next;/p指向第一个结点while(p!=L&&j / 顺指针向后查找，直到 p 指向第 i 个元素 j+;p=p->next;if(p=L|j>ireturn ERRO

9、R;e=p->data;return OK;int LocateElem(DuLinkList L,ElemType e,Status(*compare(ElemType,ElemType /返回表中第个与e满足关系compare(的数据元素的位序int i=0;DuLinkList p=L->next;while(p!=L/p未指向头结点 i+;/计数器加if(compare(p->data,e/找到这样的元素return i;p=p->next;return 0;Status PriorElem(DuLinkList L,ElemType cur_e,ElemTyp

10、e &pre_e DuLinkList p=L->next->next;/p指向第个元素while(p!=L if(p->data=cur_e/p指向值为cur_e的结点pre_e=p->prior->data;/将p的前驱结点的值赋给return OK;p=p->next;return ERROR;Status NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e/返回后继DuLinkList p=L->next->next;/p指向第二个元素while(p!=L if(p-

11、>prior ->data=cur_e/p所指结点的前驱指向cur_e next_e=p->data;/将p所指结点的值赋给next_ereturn OK;p=p->next;return ERROR;DuLinkList GetElemP(DuLinkList L,int i/在双向链表中返回第i个元素的地址int j;DuLinkList p=L;/p指向头结点if(i<0|i>ListLength(Lreturn NULL;for(j=1;j<=i;j+/p指向第i个结点p=p->next;/p指向下一个结点return p;Status

12、ListInsert(DuLinkList L,int i,ElemType e /在链表第i个位置上插入元素DuLinkList p,s;if(i<1|i>ListLength(L+1return ERROR;p=GetElemP(L,i-1;/在L中确定第i个结点前驱的位置指针pif(!p return ERROR;s=(DuLinkListmalloc(sizeof(DuLNode;/生成新结点if(!s return ERROR;s->data=e;/将e赋给新的结点s->prior=p;/新结点的前驱为第i-1个结点s->next=p->next;

13、/新结点的后继为第i个结点p->next->prior=s;/第i个结点的前驱指向新结点p->next=s;/第i-1个结点的后继指向新结点return OK;Status ListDelete(DuLinkList L,ElemType &e /删除第i个结点DuLinkList p;int i;if(i<1return ERROR;p=GetElemP(L,i;/在L中确定第i个元素的位置指针if(!p return ERROR;e=p->data;/把第i个结点的元素的值赋给ep->prior->next=p->next;/第原i-

14、1个结点的后继指向原第i+1个结点p->next->prior=p->prior;/第原i+1个结点的前驱指向原第i-1个结点free(p;return OK;void ListTraverse(DuLinkList L,void(*visit(ElemType/由双向循环链表的表头出发，正序对每个数据元素调用函数visit(DuLinkList p=L->next;/p指向首元结点while(p!=L visit(p->data;/对p所指结点调用函数visit(p=p->next;printf("n"void ListTraverse

15、Back(DuLinkList L,void(*visit(ElemType /由双向循环链表的表头出发，逆序对每个元素调用函数visit(DuLinkList p=L->prior;/p指向尾结点while(p!=L visit(p->data;p=p->prior;printf("n"void print(ElemType e printf("%2d",e;主函数文件main2_6.cpp#include #include"c2_4.h"void main( DuLinkList L;int i,k;ElemTy

16、pe e0,e,e1;InitList(L;for(i=1;i<=5;i+ListInsert(L,i,i;printf("正序输出:"ListTraverse(L,print;printf("逆序输出:"ListTraverseBack(L,print;k=ListEmpty(L;printf("n判断表是否为空:k=%d(1,是;0,否",k;printf("n判断表的长度:%dn",ListLength(L;printf("n清空表n"ClearList(L;printf("

17、;n再次判断表是否为空n"k=ListEmpty(L;printf("n判断表是否为空:k=%d(1,是;0,否",k;printf("n判断表的长度:%dn",ListLength(L;printf("重新插入元素n"for(i=1;i<=10;i+ListInsert(L,i,i;ListTraverse(L,print;printf("n前驱判断n"for(i=1;i<=10;i+ GetElem(L,i,e;/将第i个元素的值赋给ek=PriorElem(L,e,e0;/判断前驱if(k=ERROR printf("元素%d没有前驱n",e;elseprintf("元素%d的前驱为%dn",e,e0;printf("n后继判断n"for(i=1;i<=10;i+ GetElem(L,i,e;k=NextElem(L,e,e1;if(k=ERRORprintf("元素%d没有后继n",e;elseprintf(