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

1、實(shí)驗(yàn) 一 線性表的基本操作實(shí)現(xiàn)及其應(yīng)用一、實(shí)驗(yàn)?zāi)康?、熟練掌握線性表的基本操作在兩種存儲結(jié)構(gòu)上的實(shí)現(xiàn)。2、會用線性鏈表解決簡單的實(shí)際問題。二、實(shí)驗(yàn)內(nèi)容 題目一、該程序的功能是實(shí)現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。其中，程序中的單鏈表（帶頭結(jié)點(diǎn)）結(jié)點(diǎn)為結(jié)構(gòu)類型，結(jié)點(diǎn)值為整型。單鏈表操作的選擇以菜單形式出現(xiàn)，如下所示：please input the operation： 1.初始化 2.清空 3.求鏈表長度 4.檢查鏈表是否為空 5.檢查鏈表是否為滿 6.遍歷鏈表（設(shè)為輸出元素）7.從鏈表中查找元素 8.從鏈表中查找與給定元素值相同的元素在表中

2、的位置 9.向鏈表中插入元素 10. 從鏈表中刪除元素 其他鍵退出。 其中黑體部分必做題目二、約瑟夫環(huán)問題：設(shè)編號為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è)程序模擬此過程，求出出列編號序列。struct node /結(jié)點(diǎn)結(jié)構(gòu) int number; /* 人的序號 */ int cipher; /* 密碼 */ struct

3、 node *next; /* 指向下一個(gè)節(jié)點(diǎn)的指針 */;三、實(shí)驗(yàn)步驟(一) 數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、單鏈表的結(jié)點(diǎn)類型定義/* 預(yù)處理命令 */#define OK 1;#define ERROR 0;#define OVERFLOW -1;/* 定義DataType,status為int類型 */typedef int DataType;typedef int status;/* 單鏈表的結(jié)點(diǎn)類型 */typedef struct LNodeDataType data;struct LNode *next;LNode,*LinkedList;2、初始化單鏈表LinkedList L

4、inkedListInit() /定義并返回頭結(jié)點(diǎn)L3、清空單鏈表 void LinkedListClear(LinkedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針,釋放除頭結(jié)點(diǎn)外的所有內(nèi)存空間4檢查單鏈表是否為空int LinkedListEmpty(LinkedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針,判斷頭結(jié)點(diǎn)的next是否為空,如果空/返回OK，否則返回ERROR5、 遍歷單鏈表void LinkedListTraverse(LinkedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針,遍歷并輸出L所有結(jié)點(diǎn)（不包括頭/結(jié)點(diǎn)）的數(shù)據(jù)6、求單鏈表的長度int LinkedListLeng

5、th(LinkedList L)/ L是帶頭結(jié)點(diǎn)的鏈表的頭指針，通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不/包括頭結(jié)點(diǎn)），并返回i7、從單鏈表表中查找元素LinkedList LinkedListGet(LinkedList L,int i)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回第 i 個(gè)元素8、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（位置） int LinkedListGet1(LinkedList L,DataType x)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素在鏈表中的位置的/位置9、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置（指針）LinkedList LinkedLi

6、stLocate(LinkedList L, DataType x)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的指針10、 向單鏈表中插入元素 status LinkedListInsert(LinkedList L,int i,DataType x)(二) 函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)Main函數(shù)初始化鏈表調(diào)用菜單函數(shù)1.清空2.求鏈表長度3.檢查鏈表是否為空4.遍歷鏈表5. 按位置查找元素6.按值查找元素7.向鏈表中插入元素8.從鏈表中刪除元素9.退出等待選擇，等輸入1-9時(shí)，調(diào)用對應(yīng)函數(shù)，否則退出程序結(jié)束輸入1-9輸入非1-9圖1.主函數(shù)流程圖(三) 程序調(diào)試及運(yùn)行結(jié)果分析1進(jìn)入選擇界面后，先

7、選擇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é)束.(四) 實(shí)驗(yàn)總結(jié) 通過這次實(shí)驗(yàn)，我對線性鏈表有了更深的理解，深入明白了線性存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)在內(nèi)存存儲的不同特點(diǎn)，同時(shí)我還學(xué)會了用這些知識實(shí)際解決一些問題，能夠更加熟練地將算法轉(zhuǎn)化為實(shí)際程序。同時(shí)，在寫程序和調(diào)試程序的過程中，學(xué)會了一些書寫技巧和調(diào)試技巧，這對于自己能在短時(shí)間高效的寫出正確地程序有很大作用。四、主要算法流程圖及程序清單1. 主要算法流程圖：(1) 從單鏈表

