實(shí)驗(yàn)一線性表操作實(shí)驗(yàn)報(bào)告

1、中國礦業(yè)大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱 _線性表操作實(shí)驗(yàn)報(bào)告要求： 1. 實(shí)驗(yàn)?zāi)康?. 實(shí)驗(yàn)內(nèi)容3. 實(shí)驗(yàn)步驟4. 運(yùn)行結(jié)果5. 流程圖6. 實(shí)驗(yàn)體會(huì)一、實(shí)驗(yàn)?zāi)康? 熟悉并掌握線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)。精品文檔，你值得期待2 熟悉并掌握順序表的存儲(chǔ)結(jié)構(gòu)、基本操作和具體的函數(shù)定義。3 熟悉 VC+程序的基本結(jié)構(gòu)，掌握程序中的用戶頭文件、實(shí)現(xiàn)文件和主文件之間的相互關(guān)系及各自的作用。4 熟悉 VC+操作環(huán)境的使用以及多文件的輸入、編輯、調(diào)試和運(yùn)行的全過程 。二、實(shí)驗(yàn)要求1 實(shí)驗(yàn)之前認(rèn)真準(zhǔn)備，編寫好源程序。2 實(shí)驗(yàn)中認(rèn)真調(diào)試程序，對(duì)運(yùn)行結(jié)果進(jìn)行分析，注意程序的正確性和健壯性的驗(yàn)證。3

2、 不斷積累程序的調(diào)試方法 。三、實(shí)驗(yàn)內(nèi)容基本題:1 對(duì)元素類型為整型的順序存儲(chǔ)的線性表進(jìn)行插入、刪除和查找操作。源程序：#include<iostream.h>#include<conio.h>#include<stdlib.h>const LIST_INIT_SIZE=10;const LISTINCREMENT=1;typedef structint*elem;int length;int listsize;SqList;void InitList_Sq(SqList&L)/ 構(gòu)造一個(gè)空的線性表LL.elem=(int*)malloc(LIST_

3、INIT_SIZE*sizeof(int);if(!L.elem)exit(0);L.length=0;/ 存儲(chǔ)分配失敗/ 空表長(zhǎng)度為0L.listsize=LIST_INIT_SIZE;/ 初始存儲(chǔ)容量cout<<"OK!"<<endl;void ListInsert_Sq(SqList&L,int i,int j)/ 在順序線性表L 中第i 個(gè)位置之前插入新的元素j ，/i的合法值為1<=i<=ListInsert_Sq(L)+1if(i<1|i>L.length+1)cout<<"ERROR

4、!"<<endl;/i值不合法if(L.length>=L.listsize)/ 當(dāng)前存儲(chǔ)空間已滿，增加分配int *newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);L.elem=newbase;/ 存儲(chǔ)分配失敗/ 新基址L.listsize+=LISTINCREMENT;/ 增加存儲(chǔ)容量int *q=&(L.elemi-1);for(int*p=&(L.elemL.length-1);p>=q;-p)*(p+1)=

5、*p;*q=j;+L.length;cout<<"OK!"<<endl;/ListInsert_Sqvoid ListDelete_Sq(SqList&L,int i,int&j)/ 在順序線性表L 中刪除第i 個(gè)元素， 并用 j 返回其值/i 的合法值為1<=i<=ListInsert_Sq(L)if(i<1)|(i>L.length)cout<<"ERROR!"<<endl;int *p=&(L.elemi-1);j=*p;int *q=L.elem+L.

6、length-1;/i 值不合法/p 為被刪除元素的位置/ 被刪除元素的值賦給/ 表尾元素的位置jfor(+p;p<=q;+p)*(p-1)=*p;-L.listsize;cout<<"OK!"<<endl;/ 被刪除元素之后的元素左移/ 表長(zhǎng)減 1/ListDelete_Sqbool compare(int m,int n)if(m=n)return true;elsereturn false;int LocateElem_Sq(SqList L,int j)/ 在順序線性表L 中查找第1 個(gè)值與j 滿足compare()的元素的位序/ 若找

7、到，則返回其在L 中的位序，否則返回0int i=1;int *p=L.elem;/i/p的初值為第的初值為第1 個(gè)元素的位序1 個(gè)元素的存儲(chǔ)位置while(i<=L.length&&!compare(*p,j)+i;p+;if(i<=L.length)return i;elsereturn 0;/LocateElem_Sqvoid disp(SqList&L)int *p=L.elem;for(int i=0;i<L.listsize;i+)cout<<*p<<""p+;void main()SqList

8、List;InitList_Sq(List);int *p=List.elem;int m,n,j,k,x,y;for(int i=0;i<List.listsize;i+)cin>>x;*p=x;p+;List.length+;cout<<" 插入請(qǐng)按1 ；刪除請(qǐng)按2；尋找請(qǐng)按3"<<endl;for(k=0;k=10;k+)cin>>y;if(y=1)cout<<" 請(qǐng)輸入插入位置和元素的值:"<<endl;cin>>m>>n;ListInsert_

9、Sq(List,m,n);disp(List);else if(y=2)cout<<" 請(qǐng)輸入要?jiǎng)h除第幾個(gè)元素:"<<endl;cin>>m;ListDelete_Sq(List,m,j);cout<<j<<endl;disp(List);elsecout<<" 請(qǐng)輸入所要查找的元素:"<<endl;cin>>m;cout<<LocateElem_Sq(List,m)<<endl;cout<<endl;運(yùn)行結(jié)果：加強(qiáng)、提高題

10、：2、編寫一個(gè)求解Josephus 問題的函數(shù)。用整數(shù)序列1, 2, 3, n表示順序圍坐在圓桌周圍的人。然后使用n = 9, s = 1, m = 5，以及 n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性。最后分析所完成算法的時(shí)間復(fù)雜度。定義 JosephusCircle類，其中含完成初始化、報(bào)數(shù)出圈成員函數(shù)、輸出顯示等方法。（可以選做其中之一）加強(qiáng)題：1、采用數(shù)組作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。提高題：2、采用循環(huán)鏈表作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。運(yùn)行時(shí)允許指定任意 n、s、m數(shù)值，直至輸入 n =0 退出程序。

11、源程序：（1）加強(qiáng)：#include <iostream.h>#include <conio.h>#include <stdlib.h>int a100;int josephus(int n,int s,int m)if(!(n*s*m)cout<<" 輸入錯(cuò)誤 !"<<endl;exit(0);int x=1,y=n;int i=s-1;int j;while(y)for(i=0;i<n;i+)if(ai+1)ai=x+;if(ai=m)ai=-1;cout<<i+1<<"

12、 出局 !"<<endl; x=1;y-;for(j=0;j<n;j+)if(aj+1)aj=x+;if(aj=m)aj=-1;x=1;y-;if(!y)break;elsecout<<j+1<<" 出局 !"<<endl;return (j+1);void main()int n,s,m,y=0;int x;dofor(int i=0;i<100;i+)ai=0;cout<<" 請(qǐng)輸入?yún)⒓佑螒虻目側(cè)藬?shù):"<<endl;cin>>n;cout<

