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

_實(shí)驗(yàn)一 線性表的基本操作實(shí)現(xiàn)及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?、熟練掌握線性表的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。精品文檔放心下載2、會(huì)用線性鏈表解決簡(jiǎn)單的實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容題目一、該程序的功能是實(shí)現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對(duì)單鏈表操作的具體的函數(shù)定義和主函數(shù)。其中，程序中的單鏈表（帶頭結(jié)點(diǎn)）結(jié)點(diǎn)為結(jié)構(gòu)類型，結(jié)點(diǎn)值為整型。單鏈表操作的選擇以菜單形式出現(xiàn)，如下所示：謝謝閱讀pleaseinputtheoperation：謝謝閱讀1.初始化 2.清空 3.求鏈表長(zhǎng)度 4.檢查鏈表是否為空精品文檔放心下載5.檢查鏈表是否為滿 6.遍歷鏈表（設(shè)為輸出元素）7.從鏈表中查找元素謝謝閱讀8.從鏈表中查找與給定元素值相同的元素在表中的位置9.向鏈表中插入元素 10.從鏈表中刪除元素其他鍵退出。。。。。其中黑體部分必做題目二、約瑟夫環(huán)問題：設(shè)編號(hào)為1，2，3，……，n的n(n>0)個(gè)人按順時(shí)針方向圍坐一圈，每感謝閱讀個(gè)人持有一個(gè)正整數(shù)密碼。開始時(shí)任選一個(gè)正整數(shù)做為報(bào)數(shù)上限m，從第一個(gè)人開始順時(shí)針方向自1起順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的下一個(gè)人開始重新從1報(bào)數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計(jì)一個(gè)程序模擬此過程，求出出列編號(hào)序列。感謝閱讀structnode //結(jié)點(diǎn)結(jié)構(gòu){intnumber;/*人的序號(hào)*/intcipher;/*密碼*/structnode*next;/*指向下一個(gè)節(jié)點(diǎn)的指針*/精品文檔放心下載_};三、實(shí)驗(yàn)步驟(一)數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、單鏈表的結(jié)點(diǎn)類型定義/*預(yù)處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*定義DataType,status為int類型*/感謝閱讀typedefintDataType;typedefintstatus;/*單鏈表的結(jié)點(diǎn)類型*/typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;2、初始化單鏈表LinkedListLinkedListInit()精品文檔放心下載{ //定義并返回頭結(jié)點(diǎn)L}3、清空單鏈表voidLinkedListClear(LinkedListL)感謝閱讀{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,釋放除頭結(jié)點(diǎn)外的所有內(nèi)存空間精品文檔放心下載}4．檢查單鏈表是否為空_intLinkedListEmpty(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,判斷頭結(jié)點(diǎn)的next是否為空,如果空//返回OK，否則返回ERROR感謝閱讀}5、遍歷單鏈表voidLinkedListTraverse(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,遍歷并輸出L所有結(jié)點(diǎn)（不包括頭謝謝閱讀//結(jié)點(diǎn)）的數(shù)據(jù)}6、求單鏈表的長(zhǎng)度int LinkedListLength(LinkedListL)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不精品文檔放心下載//包括頭結(jié)點(diǎn)），并返回i}7、從單鏈表表中查找元素LinkedList LinkedListGet(LinkedListL,int i)謝謝閱讀{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回第i個(gè)元素謝謝閱讀}8、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（位置）精品文檔放心下載_int LinkedListGet1(LinkedListL,DataType x)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素在鏈表中的位置的精品文檔放心下載//位置}9、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（指針）感謝閱讀LinkedList LinkedListLocate(LinkedList L,DataType x)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的指針感謝閱讀}10、向單鏈表中插入元素status LinkedListInsert(LinkedListL,inti,DataType x)謝謝閱讀{}(二)函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)Main函數(shù)初始化鏈表調(diào)用菜單函數(shù)等待選擇，等輸入輸入非1-91-9時(shí)，調(diào)用對(duì)應(yīng)函數(shù)，否則退出輸入1-91.2.3.4.5.6.7.8.9.清求檢遍按按向從退空鏈查歷位值鏈鏈出表鏈鏈置查表表長(zhǎng)表表查找中中度是找元插刪否元素入除_圖1.主函數(shù)流程圖(三) 程序調(diào)試及運(yùn)行結(jié)果分析_1．進(jìn)入選擇界面后，先選擇7，進(jìn)行插入：2.選擇4，進(jìn)行遍歷，結(jié)果為：3.選擇2，得出當(dāng)前鏈表長(zhǎng)度._4.選擇3，得出當(dāng)前鏈表為.5.選擇分別選擇5、6進(jìn)行測(cè)試._6.選擇8，分別按位置和元素值刪除.7.選擇9，或非1-8的字符，程序結(jié)束._(四) 實(shí)驗(yàn)總結(jié)通過這次實(shí)驗(yàn)，我對(duì)線性鏈表有了更深的理解，深入明白了線性存儲(chǔ)結(jié)構(gòu)與精品文檔放心下載鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在內(nèi)存存儲(chǔ)的不同特點(diǎn)，同時(shí)我還學(xué)會(huì)了用這些知識(shí)實(shí)際解決一些精品文檔放心下載問題，能夠更加熟練地將算法轉(zhuǎn)化為實(shí)際程序。同時(shí)，在寫程序和調(diào)試程序的過謝謝閱讀程中，學(xué)會(huì)了一些書寫技巧和調(diào)試技巧，這對(duì)于自己能在短時(shí)間高效的寫出正確感謝閱讀地程序有很大作用。四、主要算法流程圖及程序清單主要算法流程圖：(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é)點(diǎn)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; 返回對(duì)應(yīng)值s->next=q;_程序清單：#include<iostream>usingnamespacestd;#include<conio.h>#include<stdlib.h>_/*預(yù)處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*單鏈表的結(jié)點(diǎn)類型*/typedefstructLNode{intdata;structLNode*next;}LNode,*LinkedList;/*初始化單鏈表*/LinkedListLinkedListInit()感謝閱讀{//定義并返回頭結(jié)點(diǎn)LinkedListL;L=(LinkedList)malloc(sizeof(LNode));謝謝閱讀L->next=NULL;returnL;_}/*清空單鏈表*/voidLinkedListClear(LinkedListL)謝謝閱讀{//釋放除頭結(jié)點(diǎn)外的所有內(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é)點(diǎn)的next是否為空,如果空返回OK，否則返回ERRORif(!(L->next))感謝閱讀returnOK;_returnERROR;}/*遍歷單鏈表*/voidLinkedListTraverse(LinkedListL)精品文檔放心下載{//遍歷并輸出L所有結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的數(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;}/*求單鏈表的長(zhǎng)度*/int LinkedListLength(LinkedListL)精品文檔放心下載{_//通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不含頭結(jié)點(diǎn)），并返回i感謝閱讀LinkedListp=L->next;inti=0;while(p){i++;p=p->next;}returni;}/*從單鏈表表中查找元素*/LinkedList LinkedListGet(LinkedListL,int i)精品文檔放心下載{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回第i個(gè)元素LinkedListp=L->next;intj=1;謝謝閱讀while(j<i&&p){p=p->next;j++;}if(!p)_{returnNULL;}returnp;}/*從鏈表中查找與給定元素值相同的元素在表中的位置,返回位置*/感謝閱讀int LinkedListGet1(LinkedListL,int x)謝謝閱讀{//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的位置精品文檔放心下載LinkedListp=L->next;inti=1;while(p&&!(p->data==x)){i++;p=p->next;}if(!p){return0;}returni;_}/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/LinkedListLinkedListLocate(LinkedListL,intx){精品文檔放心下載//L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的指針謝謝閱讀LinkedListp=L->next;while(p&&!(p->data==x)){p=p->next;}if(!p){returnNULL;}returnp;}/*向單鏈表中插入元素*/int LinkedListInsert(LinkedListL,inti,int x)感謝閱讀{L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法_在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素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é)點(diǎn)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個(gè)結(jié)點(diǎn),并返回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.求鏈表長(zhǎng)度"<<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時(shí)，進(jìn)行對(duì)應(yīng)功能函數(shù)調(diào)用，否則退出程序精品文檔放心下載while(i>=1&&i<=8){cout<<"\t\t"<<"請(qǐng)選擇：";cin>>i;_switch(i){//1、清空鏈表case1:LinkedListClear(L);break;精品文檔放心下載//2.求鏈表長(zhǎng)度case2:{cout<<"\t\t\t 鏈 表 長(zhǎng) 度 為 ："<<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請(qǐng)輸入要查詢的位置i：";謝謝閱讀intj;cin>>j;if(LinkedListGet(L,j)){cout<<"\t\t\t 位 置 i 的 元 素 值 為 ：謝謝閱讀"<<LinkedListGet(L,j)->data<<endl;精品文檔放心下載}else{cout<<"\t\t\ti大于鏈表長(zhǎng)度！"<<endl;謝謝閱讀}_getch();}break;//6.從鏈表中查找與給定元素值相同的元素在表中的位置精品文檔放心下載case6:{cout<<"\t\t\t請(qǐng)輸入要查找的元素值：";謝謝閱讀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請(qǐng)輸入要插入的值：";intx;cin>>x;cout<<"\t\t\t請(qǐng)輸入要插入的位置：";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請(qǐng)選擇：";cin>>d;switch(d)_{case1:{cout<<"\t\t\t請(qǐng)輸入刪除位置：";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請(qǐng)輸入刪除元素：";inty;cin>>y;if(LinkedListDel(L,y)){cout<<"\t\t\t"<<y<<"被刪除！"<<endl;感謝閱讀}_else{cout<<"\t\t\t刪除失敗！"<<endl;精品文檔放心下載}}}getch();}break;}}return1;}題二約瑟夫環(huán)問題算法、思想為了解決這一問題，可以先定義一個(gè)長(zhǎng)度為30（人數(shù)）的數(shù)組作為線性存精品文檔放心下載儲(chǔ)結(jié)構(gòu)，并把該數(shù)組看成是一個(gè)首尾相接的環(huán)形結(jié)構(gòu)，那么每次報(bào)m的人，就感謝閱讀要在該數(shù)組的相應(yīng)位置做一個(gè)刪除標(biāo)記，該單元以后就不再作為計(jì)數(shù)單元。這樣謝謝閱讀做不僅算法較復(fù)雜，而且效率低，還要移動(dòng)大量的元素。用單循環(huán)鏈表來解決這一問題，實(shí)現(xiàn)的方法相對(duì)要簡(jiǎn)單得的多。首先定義鏈表結(jié)謝謝閱讀_點(diǎn)，單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與一般單鏈表的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一精品文檔放心下載個(gè)整數(shù)來表示位置；然后將它們組成一個(gè)具有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表。接下來精品文檔放心下載從位置為1的結(jié)點(diǎn)開始數(shù)，數(shù)到第m個(gè)結(jié)點(diǎn)，就將此結(jié)點(diǎn)從循環(huán)鏈表中刪去，謝謝閱讀然后再?gòu)膭h去結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始數(shù)起，數(shù)到第m個(gè)結(jié)點(diǎn)，再將其刪去，如感謝閱讀此進(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)鏈表只剩下一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)指針返回Link*q=NULL;//指針q用來保存刪除結(jié)點(diǎn)的前驅(qū)for(intj=1;j<s;j++)感謝閱讀{q=p;p=p->next