1、 .數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)項(xiàng)目名稱(chēng)線(xiàn)性表的順序表示與實(shí)現(xiàn)所屬課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)實(shí) 驗(yàn) 類(lèi) 型 驗(yàn)證型實(shí) 驗(yàn) 日 期 班 級(jí) 學(xué) 號(hào) 姓 名 成 績(jī) 一、 實(shí)驗(yàn)概述：實(shí)驗(yàn)?zāi)康? 線(xiàn)性表的邏輯結(jié)構(gòu)特征1.1 以元素在計(jì)算機(jī)“物理位置相鄰”來(lái)表示線(xiàn)性表中數(shù)據(jù)元素之間的邏輯關(guān)系。 1.2 有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)，沒(méi)有直接前驅(qū)，且僅有一個(gè)直接后繼；有且僅有一個(gè)終結(jié)結(jié)點(diǎn)，沒(méi)有直接后繼，且僅有一個(gè)直接前驅(qū)。1.3 其余部結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。2 掌握線(xiàn)性表的基本操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。實(shí)驗(yàn)原理1 順序表的特點(diǎn) 1.1 邏輯位置上相鄰和物理位置上相鄰1.2 是一種隨機(jī)存儲(chǔ)結(jié)

2、構(gòu)，其存儲(chǔ)位置可以用一簡(jiǎn)單直觀的公式表示2 順序表的類(lèi)C語(yǔ)言表示：#define LIST_INIT_SIZE 9 /線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 2 /線(xiàn)性表存儲(chǔ)空間的分配增量typedef struct ElemType * elem;/存儲(chǔ)空間基址 int length;/當(dāng)前長(zhǎng)度 int listsize;/當(dāng)前分配的存儲(chǔ)容量（以sizeof（ElemType）為單位）SqList;實(shí)驗(yàn)環(huán)境VC+6.0二、實(shí)驗(yàn)容實(shí)驗(yàn)方案編寫(xiě)主函數(shù)，調(diào)用順序表的初始化建空表，插入和刪除算法，調(diào)試運(yùn)行得出結(jié)果實(shí)驗(yàn)過(guò)程（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）8. 先將線(xiàn)性表的動(dòng)

3、態(tài)分配順序存儲(chǔ)結(jié)構(gòu),算法與主函數(shù)編入VC+6.0中typedef struct ElemType * elem; int length; int listsize;SqList;Status InitList_Sq(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;Status ListInsert_Sq(SqList &L,int i,E

4、lemType e) if (i<1|i>L.length+1) return ERROR; if(L.length>=L.listsize) newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType); if(! newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;- -p)*(p

5、+1)=*p; *q=e; +L.length; return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e) if(i<1)|(i>L.length) return ERROR;p=&(L.elemi-1);e=*p; q=L.elem+L.length-1; for(+p;p<=q;+p) *(p-1)=*p; -L.length; return OK;void main() SqList L; int i; InitList_Sq(L);for(i=0;i<LIST_INIT_SIZ

6、E;i+) scanf("%d",&L.elemi); L.length+; for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); ElemType e; scanf("%d%d",&i,&e); ListInsert_Sq(L,i,e); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); scanf(&quo

7、t;%d",&i); ListDelect_Sq(L,i,e); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");2.調(diào)試第一次出現(xiàn)的錯(cuò)誤：原因：由于許多變量未定義，以與沒(méi)有頭文件與宏定義所以錯(cuò)誤許多，還有更多錯(cuò)誤沒(méi)有顯示出來(lái)3.將以下語(yǔ)句編入程序中：#include "stdio.h"#include "stdlib.h"#define TRUE 1#define FALSE 0#define OK 1#define ER

8、ROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 9 #define LISTINCREMENT 2typedef int ElemType; typedef int Status;4.調(diào)試第二次出現(xiàn)以下錯(cuò)誤：原因：是在每個(gè)算法中有許多變量未定義，導(dǎo)致許多錯(cuò)誤5.再將語(yǔ)句: int *newbase; int *q; int *p;寫(xiě)入插入算法中；將語(yǔ)句： int *p; int *q;寫(xiě)入刪除算法中；6.調(diào)試第三次顯示沒(méi)有錯(cuò)誤：7.運(yùn)行第一次顯示結(jié)果為：8. 但運(yùn)行后的界面顯得很單調(diào)；要是忘記下一個(gè)算法是什

