1、一.實驗名稱1 .線性表基本操作；2.處理約瑟夫環問題二.試驗目的：1 .熟悉C語言的上機環境，掌握C語言的基本結構。2 .定義單鏈表的結點類型。3 .熟悉對單鏈表的一些基本操作和具體的函數定義。4 .通過單鏈表的定義掌握線性表的鏈式存儲結構的特點。5 .熟悉對單鏈表的一些其它操作。三.實驗內容L編制一個演示單鏈表初始化、建立、遍歷、求長度、查詢、插入、刪除等操作的程序。2 .編制一個能求解除約瑟夫環問題答案的程序。實驗一線性表表的基本操作問題描述:1 .實現單鏈表的定義和基本操作。該程序包括單鏈表結構類型以及對單鏈表操作 的具體的函數定義程序中的單鏈表（帶頭結點）結點為結構類型，結點值為整型

2、。/*定義DataType為int類型*/typedef int DataType;/*單鏈表的結點類型*/typedef struct LNode DataType data; struct LNode *next;LNodez *LinkedList;LinkedList LinkedListlnit () /初始化單鏈表void LinkedListClear (LinkedList L) / 清空單鏈表 int LinkedListEmpty (LinkedList L)檢查單鏈表是否為空 void LinkedListTraverse (LinkedList L) / 遍歷單鏈表 i

3、nt LinkedListLength (LinkedList L) 求單鏈表的長度 /*從單鏈表表中查找元素*/ LinkedList LinkedListGet(LinkedList L,int i)/*從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListlnsert (LinkedList L, int iz DataType x) 向單鏈表中插入元素/*從單鏈表中刪除元素*/void LinkedListDel(LinkedList L,DataType x

4、)/*用尾插法建立單鏈表*/LinkedList LinkedListCreat ()2.約瑟夫環問題：任給正整數N和K,按下述方法可以得到1,2,n的一個置換，將 數字1,2,n環形排列，按順時針方向自1開始報數，報到K時輸出該位置上的數 字，并使其出列。然后從他在順時針方向的下一個數字繼續報數，如此下去，直到 所有的數字全部出列為止。例如N=10, K=3,則正確的出列順序應為3, 6, 9, 2, 7, 1, 8, 5, 10, 4o3,試單鏈表實現一個簡單的電子通訊本管理軟件，要求能查找聯系地址，增加和刪除 聯系人。聯系方式假定包括姓名、電話和地址。基本要求：1 .上機前要做好準備工作

5、，包括程序框圖、數據結構以及算法。2 .按時實驗3 .服從實驗室老師的安排4 .獨立實驗，有問題可以討論，但不得翻版。5 .遵守實驗室的各項紀律。四、概要設計1.單鏈表的操作(1)為了實現上述程序功能，需要定義單鏈表的抽象數據類型：ADT LuikedList 數據對象：D=ai ai G stiuct LNode set,i=0J2數據關系：R= <ai,ai+1 >|ai,ai+1 D基本操作：LinkedListInit()操作結果：構造了一個帶頭節點的空鏈表L;LHikedListCreatQ初始條件：單鏈表L已存在；操作結果：建立了一個帶頭節點的非空鏈表；LinkedLi

6、stClear(&L)初始條件：單鏈表L已存在；操作結果：將L重置為帶頭節點的空鏈表；LuikedListEmptv(&L)初始條件：單鏈表L已存在；操作結果：如果鏈表L為空則返回1,鏈表L非空則返回0：LHikedListLength(&L)初始條件：單鏈表L已存在；操作結果：返回單鏈表L中數據元素的個數，若L為空表則返回0： LuikedListTraverse(&L)初始條件：單鏈表L已存在；操作結果：依次返回單鏈表L中各節點的元素值，若L為空表則顯示鏈表為空； LuikedListGet(&L, i)初始條件：單鏈表L已存在；操作結果：顯示鏈表L

