實驗一線性表的基本操作及應用

《實驗一線性表的基本操作及應用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)實驗報告（實驗一&實驗二）?班級：軟件121?學號：201200834122?姓名：程猛實驗一線性表的基本操作及應用【實驗目的】理解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，掌握順序表的特點是邏輯上相鄰的元素的存儲地址也相鄰，熟練掌握線性表的查找、插入和刪除等算法并靈活運用這些算法?！緦嶒瀮?nèi)容】(任選一題)1、建立一個順序表，要求完成以下操作：實現(xiàn)順序表的初始化、銷毀順序表、重置順序表為空表、判斷順序表是否是空表、求順序表的元素個數(shù)、取順序表中的一個數(shù)據(jù)、查找順序表中的一個元素值、查找某一位置元素的前驅(qū)和后繼、將一個值插入到指定的

2、位置、刪除指定位置的元素。按此方法定義另一個順序表，實現(xiàn)兩個順序表的合并；如果這兩個順序表元素值是有序的，實現(xiàn)這兩個順序表的合并，并使合并后的數(shù)據(jù)也是有序排列的。要求(a)順序表的初始狀態(tài)可直接賦值，也可將初態(tài)置為空表，從鍵盤讀入數(shù)據(jù)元素。(b)每做一次操作將結(jié)果打印出來。2、建立單鏈表L(分別采用頭插法和尾插法)，打印單鏈表中的數(shù)據(jù)、打印單鏈表長度、按值查找元素、按位置取元素、插入結(jié)點和刪除結(jié)點。(a)初始將單鏈表置空(b)在單鏈表中插入元素(c)按值查找元素(d)按位置取元素(e)插入結(jié)點(f)刪除結(jié)點3、以循環(huán)單鏈表為存儲結(jié)構(gòu)，編寫程序求解

3、約瑟夫問題。編號為1，2，···，n的n個人圍坐在一圓桌旁，從第s個人開始報數(shù)，報到第m的人退席，下一個人又重新從1開始報數(shù)，依此重復，直至所有的人都退席。要求(a)循環(huán)單鏈表的初始狀態(tài)可直接賦值，也可將初態(tài)置為空表，從鍵盤（文件）讀入數(shù)據(jù)元素。(b)輸出刪除元素的順序(c)分析算法的時間性能【源代碼】#include"stdafx.h"#include#include#defineSIZE10#defineREMENT5typedefstruct{int*elem;intlength;intlsize;}S

4、qlist;SqlistL;voidstate_initlist(Sqlist&L)//線性表的初始化{L.elem=(int*)malloc(SIZE*sizeof(int));L.length=0;L.lsize=SIZE;}voidcreatlist(Sqlist&L)//線性表的建立{int*p;inte;L.elem=(int*)malloc(sizeof(int));printf("請輸入線性表的數(shù)據(jù)：");scanf_s("%d",&e);*(L.elem)=e;for(inti=1;i<10;i++){p=(int*)mall

5、oc(sizeof(int));scanf_s("%d",p);e=*p;*(L.elem+i)=e;L.length++;}}intinsertelem(Sqlist&L,inti,inte)//插入{int*p,*q;if(i<0

6、

7、i>L.length-1)exit(0);if(L.length>=L.lsize){L.elem=(int*)realloc(L.elem,(L.lsize+REMENT)*sizeof(int));if(!L.elem)exit(0);L.lsize+=REMENT;}q=L.elem+i;for(p=L.e

8、lem+L.length;p>=q;p--){*(p+1)=*p;}*q=e;++L.length;return0;}intdeletlist(Sqlist&L,inti)//刪除{int*p,*q;inte;if(i<0

9、

10、i>L.length)exit(0);q=L.elem+i;e=L.elem[i];for(p=L.elem+L.length;q<=p;q++)*q=*(q+1);--L.length;return0;}voidmain(){inti,a,b,k;//(1)do{printf("請選擇要進行的操作：.初始化2.建立3.插入

11、4.刪除5.退出");scanf("%d",&k);switch(k){case1:state_initlist(L);break;case2:creatlist(L);break;case3:state_initlist(L);//(3)creatlist(L);//(4)printf("請輸入插入線性表的位置i的值：");//(5)scanf_s("%d",&i);//(7)printf("請輸入要插入線性表的值:");//(8)scanf_s("%d",&a);//(9)b=insertelem(L,i,a);//(10)pri

12、ntf("輸出新的線性表的數(shù)據(jù)：");for(intj=0;j<=L.length;j++){printf("%d",*(L.ele