鏈表基本操作

1、題目一 鏈表基本操作、數據結構與核心算法的設計描述1、單鏈表的最大長度#define MAXSIZE 1002、單鏈表的結點類型定義/*定義elemtype 為int類型*/typedef int elemtype;/*單鏈表的結點類型*/typedef struct STDelemtype elem;STD *n ext;list, * lin klist;3、初始化單鏈表/*函數功能：對鏈表進行初始化。參數：鏈表(linklist L)。成功初始化返回1,否則返回0 */int in it(li nklist &L)L=(li nklist)malloc(sizeof(list);

2、頭結點申請內存。if(!L)II判斷有無申請到空間。return 0;II沒有申請到內存，參數失敗返回0L-> next=NULL;L->elem=0;II單鏈表中有多少元素return 1;II成功參數返回14、清空單鏈表1*II*函數功能：把鏈表清空。參數：鏈表(linklist L)。成功清空鏈表返回int makeempty(l in klist &L)lin klist p,q;p=L->n ext;while(p)II當p非空時，刪除pq=p;p=p->n ext;free(q);L-> next=NULL; L->elem=O;retu

3、rn 1;5、求鏈表長度/*函數功能：返回鏈表的長度。/只剩頭指針，所以 L->next=NULL/清空后鏈表中元素為0/清空后返回1參數;鏈表(linklist L)。函數返回鏈表的長度 */int getle ngth(li nklist L)lin klist p;p=L->n ext;int j=0;while(p)j+；/統(tǒng)計鏈表中元素return j;p=p->n ext;/最后返回鏈表長度判斷鏈表是否為空/*函數功能：判斷鏈表是否為空。參數；鏈表(linklist L)。鏈表為空時返回0,不為空返回1*/ in t isempty(l in klist L)if

4、(L->next)/頭結點后有元素表示鏈表不空則返回1return 1;elsereturn 0;/頭結點后沒有元素表示鏈表不空則返回07、檢查鏈表是否為滿/*函數功能：判斷鏈表是否為滿。參數；鏈表(linklist L)。鏈表為滿時返回0,不為滿返回1*/ in t isfull(li nklist L)if(L->elem <= MAXSIZE)/頭結點的elem儲存的為鏈表的長度。return 1;/其小于 MAXSIZE 表示鏈表不滿elsereturn 0;/否則返回08、遍歷鏈表/*函數功能：遍歷鏈表，輸出每個節(jié)點的elem值。參數；鏈表(linklist L)

5、通過循環(huán)逐個輸出節(jié)點的elem值*/void show(li nklist L)li nklist p;p=L->n ext;if(isempty(L)=0)/當鏈表為空時則輸出鏈表為空cout<<" 鏈表為空！"while(p)/當鏈表為不空時則輸出鏈表每個節(jié)點的elem值cout<<p->elem<<""p=p->n ext;cout<<e ndl;9、從鏈表中查找元素/*函數功能：從鏈表中查找有無給定元素。參數；鏈表(linklist L),給定元素(int i)如果鏈表中有給定元素

6、(i)則返回1,否則返回0*/int fin d(li nklist L, i nt i)li nklist p;p=L->n ext;while(p)return 1;p=p->n ext;return 0;/沒有找到返回010、從鏈表中查找與給定元素值相同的元素在表中的位置/*函數功能：從鏈表中查找給定元素的位置。參數;鏈表(linklist L),給定元素(int i)如果鏈表中有給定元素i則返回元素的位置，沒有則返回0*/in t locati on( li nklist L,i nt i)li nklist p;int j=0;p=L->n ext;while(p)

7、j+；if(p->elem=i) /判斷有無元素i,有返回其的位置jreturn j;p=p->n ext;return 0;/沒有則返回011、向鏈表中插入元素/*函數功能：向鏈表中的某個位置插入元素。參數；鏈表(linklistL),位置(int i),元素(elemtypee)。成功插入返回1,否則返回0 */int in sert(l in klist &L, int i, elemtype e)lin klist p, s;int j = 0;p = L;while (p&&j<i-1)/查找第i個元素的前驅p = p_>n ext;j