9、么就容易輸入出錯(cuò)，也不適合大眾使用；因此為了將程序優(yōu)化，所以在主函數(shù)中增加以下輸入輸出語(yǔ)句和條件語(yǔ)句；為了讓程序更加嚴(yán)謹(jǐn)，因此還加入一些循環(huán)語(yǔ)句。int i,p,q;p=2,q=2;printf("請(qǐng)輸入您想構(gòu)建的順序表（元素為%d個(gè)）:n",LIST_INIT_SIZE);printf("您構(gòu)建的順序表是:n");printf("請(qǐng)輸入您想在第幾個(gè)元素位置前插入元素:n",LIST_INIT_SIZE);while(i<=0|i>L.length)&&p>=0)printf("輸入的數(shù)字錯(cuò)

10、誤,（只剩下%d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n",p);-p;if(p<0)printf("原因:您輸入數(shù)字錯(cuò)誤過(guò)多,程序終止運(yùn)行n");return ERROR;scanf("%d",&i);printf("請(qǐng)輸入您想插入的數(shù):n");printf("形成的新順序表為:n");printf("請(qǐng)輸入您想刪除的是第幾個(gè)元素:n");while(i<=0|i>L.length)&&q>=0)printf("輸入的數(shù)字錯(cuò)誤,（只

11、剩下%d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n",q);-q;if(q<0)printf("原因:您輸入數(shù)字錯(cuò)誤過(guò)多,程序終止運(yùn)行n");return ERROR;printf("刪除的數(shù)為:n");printf("%dn",e);printf("形成的新順序表為:n");將語(yǔ)句scanf("%d%d",&i,&e);變?yōu)閟canf("%d",&i);scanf("%d",&e);9. 那么主函數(shù)包含的語(yǔ)句變?yōu)椋?/p>

12、main()SqList L;int i,p,q;p=2,q=2;InitList_Sq(L);printf("請(qǐng)輸入您想構(gòu)建的順序表（元素為%d個(gè)）:n",LIST_INIT_SIZE);for(i=0;i<LIST_INIT_SIZE;i+) scanf("%d",&L.elemi); L.length+;printf("您構(gòu)建的順序表是:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); Elem

13、Type e;printf("請(qǐng)輸入您想在第幾個(gè)元素位置前插入元素:n"); scanf("%d",&i);while(i<=0|i>L.length)&&p>=0)printf("輸入的數(shù)字錯(cuò)誤,（只剩下%d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n",p);-p;if(p<0)printf("原因:您輸入數(shù)字錯(cuò)誤過(guò)多,程序終止運(yùn)行n");return ERROR;scanf("%d",&i);printf("請(qǐng)輸入您想插入的數(shù):n&q

14、uot;);scanf("%d",&e);ListInsert_Sq(L,i,e);printf("形成的新順序表為:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi);printf("n");printf("請(qǐng)輸入您想刪除的是第幾個(gè)元素:n"); scanf("%d",&i);while(i<=0|i>L.length)&&q>=0)printf("輸入的數(shù)字錯(cuò)誤

15、,（只剩下%d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n",q);-q;if(q<0)printf("原因:您輸入數(shù)字錯(cuò)誤過(guò)多,程序終止運(yùn)行n");return ERROR;scanf("%d",&i);ListDelect_Sq(L,i,e);printf("刪除的數(shù)為:n");printf("%dn",e);printf("形成的新順序表為:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi);printf

16、("n");return 0;10. 調(diào)試第四次顯示沒(méi)錯(cuò)誤：11. 運(yùn)行第二次顯示結(jié)果為：12. 運(yùn)行第三次顯示結(jié)果為：13. 運(yùn)行第四次顯示結(jié)果為：這樣那么程序就完整了，清晰明了，用戶(hù)運(yùn)行的時(shí)候也容易知道自己要輸入什么了實(shí)驗(yàn)結(jié)論（結(jié)果）實(shí)驗(yàn)小結(jié)（收獲體會(huì)）1. 實(shí)驗(yàn)程序應(yīng)該多些注釋?zhuān)@樣方便人家讀懂自己編寫(xiě)的程序。2. 主函數(shù)中多增加一些printf函數(shù)，方便運(yùn)行時(shí)輸入數(shù)據(jù)3. 編寫(xiě)程序是細(xì)心一點(diǎn)，注意大小寫(xiě)，注意單詞拼寫(xiě)，還要注意分號(hào)4. 努力看書(shū)，要看懂算法的功能，結(jié)合C語(yǔ)言知識(shí)能快速調(diào)試并且改正錯(cuò)誤5. 要清楚算法不同于程序，算法就相當(dāng)于C語(yǔ)言中的定義函數(shù)功能語(yǔ)句且

