實驗三鏈式存儲結構（二）----雙向鏈表的有關操作姓名王艷青學號520713130135日期2009.12.8實驗題目雙向鏈表的有關操作實驗內容１．利用尾插法建立一個雙向鏈表。２．遍歷雙向鏈表。３．實現雙向鏈表中刪除一個指定元素。４．在非遞減有序雙向鏈表中實現插入元素e仍有序算法。５．判斷雙向鏈表中元素是否對稱若對稱返回1否則返回0。６．設元素為正整型,實現算法把所有奇數排列在偶數之前。７．在主函數中設計一個簡單的菜單調試上述算法。雙向鏈表的類型定義typedefintElemType；//元素類型typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;實驗說明1．類型定義#include<stdio.h>typedefintElemType；//元素類型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;2．為了算法實現簡單，最好采用帶頭結點的單向鏈表。實驗源代碼頭文件#pragmaonce#defineWIN32_LEAN_AND_MEAN //從Windows頭中排除極少使用的資料#include<stdio.h>#include<tchar.h>List文件#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineOK1#defineFALSE0#defineERROR0#defineNULL0#defineOVERFLOW0typedefintElemType;typedefintStatus;typedefstructDuLNode{ElemTypedata;DuLNode*prior,*next;}DuLNode,*DuLinkList;//函數聲明voidInitList(DuLinkList&L);//初始化鏈表voidClearList(DuLinkListL);//清空表voidDestroyList(DuLinkList&L);//銷毀雙向鏈表StatusListEmpty(DuLinkListL);//判斷表是否為空intListLength(DuLinkListL);//判斷表的長度StatusGetElem(DuLinkListL,inti,ElemType&e);//返回第i個元素的值intLocateElem(DuLinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//返回L中第個與e滿足關系compare()的數據元素的位序StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType&pre_e);//前驅判斷StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType&next_e);//后繼判斷DuLinkListGetElem(DuLinkListL,inti);//返回第i個元素的地址StatusListInsert(DuLinkListL,inti,ElemTypee);//在表的第i個位置之前插入元素eStatusListDelete(DuLinkListL,ElemType&e);//刪除表中第i個元素voidListTraverse(DuLinkListL,void(*visit)(ElemType));//正序對每個元素調用函數visit()voidListTraverseBack(DuLinkListL,void(*visit)(ElemType));//逆序對每個元素調用函數visit()voidprint(ElemTypee);///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////函數文件b02_7.cpp#include<stdio.h>#include"c2_4.h"voidInitList(DuLinkList&L){//產生空間的雙向循環鏈表L=(DuLinkList)malloc(sizeof(DuLNode));if(L)L->next=L->prior=L;elseexit(OVERFLOW);}voidClearList(DuLinkListL){//清空鏈表DuLinkListp=L->next;//p指向第一個結點while(p!=L){p=p->next;free(p->prior);}L->next=L->prior=L;//頭結點的兩個指針域指向其身}voidDestroyList(DuLinkList&L){ClearList(L);//將L清空free(L);L=NULL;}StatusListEmpty(DuLinkListL){//判斷表是否為空if(L->next==L&&L->prior==L)returnTRUE;elsereturnFALSE;}intListLength(DuLinkListL){//返回表的長度inti=0;DuLinkListp=L->next;//p指向第一個結點while(p!=L){i++;p=p->next;}returni;}StatusGetElem(DuLinkListL,inti,ElemType&e){//當第i個元素存在，將值賦給eintj=1;DuLinkListp=L->next;//p指向第一個結點while(p!=L&&j<i)//順指針向后查找，直到p指向第i個元素{j++;p=p->next;}if(p==L||j>i)returnERROR;e=p->data;returnOK;}intLocateElem(DuLinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//返回表中第個與e滿足關系compare()的數據元素的位序inti=0;DuLinkListp=L->next;while(p!=L)//p未指向頭結點{i++;//計數器加if(compare(p->data,e))//找到這樣的元素returni;p=p->next;}return0;}StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType&pre_e){DuLinkListp=L->next->next;//p指向第個元素while(p!=L){if(p->data==cur_e)//p指向值為cur_e的結點{pre_e=p->prior->data;//將p的前驅結點的值賦給returnOK;}p=p->next;}returnERROR;}StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType&next_e){//返回后繼DuLinkListp=L->next->next;//p指向第二個元素while(p!=L){if(p->prior->data==cur_e)//p所指結點的前驅指向cur_e{next_e=p->data;//將p所指結點的值賦給next_ereturnOK;}p=p->next;}returnERROR;}DuLinkListGetElemP(DuLinkListL,inti){//在雙向鏈表中返回第i個元素的地址intj;DuLinkListp=L;//p指向頭結點if(i<0||i>ListLength(L))returnNULL;for(j=1;j<=i;j++)//p指向第i個結點p=p->next;//p指向下一個結點returnp;}StatusListInsert(DuLinkListL,inti,ElemTypee){//在鏈表第i個位置上插入元素DuLinkListp,s;if(i<1||i>ListLength(L)+1)returnERROR;p=GetElemP(L,i-1);//在L中確定第i個結點前驅的位置指針pif(!p)returnERROR;s=(DuLinkList)malloc(sizeof(DuLNode));//生成新結點if(!s)returnERROR;s->data=e;//將e賦給新的結點s->prior=p;//新結點的前驅為第i-1個結點s->next=p->next;//新結點的后繼為第i個結點p->next->prior=s;//第i個結點的前驅指向新結點p->next=s;//第i-1個結點的后繼指向新結點returnOK;}StatusListDelete(DuLinkListL,ElemType&e){//刪除第i個結點DuLinkListp;inti;if(i<1)returnERROR;p=GetElemP(L,i);//在L中確定第i個元素的位置指針if(!p)returnERROR;e=p->data;//把第i個結點的元素的值賦給ep->prior->next=p->next;//第原i-1個結點的后繼指向原第i+1個結點p->next->prior=p->prior;//第原i+1個結點的前驅指向原第i-1個結點free(p);returnOK;}voidListTraverse(DuLinkListL,void(*visit)(ElemType)){//由雙向循環鏈表的表頭出發，正序對每個數據元素調用函數visit()DuLinkListp=L->next;//p指向首元結點while(p!=L){visit(p->data);//對p所指結點調用函數visit()p=p->next;}printf("\n");}voidListTraverseBack(DuLinkListL,void(*visit)(ElemType)){//由雙向循環鏈表的表頭出發，逆序對每個元素調用函數visit()DuLinkListp=L->prior;//p指向尾結點while(p!=L){visit(p->data);p=p->prior;}printf("\n");}voidprint(ElemTypee){printf("%2d",e);}主函數文件main2_6.cpp#include<stdio.h>#include"c2_4.h"voidmain(){DuLinkListL;inti,k;ElemTypee0,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判斷表的長度:%d\n",ListLength(L));printf("\n清空表\n");ClearList(L);printf("\n再次判斷表是否為空\n");k=ListEmpty(L);printf("\n判斷表是否為空:k=%d(1,是;0,否)",k);printf("\n判斷表的長度:%d\n",ListLength(L));printf("重新插入元素\n");for(i=1;i<=10;i++)L