數(shù)據(jù)結(jié)構(gòu)線性表的順序表示和實(shí)現(xiàn)的實(shí)習(xí)報(bào)告

1、數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱 線性表的順序表示與實(shí)現(xiàn)所屬課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證型實(shí)驗(yàn)日期班級(jí)學(xué)號(hào)姓名成績(jī)一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹? 線性表的邏輯結(jié)構(gòu)特征1.1 以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表中數(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 其余內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。2 掌握線性表的基本操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)?！緦?shí)驗(yàn)原理】1 順序表的特點(diǎn)1.1 邏輯位置上相鄰和物理位置上相鄰1.2 是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，其存儲(chǔ)位置可以用一簡(jiǎn)單直觀的公式

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

3、構(gòu) , 算法與主函數(shù)編入 VC+6.0中typedef structElemType * 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,ElemType e)if (iL.len

4、gth+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)2*(p+1)=*p;*q=e;+L.length;return OK;Status ListDelect_Sq(SqLi

5、st &L,inti,ElemType &e)if(iL.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;iLIST_INIT_SIZE;i+)scanf(%d,&L.elemi);L.length+;for(i=0;iL.length;i+)printf(%d,L.elemi);printf(n);ElemType e;scanf(%d%

6、d,&i,&e);ListInsert_Sq(L,i,e);for(i=0;iL.length;i+)printf(%d,L.elemi);printf(n);scanf(%d,&i);ListDelect_Sq(L,i,e);for(i=0;iL.length;i+)printf(%d,L.elemi);printf(n);32. 調(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#

7、define OK 1#define ERROR 0#define INFEASIBLE-1#define OVERFLOW-2#define LIST_INIT_SIZE9#define LISTINCREMENT2typedef int ElemType;typedef int Status;4. 調(diào)試第二次出現(xiàn)以下錯(cuò)誤：4原因：是在每個(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ò)誤：57. 運(yùn)行第一次顯示結(jié)果為：8. 但運(yùn)行后的界面顯

8、得很單調(diào)；要是忘記下一個(gè)算法是什么就容易輸入出錯(cuò)，也不適合大眾使用；因此為了將程序優(yōu)化，所以在主函數(shù)中增加以下輸入輸出語(yǔ)句和條件語(yǔ)句；為了讓程序更加嚴(yán)謹(jǐn)，因此還加入一些循環(huán)語(yǔ)句。inti,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(iL.length)&p=0)printf(輸入的數(shù)字錯(cuò)誤, （只剩下 %d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n,p);-p;if(p0)printf(原因 :

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

10、e);變?yōu)?scanf(%d,&i);scanf(%d,&e);9. 那么主函數(shù)包含的語(yǔ)句變?yōu)椋簃ain()SqListL;inti,p,q;p=2,q=2;InitList_Sq(L);printf( 請(qǐng)輸入您想構(gòu)建的順序表（元素為 %d個(gè)） :n,LIST_INIT_SIZE); for(i=0;iLIST_INIT_SIZE;i+)scanf(%d,&L.elemi);L.length+;printf(您構(gòu)建的順序表是:n);for(i=0;iL.length;i+)printf(%d,L.elemi);printf(n);ElemType e;printf(請(qǐng)輸入您想在第幾個(gè)元素位置前

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

12、);scanf(%d,&i);while(iL.length)&q=0)printf(輸入的數(shù)字錯(cuò)誤, （只剩下 %d次重新輸入符合要求的數(shù)字的機(jī)會(huì)）n,q);-q;if(q0)printf(原因 : 您輸入數(shù)字錯(cuò)誤過(guò)多, 程序終止運(yùn)行 n);returnERROR;scanf(%d,&i);ListDelect_Sq(L,i,e);printf(刪除的數(shù)為 :n);printf(%dn,e);printf(形成的新順序表為:n);for(i=0;iL.length;i+)printf(%d,L.elemi);printf(n);return0;10. 調(diào)試第四次顯示沒(méi)錯(cuò)誤：811. 運(yùn)行第二

