實驗三 鏈?zhǔn)酱鎯Y(jié)構(gòu)(二)----雙向鏈表的有關(guān)操作

1、實驗三 鏈?zhǔn)酱鎯Y(jié)構(gòu)（二）-雙向鏈表的有關(guān)操作姓名王艷青學(xué)號520713130135日期2009.12.8實驗題目雙向鏈表的有關(guān)操作實驗內(nèi)容利用尾插法建立一個雙向鏈表。遍歷雙向鏈表。實現(xiàn)雙向鏈表中刪除一個指定元素。在非遞減有序雙向鏈表中實現(xiàn)插入元素e仍有序算法。判斷雙向鏈表中元素是否對稱若對稱返回1否則返回0。設(shè)元素為正整型,實現(xiàn)算法把所有奇數(shù)排列在偶數(shù)之前。在主函數(shù)中設(shè)計一個簡單的菜單調(diào)試上述算法。雙向鏈表的類型定義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為了算法實現(xiàn)簡單，最好采用帶頭結(jié)點的單向鏈表。實驗源代碼頭文件#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;/函數(shù)聲明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滿足關(guān)系compare(的數(shù)據(jù)元素的位序Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e;/前驅(qū)判斷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;/正序?qū)γ總€元素調(diào)用

6、函數(shù)visit(void ListTraverseBack(DuLinkList L,void(*visit(ElemType;/逆序?qū)γ總€元素調(diào)用函數(shù)visit(void print(ElemType e;/函數(shù)文件b02_7.cpp#include #include"c2_4.h"void InitList(DuLinkList &L/產(chǎn)生空間的雙向循環(huán)鏈表L=(DuLinkListmalloc(sizeof(DuLNode;if(LL->next=L->prior=L;elseexit(OVERFLOW;void ClearList(DuLinkL

7、ist L /清空鏈表DuLinkList p=L->next;/p指向第一個結(jié)點while(p!=L p=p->next;free(p->prior;L->next=L->prior=L;/頭結(jié)點的兩個指針域指向其身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指向第一個結(jié)點while(p!=L i+;p=p->next;return i;Status GetElem(DuLinkList L,int i,ElemType &e /當(dāng)?shù)趇個元素存在，將值賦給eint j=1;DuLinkList p=L->next;/p指向第一個結(jié)點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滿足關(guān)系compare(的數(shù)據(jù)元素的位序int i=0;DuLinkList p=L->next;while(p!=L/p未指向頭結(jié)點 i+;/計數(shù)器加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的結(jié)點pre_e=p->prior->data;/將p的前驅(qū)結(jié)點的值賦給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所指結(jié)點的前驅(qū)指向cur_e next_e=p->data;/將p所指結(jié)點的值賦給next_ereturn OK;p=p->next;return ERROR;DuLinkList GetElemP(DuLinkList L,int i/在雙向鏈表中返回第i個元素的地址int j;DuLinkList p=L;/p指向頭結(jié)點if(i<0|i>ListLength(Lreturn NULL;for(j=1;j<=i;j+/p指向第i個結(jié)點p=p->next;/p指向下一個結(jié)點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個結(jié)點前驅(qū)的位置指針pif(!p return ERROR;s=(DuLinkListmalloc(sizeof(DuLNode;/生成新結(jié)點if(!s return ERROR;s->data=e;/將e賦給新的結(jié)點s->prior=p;/新結(jié)點的前驅(qū)為第i-1個結(jié)點s->next=p->next;

13、/新結(jié)點的后繼為第i個結(jié)點p->next->prior=s;/第i個結(jié)點的前驅(qū)指向新結(jié)點p->next=s;/第i-1個結(jié)點的后繼指向新結(jié)點return OK;Status ListDelete(DuLinkList L,ElemType &e /刪除第i個結(jié)點DuLinkList p;int i;if(i<1return ERROR;p=GetElemP(L,i;/在L中確定第i個元素的位置指針if(!p return ERROR;e=p->data;/把第i個結(jié)點的元素的值賦給ep->prior->next=p->next;/第原i-

14、1個結(jié)點的后繼指向原第i+1個結(jié)點p->next->prior=p->prior;/第原i+1個結(jié)點的前驅(qū)指向原第i-1個結(jié)點free(p;return OK;void ListTraverse(DuLinkList L,void(*visit(ElemType/由雙向循環(huán)鏈表的表頭出發(fā)，正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit(DuLinkList p=L->next;/p指向首元結(jié)點while(p!=L visit(p->data;/對p所指結(jié)點調(diào)用函數(shù)visit(p=p->next;printf("n"void ListTraverse

15、Back(DuLinkList L,void(*visit(ElemType /由雙向循環(huán)鏈表的表頭出發(fā)，逆序?qū)γ總€元素調(diào)用函數(shù)visit(DuLinkList p=L->prior;/p指向尾結(jié)點while(p!=L visit(p->data;p=p->prior;printf("n"void print(ElemType e printf("%2d",e;主函數(shù)文件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前驅(qū)判斷n"for(i=1;i<=10;i+ GetElem(L,i,e;/將第i個元素的值賦給ek=PriorElem(L,e,e0;/判斷前驅(qū)if(k=ERROR printf("元素%d沒有前驅(qū)n",e;elseprintf("元素%d的前驅(qū)為%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(