數(shù)據(jù)結(jié)構(gòu)第一次課內(nèi)實(shí)驗(yàn)

1、數(shù)據(jù)結(jié)構(gòu)課內(nèi)實(shí)驗(yàn)報(bào)告學(xué)生姓名:及 學(xué) 號(hào)：學(xué) 院:理學(xué)院班 級(jí):課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目:實(shí)驗(yàn)一 順序表的基本操作指導(dǎo)教師姓名及職稱(chēng)：尚寶欣講 師方 向?qū)嶒?yàn)師 目 錄一、實(shí)驗(yàn)?zāi)康?二、實(shí)驗(yàn)內(nèi)容2三、實(shí)驗(yàn)要點(diǎn)及說(shuō)明2四、實(shí)現(xiàn)方法2五、實(shí)驗(yàn)結(jié)果3六、源程序清單5七、思考及總結(jié)12一、實(shí)驗(yàn)?zāi)康?. 了解順序表的結(jié)構(gòu)特點(diǎn)及有關(guān)概念；2. 理解順序表的存儲(chǔ)結(jié)構(gòu)；3. 掌握順序表的基本操作算法。二、實(shí)驗(yàn)內(nèi)容建立順序表，完成順序表的基本操作：初始化、插入、刪除、逆轉(zhuǎn)、輸出、銷(xiāo)毀, 置空表、求表長(zhǎng)、求前驅(qū)、求后繼、查找元素、判線性表是否為空。三、實(shí)驗(yàn)要點(diǎn)及說(shuō)明四、實(shí)現(xiàn)方法這次課內(nèi)實(shí)驗(yàn)所用的的編程計(jì)算機(jī)是XP

2、系統(tǒng)的，編程軟件是Visual C+ 6.0。抽象類(lèi)型的定義：1. 定義pData為指向整型數(shù)據(jù)的指針變量。2. 定義length為一個(gè)基本整型變量。3. 定義i為基本整型變量。（出現(xiàn)在順序的初始化和主函數(shù)中）4. 定義k為整型數(shù)據(jù)，并賦初值為0。（出現(xiàn)在插入，刪除，逆轉(zhuǎn)等操作中）5. 定義x為基本整型數(shù)據(jù)。（出現(xiàn)在主函數(shù)中）6. SeqList* L=NULL。（定義L為結(jié)構(gòu)體類(lèi)型的指針變量）下面是對(duì)于算法的詳細(xì)分析：1.順序表的初始化。判斷順序表是否為空。-若順序表為空，就為順序表L開(kāi)辟一個(gè)存儲(chǔ)空間，以便于之后向里面輸入數(shù)據(jù)，并進(jìn)行各種操作。-若順序表不為空，就初始化指針變量L-Data-

3、完成上述操作之后，就判斷上一次分配存儲(chǔ)空間時(shí)是否成功。-如果分配存儲(chǔ)空間失敗，就返回“空”。-否則，請(qǐng)用戶(hù)輸入順序表長(zhǎng)度，并初始化。-最后，返回順序表L。2.對(duì)順序表的插入操作?？疾齑鎯?chǔ)空間是否分配失敗或者線性表的長(zhǎng)度是否超過(guò)人為分配的總長(zhǎng)度或者i值是否合法。-如果，上述條件中，要是有一個(gè)成立，就提示用戶(hù)“順序表或插入位置有問(wèn)題”。并返回ERROR。-把插入的位置及以后的元素右移，返回OK。3.求直接后繼的操作?？疾祉樞虮硎欠駷榭眨⒖疾祉樞虮淼拈L(zhǎng)度是否為0，如果為0，則不存在直接后繼。-提示用戶(hù)順序表不存在或是為空表- 從第1個(gè)元素開(kāi)始找，一直找到倒數(shù)第二個(gè)元素為止，因?yàn)樽詈笠粋€(gè)元素必然不存

4、在直接后繼。-如果指定元素不存在直接后繼，就終止程序。4.求直接前驅(qū)的操作?？疾祉樞虮硎欠翊嬖冢樞虮硎欠駷榭?。-如果上述條件有一個(gè)存在，就提示用戶(hù)順序表不存在或是為空表。-從第2個(gè)元素開(kāi)始用順序查找法查找，因?yàn)榈谝粋€(gè)元素必然不存在直接前驅(qū)。-如果查找到，就返回這個(gè)元素。-如果沒(méi)有找到，就終止程序。5. 查找指定位置的元素?？疾祉樞虮硎欠翊嬖?，i的值是否合法。-如果順序表不存在或是為空表，就提示用戶(hù)“順序表不存在或?yàn)榭毡怼薄?如果，順序表存在而且i的值合法。-就返回這個(gè)位置的元素。6.順序表的逆轉(zhuǎn)操作。考察順序表長(zhǎng)度是否小于等于1，小于1表示其中沒(méi)有元素，等于1表示只有一個(gè)元素，不需要進(jìn)行逆轉(zhuǎn)

