1、題目一 鏈表基本操作一、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述1、單鏈表的最大長度#define MAXSIZE 1002、單鏈表的結(jié)點(diǎn)類型定義/* 定義elemtype為int類型 */typedef int elemtype;/* 單鏈表的結(jié)點(diǎn)類型 */typedef struct STDelemtype elem;STD *next;list, * linklist;3、初始化單鏈表/* 函數(shù)功能：對鏈表進(jìn)行初始化 。參數(shù)：鏈表(linklist L)。成功初始化返回1,否則返回0 */int init(linklist &L)L=(linklist)malloc(sizeof(list)

2、;/頭結(jié)點(diǎn)申請內(nèi)存。if(!L) /判斷有無申請到空間。return 0; /沒有申請到內(nèi)存,參數(shù)失敗返回0L->next=NULL;L->elem=0; /單鏈表中有多少元素 return 1; /成功參數(shù)返回14、清空單鏈表/* 函數(shù)功能：把鏈表清空 。參數(shù)：鏈表(linklist L)。成功清空鏈表返回1*/int makeempty(linklist &L)linklist p,q;p=L->next;while(p) /當(dāng)p非空時(shí)，刪除pq=p;p=p->next;free(q);L->next=NULL; /只剩頭指針，所以L->next

3、=NULLL->elem=0; /清空后鏈表中元素為0return 1; /清空后返回15、求鏈表長度 /*函數(shù)功能:返回鏈表的長度。 參數(shù);鏈表(linklist L)。 函數(shù)返回鏈表的長度 */int getlength(linklist L)linklist p;p=L->next;int j=0;while(p)j+; /統(tǒng)計(jì)鏈表中元素p=p->next;return j; /最后返回鏈表長度.6、判斷鏈表是否為空/*函數(shù)功能:判斷鏈表是否為空。參數(shù);鏈表(linklist L)。鏈表為空時(shí)返回0,不為空返回1*/int isempty(linklist L) if(

4、L->next) /頭結(jié)點(diǎn)后有元素表示鏈表不空則返回1 return 1; else return 0; /頭結(jié)點(diǎn)后沒有元素表示鏈表不空則返回07、檢查鏈表是否為滿/*函數(shù)功能:判斷鏈表是否為滿。參數(shù);鏈表(linklist L)。鏈表為滿時(shí)返回0,不為滿返回1*/int isfull(linklist L) if(L->elem <= MAXSIZE) /頭結(jié)點(diǎn)的elem儲(chǔ)存的為鏈表的長度。 return 1; /其小于MAXSIZE表示鏈表不滿 else return 0; /否則返回08、遍歷鏈表/*函數(shù)功能:遍歷鏈表,輸出每個(gè)節(jié)點(diǎn)的elem值。參數(shù);鏈表(linkli

5、st L)通過循環(huán)逐個(gè)輸出節(jié)點(diǎn)的elem值*/void show(linklist L) linklist p; p=L->next; if(isempty(L)=0) /當(dāng)鏈表為空時(shí)則輸出鏈表為空 cout<<"鏈表為空！" while(p) /當(dāng)鏈表為不空時(shí)則輸出鏈表每個(gè)節(jié)點(diǎn)的elem值 cout<<p->elem<<" " p=p->next; cout<<endl;9、從鏈表中查找元素/*函數(shù)功能: 從鏈表中查找有無給定元素。參數(shù);鏈表(linklist L),給定元素(int i

6、)如果鏈表中有給定元素(i)則返回1,否則返回0*/int find(linklist L, int i) linklist p; p=L->next; while(p) if(p->elem=i) /判斷有無元素I,有返回1 return 1; p=p->next; return 0; /沒有找到返回010、從鏈表中查找與給定元素值相同的元素在表中的位置/*函數(shù)功能: 從鏈表中查找給定元素的位置。參數(shù);鏈表(linklist L),給定元素(int i)如果鏈表中有給定元素i則返回元素的位置, 沒有則返回0*/int location(linklist L,int i) l

7、inklist p; int j=0; p=L->next; while(p) j+; if(p->elem=i) /判斷有無元素i,有返回其的位置j return j; p=p->next; return 0; /沒有則返回011、向鏈表中插入元素/*函數(shù)功能:向鏈表中的某個(gè)位置插入元素。參數(shù);鏈表(linklist L),位置(int i),元素(elemtype e)。成功插入返回1,否則返回0 */int insert(linklist &L, int i, elemtype e) linklist p, s; int j = 0; p = L; while