8、 +;if(j>i-1|!p)/不符合條件返回0return 0;s = (linklist)malloc(sizeof(list);/ 給節(jié)點 s 分配內存/插入操作/插入完成后頭結點的elem加1/成功插入返回1s->elem = e; s->next = p->n ext; p_>n ext = s;L_>elem+; return 1;12、從鏈表中刪除元素i),元素 (elemtype/*函數功能：在鏈表中的某個位置刪除元素。參數；鏈表(linklist L),位置(inte)。成功刪除返回1,否則返回0 */int deleteelem(li n

9、klist & L,i nt i)lin klist p,q;int j=0;p=L;while (p-> next&&j<i-1)p=p->n ext;j+;if( j>i-1|!(p->next)return 0;q=p->n ext;p_>n ext=q _>n ext;free(q);L->elem-;return 1;13、主界面函數/查找第i個元素的前驅/不符合條件返回0/刪除操作/插入完成后頭結點的elem減1/成功刪除返回1/*函數功能：顯示所有操作功能。參數；無*/ void zhujiemia n

10、()cout<<e ndl<<e ndl;cout<<"tttt數據結構實驗一 "<<endl;cout<<"tt"<<e ndl<<e ndl;cout<<"tt 1鏈表初始化"<<endl;cout<<"tt 2清空鏈表"<<endl;cout<<"tt 3求鏈表長度"<<endl;cout<<"tt 4鏈表是否為空

11、"<<endl;cout<<"tt 5檢查鏈表是否為滿"<<e ndl;cout<<"tt 6遍歷鏈表"<<endl;cout<<"tt 7從鏈表中查找元素"<<e ndl;cout<<"tt 8從鏈表中查找與給定元素值相同的元素在表中的位置"<<e ndl;cout<<"tt 9向鏈表中插入元素"<<e ndl;cout<<"tt1

12、0從鏈表中刪除元素"<<e ndl<<e ndl;cout<<"tt 其他鍵退出"<<endl;cout<<"tt"<<e ndl<<e ndl<<e ndl;cout<<"t請選擇要進行操作的序號(1-10 ):"二、函數調用及主函數設計主函數主要設計：zhujiemian();/顯示主界面cin>>a;/輸入要進行的操作的序號cout<<e ndl;doswitch(a)/用switch語句

13、進行選擇操作case 1:/初始化if(i nit(L)=1)cout<<"初始化成功！"<<e ndl;elsecout<<"初始化失敗！"<<e ndl;break;case 2:if(makeempty(L)=1)/ 鏈表置空cout<<"鏈表已清空！"<<e ndl;elsecout<<" 鏈表清空失?。?quot;<<e ndl;break;case 3:/鏈表的長度b=getle ngth(L);cout<<

14、;"鏈表的長度為："<<b<<e ndl; break;case 4:/判斷鏈表是否空if(isempty(L)=1)cout<<"鏈表不空！"<<e ndl;elsecout<<"鏈表為空！"<<e ndl;break;case 5:/判斷鏈表是否滿if(isfull(L)=1)cout<<"鏈表不滿！"<<e ndl;elsecout<<"鏈表已滿！"<<e ndl;bre

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

16、gt; >b;if(locatio n(L,b)=O)cout<<" 沒有您要查找的元素"<<b<<e ndl;個位置。elsecout<<" 您查找 的元素"<<b<<" 在第"<<location(L,b)<<""<<e ndl;break;case 9:do cout<<"輸入你要插入的位置和元素"<<e ndl;cin> >b»c

17、;while (b<=0|b>getle ngth(L)+1)/*此處可以對錯誤的輸入進行判斷*/cout<<"插入位置錯誤！請重新插入！"<<e ndl;cin> >b»c;if(i nsert(L,b,c)=O)cout<<"您插入的位置不對，插入失?。?quot;<<e ndl;elsecout<<"插入成功！ "<<e ndl;提示是否繼續(xù)cout<<"是否繼續(xù)插入元素(Y/y繼續(xù)),其他鍵停止插入n"

18、;進行插入操作ci n»YES; while(YES='Y'|YES='y');break;case 10:do if(getle ngth(L)=O)/判斷鏈表是否為空若是則輸出鏈表為空，并繼續(xù)cout<<" 鏈表為空無法刪除！"<<e ndl;break;cout<<"輸入你要刪除元素的位置："<<e ndl;cin> >b;while(b<=O|b>getle ngth(L)/*此處可以對錯誤的輸入進行判斷*/cout<<&

19、quot; 輸入錯誤！請重新輸入！"<<e ndl;cin> >b;if(deleteelem(L,b)=O)cout<<"您刪除的位置不對，刪除失敗！"<<e ndl;elsecout<<"刪除成功！ "<<e ndl;cout<<"是否繼續(xù)刪除元素(Y/y繼續(xù)),其他鍵停止刪除n"提示是否繼續(xù) 進行刪除操作ci n»YES; while(YES='Y'|YES='y');break;default

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

21、完美運行，在進行任何函數操作程序都是正常運行， 而且本程序對插入和刪除時進行錯誤檢測如有的地方不可以插入，有點地方不能刪除，如果鏈表 為空時則程序會輸出鏈表為空，并繼續(xù)進行其他操作，大大減少了程序的bug。四、實驗總結通過這次試驗我熟悉了對鏈表的基本操作，對基本的鏈表操作有了很好的掌握，知道自己容 易在什么地方出錯。五、程序清單/ 實驗一 _1.h#i nclude "iostream"#i nclude "malloc.h"#in elude "stdlib.h"using n amespace std;#defi ne MAXSI

22、ZE 100/鏈表的最大長度typedef int elemtype;typedef struct STDelemtype elem;STD *n ext;list, * lin klist;void zhujiemia n()cout<<e ndl<<e ndl;cout<<"*數據纟結構實驗- *】"<<endl;cout<<"*】"<<endl<<endl;cout<<"【1鏈表初始化】"<<e ndl;cout<&

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

24、素在表中的位置】"<<e ndl;cout<<"【9向鏈表中插入元素"<<endl;cout<<"【10從鏈表中刪除元素"<<endl;cout<<"【其他鍵退出】"<<e ndl;cout<<*"<<endl<<endl;cout<<"【*請選擇要進行操作的序號1-10) :*"<<endl;int in it(li nklist &L)L=(

25、l in klist)malloc(sizeof(list); if(!L)return 0;L-> next=NULL;L->elem=0;return 1;int in sert(l in klist &L, int i, elemtype e)lin klist p, s;int j = 0;p = L;while (p&&j<i-1)p = p_>n ext;j +;if( j>i-1|!p)return 0;s = (li nklist)malloc(sizeof(list); s->elem = e;s->next

26、= p->n ext;p_>n ext = s;L_>elem+;return 1;int deleteelem(li nklist & L,i nt i)lin klist p,q;int j=0;p=L;while (p-> next&&j<i-1)p=p->n ext;j+；if( j>i-1|!(P->next)return 0;q=p->n ext;p_>n ext=q _>n ext; free(q);L->elem-;return 1;int isempty(li nklist L)i

27、f(L-> next)return 1;elsereturn 0;void show(l in klist L)li nklist p;p=L->n ext; if(isempty(L)=O) cout<<" 鏈表為空!while(p)cout<<p->elem<<" p=p->n ext;cout<<e ndl;int getle ngth(li nklist L)li nklist p;p=L->n ext;int j=0;while(p)j+；p=p->n ext;return j;i

28、nt makeempty(l in klist &L)lin klist p,q;p=L->n ext;while(p)q=p;p=p->n ext; free(q);L-> next=NULL;L->elem=0;return 1;int fin d(li nklist L, i nt i)li nklist p;p=L->n ext; while(p)if(p->elem=i)return 1;p=p->n ext;return 0;int locati on( li nklist L,i nt i)li nklist p;int j=0;

29、p=L->n ext;while(p)j+； if(p_>elem=i) return j;p=p->n ext;return 0;int isfull(li nklist L)if(L->elem <= MAXSIZE)return 1;elsereturn 0;mai n.cpp#i nclude "iostream"#i nclude "malloc.h"#i nclude "stdlib.h"#include "實驗一 .h"using n amespace std;int m

30、ai n()char YES;lin klist L;int a,b,c;zhujiemia n();cin> >a;cout<<e ndl;doswitch(a)case 1:if(i nit(L)=1)cout<<"初始化成功！"<<e ndl;elsecout<<"初始化失?。?quot;<<e ndl;break;case 2:if(makeempty(L)=1)cout<<"鏈表已清空！"<<e ndl;elsecout<<&q

31、uot; 鏈表清空失?。?quot;<<e ndl;break;case 3:b=getle ngth(L);cout<<"鏈表的長度為："<<b<<e ndl; break;case 4:if(isempty(L)=1)cout<<"鏈表不空！"<<e ndl;elsecout<<"鏈表為空！"<<e ndl;break;case 5:if(isfull(L)=1)cout<<"鏈表不滿！"<<

32、e ndl;cout<<"鏈表已滿！ "<<e ndl;break;case 6:show(L);break;case 7:cout<<" 您要查找的元素："cin> >b;if(fin d(L,b)=1)cout<<" 鏈表中有元素"<<b<<endl;elsecout<<" 鏈表沒中有元素"<<b<<endl;break;case 8:cout<<" 您要查找的元素為：&

33、quot;<<e ndl;cin> >b;if(locatio n(L,b)=O)cout<<" 沒有您要查找的元素 "<<b<<e ndl;else個位置。cout<<" 您查找 的元素"<<b<<" 在第"<<location(L,b)<<" "<<e ndl;break;case 9:do cout<<"輸入你要插入的位置和元素"<<e

34、 ndl;cin> >b»c;while (b<=O|b>getle ngth(L)+1)cout<<"插入位置錯誤！請重新插入！ "<<e ndl;cin> >b»c;if(i nsert(L,b,c)=O)cout<<"您插入的位置不對，插入失?。?quot;<<e ndl;cout<<"插入成功！ "<<e ndl;cout<<"是否繼續(xù)插入元素(Y/y繼續(xù)),其他鍵停止插入n"

35、ci n»YES; while(YES='Y'|YES='y');break;case 10:do if(getle ngth(L)=O)cout<<" 鏈表為空無法刪除！ "<<e ndl;break;cout<<"輸入你要刪除元素的位置："<<e ndl;cin> >b;while(b<=O|b>getle ngth(L)cout<<" 輸入錯誤！請重新輸入！"<<e ndl;cin> &

36、gt;b;if(deleteelem(L,b)=O)cout<<"您刪除的位置不對，刪除失敗！"<<e ndl;elsecout<<"刪除成功！ "<<e ndl;cout<<"是否繼續(xù)刪除元素(Y/y繼續(xù)),其他鍵停止刪除n"ci n»YES; while(YES='Y'|YES='y');break;default:break;system("pause");system("cls");zh

37、ujiemia n();cin> >a;cout<<e ndl;while(a>0&&a<=10);return 0;題目二約瑟夫環(huán)問題一、循環(huán)鏈表的結點類型定義/*單鏈表的結點類型 */typedef struct node/*人的序號*/*密碼*/*指向下一個節(jié)點的指針 */int nu mber;int cipher; struct node *n ext;List, *ListLi nk;二、循環(huán)鏈表的初始化int n )/*函數功能：初始化n個元素的循環(huán)鏈表。參數;鏈表(linklist L)，元素個數( 通過后插法對無頭結點的鏈表

38、初始化。*/void In itList(ListLi nk & L,i nt n)int m,i;cout<<"輸入第1個人的密碼："cin»m;L=new List;L->nu mber=1;L->cipher=m;L->n ext=L;for(i=2;i<=n ;i+)ListL ink lpp;cout<<" 輸入第"<<i<<" 個人的密碼："cin»m;lpp=new List; lpp->nu mber=i;Ipp_

39、>cipher=m;Ipp->n ext=L->n ext;L_>n ext=lpp;L=L->n ext;cout<<e ndl;L=L->n ext;三、循環(huán)鏈表的長度/*函數功能：求循環(huán)鏈表的長度。參數；鏈表(linklist L) 通過各個掃描求循環(huán)鏈表長度*/int ListLe ngth(ListLi nk L)ListL ink lpp;if(L=NULL)cout<<" 鏈表是空的."return 0;int i=1;lpp=L->n ext;while(lpp!=L)i+;lpp=lpp-&

40、gt;n ext;return i;四、顯示循環(huán)鏈表/*函數功能：循環(huán)鏈表的顯示。參數；鏈表(linklist L)。通過各個掃描各個節(jié)點輸出各個節(jié)點的密碼*/void ListTraverse(ListL ink L)ListL ink lpp;lpp=L；int i=1;cout<<"輸入第 1 個人的密碼："<<lpp->cipher<<e ndl;lpp=lpp->n ext;while(lpp!=L)i+；cout<<"輸入第"<<i<<"個人的密碼：

41、"<<lpp->cipher<<endl;lpp=lpp->n ext;cout<<e ndl;五、約瑟夫環(huán)實現/*函數功能：實現所有人的出列次序。參數鏈表(linklist L)，密碼(int m )。每次要找到出列者的前驅，把出列者刪除*/void ListTraverse(ListL ink L)ListL ink lpp;lpp=L;int i=1;cout<<"輸入第 1 個人的密碼："<<lpp->cipher<<e ndl;lpp=lpp->n ext;w

42、hile(lpp!=L)i+;cout<<"輸入第"<<i<<"個人的密碼："<<lpp->cipher<<endl;lpp=lpp->n ext;cout<<e ndl;int ListLe ngth(ListLi nk L)ListL ink lpp;if(L=NULL)cout<<" 鏈表是空的."return 0;int i=1;lpp=L->n ext;while(lpp!=L)i+；lpp=lpp->n ext;re

43、turn i;void shixia n( ListL ink &L,i nt m)ListL ink lpp=L;ListLi nk l;while(lpp->n ext!=L)lpp=lpp->n ext;for(i nt n=ListLe ngth(L); n>0;n-)cout<<"密碼為："<<m<<e ndl; cout<<"出列人的編號是："for(i nt i=1;i<=m% n-1;i+)lpp=lpp->n ext;cout<<lpp-&

44、gt;n ext->nu mber<<e ndl;m=lpp->n ext->cipher;l=lpp->n ext;lpp->n ext=l->n ext;delete l;函數調用及主函數設計：int mai n()int m,n;ListL ink L;cout<<" 輸入人數(一個大于0小于30的數)和密碼(一個大于0的數)："<<endl; cin»n»m;while( * 0| n>30|m<0)cout<<"輸入的數字不符合要求，請重新

45、輸入："<<e ndl;cin»n»m;cout<<" 請輸入"<<n<<"個人的密碼："<<endl;In itList(L, n);cout <<*<"個人的密碼分別為："<<e ndl;ListTraverse(L);cout <<*<"個人的出列密碼和編號分別是："<<e ndl;shixia n(L,m);return 0;總結：ma in函數先調用初始化循

46、環(huán)鏈表的的函數void in it(li nklist & L,i nt n)，然后將循環(huán)鏈表輸出void show(li nklist L)，最后調用可以使人出列的函數void Joseph(li nklist & L,i nt m)本程序可以很好地運行，具有一定的除錯能力，輸入數據時可以對其進行判斷，減少程序出 現bug的可能性。通過對本實驗的操作，我熟悉了循環(huán)鏈表的基本操作，而且對循環(huán)鏈表的基本操作有了很好 的掌握。程序清單#in clude "iostream"#in clude "stdlib.h" using n amespace std; typedef struct node int nu mber;int cipher;struct node *n ext;/*人的序號*/*密碼*/*指向下一個節(jié)點的指針 */List, *ListLi nk;void In itList(ListLi nk & L,i nt n)int m,i;cout<<"輸入第1個人的密碼：”； cin»m;L=new List;L->nu mber=1;L_>cipher=m;L->n ext=L