5、。-如果上述條件中有一個(gè)滿足，就返回ERROR。-把第一個(gè)元素和最后一個(gè)元素調(diào)換位置，第二個(gè)元素與倒數(shù)第二個(gè)元素調(diào)換位置。以此類(lèi)推，就可以完成逆轉(zhuǎn)操作了。7.順序表的刪除操作（按照序號(hào)）考察i是否合法。-若i不合法，就提示用戶(hù)，他想要?jiǎng)h除的這個(gè)元素不存在。并返回ERROE。-把i之前所在位置的后面的元素統(tǒng)一朝左移動(dòng)-返回OK。8.順序表的銷(xiāo)毀操作?？疾?L-pData是否占用空間。-如果占用，就將其釋放掉。-令L-pData為空。-將順序表長(zhǎng)度置為零，并返回OK。還有就是，輸出操作，置空順序表操作等，在這里不再一一贅述，下面已經(jīng)給出了詳細(xì)的運(yùn)行結(jié)果。 函數(shù)的調(diào)用關(guān)系：這段程序的調(diào)用關(guān)系比較簡(jiǎn)單

6、，就是由主函數(shù)依次調(diào)用“初始化順序表函數(shù)”“打印順序表函數(shù)”“插入數(shù)據(jù)操作” “打印順序表函數(shù)”“求后繼，前驅(qū)，指定位置的元素函數(shù)，并將打印順序表函數(shù)穿插其中”“逆轉(zhuǎn)順序表”“打印順序表函數(shù)”“刪除指定序號(hào)的元素” “打印順序表函數(shù)”“顯示目前的順序表函數(shù)” “打印順序表函數(shù)”“判斷線性表是否為空的函數(shù)” “打印順序表函數(shù)”“置空線性表函數(shù)” “打印順序表函數(shù)”“銷(xiāo)毀線性表函數(shù)” “打印順序表函數(shù)” 五、實(shí)驗(yàn)結(jié)果1.下面表示的是順序表的初始化： （圖1-1）2.下面表示的是順序表的插入操作：(圖1-2)3.求后繼：（圖1-3）4.求前驅(qū)：（圖1-4）5.求指定位置的元素：（圖1-5）6.順序表

7、的逆轉(zhuǎn)：（圖1-6）7.刪除操作：（圖1-7）8.求表長(zhǎng)：（圖1-8）9判斷順序表是否為空：（圖1-9）10.置空順序表：（圖1-10）11.銷(xiāo)毀順序表：（圖1-11）六、源程序清單#include /*此程序包含標(biāo)準(zhǔn)輸入輸出函數(shù)庫(kù)中的函數(shù)*/#include /*下面程序中出現(xiàn)的函數(shù)malloc()就被包含在這個(gè)函數(shù)庫(kù)里面*/#define OK 1 /*定義OK為1*/#define ERROR 0 /*定義ERROR為0*/int MAX_SIZE = 100; /*開(kāi)辟一個(gè)盡可能大的存儲(chǔ)順序表的空間*/typedef int DataType; /*定義DataType也表示int型數(shù)