8、(p&&j<i-1) /查找第i個(gè)元素的前驅(qū) p = p->next; j +; if(j>i-1|!p) /不符合條件返回0 return 0; s = (linklist)malloc(sizeof(list); /給節(jié)點(diǎn)s分配內(nèi)存 s->elem = e; s->next = p->next; /插入操作 p->next = s; L->elem+; /插入完成后頭結(jié)點(diǎn)的elem加1 return 1; /成功插入返回112、從鏈表中刪除元素/*函數(shù)功能:在鏈表中的某個(gè)位置刪除元素。參數(shù);鏈表(linklist L),位置(

9、int i),元素(elemtype e)。成功刪除返回1,否則返回0 */int deleteelem(linklist &L,int i)linklist p,q;int j=0;p=L;while (p->next&&j<i-1) /查找第i個(gè)元素的前驅(qū)p=p->next;j+;if(j>i-1|!(p->next) /不符合條件返回0return 0;q=p->next;p->next=q->next; /刪除操作free(q);L->elem-; /插入完成后頭結(jié)點(diǎn)的elem減1return 1; /成功刪

10、除返回113、主界面函數(shù)/* 函數(shù)功能:顯示所有操作功能。參數(shù);無*/void zhujiemian()cout<<endl<<endl;cout<<"tttt數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一"<<endl;cout<<"tt-"<<endl<<endl;cout<<"tt 1 鏈表初始化"<<endl;cout<<"tt 2 清空鏈表"<<endl;cout<<"tt 3 求鏈表

11、長度"<<endl;cout<<"tt 4 鏈表是否為空"<<endl;cout<<"tt 5 檢查鏈表是否為滿"<<endl;cout<<"tt 6 遍歷鏈表"<<endl;cout<<"tt 7 從鏈表中查找元素"<<endl;cout<<"tt 8 從鏈表中查找與給定元素值相同的元素在表中的位置"<<endl;cout<<"tt

12、 9 向鏈表中插入元素"<<endl;cout<<"tt10 從鏈表中刪除元素"<<endl<<endl;cout<<"tt其他鍵退出"<<endl;cout<<"tt-"<<endl<<endl<<endl;cout<<"t請選擇要進(jìn)行操作的序號(hào)（1-10）:"二、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)主函數(shù)主要設(shè)計(jì)：zhujiemian(); /顯示主界面cin>>a; /輸入

13、要進(jìn)行的操作的序號(hào)cout<<endl;doswitch(a) /用switch語句進(jìn)行選擇操作case 1: /初始化if(init(L)=1)cout<<"初始化成功！"<<endl;elsecout<<"初始化失?。?quot;<<endl;break;case 2:if(makeempty(L)=1) /鏈表置空cout<<"鏈表已清空！"<<endl;elsecout<<"鏈表清空失??！"<<endl;bre

14、ak;case 3: /鏈表的長度b=getlength(L);cout<<"鏈表的長度為："<<b<<endl;break;case 4: /判斷鏈表是否空if(isempty(L)=1)cout<<"鏈表不空！"<<endl;elsecout<<"鏈表為空！"<<endl;break;case 5: /判斷鏈表是否滿if(isfull(L)=1)cout<<"鏈表不滿！"<<endl;elsecout&l

15、t;<"鏈表已滿！"<<endl;break;case 6: /遍歷鏈表show(L);break;case 7: /鏈表是否有要查找元素cout<<"您要查找的元素："cin>>b;if(find(L,b)=1)cout<<"鏈表中有元素"<<b<<endl;elsecout<<"鏈表沒中有元素"<<b<<endl;break;case 8: /輸出鏈表要查找元素的位置cout<<&quo

16、t;您要查找的元素為："<<endl;cin>>b;if(location(L,b)=0)cout<<"沒有您要查找的元素"<<b<<endl;elsecout<<"您查找的元素"<<b<<"在第"<<location(L,b)<<"個(gè)位置。"<<endl;break;case 9:do cout<<"輸入你要插入的位置和元素"<<

17、endl;cin>>b>>c;while (b<=0|b>getlength(L)+1)/* 此處可以對錯(cuò)誤的輸入進(jìn)行判斷 */cout<<"插入位置錯(cuò)誤！請重新插入！"<<endl;cin>>b>>c;if(insert(L,b,c)=0)cout<<"您插入的位置不對，插入失??！"<<endl;elsecout<<"插入成功！"<<endl;cout<<"是否繼續(xù)插入元素(Y/y

18、繼續(xù)),其他鍵停止插入n"/提示是否繼續(xù)進(jìn)行插入操作cin>>YES; while(YES='Y'|YES='y');break;case 10:do if(getlength(L)=0)/判斷鏈表是否為空若是則輸出鏈表為空，并繼續(xù)cout<<"鏈表為空無法刪除！"<<endl;break;cout<<"輸入你要?jiǎng)h除元素的位置："<<endl;cin>>b;while(b<=0|b>getlength(L)/* 此處可以對錯(cuò)誤的輸