13、<" 請(qǐng)輸入開始人的位置與報(bào)數(shù)長(zhǎng)度:"<<endl;cin>>s;cin>>m;x=josephus(n,s,m);cout<<x<<" 勝出 !"<<endl;cout<<" 請(qǐng)選擇 :"<<endl;cout<<"1. 重新游戲。2.退出程序。 :"<<endl;cin>>y;while(y=1);getch();運(yùn)行結(jié)果：（2）提高：#include<iostream

14、>using namespace std;typedef struct LNodestruct LNode *next;int a;LNode,*LinkList;class JosephouCircle/ 定義一個(gè)類包括三個(gè)元素public:void SetValue();void PickOut();private:int n;int s;int m;void JosephouCircle:SetValue()/ 設(shè)置初值的大小cout<<" 請(qǐng)輸入?yún)⒓佑螒虻目側(cè)藬?shù):"<<endl;cin>>n;cout<<&quo

15、t; 請(qǐng)輸入開始人的位置:"<<endl;cin>>s;cout<<" 請(qǐng)輸入報(bào)數(shù)長(zhǎng)度:"<<endl;cin>>m;void JosephouCircle:PickOut()LinkList L;LNode *p,*q;int j,k;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;LNode*r;r=L;for (int i=1;i<=n;+i)/構(gòu)建一個(gè)循環(huán)鏈表p=(LinkList)malloc(sizeof(LNode);p->a=i

16、;p->next=NULL;r->next=p;r=p;p->next=L->next;p=L->next;j=1;while(p&&j<s)p=p->next;+j;for(i=1;i<=n;i+)for(j=1;j<m-1;j+)p=p->next;q=p->next;p->next=q->next;p=q->next;k=q->a;cout<<" 輸出的結(jié)果為 :"<<k<<endl;free(q);int main(int a

17、rgc,char* argv)JosephouCircle Jo1;Jo1.SetValue();Jo1.PickOut();return 0;運(yùn)行結(jié)果：四、實(shí)驗(yàn)體會(huì)與總結(jié)1、對(duì)于線性鏈表和順序表都屬于線性表問題，但是線性鏈表比順序表要靈活，方便；2、線性表在做元素尋找的操作的時(shí)候，必須從頭結(jié)點(diǎn)開始尋找。體會(huì)：在編程序的時(shí)候，我們每個(gè)人肯定會(huì)遇到許多問題，我遇到的問題是：當(dāng)我在運(yùn)行程序的時(shí)候， 在輸入一個(gè)元素后，程序就不繼續(xù)做下面的操作也不停止運(yùn)行，自己尋找并修改了好久都沒發(fā)現(xiàn)問題的所在， 最后實(shí)在沒辦法， 就去問同學(xué)， 結(jié)果終于發(fā)現(xiàn)是一條語句在編寫時(shí)出現(xiàn)了錯(cuò)誤。所以，以后再寫程序的時(shí)候我一定

18、要再認(rèn)真仔細(xì)一點(diǎn)仔細(xì)點(diǎn)。教師評(píng)價(jià)優(yōu)良中及格不及格教師簽名日期想來生活，從來就不是陽春白雪的神話。光陰的陌上，總有風(fēng)自八方來，或許是憂凄，也許是歡喜,無論怎樣，都是歲月最真的饋贈(zèng)。待到老去的那一日，偶爾有回憶念及了過往，依舊還會(huì)有初初的心動(dòng)，流轉(zhuǎn)了眉眼。而那一路迤邐而來的美好，一步一步寫就兩個(gè)梅花小楷 日常。暖陽小窗，無事此靜坐。杯盞光陰，又在指間如風(fēng)輕過，回首，依稀還是那年秋，低低一低眉，卻已是春光葳蕤。光陰荏苒，而流年從來也不曾缺少錯(cuò)亂和猶疑。是否在這樣一個(gè)萬物復(fù)蘇的季節(jié)里，一切的紛擾是非，終究會(huì)給出一個(gè)水落石出的答案。輕倚初春的門楣，且把盞清風(fēng)，問心明月，讓來者可來，去者可去，宿命里的擁有，一一欣喜悅納。而我也只需以花香繞肩的美，步履從容的，走過生命里的山山水水。若說，那一