13、次顯示結(jié)果為：12. 運(yùn)行第三次顯示結(jié)果為：913. 運(yùn)行第四次顯示結(jié)果為：這樣那么程序就完整了，清晰明了，用戶運(yùn)行的時(shí)候也容易知道自己要輸入什么了10【實(shí)驗(yàn)結(jié)論（】結(jié)果）11【實(shí)驗(yàn)小結(jié)】（收獲體會(huì)）1. 實(shí)驗(yàn)程序應(yīng)該多些注釋，這樣方便人家讀懂自己編寫(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ǔ)句且是不完整的語(yǔ)句。三、指導(dǎo)教師評(píng)語(yǔ)及成績(jī)：評(píng)語(yǔ)等級(jí)評(píng)語(yǔ)及優(yōu)良中不及格

14、格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)教師簽名：批閱日期：12附錄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 LIST_INIT_SIZE9 / 線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT2 /

15、 線性表存儲(chǔ)空間的分配增量typedef int ElemType; /自定義類型名typedef int Status;typedef structElemType * elem;/存儲(chǔ)空間基址int length;/ 當(dāng)前長(zhǎng)度int listsize;/ 當(dāng)前分配的存儲(chǔ)容量（以sizeof（ElemType）為單位）SqList;Status InitList_Sq(SqList &L) / 構(gòu)造一個(gè)空的線性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);/ 存儲(chǔ)分

16、配失敗L.length=0; / 空表長(zhǎng)度為0L.listsize=LIST_INIT_SIZE;/ 初始存儲(chǔ)容量return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e)/ 在順序線性表 L 的第 i 個(gè)元素之前插入新的元素 e , i 的合法值為 1i ListLength_Sq(L)+1int *newbase;int *q;int *p;if (iL.length+1) return ERROR;/ i 值不合法if (L.length=L.listsize) / 當(dāng)前存儲(chǔ)空間已滿，增加容量newbase=(ElemType *

17、)realloc(L.elem,(L.listsize+LISTINCREMENT)* sizeof (ElemType); if (! newbase)exit(OVERFLOW); / 存儲(chǔ)分配失敗L.elem=newbase;/ 新基址L.listsize+=LISTINCREMENT;/ 增加存儲(chǔ)容量13q=&(L.elemi-1);/ q 為插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/ 插入位置及之后的元素右移*q=e;/ 插入 e+L.length; / 表長(zhǎng)增 1return OK;Status ListDelect_Sq(Sq

18、List&L,inti,ElemType &e)/在順序線性表L 中刪除第 i 個(gè)元素，并用e 返回其值 ,i 的合法值為1 i ListLength_Sq(L)int *p;int *q;if (iL.length)return ERROR;/ i 值不合法p=&(L.elemi-1);/ p 為被刪除元素的位置e=*p; / 被刪除元素的值賦給eq=L.elem+L.length-1; / 表尾元素的位置for(+p;p=q;+p)*(p-1)=*p; / 被刪除元素之后的元素左移-L.length; / 表長(zhǎng)減 1return OK;main()SqList L;int i,p,q;p=

19、2,q=2;InitList_Sq(L);printf( 請(qǐng)輸入您想構(gòu)建的順序表（元素為 %d 個(gè)） :n,LIST_INIT_SIZE); for (i=0;iLIST_INIT_SIZE;i+)scanf(%d,&L.elemi);L.length+;printf( 您構(gòu)建的順序表是:n);for (i=0;iL.length;i+)printf(%d,L.elemi);printf(n);ElemType e;printf( 請(qǐng)輸入您想在第幾個(gè)元素位置前插入元素:n,L.length);scanf(%d,&i);14while (iL.length)&p=0)printf( 輸入的數(shù)字錯(cuò)誤 ,（只剩下 %d 次重新輸入符合要求的數(shù)字的機(jī)會(huì)） n,p); -p;if (p0)printf( 原因 :您輸入數(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;iL.length;i+)printf(%d,L.elemi);printf(n);printf( 請(qǐng)輸入您想刪除的是第幾個(gè)元素:n,L.length);scanf(%d,&i);while (iL.length)&q=