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

1、實(shí)驗(yàn)線性表的基本操作實(shí)現(xiàn)及其應(yīng)用struct node *n ext; /*指向下一個(gè)節(jié)點(diǎn)的指針 */、實(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)，如下所示：pl ease input the op eratio n1. 初始化2.清空3.求鏈表長(zhǎng)度 4.檢查鏈表是否為空5. 檢查鏈表是否為滿6.遍歷鏈表（設(shè)為輸出元素）7

2、.從鏈表中查找元素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)序列。struct node/結(jié)點(diǎn)結(jié)構(gòu)int number; /* 人的序號(hào)

3、 */ int cipher; /* 密碼 */;三、實(shí)驗(yàn)步驟（一）數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、單鏈表的結(jié)點(diǎn)類型定義/*預(yù)處理命令*/ #defi ne OK 1;#defi ne ERROR 0;#defi ne OVERFLOW -1;/* 定義 DataType,status 為 int 類型 */ typ edef int DataT ype;typ edef int status;/*單鏈表的結(jié)點(diǎn)類型*/ typ edef struct LNodeDataT ype data; struct LNode *n ext;LNode,*L in kedList;2、初始化單鏈表Lin

4、 kedList Lin kedList In it() /定義并返回頭結(jié)點(diǎn)L3、清空單鏈表void Lin kedListClear(L in kedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針，釋放除頭結(jié)點(diǎn)外的所有內(nèi)存空間4 .檢查單鏈表是否為空int Lin kedListE mp ty(L in kedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針，判斷頭結(jié)點(diǎn)的next是否為空，如果空返回0K，否貝U返回ERROR5、遍歷單鏈表void Lin kedListTraverse(L in kedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針，遍歷并輸出L所有結(jié)點(diǎn)（不包括頭/結(jié)點(diǎn)）的數(shù)據(jù)6、求

5、單鏈表的長(zhǎng)度intLi nkedListLe ngth(Li nkedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針，通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不/包括頭結(jié)點(diǎn)），并返回i7、從單鏈表表中查找元素Lin kedListLin kedListGet(Li nkedList L,i nti)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回第i個(gè)元素8、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（位置）intLin kedListGet1(Li nkedList LQataTy pex)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回值為x元素在鏈表中的位置的/位置9、從單鏈表表中查找與給定元素值相同的元素在鏈表中的

6、位置（指針）Lin kedListLin kedListLocate(L in kedListL, DataT ypex)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回值為x元素的指針10、向單鏈表中插入元素X）statusLin kedListI nsert(L in kedList L,i nt i,DataT ype(二) 函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)圖1.主函數(shù)流程圖（三）程序調(diào)試及運(yùn)行結(jié)果分析1. 進(jìn)入選擇界面后，先選擇7,進(jìn)行插入:2. 選擇4，進(jìn)行遍歷，結(jié)果為:3. 選擇2，得出當(dāng)前鏈表長(zhǎng)度.5.選擇分別選擇5、6進(jìn)行測(cè)試.4.選擇3,得出當(dāng)前鏈表為.6.選擇8，分別按位置和元素值刪除.7.選擇9，

7、或非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.主要算法流程圖:(1)從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置2.程序清單:#in cludeviostream> using n ames pace std;#in clude<c oni o.

8、h> #in clude<stdlib.h>/*預(yù)處理命令*/ #defi ne OK 1;#defi ne ERROR 0;#defi ne OVERFLOW -1;/*單鏈表的結(jié)點(diǎn)類型*/ typ edef struct LNodeint data;struct LNode *n ext;LNode,*L in kedList;/*初始化單鏈表*/Lin kedList Lin kedList In it()/定義并返回頭結(jié)點(diǎn)Lin kedList L;L=(L in kedList)malloc(sizeof(LNode);l_->n ext=NULL;retur

9、n L;/*清空單鏈表*/ void Lin kedListClear(L in kedList L)/釋放除頭結(jié)點(diǎn)外的所有內(nèi)存空間Lin kedList p=L->n ext,q;L>n ext=NULL;while (p)q=p->n ext;free( p);p=q;coutvv"ttt已清空！ "<<e ndl;/*檢查單鏈表是否為空*/ int Lin kedListE mp ty(L in kedList L)II判斷頭結(jié)點(diǎn)的next是否為空，如果空返回OK，否則返回ERRORif (!(L-> next)return OK;

10、return ERROR;/*遍歷單鏈表*/ void Lin kedListTraverse(L in kedList L)/遍歷并輸出L所有結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的數(shù)據(jù)Lin kedList p=L->n ext;if (!p)cout<<"ttt鏈表為空！ "<<e ndl;cout<<"tt"while( p)coutv vp->datavv"t"p=p->n ext;coutvve ndl;/*求單鏈表的長(zhǎng)度*/intLin kedListLe ngth(L in kedLi

11、st L)/通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不含頭結(jié)點(diǎn)），并返回iLin kedList p=L->n ext;int i=0;while( p)i+； p=p->n ext;return i;/*從單鏈表表中查找元素*/i)Lin kedList Lin kedListGet(L in kedList L,i nt/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回第i個(gè)元素Lin kedList p=L->n ext;int j=1;while(j<i&&P)p=p->n ext;j+;if (!p)return NULL;return p;/*從鏈表中查找與給定

12、元素值相同的元素在表中的位置 ，返回位置*/x)int Li nkedListGet1(Li nkedList L,i nt/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回值為x元素的位置Lin kedList p=L->n ext;int i=1;while( p&&!(p->data=x)i+;p=p->n ext;if (!p)return 0;return i;/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置 */L, int X)Lin kedListLin kedListLocate(L in kedList/L是帶頭結(jié)點(diǎn)的鏈表的頭指針，返回值為X元素的

13、指針Lin kedList p=L->n ext;while( p&&!(p->data=x)p=p->n ext;if (!p)return NULL;return p;/*向單鏈表中插入元素*/x)intLin kedListI nsert(L in kedList L,i nt i,i nt/ L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法/在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素xLin kedList s=(L in kedList)malloc(sizeof(LNode);s->data=x;Lin kedList p=L->n ext,q;if (i

14、=1)if (p=NULL)L->n ext=s;s-> next=NULL;return OK;elseL->n ext=s;s->n ext=p;return OK;int j=1;while(j<i-1 &&P)p=p->n ext;j+；if (!p)free(s);return ERROR;q=p->n ext;p->n ext=s;s->n ext=q;return OK;/*從單鏈表中刪除元素*/L,i nt x)int Li nkedListDel(Li nkedList/刪除以L為頭指針的單鏈表中值為x結(jié)點(diǎn)

15、Lin kedList p=L->n ext,q=L;while( p&&!(p->data=x)q=p;p=p->n ext;if (!p)return ERROR;q->n ext=p->n ext;free( p);return OK;L,i nt i,i nt &x)int Li nkedListDel(Li nkedList/刪除以L為頭指針的單鏈表中第i個(gè)結(jié)點(diǎn)，并返回x的值Lin kedList p=L->n ext,q=L;int j=1;while(j<=i-1 &&P)q=p;p=p->n

16、 ext;j+;if (!p)x=0;return ERROR;q->n ext=p->n ext;x=p->data;free( p);return OK;/*菜單顯示*/void Scree nShow()cout<<"ttt"<<"1.清空"<<e ndl;cout<<"ttt"<<"2.求鏈表長(zhǎng)度"<<endl;cout<<"ttt"<<"3.檢查鏈表是否為空&qu

17、ot;<<endl;cout<<"ttt"<<"4.遍歷鏈表"<<endl;cout<<"ttt"<<"5.從鏈表中查找元素 "<<e ndl;cout<<"ttt"<<"6.從鏈表中查找與給定元素值相同的元素在表中cout<<"ttt"<<"7.向鏈表中插入元素"<<endl;的位置"<

18、<e ndl;coutvv"ttt"vv"8.從鏈表中刪除元素"<<endl;coutvv"ttt"vv"9.退出"<<e ndl;/*主函數(shù)*/ int main()/初始化鏈表int i=1;Lin kedList L=Li nkedListI ni t();if (L)cout<<"ttt初始化成功！ n"vve ndl;/顯示菜單Scree nShow();/進(jìn)行選擇，當(dāng)選擇為1-8時(shí)，進(jìn)行對(duì)應(yīng)功能函數(shù)調(diào)用，否則退出程序while(i>=1

19、 &&i <=8)cout<<"tt"<<"請(qǐng)選擇："cin> >i;switch (i)/1、清空鏈表case 1:Li nkedListClear(L);break;112.求鏈表長(zhǎng)度case 2:cout<<"ttt"<<Li nkedListLe ngth(L)vve ndl;getch();break;/3.檢查鏈表是否為空case 3:if (!Li nkedListEm pty(L)cout<<"ttt鏈表不為空！ &

20、quot;<<e ndl;elsegetch();cout<<"ttt鏈表為空！ "<<e ndl;break;114.遍歷鏈表case 4:Lin kedListTraverse(L);getchO;break;/5.從鏈表中查找元素case 5:coutvv"ttt請(qǐng)輸入要查詢的位置i:"int j;cin>>j;if (Li nkedListGet(L,j)cout<<"ttt的元素值為"<<Li nkedListGet(L,j)->datavve n

21、dl;elsecout<<"ttti大于鏈表長(zhǎng)度!"<<e ndl;getchO;break;116.從鏈表中查找與給定元素值相同的元素在表中的位置case 6:coutvv"ttt請(qǐng)輸入要查找的元素值："int b;cin>>b;if (Li nkedListGet1(L,b)cout<<"ttt要查找的元素值位置為："<<Li nkedListGet1(L,b)vve ndl;cout<<"ttt要查找的元素值內(nèi)存地址為："<<

22、L in kedListLocate(L,b)<<e ndl;elsecout<<"ttt該值不存在！ "<<e ndl;getch();break;cout<<"ttt請(qǐng)輸入要插入的值："i nt x; cin >>x;/7.向鏈表中插入元素case 7:cout<<"ttt請(qǐng)輸入要插入的位置："i nt k; cin >>k;if(Li nkedList In sert(L,k,x)cout<<"ttt插入成功！ "

23、<<e ndl;elsecout<<"ttt插入失敗！ "<<e ndl;getch();break;/8.從鏈表中刪除元素case 8:coutvv"ttt1.按位置刪除"<<endl;cout<<"ttt2.按元素刪除"<<endl;int d;cout<<"tt請(qǐng)選擇："cin>>d;switch(d)coutvv"ttt請(qǐng)輸入刪除位置:H.case 1:cin>>d;if (Li nkedL

24、istDel(L,d,y)cout<<"ttt"<<y<<"被刪除！ "<<endl;elsecoutvv"ttt刪除失??！ "<<e ndl;break;case 2:cout<<"ttt請(qǐng)輸入刪除元素："cin>>y;if (Li nkedListDel(L,y)cout<<"ttt"<<y<<" 被刪除！ "<<endl;coutvv&qu

25、ot;ttt刪除失??！ "<<e ndl;elsegetch();break;return 1;約瑟夫環(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)鏈表。接下來從

26、位置為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)鏈表struct Linkint Data;Link*n ext;；Link *Creat(i nt n)Link *head,*s,*r;head=new Link;r=head;for (i nt i=0;i vn ;i+)s=new Link;cin> >s->Data;r->n ext=s;r=s;r->n ext=head->n ext;retur n head;（二）“約瑟夫環(huán)”的操作模塊;Link* Jose(L ink*p ,i nt m)int s=m;if (p=p->n ext)return p;/遞歸出口即循環(huán)鏈表只剩下一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)指針返回Link*q=NULL;/指針q用來保存刪除結(jié)點(diǎn)的前驅(qū)for (i nt j=1;jvs;j+)q=p;p=p-&