7、中第1個節點個元素值，若鏈表L中沒有第1個節點則顯示查詢位置 不正確：LuikedListLocate(&L, x)初始條件：單鏈表L已存在；操作結果：顯示鏈表L中元素x的位置，若鏈表L中沒有元素x則顯示所查找元素不存在： LuikedListInseit(&L, i, x)初始條件：單鏈表L已存在；操作結果：在單鏈表L第1個節點后插入一個元素值為x的節點，L的長度加1,若單鏈表 L中沒有第1個節點則顯示插入位置不正確；LuikedListDel(&L, i)初始條件：單鏈表L已存在；操作結果：在單鏈表L中刪除第1個節點，L的長度減1,若單鏈表L中沒有第1個節點則 顯示

8、刪除位置不正確；(2)本程序包含11個函數：1 .主函數niarnQ2 .初始化單鏈表函數LuikListhutO3 .清空單鏈表函數LuikedListClear ()4 .檢查單鏈表是否為空函數LuikedListEmpty ()5,遍歷遍歷單鏈表函數LmkudListTraverse ()6 .求單鏈表的長度函數LnikedListLength ()7 .從單鏈表表中查找元素函數LmkedListGet ()8從單鏈表表中查找指定元素的位序函數LuikedListLocate ()9 .插入元素函數 LnikedListliisert ()10 .刪除元素函數LinkedListDel

9、()11 .建立單鏈表函數LinkedListCreat()各函數之間的關系：LuikL IStllllt 0Luike dList Clear ()Linke dList EmptLiiike dList Trave rse ()Liiike dList Lengt h ()LinkeLiiikeLiiikeLinkeLiiikedListdListdListldListdListGetOLocatnseitDelOCreat(e ()()五.詳細設計1結點類型和指針類型 typedef stnict LNode mt data;struct LNode "next; LNode,

10、*LuikedList;2單鏈表的基本操作(1)初始化單鏈表LnikedList LmkedListlnitQ LuikedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;)(2)清空單鏈表void LinkedListCleai (LnikedList L) L->next=NULL;pnntf("鏈表已經清空n)(3)檢查單鏈表是否為空 mt LnikedListEmpty(LuikedList L)if(L->next=NULL) return TRUE;else return F

11、ALSE;)(4)遍歷單鏈表void LinkedListTraverse(LuikedList L) LuikedList p;p=L->next;if(p=NULL) pnntf("單鏈表為空表 1T);elseprintf("鏈表中的元素為NT);while(p!=NULL)printf(H%d fp->data); p=p->next; jpnntff'n")；(5)求單鏈表長度mt LuikedListLength (LuikedList L) LuikedList p;intj;p=L->next;J=°；wh

12、ile(p!=NULL) j+;p=p->next; return j;(6)從鏈表中查找元素LuikedList LuikedListGet(LHikedList Ljnt i) LuikedList p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL; )(7)從鏈表中查找與給定元素值相同的元素在順序表中的位置 mt LnikedListLocate (LuikedList L, mt x) LuikedList p=L->

13、;next; j=l;while (p!=NULL && p->data != x) p=p->next;j+; if(p) return j;else return 0;j(8)向鏈表中插入元素void LinkedListIiisert(LiiikedList L, mt i, mt x) LuikedList p,s;intj;J=1；P=L；while(p&&j<i)p=p->nextj+; if(p=NULL|j>i) pnntf("插入位置不正確n) else s=(LNode *)nialloc(sizeof

14、(LNode); s->data=x;s->next=p->next; p->next=s;pnntf("d已插入到鏈表中11"了)； ) )(9)從鏈表中刪除元素void LinkedListDel(LiiikedList L,int i) LinkedList p,q;intj;J=1；P=L；while(p->next&&j <i)p=p->next;j+;if(p->next=NULL)pnntf("刪除位置不正確n")；else q=p->next;p->next=q-

