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

_實驗一 線性表的基本操作實現(xiàn)及其應(yīng)用一、實驗?zāi)康?、熟練掌握線性表的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)。精品文檔放心下載2、會用線性鏈表解決簡單的實際問題。二、實驗內(nèi)容題目一、該程序的功能是實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。其中，程序中的單鏈表（帶頭結(jié)點）結(jié)點為結(jié)構(gòu)類型，結(jié)點值為整型。單鏈表操作的選擇以菜單形式出現(xiàn)，如下所示：謝謝閱讀pleaseinputtheoperation：謝謝閱讀1.初始化 2.清空 3.求鏈表長度 4.檢查鏈表是否為空精品文檔放心下載5.檢查鏈表是否為滿 6.遍歷鏈表（設(shè)為輸出元素）7.從鏈表中查找元素謝謝閱讀8.從鏈表中查找與給定元素值相同的元素在表中的位置9.向鏈表中插入元素 10.從鏈表中刪除元素其他鍵退出。。。。。其中黑體部分必做題目二、約瑟夫環(huán)問題：設(shè)編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每感謝閱讀個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程，求出出列編號序列。感謝閱讀structnode //結(jié)點結(jié)構(gòu){intnumber;/*人的序號*/intcipher;/*密碼*/structnode*next;/*指向下一個節(jié)點的指針*/精品文檔放心下載_};三、實驗步驟(一)數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述1、單鏈表的結(jié)點類型定義/*預(yù)處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*定義DataType,status為int類型*/感謝閱讀typedefintDataType;typedefintstatus;/*單鏈表的結(jié)點類型*/typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;2、初始化單鏈表LinkedListLinkedListInit()精品文檔放心下載{ //定義并返回頭結(jié)點L}3、清空單鏈表voidLinkedListClear(LinkedListL)感謝閱讀{//L是帶頭結(jié)點的鏈表的頭指針,釋放除頭結(jié)點外的所有內(nèi)存空間精品文檔放心下載}4．檢查單鏈表是否為空_intLinkedListEmpty(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針,判斷頭結(jié)點的next是否為空,如果空//返回OK，否則返回ERROR感謝閱讀}5、遍歷單鏈表voidLinkedListTraverse(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針,遍歷并輸出L所有結(jié)點（不包括頭謝謝閱讀//結(jié)點）的數(shù)據(jù)}6、求單鏈表的長度int LinkedListLength(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針，通過遍歷鏈表用i記錄結(jié)點個數(shù)（不精品文檔放心下載//包括頭結(jié)點），并返回i}7、從單鏈表表中查找元素LinkedList LinkedListGet(LinkedListL,int i)謝謝閱讀{//L是帶頭結(jié)點的鏈表的頭指針,返回第i個元素謝謝閱讀}8、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（位置）精品文檔放心下載_int LinkedListGet1(LinkedListL,DataType x)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針,返回值為x元素在鏈表中的位置的精品文檔放心下載//位置}9、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（指針）感謝閱讀LinkedList LinkedListLocate(LinkedList L,DataType x)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針,返回值為x元素的指針感謝閱讀}10、向單鏈表中插入元素status LinkedListInsert(LinkedListL,inti,DataType x)謝謝閱讀{}(二)函數(shù)調(diào)用及主函數(shù)設(shè)計Main函數(shù)初始化鏈表調(diào)用菜單函數(shù)等待選擇，等輸入輸入非1-91-9時，調(diào)用對應(yīng)函數(shù)，否則退出輸入1-91.2.3.4.5.6.7.8.9.清求檢遍按按向從退空鏈查歷位值鏈鏈出表鏈鏈置查表表長表表查找中中度是找元插刪否元素入除_圖1.主函數(shù)流程圖(三) 程序調(diào)試及運行結(jié)果分析_1．進(jìn)入選擇界面后，先選擇7，進(jìn)行插入：2.選擇4，進(jìn)行遍歷，結(jié)果為：3.選擇2，得出當(dāng)前鏈表長度._4.選擇3，得出當(dāng)前鏈表為.5.選擇分別選擇5、6進(jìn)行測試._6.選擇8，分別按位置和元素值刪除.7.選擇9，或非1-8的字符，程序結(jié)束._(四) 實驗總結(jié)通過這次實驗，我對線性鏈表有了更深的理解，深入明白了線性存儲結(jié)構(gòu)與精品文檔放心下載鏈?zhǔn)酱鎯Y(jié)構(gòu)在內(nèi)存存儲的不同特點，同時我還學(xué)會了用這些知識實際解決一些精品文檔放心下載問題，能夠更加熟練地將算法轉(zhuǎn)化為實際程序。同時，在寫程序和調(diào)試程序的過謝謝閱讀程中，學(xué)會了一些書寫技巧和調(diào)試技巧，這對于自己能在短時間高效的寫出正確感謝閱讀地程序有很大作用。四、主要算法流程圖及程序清單主要算法流程圖：(1)從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置謝謝閱讀調(diào)用函數(shù)，傳入?yún)?shù)L，xtrue

p=L->nextp=p->nextp&&!(p->data==x)false返回p_調(diào)用函數(shù)，傳入?yún)?shù)L，i，x建立新結(jié)點s，令s->data=x;p=L->nexti==1 p=nullfalsetruep=p->nextj++true