17、是不完整的語(yǔ)句。三、指導(dǎo)教師評(píng)語(yǔ)與成績(jī)：評(píng) 語(yǔ)評(píng)語(yǔ)等級(jí)優(yōu)良中與格不與格1.實(shí)驗(yàn)報(bào)告按時(shí)完成,字跡清楚,文字?jǐn)⑹隽鲿?邏輯性強(qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過(guò)程（實(shí)驗(yàn)步驟詳細(xì),記錄完整,數(shù)據(jù)合理,分析透徹）4實(shí)驗(yàn)結(jié)論正確. 成 績(jī)： 指導(dǎo)教師簽名： 批閱日期：附錄1：源 程 序#include "stdio.h"#include "stdlib.h"#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LI

18、ST_INIT_SIZE 9 /線(xiàn)性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 2 /線(xiàn)性表存儲(chǔ)空間的分配增量typedef int ElemType; /自定義類(lèi)型名typedef int Status;typedef struct ElemType * elem;/存儲(chǔ)空間基址int length;/當(dāng)前長(zhǎng)度int listsize;/當(dāng)前分配的存儲(chǔ)容量（以sizeof（ElemType）為單位）SqList;Status InitList_Sq(SqList &L)/ 構(gòu)造一個(gè)空的線(xiàn)性表L L.elem=(ElemType*)malloc(LIST_INIT

19、_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); / 存儲(chǔ)分配失敗 L.length=0;/ 空表長(zhǎng)度為0 L.listsize=LIST_INIT_SIZE;/ 初始存儲(chǔ)容量return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e)/ 在順序線(xiàn)性表L的第i個(gè)元素之前插入新的元素e , i的合法值為1iListLength_Sq(L)+1int *newbase;int *q;int *p;if (i<1|i>L.length+1) return ERROR;/

20、i值不合法if(L.length>=L.listsize)/ 當(dāng)前存儲(chǔ)空間已滿(mǎn)，增加容量 newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if(! newbase)exit(OVERFLOW);/ 存儲(chǔ)分配失敗 L.elem=newbase;/ 新基址 L.listsize+=LISTINCREMENT;/ 增加存儲(chǔ)容量 q=&(L.elemi-1); / q為插入位置for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p

21、; / 插入位置與之后的元素右移 *q=e;/ 插入e +L.length;/ 表長(zhǎng)增1 return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e)/ 在順序線(xiàn)性表L中刪除第i個(gè)元素，并用e返回其值,i的合法值為1iListLength_Sq(L)int *p; int *q;if(i<1)|(i>L.length) return ERROR;/ i值不合法 p=&(L.elemi-1);/ p為被刪除元素的位置 e=*p; / 被刪除元素的值賦給e q=L.elem+L.length-1;/ 表尾

22、元素的位置 for(+p;p<=q;+p) *(p-1)=*p;/ 被刪除元素之后的元素左移 -L.length;/ 表長(zhǎng)減1return OK;main() SqList L;int i,p,q; p=2,q=2; InitList_Sq(L); printf("請(qǐng)輸入您想構(gòu)建的順序表（元素為%d個(gè)）:n",LIST_INIT_SIZE);for(i=0;i<LIST_INIT_SIZE;i+) scanf("%d",&L.elemi); L.length+; printf("您構(gòu)建的順序表是:n");for(i

23、=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); ElemType e; printf("請(qǐng)輸入您想在第幾個(gè)元素位置前插入元素:n",L.length); scanf("%d",&i);while(i<=0|i>L.length)&&p>=0)printf("輸入的數(shù)字錯(cuò)誤,（只剩下%d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n",p);-p;if(p<0)printf("原因:您輸

24、入數(shù)字錯(cuò)誤過(guò)多,程序終止運(yùn)行n");return ERROR;scanf("%d",&i); printf("請(qǐng)輸入您想插入的數(shù):n"); scanf("%d",&e); ListInsert_Sq(L,i,e); printf("形成的新順序表為:n"); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); printf("請(qǐng)輸入您想刪除的是第幾個(gè)元素:n",L.length); scanf("%d",&i);w