8、據(jù)，以后DataType出現(xiàn)的話當(dāng)做int型處理。*/*描述順序表*/typedef struct DataType* pData; /*定義pData為指向整型數(shù)據(jù)的指針變量*/int length; /*定義length為一個(gè)基本整型變量*/SeqList;/*順序表的初始化*/SeqList* InitList(SeqList* L)int i; /*定義i為基本整型變量*/if (NULL=L) /*并不是每次運(yùn)行程序，都需要將順序表初始化的，故可在這里做一個(gè)判斷*/L=(SeqList*)malloc(sizeof(SeqList); /*開(kāi)辟一個(gè)跟SeqList一樣大的內(nèi)存空間給L

9、*/L-pData=(DataType*)malloc(MAX_SIZE*sizeof(DataType); /*給指針變量分配存儲(chǔ)空間*/if(!L-pData) /*如果上一步分配存儲(chǔ)空間失敗*/return NULL; /*返回空*/printf(請(qǐng)輸入線性表長(zhǎng)度：); /*請(qǐng)用戶(hù)輸入線性表長(zhǎng)度*/scanf(%d,&L-length); /*把輸入的數(shù)據(jù)存儲(chǔ)在L-length里面*/printf(為線性表賦值：); /*提示用戶(hù)給線性表賦值*/for(i=0;ilength-1;i+) /*依次存儲(chǔ)輸入的數(shù)值*/scanf(%5d,&L-pDatai);return L; /*返回L*

10、/*順序表的銷(xiāo)毀*/int DestroyList(SeqList* L)if(L-pData) /*如果L-pData不為零*/free(L-pData); /*釋放L-pData所占用的存儲(chǔ)空間*/L-pData=NULL; /*令L-pData為空*/L-length=0; /*將線性表長(zhǎng)度置為零*/return OK; /*返回1*/*插入一個(gè)元素*/int InsertElem(SeqList* L, DataType x, int i)int k=0; /*定義k為整型數(shù)據(jù)，并賦初值為0*/if(!L-pData | L-length=MAX_SIZE | i-1L-length)

11、 /*如果存儲(chǔ)空間分配失敗或者線性表的長(zhǎng)度超過(guò)人為分配的總長(zhǎng)度或者i值不合法*/printf(順序表或是數(shù)據(jù)位置有問(wèn)題, 不能插入!n); /*輸出順序表或是數(shù)據(jù)結(jié)構(gòu)有問(wèn)題，不能插入*/return ERROR; /*返回ERROR*/for(k=L-length-1; k=i-1; k-) /*插入的位置及以后的元素右移*/L-pDatak+1=L-pDatak;L-pDatai-1=x;L-length+;return OK; /*返回OK*/*按照序號(hào)刪除順序表中的數(shù)據(jù)*/int DeleteElem(SeqList* L, int i)int k; /*定義k為基本整型變量*/if(i

12、L-length) /*考察i是否合法*/printf(此元素不存在！n); /*輸出此元素不存在*/return ERROR; /*返回ERROR*/for(k=i; klength; k+) /*把i之前所在位置的后面的元素統(tǒng)一朝左移動(dòng)*/ / 注意: 若DataType里面有指針變量的話, 應(yīng)先釋放其占用的空間L-pDatak-1=L-pDatak; L-length-;return OK; /*返回OK*/*逆轉(zhuǎn)順序表*/int ReverseList(SeqList* L)int k=0; /*定義k為基本整型變量，并初始化為0*/DataType temp; /*定義temp為Da

13、taType型變量*/ if (L-length=1) /考察順序表長(zhǎng)度是否小于等于1，小于1表示其中沒(méi)有元素，等于1表示只有一個(gè)元素，不需要進(jìn)行逆轉(zhuǎn)。return ERROR; /返回ERRORfor(k=0; klength/2; k+) /把第一個(gè)元素和最后一個(gè)元素調(diào)換位置，第二個(gè)元素與倒數(shù)第二個(gè)元素調(diào)換位置。以此類(lèi)推，就可以完成逆轉(zhuǎn)操作了temp=L-pDatak;L-pDatak=L-pDataL-length-1-k;L-pDataL-length-1-k=temp;return OK; /返回OKvoid PrintDataType(DataType x) / 方便使用，可以隨時(shí)

14、打印x的值 printf(%d, x); /以基本整型數(shù)據(jù)輸出x的值printf(n); /使光標(biāo)跳到下一行/*輸出這個(gè)順序表*/ void PrintList(SeqList* L)int k=0; /定義k為基本整型數(shù)據(jù)，并賦初值為0if(!L-pData) /考察順序表是否被分配了內(nèi)存printf(順序表不存在!n); /輸出“順序表不存在!”if(0=L-length) /考察順序表是否為空printf(順序表是空的!n);printf(-n);for(k=0; klength; k+) /一次輸出順序表中存儲(chǔ)的數(shù)值PrintDataType(L-pDatak);printf(-n);

15、/*置空表*/int SetEmpty(SeqList* L)if(!L-pData) /考察順序表是否被分配了存儲(chǔ)空間return ERROR; /返回ERRORL-length=0; /置空線性表return OK; /返回OK/*求順序表的長(zhǎng)度*/int GetListLength(SeqList* L)if(L-pData) /如果順序表不為空return L-length; /返回順序表的長(zhǎng)度return ERROR;/*求直接前驅(qū)*/DataType GetPrior(SeqList* L, DataType x)int k=0;if(!L-pData | 0=L-length)p

16、rintf(順序表不存在或是為空表!n);for (k=1; klength; k+) / 從第2個(gè)元素開(kāi)始找，因?yàn)榈谝粋€(gè)元素必然不存在直接前驅(qū)if (L-pDatak=x)return L-pDatak-1; /返回作為指定元素直接前驅(qū)的元素exit(1); /結(jié)束程序/*求直接后繼*/DataType GetNext(SeqList* L, DataType x)int k=0; /定義k為基本整型變量，并賦初值為0if(!L-pData | 0=L-length) /考察順序表是否為空，并考察順序表的長(zhǎng)度是否為0，如果為0，則不存在直接后繼。printf(順序表不存在或是為空表!n);f

17、or (k=0; klength-1; k+) /從第1個(gè)元素開(kāi)始找，一直找到倒數(shù)第二個(gè)元素為止，因?yàn)樽詈笠粋€(gè)元素必然不存在直接后繼if (L-pDatak=x) /用順序查找法，逐個(gè)對(duì)照，考察線性表中是否存在那個(gè)指定的元素return L-pDatak+1;exit(1); /結(jié)束程序/*查找指定位置的元素*/DataType GetElem(SeqList* L, int i)if(0=i | !L-pData | iL-length) /考察順序表是否存在，i的值是否合法printf(順序表不存在或是為空表!n); /輸出“順序表不存在或是為空表!”return L-pDatai-1;