19、入進(jìn)行判斷 */cout<<"輸入錯(cuò)誤！請重新輸入！"<<endl;cin>>b;if(deleteelem(L,b)=0)cout<<"您刪除的位置不對，刪除失??！"<<endl;elsecout<<"刪除成功！"<<endl;cout<<"是否繼續(xù)刪除元素(Y/y繼續(xù)),其他鍵停止刪除n"/提示是否繼續(xù)進(jìn)行刪除操作cin>>YES; while(YES='Y'|YES='y'

20、;);break;default:break;system("pause");/按任意鍵繼續(xù)system("cls");/清理屏幕上的內(nèi)容zhujiemian();/顯示主界面cin>>a; /輸入要進(jìn)行操作的序號(hào)cout<<endl;while(a>0&&a<=10);/對進(jìn)行輸入的數(shù)進(jìn)行判斷(不在09則程序結(jié)束)說明：通過調(diào)用序列號(hào)不同的函數(shù)進(jìn)行各種操作。函數(shù)根據(jù)每次輸入的數(shù)進(jìn)行判斷不在110內(nèi)的函數(shù)將結(jié)束，否則將繼續(xù)進(jìn)行。三、程序調(diào)試及運(yùn)行結(jié)果分析程序第一步必須執(zhí)行初始化，否則程序不能運(yùn)行。在程序

21、第一步必須執(zhí)行初始化后，程序完美運(yùn)行，在進(jìn)行任何函數(shù)操作程序都是正常運(yùn)行，而且本程序?qū)Σ迦牒蛣h除時(shí)進(jìn)行錯(cuò)誤檢測如有的地方不可以插入，有點(diǎn)地方不能刪除，如果鏈表為空時(shí)則程序會(huì)輸出鏈表為空，并繼續(xù)進(jìn)行其他操作，大大減少了程序的bug。四、實(shí)驗(yàn)總結(jié)通過這次試驗(yàn)我熟悉了對鏈表的基本操作，對基本的鏈表操作有了很好的掌握，知道自己容易在什么地方出錯(cuò)。五、程序清單/實(shí)驗(yàn)一_1.h#include "iostream"#include "malloc.h"#include "stdlib.h"using namespace std;#define M

22、AXSIZE 100 /鏈表的最大長度typedef int elemtype;typedef struct STDelemtype elem;STD *next;list, * linklist;void zhujiemian() cout<<endl<<endl;cout<<"【*數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一*】"<<endl; cout<<"【*】"<<endl<<endl;cout<<"【1 鏈表初始化】"<<endl; cout&l

23、t;<"【2清空鏈表】"<<endl; cout<<"【3求鏈表長度】"<<endl;cout<<"【4鏈表是否為空】"<<endl;cout<<"【5檢查鏈表是否為滿】"<<endl; cout<<"【6遍歷鏈表】"<<endl;cout<<"【7從鏈表中查找元素】"<<endl;cout<<"【8 從鏈表中查找與給