j=1L->next=s;s->next=NULL;j<i-1&&pFalse

L->next=s;False不為空

s->next=p;q=p->next;p->next=s; 返回對應(yīng)值s->next=q;_程序清單：#include<iostream>usingnamespacestd;#include<conio.h>#include<stdlib.h>_/*預(yù)處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*單鏈表的結(jié)點類型*/typedefstructLNode{intdata;structLNode*next;}LNode,*LinkedList;/*初始化單鏈表*/LinkedListLinkedListInit()感謝閱讀{//定義并返回頭結(jié)點LinkedListL;L=(LinkedList)malloc(sizeof(LNode));謝謝閱讀L->next=NULL;returnL;_}/*清空單鏈表*/voidLinkedListClear(LinkedListL)謝謝閱讀{//釋放除頭結(jié)點外的所有內(nèi)存空間LinkedListp=L->next,q;L->next=NULL;while(p){q=p->next;free(p);p=q;}cout<<"\t\t\t已清空！"<<endl;精品文檔放心下載}/*檢查單鏈表是否為空*/intLinkedListEmpty(LinkedListL)謝謝閱讀{//判斷頭結(jié)點的next是否為空,如果空返回OK，否則返回ERRORif(!(L->next))感謝閱讀returnOK;_returnERROR;}/*遍歷單鏈表*/voidLinkedListTraverse(LinkedListL)精品文檔放心下載{//遍歷并輸出L所有結(jié)點（不含頭結(jié)點）的數(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;}/*求單鏈表的長度*/int LinkedListLength(LinkedListL)精品文檔放心下載{_//通過遍歷鏈表用i記錄結(jié)點個數(shù)（不含頭結(jié)點），并返回i感謝閱讀LinkedListp=L->next;inti=0;while(p){i++;p=p->next;}returni;}/*從單鏈表表中查找元素*/LinkedList LinkedListGet(LinkedListL,int i)精品文檔放心下載{//L是帶頭結(jié)點的鏈表的頭指針,返回第i個元素LinkedListp=L->next;intj=1;謝謝閱讀while(j<i&&p){p=p->next;j++;}if(!p)_{returnNULL;}returnp;}/*從鏈表中查找與給定元素值相同的元素在表中的位置,返回位置*/感謝閱讀int LinkedListGet1(LinkedListL,int x)謝謝閱讀{//L是帶頭結(jié)點的鏈表的頭指針,返回值為x元素的位置精品文檔放心下載LinkedListp=L->next;inti=1;while(p&&!(p->data==x)){i++;p=p->next;}if(!p){return0;}returni;_}/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/LinkedListLinkedListLocate(LinkedListL,intx){精品文檔放心下載//L是帶頭結(jié)點的鏈表的頭指針,返回值為x元素的指針謝謝閱讀LinkedListp=L->next;while(p&&!(p->data==x)){p=p->next;}if(!p){returnNULL;}returnp;}/*向單鏈表中插入元素*/int LinkedListInsert(LinkedListL,inti,int x)感謝閱讀{L為帶頭結(jié)點的單鏈表的頭指針，本算法_在鏈表中第i個結(jié)點之前插入新的元素xLinkedLists=(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(LinkedList L,intx)精品文檔放心下載{//刪除以L為頭指針的單鏈表中值為x結(jié)點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(LinkedList L,inti,int&x)精品文檔放心下載{//刪除以L為頭指針的單鏈表中第i個結(jié)點,并返回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();//進(jìn)行選擇，當(dāng)選擇為1-8時，進(jìn)行對應(yīng)功能函數(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 要查找的元素值內(nèi)存地址為：精品文檔放心下載"<<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ù)組作為線性存精品文檔放心下載儲結(jié)構(gòu)，并把該數(shù)組看成是一個首尾相接的環(huán)形結(jié)構(gòu)，那么每次報m的人，就感謝閱讀要在該數(shù)組的相應(yīng)位置做一個刪除標(biāo)記，該單元以后就不再作為計數(shù)單元。這樣謝謝閱讀做不僅算法較復(fù)雜，而且效率低，還要移動大量的元素。用單循環(huán)鏈表來解決這一問題，實現(xiàn)的方法相對要簡單得的多。首先定義鏈表結(jié)謝謝閱讀_點，單循環(huán)鏈表的結(jié)點結(jié)構(gòu)與一般單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一精品文檔放心下載個整數(shù)來表示位置；然后將它們組成一個具有n個結(jié)點的單循環(huán)鏈表。接下來精品文檔放心下載從位置為1的結(jié)點開始數(shù)，數(shù)到第m個結(jié)點，就將此結(jié)點從循環(huán)鏈表中刪去，謝謝閱讀然后再從刪去結(jié)點的下一個結(jié)點開始數(shù)起，數(shù)到第m個結(jié)點，再將其刪去，如感謝閱讀此進(jìn)行下去，直至全部刪去為止。代碼分析(一)創(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)鏈表只剩下一個結(jié)點，將該結(jié)點指針返回Link*q=NULL;//指針q用來保存刪除結(jié)點的前驅(qū)for(intj=1;j<s;j++)感謝閱讀{q=p;p=p->next