中國礦業(yè)大學數(shù)據(jù)結(jié)構(gòu)實驗一.doc

中國礦業(yè)大學計算機科學與技術(shù)系試驗報告課程名稱 _數(shù)據(jù)結(jié)構(gòu)_ 試驗名稱_線性表操作_班級 X班 姓名 XXX 學號XXXX 儀器組號_ 實驗日期 實驗報告要求：1.實驗?zāi)康?2.實驗內(nèi)容 3.實驗步驟 4.程序清單5.運行結(jié)果 6.流程圖 7.實驗體會實驗一 線性表操作一、實驗?zāi)康模?、并掌握線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)。2、并掌握順序表的存儲結(jié)構(gòu)、基本操作和具體的函數(shù)定義。3、VC+程序的基本結(jié)構(gòu)，掌握程序中的用戶頭文件、實現(xiàn)文件和主文件之間的相互關(guān)系及各自的作用。4、悉VC+操作環(huán)境的使用以及多文件的輸入、編輯、調(diào)試和運行的全過程。二、實驗要求：1 實驗之前認真準備，編寫好源程序。2 實驗中認真調(diào)試程序，對運行結(jié)果進行分析，注意程序的正確性和健壯性的驗證。3 不斷積累程序的調(diào)試方法。三、實驗內(nèi)容基本題:1 對元素類型為整型的順序存儲的線性表進行插入、刪除和查找操作。加強、提高題：2、編寫一個求解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ù)，檢查你的程序的正 確性和健壯性。最后分析所完成算法的時間復(fù)雜度。定義JosephusCircle類，其中含完成初始化、報數(shù)出圈成 員函數(shù)、輸出顯示等方法。（可以選做其中之一）加強題：（1）采用數(shù)組作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。提高題：（2）采用循環(huán)鏈表作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。運行時允許指定任意n、s、m數(shù)值，直至輸入 n = 0 退出程序。 四、五 程序清單和運行結(jié)果1-1基本題:#include #include #define TRUE 1 #define FALSE 0 typedef struct LNode ElemType dataMAXSIZE;int length; /length為線性表的長度SqList; /線性表定義/1.初始化操作，將線性表L置空void InitList(SqList &L)L.length=0;/2.建立一個順序存儲的線性表void CreatSqlist(SqList &L,int n)int i;for(i=0;in;i+)scanf(%d,&L.datai);L.length=n;/3.輸出順序表Lvoid output(SqList L) int i;for(i=0;iL.length;i+)printf(%5d,L.datai);printf(n);/4.判空int IsEmpty(SqList L)if(L.length=0)printf(此列表為空);elseprintf(此列表非空);return 0;/5.定位函數(shù)int LocateElem(SqList L,ElemType x)int k=0;while(kL.length&L.datak!=x)k+;if(kL.length)return k;elsereturn -1;/6.插入元素int Insert(SqList &L,ElemType x,int i)int k;if(iL.length|L.length=MAXSIZE)return 0;elsefor(k=L.length;k=i;k-) L.datak=L.datak-1;L.datai=x;L.length=L.length+1;return 1;/7.刪除元素int Delete(SqList &L,int i)int k;if(iL.length)return 0;else for(k=i;kL.length;k+) L.datak=L.datak+1; L.length-;return 1; void main()SqList List; /構(gòu)造線性表InitList(List); /置空printf(please input 10 numbers:n);CreatSqlist(List,10); /建立一個順序線性表output(List); /輸出線性表IsEmpty(List); /表的判空 printf(n); int x,k,i; /搜索元素printf(please intput a number you want to search:);scanf(%d,&x);k=LocateElem(List,x);printf(n); printf(output the position the number:%dn,k+1); /k+1;因為數(shù)組和閱讀的關(guān)系，所以加1，下面也是如此printf(n);printf(input a nuebers position and a number you want to insert:);/插入元素scanf(%d,&i);scanf(%d,&x);Insert(List,x,i-1);output(List);printf(n); printf(please input a position of a number you want to delete:);/刪除元素 scanf(%d,&i);Delete(List,i-1);output(List);printf(n);1-2加強：用數(shù)組解決#include #include #include #include int a100;int josephus(int n,int s,int m)if(!(n*s*m)printf(輸入錯誤！n);exit(0);int x=1,y=n;int i=s-1;int j;while(y)for(;in;i+)if(ai+1)ai=x+;if(ai=m)ai=-1;printf(%d,i+1);printf(出局n);x=1;y-;for(j=0;jn;j+)if(aj+1)aj=x+;if(aj=m)aj=-1;x=1;y-;if(!y)break;elseprintf(%d,j+1);printf(出局n);return (j+1);void main()int n,s,m,y=0;int x;dofor(int i=0;i100;i+)ai=0;printf(請輸入人游戲總?cè)藬?shù)：n);scanf(%d,&n);printf(請輸入開始人位置與報數(shù)長度：n);scanf(%d,&s);scanf(%d,&m);x=josephus(n,s,m);printf(%d,x);printf(勝出n);printf(請選擇：n);printf(1,重新游戲; 2,退出程序：n);scanf(%d,&y);while(y=1);getch();1-3提高題：循環(huán)鏈表#include#include#define NULL 0#includetypedef struct Lnodeint data;struct Lnode *next;Josephus;void CreateList(Josephus*&L,int n)/建立循環(huán)鏈表int i;Josephus *p,*s;s=(Josephus*)malloc(sizeof(Josephus);s-data=1;L=p=s;for(i=2;idata=i;p-next=s;p=s;p-next=L;void DeleteList(Josephus*&L,Josephus*p,Josephus*q)q-next=p-next;free(p);void Josephus1(Josephus*&L,int s,int m)Josephus *p,*q;int i;p=L;for(i=1;inext;q=p-next;while(q-next!=p)q=q-next;while(p-next!=p)for(int j=1;jnext;printf(%d,p-data);DeleteList(L,p,q);p=q-next;printf(%d,p-data);printf(n);void main()Josephus *L=NULL;int m,n,s;printf(請輸入人數(shù)，報數(shù)的開始位置，報數(shù)的上限:n);scanf(%d%