24、定元素值相同的元素在表中的位置】"<<endl;cout<<"【9向鏈表中插入元素】"<<endl;cout<<"【10從鏈表中刪除元素】"<<endl;cout<<"【其他鍵退出】"<<endl;cout<<【*】"<<endl<<endl;cout<<"【*請選擇要進(jìn)行操作的序號(hào)（1-10）:*】"<<endl;int init(linklist &

25、amp;L)L=(linklist)malloc(sizeof(list);if(!L)return 0;L->next=NULL;L->elem=0;return 1;int insert(linklist &L, int i, elemtype e)linklist p, s;int j = 0;p = L;while (p&&j<i-1)p = p->next;j +;if(j>i-1|!p)return 0;s = (linklist)malloc(sizeof(list);s->elem = e;s->next = p

26、->next;p->next = s;L->elem+;return 1;int deleteelem(linklist &L,int i)linklist p,q;int j=0;p=L;while (p->next&&j<i-1)p=p->next;j+;if(j>i-1|!(p->next)return 0;q=p->next;p->next=q->next;free(q);L->elem-;return 1;int isempty(linklist L)if(L->next)retur

27、n 1;elsereturn 0;void show(linklist L)linklist p;p=L->next;if(isempty(L)=0)cout<<"鏈表為空！"while(p)cout<<p->elem<<" "p=p->next;cout<<endl;int getlength(linklist L)linklist p;p=L->next;int j=0;while(p)j+;p=p->next;return j;int makeempty(linklist

28、 &L)linklist p,q;p=L->next;while(p)q=p;p=p->next;free(q);L->next=NULL;L->elem=0;return 1;int find(linklist L, int i)linklist p;p=L->next;while(p)if(p->elem=i)return 1;p=p->next;return 0;int location(linklist L,int i)linklist p;int j=0;p=L->next;while(p)j+;if(p->elem=i)

29、return j;p=p->next;return 0;int isfull(linklist L)if(L->elem <= MAXSIZE)return 1;elsereturn 0;/main.cpp#include "iostream"#include "malloc.h"#include "stdlib.h"#include "實(shí)驗(yàn)一.h"using namespace std;int main()char YES;linklist L;int a,b,c;zhujiemian();ci

30、n>>a;cout<<endl;doswitch(a)case 1:if(init(L)=1)cout<<"初始化成功！"<<endl;elsecout<<"初始化失??！"<<endl;break;case 2:if(makeempty(L)=1)cout<<"鏈表已清空！"<<endl;elsecout<<"鏈表清空失?。?quot;<<endl;break;case 3:b=getlength(L);c

31、out<<"鏈表的長度為："<<b<<endl;break;case 4:if(isempty(L)=1)cout<<"鏈表不空！"<<endl;elsecout<<"鏈表為空！"<<endl;break;case 5:if(isfull(L)=1)cout<<"鏈表不滿！"<<endl;elsecout<<"鏈表已滿！"<<endl;break;case 6:sh

32、ow(L);break;case 7:cout<<"您要查找的元素："cin>>b;if(find(L,b)=1)cout<<"鏈表中有元素"<<b<<endl;elsecout<<"鏈表沒中有元素"<<b<<endl;break;case 8:cout<<"您要查找的元素為："<<endl;cin>>b;if(location(L,b)=0)cout<<"沒有您

33、要查找的元素"<<b<<endl;elsecout<<"您查找的元素"<<b<<"在第"<<location(L,b)<<"個(gè)位置。"<<endl;break;case 9:do cout<<"輸入你要插入的位置和元素"<<endl;cin>>b>>c;while (b<=0|b>getlength(L)+1)cout<<"插入位

34、置錯(cuò)誤！請重新插入！"<<endl;cin>>b>>c;if(insert(L,b,c)=0)cout<<"您插入的位置不對，插入失敗！"<<endl;elsecout<<"插入成功！"<<endl;cout<<"是否繼續(xù)插入元素(Y/y繼續(xù)),其他鍵停止插入n"cin>>YES; while(YES='Y'|YES='y');break;case 10:do if(getlength(

35、L)=0)cout<<"鏈表為空無法刪除！"<<endl;break;cout<<"輸入你要?jiǎng)h除元素的位置："<<endl;cin>>b;while(b<=0|b>getlength(L)cout<<"輸入錯(cuò)誤！請重新輸入！"<<endl;cin>>b;if(deleteelem(L,b)=0)cout<<"您刪除的位置不對，刪除失??！"<<endl;elsecout<<&

36、quot;刪除成功！"<<endl;cout<<"是否繼續(xù)刪除元素(Y/y繼續(xù)),其他鍵停止刪除n"cin>>YES; while(YES='Y'|YES='y');break;default:break;system("pause");system("cls");zhujiemian();cin>>a;cout<<endl;while(a>0&&a<=10);return 0;題目二 約瑟夫環(huán)問題一、循環(huán)

37、鏈表的結(jié)點(diǎn)類型定義/* 單鏈表的結(jié)點(diǎn)類型 */typedef struct nodeint number; /* 人的序號(hào) */int cipher; /* 密碼 */ struct node *next; /* 指向下一個(gè)節(jié)點(diǎn)的指針 */List, *ListLink;二、循環(huán)鏈表的初始化/* 函數(shù)功能:初始化n個(gè)元素的循環(huán)鏈表。參數(shù);鏈表(linklist L)，元素個(gè)數(shù)（int n）通過后插法對無頭結(jié)點(diǎn)的鏈表初始化。 */void InitList(ListLink &L,int n)int m,i;cout<<"輸入第1個(gè)人的密碼："cin>

38、;>m;L=new List;L->number=1;L->cipher=m;L->next=L;for(i=2;i<=n;i+)ListLink lpp;cout<<"輸入第"<<i<<"個(gè)人的密碼："cin>>m;lpp=new List;lpp->number=i;lpp->cipher=m;lpp->next=L->next;L->next=lpp;L=L->next;cout<<endl;L=L->next;三、循

39、環(huán)鏈表的長度/* 函數(shù)功能:求循環(huán)鏈表的長度。參數(shù);鏈表(linklist L) 通過各個(gè)掃描求循環(huán)鏈表長度 */int ListLength(ListLink L)ListLink lpp;if(L=NULL)cout<<"鏈表是空的."return 0;int i=1;lpp=L->next;while(lpp!=L)i+;lpp=lpp->next;return i;四、顯示循環(huán)鏈表/*函數(shù)功能:循環(huán)鏈表的顯示。參數(shù);鏈表(linklist L) 。通過各個(gè)掃描各個(gè)節(jié)點(diǎn)輸出各個(gè)節(jié)點(diǎn)的密碼 */void ListTraverse(ListLink

40、 L)ListLink lpp;lpp=L;int i=1;cout<<"輸入第1個(gè)人的密碼："<<lpp->cipher<<endl;lpp=lpp->next;while(lpp!=L)i+;cout<<"輸入第"<<i<<"個(gè)人的密碼："<<lpp->cipher<<endl;lpp=lpp->next;cout<<endl;五、約瑟夫環(huán)實(shí)現(xiàn)/*函數(shù)功能:實(shí)現(xiàn)所有人的出列次序。參數(shù);鏈表(linkl

41、ist L) ，密碼（int m）。每次要找到出列者的前驅(qū)，把出列者刪除 */void ListTraverse(ListLink L)ListLink lpp;lpp=L;int i=1;cout<<"輸入第1個(gè)人的密碼："<<lpp->cipher<<endl;lpp=lpp->next;while(lpp!=L)i+;cout<<"輸入第"<<i<<"個(gè)人的密碼："<<lpp->cipher<<endl;lpp=lp

42、p->next;cout<<endl;int ListLength(ListLink L)ListLink lpp;if(L=NULL)cout<<"鏈表是空的."return 0;int i=1;lpp=L->next;while(lpp!=L)i+;lpp=lpp->next;return i;void shixian(ListLink &L,int m)ListLink lpp=L;ListLink l; while(lpp->next!=L) lpp=lpp->next;for(int n=ListLen

43、gth(L);n>0;n-)cout<<"密碼為："<<m<<endl;cout<<"出列人的編號(hào)是："for(int i=1;i<=m%n-1;i+)lpp=lpp->next;cout<<lpp->next->number<<endl;m=lpp->next->cipher;l=lpp->next;lpp->next=l->next;delete l;函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)：int main()int m,n;ListLi

44、nk L;cout<<"輸入人數(shù)(一個(gè)大于0小于30的數(shù))和密碼(一個(gè)大于0的數(shù))："<<endl;cin>>n>>m;while(n<0|n>30|m<0)cout<<"輸入的數(shù)字不符合要求，請重新輸入："<<endl;cin>>n>>m;cout<<"請輸入"<<n<<"個(gè)人的密碼："<<endl;InitList(L,n);cout<<n

45、<<"個(gè)人的密碼分別為："<<endl;ListTraverse(L);cout<<n<<"個(gè)人的出列密碼和編號(hào)分別是："<<endl;shixian(L,m);return 0;總結(jié)：main函數(shù)先調(diào)用初始化循環(huán)鏈表的的函數(shù)void init(linklist &L,int n)，然后將循環(huán)鏈表輸出void show(linklist L)，最后調(diào)用可以使人出列的函數(shù)void Joseph(linklist &L,int m)。本程序可以很好地運(yùn)行，具有一定的除錯(cuò)能力，輸入數(shù)據(jù)

46、時(shí)可以對其進(jìn)行判斷，減少程序出現(xiàn)bug的可能性。通過對本實(shí)驗(yàn)的操作，我熟悉了循環(huán)鏈表的基本操作，而且對循環(huán)鏈表的基本操作有了很好的掌握。程序清單#include "iostream"#include "stdlib.h"using namespace std;typedef struct nodeint number; /* 人的序號(hào) */int cipher; /* 密碼 */ struct node *next; /* 指向下一個(gè)節(jié)點(diǎn)的指針 */List, *ListLink;void InitList(ListLink &L,int n)int m,i;cout<<"輸入第1個(gè)人的密碼："cin>>m;L=new List;L->number=1;L->ciphe