15、>next;fiee(q);printf("第d個元素已從鏈表中刪除111);) )(10)建立單鏈表LinkedList LiiikedListCreat() LinkedList L=LinkedListInit(),p,t; mt x;r=L;pnntf("請依次輸入鏈表中的元素，輸入負數時結束1門； scanf(”d”,&x);while (x>=0)p=(LuikedList)malloc(sizeof(LNode);p->data=x;r->next=p; r=p；scanf("%d”.&x);)r->ne

16、xt=NULL;return L;)(11)主函數niainQ mt i,h,d,e,xj,n,q; chai ch;LinkedList L,p;while(q!=0) pnntf("請選擇要進行的操作W)pnntf(“L初始化2.清空3.求鏈表長度4.檢查鏈表是否為空n")；pnntf("5.遍歷鏈表6,從鏈表中查找元素n")；pnntf(”7 .從鏈表中查找與給定元素值相同的元素在順序表中的位置n")；pnntf(”8.向鏈表中插入元素9.從鏈表中刪除元素W)priiitf(nl 0 .建立單鏈表 n")； printf(&qu

17、ot;按其它鍵結束n) scanf(”d”,&x);switch(x)case l:L=LinkudList!nit();printf("鏈表已經初始化 nn);break;case 2:LinkedListCleai(L);prmtf(niiH);bieak;case 3:printf("鏈表的長雇為 %dn,LinkedListLength(L);bieak;case 4:i= LinkedListEmpty(L);if pnntf("鏈表為空 n");else printf("鏈表非空 n”);break;case 5 :Link

18、edListTraveise(L); break;case 6:pnntf(“請輸入待查詢元素在鏈表中的位置:")；scanf(”%d”,&j);p=LnikedListGet(L,j);if(p) pnntff鏈表中第泡 個元素的值為:dh“j,p->data);else piintf("查詢位置不正確n)break;case 7:pnntf("請輸入待查詢元素的值:)scanf(',%d,&e);h=LinkedListLocate(L,e);時)pnntf("d在鏈表中的位置是:%MT,e,h);else pnntf(

19、"鏈表中沒有值為(1的元素n”,e);break;case 8:pnntf(“請輸入插入元素的位置和值(中間以空格或回車分隔)An”)；scanff'%d%d”,&d,&e);LnikedListIiisert(L,d,e);break;case 9:if(LuikedListLength(L)=O)pnntf("鏈表已經為空，不能刪除n)else pnntf("請輸入待刪除元素的彳立置:n")；scanf(”d”,&n);LnikedListDel(L,n);break;case 10: L=LHikedListCrea

20、t();prmtf(nnH);break;default:q=O:)六.測試結果1、單鏈表的操作(1)建立單鏈表：選擇1,然后選擇10 ,輸入123.4.5.6.7,8.9最后一個負數(2)求鏈表長度：選擇3,得到執行結果：鏈表的長度為9(3)檢查鏈表是否為空：選擇4,得到執行結果：單鏈表非空(4)遍歷鏈表：選擇5,得到執行結果：鏈表中的元素為1, 2, 3, 4, 5, 6, 7,8, 9,(5)從鏈表中查找元素：選擇6,輸入5,顯示：鏈表中第5個元素的值為5(6)從鏈表中查找與給定元素值相同的元素在順序表中的位置選擇7,輸入2,顯示：2在鏈表中的位置是：2選擇7,輸入25,顯示：鏈表中沒有

21、值為25的元素向鏈表中插入元素選擇8,輸入(6, 5),顯示5以插入到鏈表中選擇5：鏈表中的元素為1, 2, 3, 4, 5, 5, 6, 7, 8, 9,(8)從鏈表中刪除元素選擇9,輸入5,顯示第5個元素已從表中刪除選擇9,輸入12,顯示刪除位置不正確選擇5,顯示鏈表中的元素為鏈表中的元素為1, 2, 3, 4, 5, 6, 7, 8, 9,實驗二約瑟夫環1.問J描述設有編號1,2,3。n（n>0）的N個人圍成一個圈，每個人持有一個密碼（正整數）。開始時從第k （1<=k<=n）個人按順時針方向自1開始順序報數，報到m （m為第K個人的密碼）的人出圈，再以這個人順時針方向

22、上的下一個人的密碼為m,并開始重新從1報數。如此下去，宜至所有人 全部出列為止。試設計一個程序求出出列順序。例如，設總人數n的初值為8.他們所持的密碼分 別為：3,10,7,1,4,8,4,5,開始報數人的編號k的初值為7,則出列順序為:2,1,3,4,8,57,62.數據結構設計問題中以序號標示某個人，所以結點的數據域設為一個整型類型的變量當某人出圈后，報數的工作要從下一個人開始繼續，剩下的人仍然圍成一圈，可以使用循環 表。由于出圈的人將不再屈于圈內，意味著數據元素的刪除。因此，算法中存有頻繁的元素刪除 操作，存儲結構宜采用鏈表。每個結點中既存儲密碼還存儲初始位置，所以結點有兩個數據域， 一

23、個指針域。另外，每個結點代表一個人所以，可以令尾結點指針指向首元結點來進行循環。/結點類template <class ElemType>struct Node/數據成員：/數據域 指針域ElemType data;ElemType num;Node<ElemType> *next;/構造函數：Node();/無參數的構造函數Node(ElemType item, ElemType iteml ,Node<ElemType> *link = NULL);/已知數數據元素值和指針建立結構;/結點類的實現部分 template<class ElemType

24、> Node<ElemType>:Node()/操作結果：構造指針域為空的結點 (next = NULL;)template<class ElemType>Node<ElemType>:Node(ElemType item, ElemType iteml,Node<ElemType>*link)/操作結果：構造一個數據域為item和iteml,指針域為link的結點data = item;num = iteml;next = link; #endif3.算法設計編寫一個函數實現結點的刪除與輸入工作，另編寫一個主函數main ()完成鏈 表的

25、創建與函數調用工作。(1)插入template <class ElemType>Status LinkList<ElemType>:lnsert(int position, const ElemType &e)/操作結果：在線性表的第position個位置前插入元素e/ position 的取值范圍為 1WpositionWLength()+1/ position合法時返回SUCCESS,否則函數返回RANGE_ERROR(if (position < 1 | position > Length() + 1) “position 范圍錯return

26、RANGE_ERROR; / 位置不合法) else/ position 合法Node<ElemType> *tmpPtr;/取出指向第position-1個結點的指針tmpPtr = GetElemPtr(position - 1);Node<ElemType> *newPtr;if(position>Length()/如果插入尾結點，則域指針指向首元結點newPtr = new Node<ElemType>(e, position,head->next); elsenewPtr= new Node<ElemType>(e, pos

27、ition,tmpPtr->next);/ 生成新結點/將tmpPtr插入到鏈表中/設置當前位置的序號設置指向當前位置的指針/插入成功后元素個數加1tmpPtr->next = newPtr; curPosition = position; curPtr = newPtr;count+;return SUCCESS;)(2)刪除template <class ElemType>Status LinkList<ElemType>:Delete(int position, ElemType &e)操作結果：刪除線性表的第position個位置的元素，并用

28、e返回其值,/ position 的取值范圍為 1WpositionWLength。,/ position合法時函數返回SUCCESS,否則函數返回RANGE.ERROR/ position 合法Node<ElemType> *tmpPtr;if(position=1)/如果刪除首元結點，取出指向尾結點的指針tmpPtr=GetElemPtr(Length();else/取出指向第position-1個結點的指針tmpPtr = GetElemPtr(position - 1);Node<ElemType> *nextPtr = tmpPtr->next;if(p

29、osition=1)頭結點與新的首元結點相連head->next=nextPtr->next; / nextPtr 為 tmpPtr 的后繼 tmpPtr->next = nextPtr->next;II 刪除結點e = nextPtr->data;用e返回被刪結點元素值if (position = Length()/設置當前位置的序號 設置指向當前位置的指針 II刪除尾結點,當前結點變為頭結點curPosition = 1;curPtr = head->next;)else/刪除非尾結點，當前結點變為第position個結點curPosition = po

30、sition; curPtr = tmpPtr->next;)count-;delete nextPtr;return SUCCESS;)(3)出圈次序的算法描述template <class ElemType>/設置當前位置的序號II設置指向當前位置的指針II刪除成功后元素個數減1II釋放被刪結點int LinkList<ElemType>:Pass(int position , int n ,ElemType &e)int i;curPtr = GetElemPtr(position);curPosition=position;for(i=0;i<

31、;n-1 ;i+)curPtr = curPtr->next;curPosition+;)coutvvcurPtr->numvv" ”；e=curPosition;當前指針指向position記錄當前位置依次報數直到n輸出起始位置)(4)主程序#includeHassistance.hH#include"lk_list.h"int POS(int n,int i)計算當前位置的函數jf(n%i=O) n=i;else n=n%i;return n;int main() int tmp,i,k=O,n=O,key;int pos;LinkList<

32、int> Ic;創建空鏈表while(n<1|n>20)限制人數cout<<”請輸入人數，人數小于20:”；cin»n;coutvv”請輸入每個人的密碼，用空格分隔，密碼大于0:“vvendl;for(i=1;i<=n;i+)cin»tmp;插入尾結點lc.lnsert(i,tmp); 1while(k<1|k>n) coutvv”從幾號開始？ 0<K<=H«n<<,1:11;cin»k;coutvv"出列順序:"；for(i=n;i>0;i-)if(i=n

33、)一開始，從k開始報數出列計算出列位置刪除當前結點，當前指針指向當前位置的下游取當前位置的密碼從當前位置開始報數，并出列計算出列位置lc.GetElem(k,key); lc.Pass(k,key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp);)elselc.GetElem(key); lc.Pass(key,tmp); pos=POS(tmp,i); lc.Delete(pos,tmp); ) ) system(Hpause"); return 0;)九：心得體會通過做這次實驗，發現自己在數據結構這門課程中還有很多不足，有很多知識 還沒掌握實驗的

34、時候出現了很多錯誤，有很多知識還不能運用，最后在同學的幫助 下，終于完成了任務。因為以前的C語言沒學好，這學期的數據結構感到學的時候有些吃力，在實驗 的時候，我所以的不足都體現出來了，如果沒有同學的幫助，我程序中的問題可能 需要很長時間才會解決，所以以后還是要努力趕上來。在這次實驗中，我也得到了很多收獲，比如鏈表的應用，以前總是弄不明白，通過這次實驗，在鏈表這一方面我懂了很多，但還不能運用自如，需要更多的練習。這次實驗，對本學期所學習的內容也是一次鞏固，讓我加深了對學過知識的記 憶。總之，這次實驗讓我既發現了自身的很多不足，又增長了很多知識。#include<stdio .h>#i

35、nclude<malloc.h>#defuie TRUE 1#defuie FALSE 0typedef stnict LNodehit data;stnict LNode *next; LNode, *LnikedList;LnikedList LinkedListImt()LinkedList L;L=(LinkedList)malloc(sizeof(LNode);L->next=NULL;return L;void LinkedListCleai(LuikedList L)L->next=NULL;pnntf("鏈表已經清空n)mt LinkedLis

36、tEnipty(LnikedList L) if(L->next=NULL) return TRUE;else return FALSE;void LinkedListTraverse(LHikedList L)LinkedList p;p=L->next;if(p=NULL) pnntf("單鏈表為空表 n”)；elsepnntf("鏈表中的元素為:n");wliile(p!=NULL)priiitf(M%d fp->data); p=p->next;mt LinkedListLength (LinkedList L) LinkedLis

37、t p;intj;p=L->next;J=0；while(p!=NULL)j+；p=p->next; return j;LnikedList LuikedListGet(LnikedList L,int i)LinkedList j;p=L->next; j=l;while (p!=NULL && j<i)p=p->next; j+; if (j=i) return p; else return NULL;mt LinkedListLocate (LinkedList L. int x) LinkedList p=L->next; j=l;w

38、hile ( p!=NULL && p->data != x) p=p->next;j+; if(p) retuinj;else return 0;void LinkedListIiiseit(LHikedList L, mt i. int x) LinkedList p,s;intj;j=l；P=L；while(p&&j<i)p=p->next;j+;if(p=NULL|j>i)pnntf("插入位置不正確11");else s=(LNode *)malloc(sizeof(LNode);s->data=

39、x;s->next=p->next;p->next=s;pnntf("%d已插入到鏈表中11"不)；void LinkedListDel(LHikedList Ljnt i) LuikedList p,q;intj;j=l；P=L；wlule(p->next&&j<i)p=p->next;j+; if(p->next=NULL) pnntf("刪除位置不正確n")； else q=p->next;p->next=q->next;fiee(q);printf("第d個元素已從鏈表中刪除)LuikedList LuikedListCreat() LuikedList L=LuikedListIiiit(),p,i;mt x;r=L;pnn氓”請依次輸入鏈表中的元素，輸入負數時結束 scanfC%d&