18、/返回第i個(gè)數(shù)據(jù)元素DataType GetPosition(SeqList* L, DataType x) /*查找指定元素所在的位置*/int k=0; /定義k為基本整型變量，并賦初值為0if(!L-pData)printf(順序表不存在!n); /輸出“順序表不存在!”for(k=0; klength; k+) /用順序查找的方法，把指定的數(shù)據(jù)元素依次和表中原本就存在的數(shù)據(jù)元素進(jìn)行比較if (x=L-pDatak)return k+1;return -1; /表示順序表中無(wú)此元素int IsEmpty(SeqList* L) /*判斷順序表是否為空*/if(!L-pData) prin

19、tf(順序表不存在!n);else return ERROR;void main() /*定義主函數(shù)為空*/int x; /*定義x為基本整型數(shù)據(jù)*/int i; /*定義i為基本整型數(shù)據(jù)*/SeqList* L=NULL;L=InitList(L); / 初始化順序表PrintList(L); / 打印順序表printf(請(qǐng)輸入你要插入的元素以及你需要將這個(gè)元素插入的位置(把兩個(gè)數(shù)據(jù)用逗號(hào)隔開(kāi))：); /*這四行的作用把指定的元素插入到指定的位置處，并打印結(jié)果*/scanf(%d,%d,&x,&i);InsertElem(L, x, i); / 把元素x插入到第i個(gè)位置PrintList(L

20、); / 打印順序表printf(請(qǐng)輸入你想求后繼的那個(gè)元素：n); /*這四行的作用是查找指定元素的直接后繼，并打印結(jié)果*/scanf(%d,&x);printf(%d的直接后繼是:n,x);PrintDataType(GetNext(L, x);printf(請(qǐng)輸入你想求前驅(qū)的那個(gè)元素：n); /*這四行的作用是查找指定元素的直接前驅(qū)，并打印結(jié)果*/scanf(%d,&x);printf(%d的直接前驅(qū)是：n,x);PrintDataType(GetPrior(L, x);printf(請(qǐng)輸入你想查詢(xún)第幾個(gè)元素：n); /*這四行的作用是查找指定序號(hào)的元素，并打印結(jié)果*/scanf(%d,&i);printf(第%d個(gè)元素是：n,i);PrintDataType(GetElem(L, i);printf(逆轉(zhuǎn)之后的結(jié)果如下所示：n); /*這三行程序的作用是逆轉(zhuǎn)順序表，并把逆轉(zhuǎn)之后的結(jié)果打印出來(lái)*/ReverseList(L); /逆轉(zhuǎn)順序表PrintList(L); / 打印順序表printf(請(qǐng)輸入您想要?jiǎng)h除的元素序號(hào)：); /*這五行程序的作用是根據(jù)序號(hào)刪除你想要?jiǎng)h除的元素*/ scanf(%d,&i);Del