實驗一 線性表的基本操作實現(xiàn)及其應用

./實驗一線性表的基本操作實現(xiàn)及其應用一、實驗目的1、熟練掌握線性表的基本操作在兩種存儲結構上的實現(xiàn)。2、會用線性鏈表解決簡單的實際問題。二、實驗容題目一、該程序的功能是實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結構類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。其中,程序中的單鏈表〔帶頭結點結點為結構類型,結點值為整型。單鏈表操作的選擇以菜單形式出現(xiàn),如下所示：pleaseinputtheoperation：1.初始化2.清空3.求鏈表長度4.檢查鏈表是否為空5.檢查鏈表是否為滿6.遍歷鏈表〔設為輸出元素7.從鏈表中查找元素8.從鏈表中查找與給定元素值相同的元素在表中的位置9.向鏈表中插入元素10.從鏈表中刪除元素其他鍵退出。。。。。其中黑體部分必做題目二、約瑟夫環(huán)問題：設編號為1,2,3,……,n的n<n>0>個人按順時針方向圍坐一圈,每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m,從第一個人開始順時針方向自1起順序報數(shù),報到m時停止報數(shù),報m的人出列,將他的密碼作為新的m值,從他的下一個人開始重新從1報數(shù)。如此下去,直到所有人全部出列為止。令n最大值取30。要求設計一個程序模擬此過程,求出出列編號序列。structnode//結點結構{intnumber;/*人的序號*/intcipher;/*密碼*/structnode*next;/*指向下一個節(jié)點的指針*/};三、實驗步驟數(shù)據(jù)結構與核心算法的設計描述1、單鏈表的結點類型定義/*預處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*定義DataType,status為int類型*/typedefintDataType;typedefintstatus;/*單鏈表的結點類型*/typedefstructLNode{ DataTypedata; structLNode*next;}LNode,*LinkedList;2、初始化單鏈表LinkedListLinkedListInit<>{//定義并返回頭結點L}3、清空單鏈表voidLinkedListClear<LinkedListL>{ //L是帶頭結點的鏈表的頭指針,釋放除頭結點外的所有存空間}4．檢查單鏈表是否為空intLinkedListEmpty<LinkedListL>{//L是帶頭結點的鏈表的頭指針,判斷頭結點的next是否為空,如果空//返回OK,否則返回ERROR}5、遍歷單鏈表voidLinkedListTraverse<LinkedListL>{//L是帶頭結點的鏈表的頭指針,遍歷并輸出L所有結點〔不包括頭//結點的數(shù)據(jù)}6、求單鏈表的長度intLinkedListLength<LinkedListL>{//L是帶頭結點的鏈表的頭指針,通過遍歷鏈表用i記錄結點個數(shù)〔不//包括頭結點,并返回i}7、從單鏈表表中查找元素LinkedListLinkedListGet<LinkedListL,inti>{ //L是帶頭結點的鏈表的頭指針,返回第i個元素}8、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置〔位置intLinkedListGet1<LinkedListL,DataTypex>{ //L是帶頭結點的鏈表的頭指針,返回值為x元素在鏈表中的位置的 //位置}9、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置〔指針LinkedListLinkedListLocate<LinkedListL,DataTypex>{ //L是帶頭結點的鏈表的頭指針,返回值為x元素的指針}10、向單鏈表中插入元素statusLinkedListInsert<LinkedListL,inti,DataTypex>{}函數(shù)調(diào)用及主函數(shù)設計MMain函數(shù)初始化鏈表調(diào)用菜單函數(shù)1.清空2.求鏈表長度3.檢查鏈表是否為空4.遍歷鏈表5.按位置查找元素6.按值查找元素7.向鏈表中插入元素8.從鏈表中刪除元素9.退出等待選擇,等輸入1-9時,調(diào)用對應函數(shù),否則退出程序結束輸入1-9輸入非1-9圖1.主函數(shù)流程圖程序調(diào)試及運行結果分析1．進入選擇界面后,先選擇7,進行插入：2.選擇4,進行遍歷,結果為：選擇2,得出當前鏈表長度.4.選擇3,得出當前鏈表為.選擇分別選擇5、6進行測試.選擇8,分別按位置和元素值刪除.選擇9,或非1-8的字符,程序結束.實驗總結 通過這次實驗,我對線性鏈表有了更深的理解,深入明白了線性存儲結構與鏈式存儲結構在存存儲的不同特點,同時我還學會了用這些知識實際解決一些問題,能夠更加熟練地將算法轉化為實際程序。同時,在寫程序和調(diào)試程序的過程中,學會了一些書寫技巧和調(diào)試技巧,這對于自己能在短時間高效的寫出正確地程序有很大作用。四、主要算法流程圖及程序清單主要算法流程圖：<1>從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置p=p->nextp=p->nextp&&!<p->data==x>true調(diào)用函數(shù),傳入?yún)?shù)L,xp=L->nextfalse返回p調(diào)用函數(shù),傳入?yún)?shù)調(diào)用函數(shù),傳入?yún)?shù)L,i,x建立新結點s,令s->data=x;p=L->nexti==1p=nullfalseL->next=s;s->next=NULL;trueL->next=s;s->next=p;j=1j<i-1&&pp=p->nextj++trueq=p->next;p->next=s;s->next=q;P不為空返回對應值FalseFalse程序清單：#include<iostream>usingnamespacestd;#include<conio.h>#include<stdlib.h>/*預處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*單鏈表的結點類型*/typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkedList;/*初始化單鏈表*/LinkedListLinkedListInit<>{ //定義并返回頭結點 LinkedListL; L=<LinkedList>malloc<sizeof<LNode>>; L->next=NULL; returnL;}/*清空單鏈表*/voidLinkedListClear<LinkedListL>{ //釋放除頭結點外的所有存空間 LinkedListp=L->next,q; L->next=NULL; while<p> { q=p->next; free<p>; p=q; } cout<<"\t\t\t已清空！"<<endl;}/*檢查單鏈表是否為空*/intLinkedListEmpty<LinkedListL>{ //判斷頭結點的next是否為空,如果空返回OK,否則返回ERROR if<!<L->next>> returnOK; returnERROR;}/*遍歷單鏈表*/voidLinkedListTraverse<LinkedListL>{ //遍歷并輸出L所有結點〔不含頭結點的數(shù)據(jù) LinkedListp=L->next; if<!p> { cout<<"\t\t\t鏈表為空！"<<endl; } cout<<"\t\t"; while<p> { cout<<p->data<<"\t"; p=p->next; } cout<<endl;}/*求單鏈表的長度*/intLinkedListLength<LinkedListL>{ //通過遍歷鏈表用i記錄結點個數(shù)〔不含頭結點,并返回i LinkedListp=L->next; inti=0; while<p> { i++; p=p->next; } returni;}/*從單鏈表表中查找元素*/LinkedListLinkedListGet<LinkedListL,inti>{ //L是帶頭結點的鏈表的頭指針,返回第i個元素 LinkedListp=L->next; intj=1; while<j<i&&p> { p=p->next; j++; } if<!p> { returnNULL; } returnp;}/*從鏈表中查找與給定元素值相同的元素在表中的位置,返回位置*/intLinkedListGet1<LinkedListL,intx>{ //L是帶頭結點的鏈表的頭指針,返回值為x元素的位置 LinkedListp=L->next; inti=1; while<p&&!<p->data==x>> { i++; p=p->next; } if<!p> { return0; } returni;}/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/LinkedListLinkedListLocate<LinkedListL,intx>{ //L是帶頭結點的鏈表的頭指針,返回值為x元素的指針 LinkedListp=L->next; while<p&&!<p->data==x>> { p=p->next; } if<!p> { returnNULL; } returnp;}/*向單鏈表中插入元素*/intLinkedListInsert<LinkedListL,inti,intx>{ //L為帶頭結點的單鏈表的頭指針,本算法 //在鏈表中第i個結點之前插入新的元素x LinkedLists=<LinkedList>malloc<sizeof<LNode>>; s->data=x; LinkedListp=L->next,q; if<i==1> { if<p==NULL> { L->next=s; s->next=NULL; returnOK; } else { L->next=s; s->next=p; returnOK; } } intj=1; while<j<i-1&&p> { p=p->next; j++; } if<!p> { free<s>; returnERROR; } q=p->next; p->next=s; s->next=q; returnOK;}/*從單鏈表中刪除元素*/intLinkedListDel<LinkedListL,intx>{ //刪除以L為頭指針的單鏈表中值為x結點 LinkedListp=L->next,q=L; while<p&&!<p->data==x>> { q=p; p=p->next; } if<!p> { returnERROR; } q->next=p->next; free<p>; returnOK;}intLinkedListDel<LinkedListL,inti,int&x>{ //刪除以L為頭指針的單鏈表中第i個結點,并返回x的值 LinkedListp=L->next,q=L; intj=1; while<j<=i-1&&p> { q=p; p=p->next; j++; } if<!p> { x=0; returnERROR; } q->next=p->next; x=p->data; free<p>; returnOK;}/*菜單顯示*/voidScreenShow<>{ cout<<"\t\t\t"<<"1.清空"<<endl; cout<<"\t\t\t"<<"2.求鏈表長度"<<endl; cout<<"\t\t\t"<<"3.檢查鏈表是否為空"<<endl; cout<<"\t\t\t"<<"4.遍歷鏈表"<<endl; cout<<"\t\t\t"<<"5.從鏈表中查找元素"<<endl; cout<<"\t\t\t"<<"6.從鏈表中查找與給定元素值相同的元素在表中的位置"<<endl; cout<<"\t\t\t"<<"7.向鏈表中插入元素"<<endl; cout<<"\t\t\t"<<"8.從鏈表中刪除元素"<<endl; cout<<"\t\t\t"<<"9.退出"<<endl;}/*主函數(shù)*/intmain<>{ //初始化鏈表 inti=1; LinkedListL=LinkedListInit<>; if<L> { cout<<"\t\t\t初始化成功！\n"<<endl; } //顯示菜單 ScreenShow<>; //進行選擇,當選擇為1-8時,進行對應功能函數(shù)調(diào)用,否則退出程序 while<i>=1&&i<=8> { cout<<"\t\t"<<"請選擇："; cin>>i; switch<i> { //1、清空鏈表 case1:LinkedListClear<L>;break; //2.求鏈表長度 case2:{ cout<<"\t\t\t鏈表長度為："<<LinkedListLength<L><<endl; getch<>; } break; //3.檢查鏈表是否為空 case3:{ if<!LinkedListEmpty<L>> { cout<<"\t\t\t鏈表不為空！"<<endl; } else { cout<<"\t\t\t鏈表為空！"<<endl; } getch<>; } break; //4.遍歷鏈表 case4:{ LinkedListTraverse<L>; getch<>; } break; //5.從鏈表中查找元素 case5:{ cout<<"\t\t\t請輸入要查詢的位置i："; intj; cin>>j; if<LinkedListGet<L,j>> { cout<<"\t\t\t位置i的元素值為："<<LinkedListGet<L,j>->data<<endl; } else { cout<<"\t\t\ti大于鏈表長度！"<<endl; } getch<>; } break; //6.從鏈表中查找與給定元素值相同的元素在表中的位置 case6:{ cout<<"\t\t\t請輸入要查找的元素值："; intb; cin>>b; if<LinkedListGet1<L,b>> { cout<<"\t\t\t要查找的元素值位置為："<<LinkedListGet1<L,b><<endl; cout<<"\t\t\t要查找的元素值存地址為："<<LinkedListLocate<L,b><<endl; } else { cout<<"\t\t\t該值不存在！"<<endl; } getch<>; } break; //7.向鏈表中插入元素 case7:{ cout<<"\t\t\t請輸入要插入的值：";intx;cin>>x; cout<<"\t\t\t請輸入要插入的位置：";intk;cin>>k; if<LinkedListInsert<L,k,x>> { cout<<"\t\t\t插入成功！"<<endl; } else { cout<<"\t\t\t插入失?。?<<endl; } getch<>; } break; //8.從鏈表中刪除元素 case8:{ cout<<"\t\t\t1.按位置刪除"<<endl; cout<<"\t\t\t2.按元素刪除"<<endl; intd; cout<<"\t\t請選擇：";cin>>d; switch<d> { case1:{ cout<<"\t\t\t請輸入刪除位置："; cin>>d; inty; if<LinkedListDel<L,d,y>> { cout<<"\t\t\t"<<y<<"被刪除！"<<endl; } else { cout<<"\t\t\t刪除失敗！"<<endl; } }break; case2:{ cout<<"\t\t\t請輸入刪除元素："; inty; cin>>y; if<LinkedListDel<L,y>> { cout<<"\t\t\t"<<y<<"被刪除！"<<endl; } else { cout<<"\t\t\t刪除失?。?<<endl; } } } getch<>; } break; } } return1;}題二約瑟夫環(huán)問題算法、思想為了解決這一問題,可以先定義一個長度為30〔人數(shù)的數(shù)組作為線性存儲結構,并把該數(shù)組看成是一個首尾相接的環(huán)形結構,那么每次報m的人,就要在該數(shù)組的相應位置做一個刪除標記,該單元以后就不再作為計數(shù)單元。這樣做不僅算法較復雜,而且效率低,還要移動大量的元素。用單循環(huán)鏈表來解決這一問題,實現(xiàn)的方法相對要簡單得的多。首先定義鏈表結點,單循環(huán)鏈表的結點結構與一般單鏈表的結點結構完全相同,只是數(shù)據(jù)域用一個整數(shù)來表示位置；然后將它們組成一個具有n個結點的單循環(huán)鏈表。接下來從位置為1的結點開始數(shù),數(shù)到第m個結點,就將此結點從循環(huán)鏈表中刪去,然后再從刪去結點的下一個結點開始數(shù)起,數(shù)到第m個結點,再將其刪去,如此進行下去,直至全部刪去為止。代碼分析創(chuàng)建單循環(huán)鏈表structLink{ intData; Link*next;};Link*Creat<intn>{ Link*head,*s,*r; head=newLink; r=head; for<inti=0;i<n;i++> { s=newLink; cin>>s->Data; r->next=s; r=s; }r->next=head->next; returnhead;}"約瑟夫環(huán)"的操作模塊；Link*Jose<Link*p,intm>{ ints=m; if<p==p->next> returnp;//遞歸出口即循環(huán)鏈表只剩下一個結點,將該結點指針返回 Link*q=NULL;//指針q用來保存刪除結點的前驅(qū) for<intj=1;j<s;j++> {