8、表中查找與給定元素值相同的元素在鏈表中的位置p=p->nextp&&!(p->data=x)true調(diào)用函數(shù)，傳入?yún)?shù)L，xp=L->nextfalse返回p調(diào)用函數(shù)，傳入?yún)?shù)L，i，x建立新結(jié)點(diǎn)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不為空返

9、回對應(yīng)值FalseFalse2. 程序清單：#include<iostream>using namespace std;#include<conio.h>#include<stdlib.h>/* 預(yù)處理命令 */#define OK 1;#define ERROR 0;#define OVERFLOW -1; /* 單鏈表的結(jié)點(diǎn)類型 */typedef struct LNodeint data;struct LNode *next;LNode,*LinkedList;/*初始化單鏈表*/LinkedList LinkedListInit()/定義并返回頭結(jié)點(diǎn)

10、LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;/*清空單鏈表*/void LinkedListClear(LinkedList L)/釋放除頭結(jié)點(diǎn)外的所有內(nèi)存空間LinkedList p=L->next,q;L->next=NULL;while (p)q=p->next;free(p);p=q;cout<<"ttt已清空！"<<endl;/*檢查單鏈表是否為空*/int LinkedListEmpty(LinkedList L)/判斷

11、頭結(jié)點(diǎn)的next是否為空,如果空返回OK，否則返回ERRORif (!(L->next)return OK;return ERROR;/*遍歷單鏈表*/void LinkedListTraverse(LinkedList L)/遍歷并輸出L所有結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的數(shù)據(jù)LinkedList p=L->next;if (!p)cout<<"ttt鏈表為空！"<<endl;cout<<"tt"while(p)cout<<p->data<<"t"p=p->ne

12、xt;cout<<endl;/*求單鏈表的長度*/int LinkedListLength(LinkedList L)/通過遍歷鏈表用i記錄結(jié)點(diǎn)個(gè)數(shù)（不含頭結(jié)點(diǎn)），并返回iLinkedList p=L->next;int i=0;while(p)i+;p=p->next;return i;/*從單鏈表表中查找元素*/LinkedList LinkedListGet(LinkedList L,int i)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回第 i 個(gè)元素LinkedList p=L->next;int j=1;while(j<i&&p)p=p-&

13、gt;next;j+;if (!p)return NULL;return p;/*從鏈表中查找與給定元素值相同的元素在表中的位置,返回位置*/int LinkedListGet1(LinkedList L,int x)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的位置LinkedList p=L->next;int i=1;while(p&&!(p->data=x)i+;p=p->next;if (!p)return 0;return i;/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/LinkedList LinkedListLocate(Lin

14、kedList L, int x)/L是帶頭結(jié)點(diǎn)的鏈表的頭指針,返回值為x元素的指針LinkedList p=L->next;while(p&&!(p->data=x)p=p->next;if (!p)return NULL;return p;/*向單鏈表中插入元素*/int LinkedListInsert(LinkedList L,int i,int x)/ L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法/ 在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素 xLinkedList s=(LinkedList)malloc(sizeof(LNode);s->data=x;

15、LinkedList p=L->next,q;if (i=1)if (p=NULL)L->next=s;s->next=NULL;return OK;elseL->next=s;s->next=p;return OK;int j=1;while(j<i-1&&p)p=p->next;j+;if (!p)free(s);return ERROR;q=p->next;p->next=s;s->next=q;return OK;/*從單鏈表中刪除元素*/int LinkedListDel(LinkedList L,int x

16、)/刪除以 L 為頭指針的單鏈表中值為x結(jié)點(diǎn)LinkedList p=L->next,q=L;while(p&&!(p->data=x)q=p;p=p->next;if (!p)return ERROR;q->next=p->next;free(p);return OK;int LinkedListDel(LinkedList L,int i,int &x)/刪除以 L 為頭指針的單鏈表中第 i 個(gè)結(jié)點(diǎn),并返回x的值LinkedList p=L->next,q=L;int j=1;while(j<=i-1&&p)

17、q=p;p=p->next;j+;if (!p)x=0;return ERROR;q->next=p->next;x=p->data;free(p);return OK;/*菜單顯示*/void ScreenShow()cout<<"ttt"<<"1.清空"<<endl;cout<<"ttt"<<"2.求鏈表長度"<<endl;cout<<"ttt"<<"3.檢查鏈表

18、是否為空"<<endl;cout<<"ttt"<<"4.遍歷鏈表"<<endl;cout<<"ttt"<<"5.從鏈表中查找元素 "<<endl;cout<<"ttt"<<"6.從鏈表中查找與給定元素值相同的元素在表中的位置"<<endl;cout<<"ttt"<<"7.向鏈表中插入元素&quo

19、t;<<endl;cout<<"ttt"<<"8.從鏈表中刪除元素"<<endl;cout<<"ttt"<<"9.退出"<<endl;/*主函數(shù)*/int main()/初始化鏈表int i=1;LinkedList L=LinkedListInit();if (L)cout<<"ttt初始化成功！n"<<endl;/顯示菜單ScreenShow();/進(jìn)行選擇，當(dāng)選擇為1-8時(shí)，進(jìn)行對應(yīng)

20、功能函數(shù)調(diào)用，否則退出程序while(i>=1&&i<=8)cout<<"tt"<<"請選擇："cin>>i;switch (i)/1、清空鏈表case 1:LinkedListClear(L);break;/2.求鏈表長度case 2:cout<<"ttt鏈表長度為："<<LinkedListLength(L)<<endl;getch(); break;/3.檢查鏈表是否為空case 3:if (!LinkedListEmpty(L)

21、cout<<"ttt鏈表不為空！"<<endl;elsecout<<"ttt鏈表為空！"<<endl;getch(); break;/4.遍歷鏈表case 4:LinkedListTraverse(L);getch(); break;/5.從鏈表中查找元素case 5:cout<<"ttt請輸入要查詢的位置i："int j;cin>>j;if (LinkedListGet(L,j)cout<<"ttt位置i的元素值為："<&l

22、t;LinkedListGet(L,j)->data<<endl;elsecout<<"ttti大于鏈表長度！"<<endl;getch(); break;/6.從鏈表中查找與給定元素值相同的元素在表中的位置case 6:cout<<"ttt請輸入要查找的元素值："int b;cin>>b;if (LinkedListGet1(L,b)cout<<"ttt要查找的元素值位置為："<<LinkedListGet1(L,b)<<endl;

23、cout<<"ttt要查找的元素值內(nèi)存地址為："<<LinkedListLocate(L,b)<<endl;elsecout<<"ttt該值不存在！"<<endl;getch(); break;/7.向鏈表中插入元素case 7:cout<<"ttt請輸入要插入的值："int x; cin>>x;cout<<"ttt請輸入要插入的位置："int k; cin>>k;if(LinkedListInsert(L,

24、k,x)cout<<"ttt插入成功！"<<endl;elsecout<<"ttt插入失?。?quot;<<endl;getch(); break;/8.從鏈表中刪除元素case 8:cout<<"ttt1.按位置刪除"<<endl;cout<<"ttt2.按元素刪除"<<endl;int d;cout<<"tt請選擇："cin>>d;switch(d)case 1:cout<&l

25、t;"ttt請輸入刪除位置："cin>>d;int y;if (LinkedListDel(L,d,y)cout<<"ttt"<<y<<"被刪除！"<<endl;elsecout<<"ttt刪除失??！"<<endl; break;case 2:cout<<"ttt請輸入刪除元素："int y;cin>>y;if (LinkedListDel(L,y)cout<<"tt

26、t"<<y<<"被刪除！"<<endl;elsecout<<"ttt刪除失敗！"<<endl; getch(); break;return 1;題二 約瑟夫環(huán)問題算法、思想為了解決這一問題，可以先定義一個(gè)長度為30（人數(shù)）的數(shù)組作為線性存儲結(jié)構(gòu)，并把該數(shù)組看成是一個(gè)首尾相接的環(huán)形結(jié)構(gòu)，那么每次報(bào)m的人，就要在該數(shù)組的相應(yīng)位置做一個(gè)刪除標(biāo)記，該單元以后就不再作為計(jì)數(shù)單元。這樣做不僅算法較復(fù)雜，而且效率低，還要移動大量的元素。用單循環(huán)鏈表來解決這一問題，實(shí)現(xiàn)的方法相對要簡單得的多。首先定義

27、鏈表結(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)鏈表中刪去，然后再從刪去結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始數(shù)起，數(shù)到第m個(gè)結(jié)點(diǎn)，再將其刪去，如此進(jìn)行下去，直至全部刪去為止。代碼分析(一) 創(chuàng)建單循環(huán)鏈表 struct Link int Data;Link*next; Link *Creat(int n) Link *head,*s,*r; head=new Link; r=head; for (int i=0;i<n;i+) s=new Link; cin>>s->Data; r->next=s; r=s; r->next=head->next; return head; (二) “約瑟夫環(huán)”的操作模塊；Link* Jose(Link*p,int m) int s=m; if (p=p->next) return p;/遞歸出口即循環(huán)鏈表只剩下一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)指針返回 Link*q=NULL;/指針q用來保存刪除結(jié)點(diǎn)的前驅(qū) for (int j=1;j<s;j+) q=p; p=p->next; /查找要?jiǎng)h除