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

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

2、.從鏈表中查找元素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è)計一個程序模擬此過程， 求出出列編號序列。struct node/結(jié)點結(jié)構(gòu)int number; /* 人的序號

3、 */ int cipher; /* 密碼 */;三、實驗步驟（一）數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計描述1、單鏈表的結(jié)點類型定義/*預(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é)點類型*/ typ edef struct LNodeDataT ype data; struct LNode *n ext;LNode,*L in kedList;2、初始化單鏈表Lin

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

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

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

7、或非1-8的字符，程序結(jié)束.(四) 實驗總結(jié)通過這次實驗，我對線性鏈表有了更深的理解，深入明白了線性存儲結(jié)構(gòu)與 鏈?zhǔn)酱鎯Y(jié)構(gòu)在內(nèi)存存儲的不同特點，同時我還學(xué)會了用這些知識實際解決一些 問題，能夠更加熟練地將算法轉(zhuǎn)化為實際程序。 同時，在寫程序和調(diào)試程序的過 程中，學(xué)會了一些書寫技巧和調(diào)試技巧，這對于自己能在短時間高效的寫出正確 地程序有很大作用。四、主要算法流程圖及程序清單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é)點類型*/ typ edef struct LNodeint data;struct LNode *n ext;LNode,*L in kedList;/*初始化單鏈表*/Lin kedList Lin kedList In it()/定義并返回頭結(jié)點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é)點外的所有內(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é)點的next是否為空，如果空返回OK，否則返回ERRORif (!(L-> next)return OK;

10、return ERROR;/*遍歷單鏈表*/ void Lin kedListTraverse(L in kedList L)/遍歷并輸出L所有結(jié)點（不含頭結(jié)點）的數(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;/*求單鏈表的長度*/intLin kedListLe ngth(L in kedLi

11、st L)/通過遍歷鏈表用i記錄結(jié)點個數(shù)（不含頭結(jié)點），并返回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é)點的鏈表的頭指針，返回第i個元素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é)點的鏈表的頭指針，返回值為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é)點的鏈表的頭指針，返回值為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é)點的單鏈表的頭指針，本算法/在鏈表中第i個結(jié)點之前插入新的元素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é)點

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個結(jié)點，并返回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.求鏈表長度"<<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();/進行選擇，當(dāng)選擇為1-8時，進行對應(yīng)功能函數(shù)調(diào)用，否則退出程序while(i>=1

19、 &&i <=8)cout<<"tt"<<"請選擇："cin> >i;switch (i)/1、清空鏈表case 1:Li nkedListClear(L);break;112.求鏈表長度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請輸入要查詢的位置i:"int j;cin>>j;if (Li nkedListGet(L,j)cout<<"ttt的元素值為"<<Li nkedListGet(L,j)->datavve n

21、dl;elsecout<<"ttti大于鏈表長度!"<<e ndl;getchO;break;116.從鏈表中查找與給定元素值相同的元素在表中的位置case 6:coutvv"ttt請輸入要查找的元素值："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請輸入要插入的值："i nt x; cin >>x;/7.向鏈表中插入元素case 7:cout<<"ttt請輸入要插入的位置："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請選擇："cin>>d;switch(d)coutvv"ttt請輸入刪除位置: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請輸入刪除元素："cin>>y;if (Li nkedListDel(L,y)cout<<"ttt"<<y<<" 被刪除！ "<<endl;coutvv&qu

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

26、位置為1的結(jié)點開始數(shù)，數(shù)到第 m個結(jié)點，就將此結(jié)點從循環(huán)鏈表中刪去,然后再從刪去結(jié)點的下一個結(jié)點開始數(shù)起，數(shù)到第m個結(jié)點，再將其刪去，如此進行下去，直至全部刪去為止。代碼分析（一）創(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)鏈表只剩下一個結(jié)點，將該結(jié)點指針返回Link*q=NULL;/指針q用來保存刪除結(jié)點的前驅(qū)for (i nt j=1;jvs;j+)q=p;p=p-&