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

1、數(shù)學與計算科學學院實驗報告實驗項目名稱 線性表的順序表示與實現(xiàn) 所屬課程名稱數(shù)據(jù)結(jié)構(gòu)實驗類型驗證型實驗日期 班 級學 號姓 名成 績實驗概述:【實驗目的】1線性表的邏輯結(jié)構(gòu)特征1.1以元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏 輯關(guān)系。1.2有且僅有一個開始結(jié)點，沒有直接前驅(qū)，且僅有一個直接后繼；有且僅 有一個終結(jié)結(jié)點，沒有直接后繼，且僅有一個直接前驅(qū)。1.3其余內(nèi)部結(jié)點都有且僅有一個直接前驅(qū)和一個直接后繼。2掌握線性表的基本操作在順序存儲結(jié)構(gòu)上的實現(xiàn)?！緦嶒炘怼?順序表的特點1.1邏輯位置上相鄰和物理位置上相鄰1.2是一種隨機存儲結(jié)構(gòu)，其存儲位置可以用一簡單直觀的公式表示

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

3、結(jié)構(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.le ngth=0;L.listsize=LIST_INIT_SIZE;return OK;Status List In sert_Sq(SqList &L,i nt i,ElemType e)if (iL.le

4、ngth+1) return ERROR;if(L.len gth=L .li stsize)newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType); if(! newbase)exit(OVERFLOW);L.elem=n ewbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL .len gth-1);p=q;-p)*(p+1)=*p;*q=e;+L .len gth; return OK;Status ListDel

5、ect_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L .len gth-1;for(+p;p=q;+p)*(p-1)=*p;-L .len gth; return OK;void main()SqList L;int i;In itList_Sq(L); for(i=0;iLIST_INIT_SIZE;i+)scan f(%d,&L.elemi); L.len gth+; for(i=0;iL .len gth;i+) prin tf(%d,L .elemi);

6、prin tf(n);ElemType e;sca nf(%d%d, &i,& e);ListI nsert_Sq(L,i,e);for(i=0;iL .len gth;i+) prin tf(%d,L .elemi);prin tf(n);sca nf(%d,&i);ListDelect_Sq(L,i,e);for(i=0;iL .len gth;i+) prin tf(%d,L .elemi);prin tf(n);2. 調(diào)試第一次出現(xiàn)的錯誤:cpp（y）-errorcpp)-errorcpp(3)errorcpp(6)-啟 rrorcpp(e)errorcpp(8)aFatalC214：

7、Lordt|i?-tla ur Lypt? spt?tiFiersC2146: 5i|ritax error : missing ; before identifier InitList _Sq C2591:1 Status * : missing storage-class or type pocifiererror C130*urep&cted pnd oF Fil found原因：由于許多變量未定義，以及沒有頭文件與宏定義所以錯誤許多，還有更多錯 誤沒有顯示出來3. 將以下語句編入程序中:#include stdio.h#inelude stdlib.h#define TRUE 1#de

8、fine FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 9#define LISTINCREMENT 2 typedef int ElemType;typedef int Status;4. 調(diào)試第二次出現(xiàn)以下錯誤:.cpp(9) : error C2965; *ncMbase : Ufidrclrrd identifier eppe薊 :trror 020;: Cdniml cutivcrt fruin ibl *f tv inLrpi rirp

9、rprpt cT r J c-ryi p r cr Funrttnnryip r；r.cpp(3S : error- : cannot convert fram int1 ta 1int *pe to pointer type requires i pinterprrt cast, C style cast or functioncast.) : t-rrtir C?965: .cpp)(Ji1 : error C2JPiU： * = reinterpret oast, a C-stle 工: trror CZ905: p.rppl即2:frrur cpiuin： = reinterpretc

10、ast, 2 C-stloinLinr-:umJecltireij iJentifii?r:cannot convert +rom int 備* toor Function-style cjst;uiideLldreL iJetitifier:cannnr cflruprt 卡ram -i nr * tn cast oi* Punction-ftlc cstes a reinterpret cast, a Cstyle cast or Function-stle cast asFus _cpp02) tasfiis cpp(42) asFus.cpp(42) asfuscpp(U3) 需弓fu

11、與 _cppcpp(51) asfu.cpp(51)errorerror error errorerror rr orerrorerror err orC21OO: illegal indirectioinC21oo： illegal indirectionC2196: 1= : left operand must be 1-ualueC210C: illegalC2018:C20i8:C2918：C2C18：unknown unicnoun unknown unknownC244C：indirection character 10xa11 character * character 0xa1

12、* character Oxa1*:cannot conuert from int to * intes a reinterpret cast * a C-style cast or function-style cast us _cpp(52) : error C2018: unknown character * 0xa1* us _cpp52) : error C2 018: unknown character Qxa!*FUS.cpp(52)fus .cpp(S2)FUS .cpp(52)fU5.cpp(52)Fvscpp(52)麗scpp(53)error error error er

13、ror error errorC2 018：C2EMB：C2018： C2 01：unknown unknovjn unknovm unkin omcharacter chractr character character Oxal10xa1 Oxal1C210O: illegalC240:indirection :cannot convert from *int *p to intC2106: : left operand must be 1-ualuea reinterpretcast, a Cstyle cast or functionstyle cast fvs.cppCSS) : e

14、rror C2100: illegal indirection Fus.cpp(55) : error C2100: illegal indirection Fus.cpp(55) : error 原因：是在每個算法中有許多變量未定義，導致許多錯誤 5.再將語句：int *newbase;int *q;int *p;寫入插入算法中;將語句：int *p;int *q;寫入刪除算法中;6. 調(diào)試第三次顯示沒有錯誤:Compiling asFvs (7ppasfus.obj - & error(s), 0 warning(s)7. 運行第一次顯示結(jié)果為:逹:作呂謐搞結(jié)昭理序草精所埶回12 34 5

15、6 78 9*12345671196782346?856?892346786?B9Pressanykevto cont inuearrrIZI8. 但運行后的界面顯得很單調(diào)；要是忘記下一個算法是什么就容易輸入出錯，也 不適合大眾使用；因此為了將程序優(yōu)化，所以在主函數(shù)中增加以下輸入輸出語句 和條件語句；為了讓程序更加嚴謹，因此還加入一些循環(huán)語句。int i,p,q;p=2,q=2;prin tf(”請輸入您想構(gòu)建的順序表(元素為c個)：n,LIST_INIT_SIZE);printf(”您構(gòu)建的順序表是:n);prin tf(請輸入您想在第幾個元素位置前插入元素:n, LIST_INIT_SIZ

16、E);while(iL.le ngth) &p=0)printf(輸入的數(shù)字錯誤，(只剩下畝重新輸入符合要求的數(shù)字的機會)n,p);-p;if(p0)printf( 原因:您輸入數(shù)字錯誤過多，程序終止運行n”)；return ERROR;scan f(%d, &i);printf(”請輸入您想插入的數(shù):n);printf(”形成的新順序表為:n);printf(”請輸入您想刪除的是第幾個元素:n);while(iL.le ngth) &q=0)printf(輸入的數(shù)字錯誤，(只剩下畝重新輸入符合要求的數(shù)字的機會)n,q);-q;if(q0)printf(”原因：您輸入數(shù)字錯誤過多,程序終止運行

17、n”)；return ERROR;printf(刪除的數(shù)為:n);prin tf(%dn ”,e);printf(”形成的新順序表為:n);將語句 seanf(%d%d,&i,&e);變?yōu)?seanf(%d,&i);scanf(%d,&e);9. 那么主函數(shù)包含的語句變?yōu)椋簃ain ()SqList L;int i,p,q;p=2,q=2;In itList_Sq(L);printf(請輸入您想構(gòu)建的順序表(元素為d個)：n,LIST_INIT_SIZE);for(i=0;iLIST_INIT_SIZE;i+)scan f(%d,&L.elemi);L.len gth+;printf(您構(gòu)建的

18、順序表是:n);for(i=0;iLen gth;i+)prin tf(%d, L.elemi);prin tf(n ”);ElemType e;prin tf(請輸入您想在第幾個元素位置前插入元素:n);scan f(%d, &i);while(iL.le ngth)&p=0)n,p);printf(輸入的數(shù)字錯誤，(只剩下4次重新輸入符合要求的數(shù)字的機會)-p;if(p0)printf( 原因：您輸入數(shù)字錯誤過多，程序終止運行n”)；return ERROR;scan f(%d,&i);printf(請輸入您想插入的數(shù):n);scan f(%d, &e);List In sert_Sq(L

19、,i,e); printf(”形成的新順序表為:n);for(i=0;iLen gth;i+)prin tf(%d,L .elemi);prin tf(n);prin tf(請輸入您想刪除的是第幾個元素:n);sca nf(%d,&i);while(iL.le ngth)&q=0)n,q);printf(輸入的數(shù)字錯誤，(只剩下4次重新輸入符合要求的數(shù)字的機會)-q;if(q0)printf( 原因：您輸入數(shù)字錯誤過多，程序終止運行n”)；return ERROR;scan f(%d,&i);ListDelect_Sq(L,i,e);printf( 刪除的數(shù)為:n);prin tf(%dn,e

20、); printf(”形成的新順序表為:n);for(i=0;iLen gth;i+)prin tf(%d,L .elemi);prin tf(n ”);return 0;10. 調(diào)試第四次顯示沒錯誤：uunt xyui auxutt.i忖丄Compilingasfvs.cppasfus.obj - Q error(s)r 0 warning(s)11.運行第二次顯示結(jié)果為:（只剩下2次重新輸入符合要求的數(shù)字的機會） （只剩下曲重新輸入符合要求的數(shù)字的機會） （只剰下苗枕重新輸入符合要求的數(shù)字的機會）犢輸入您想構(gòu)建的順序表（元素為乎個）：123456789您構(gòu)建的順序表是= 22456789請

21、輸入您想在第幾個元素位置前插入元素10輸入的數(shù)字錯誤串入的數(shù)字錯誤為入瓣字髓原因遜輸入翳Press any key to continue12.運行第三次顯示結(jié)果為:重:（只剩下2次重新輸入符合要求的數(shù)字的機會） （只剩下1次重新輸入符合要求的數(shù)字的機會）A簷合要求的數(shù)字的機會） 運行幘輸入您擔構(gòu)建的順序表（元素為號個）：12 334 S3 5 3 536 7 4 7您構(gòu)建的順序表杲：123345353536?47請輸入您想在第幾個元素位置前插入元素匚87很中的數(shù)字錯誤.（只剩下瑙重新輸入符合要求的數(shù)字的機會） 轎頭的數(shù)字錯誤.（只剩下1次重新輸入符合要求的數(shù)字的機會） 青輸入您想插入的數(shù)二3

22、234阿成的新順序表為:1233453533234536747幘輸入您想刪除的是第幾個元素：90秒入的數(shù)字錯誤謚入的數(shù)字錯誤Piess any kwy to continueH：Debug性表的咳序表兩W實現(xiàn)心己*H:De bug時臨?；騾虮硪黈實現(xiàn)芒灼耳13.運行第四次顯示結(jié)果為:請輸入您想構(gòu)建的順序表（元素為9個）=1 2 3 4 E 6 7 S 9您構(gòu)建的順序表杲：22456789請輸入您想在第幾個元素位置前插入元素二18輸入的數(shù)字錯誤.（只乘U下瞅重新輸入符合要求的數(shù)字的機會） 常入的數(shù)字錯誤.（只剩Ft枕重新輸入符合要求的數(shù)字的機會） 青輸入您想插入的數(shù)：6183形成的新順序表為；

23、彳 744 C 仇 （曲4.5 Q o睛輸入您想刪除的是第幾個元素：13輸入的數(shù)字諸誤.（只剩下2次重新輸入符合要求的數(shù)字的機會） 易入的數(shù)字錯誤，（只剩下丄次重新輸入符合要求的數(shù)字的機會） 電除的數(shù)為：協(xié)咸的新順序表為=123456183?89Press ani y to comtinue1刑這樣那么程序就完整了，清晰明了，用戶運行的時候也容易知道自己要輸入什么 了【實驗結(jié)論】（結(jié)果）i曲諜性義的1驚表示與實現(xiàn)心bL 口 |屈 *3幘輸入您想構(gòu)建的順序表（元素為9個廠123 434 8395 348 349 934 923 523 937欣構(gòu)建的順序表是：123434839534834993

24、492352393?請輸入您想在第幾個元素位置前荷入元素：爲入的數(shù)字錯誤亠（只剩下煤董新輸入符合要求的數(shù)字的機會）隋輸入您想插入的數(shù)，84?8旳成的新順序表為匕12343483953483499349238478523937辰輸入您想刪除的是第幾個元素=踣V的數(shù)字錯誤.只乘R次重新輸入符合要求的數(shù)字的機會） 初除的數(shù)為S523阿成的新順序表為:123434839534834?9349238478937Press any key to cont inme【實驗小結(jié)】（收獲體會）1. 實驗程序應該多些注釋，這樣方便人家讀懂自己編寫的程序。2. 主函數(shù)中多增加一些printf函數(shù)，方便運行時輸入數(shù)據(jù)

25、3. 編與程序是細心 點，注意人小寫，注意單詞拼寫，還要注意分號4. 努力看書，要看懂算法的功能，結(jié)合 C語言知識能快速調(diào)試并且改正錯誤5. 要清楚算法不同于程序，算法就相當于 C語言中的定義函數(shù)功能語句且是不完 整的語句。三、指導教師評語及成績：評語評語等級優(yōu)良中及格不及格1.實驗報告按時完成，字跡清楚,文字敘述流暢,邏輯性強2.實驗方案設(shè)計合理3.實驗過程（實驗步驟詳細，記錄完整，數(shù)據(jù)合理,分析透徹）4實驗結(jié)論正確.成績：指導教師簽名：批閱日期：附錄1源程序#include stdio.h#inelude stdlib.h#define TRUE 1#define FALSE 0#defi

26、ne OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 9 /線性表存儲空間的初始分配量#define LISTINCREMENT 2 /線性表存儲空間的分配增量typedef int ElemType; 自定義類型名typedef int Status;typedef structElemType * elem;/存儲空間基址int length;/當前長度int listsize;/當前分配的存儲容量(以 sizeof( ElemType )為單位)SqList;Status

27、InitList_Sq(SqList &L) / 構(gòu)造一個空的線性表 LL.elem=(ElemType*)malloc(LIST_INIT_SIZE* sizeof(ElemType);if(!L.elem) exit(OVERFLOW); / 存儲分配失敗L.length=O; /空表長度為0L.listsize=LIST_INIT_SIZE; / 初始存儲容量 return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e)/在順序線性表 L的第i個元素之前插入新的 元素 e, i 的合法值為 1 w i ListLength_Sq(L

28、)+1int *newbase;int *q;int *p;if (iL.length+1) return ERROR;/ i 值不合法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); / q

29、為插入位置for(p=&(L.elemLen gth_1);p=q;_p)*(p+1)=*p; /插入位置及之后的元素右移*q=e; 插入 e+L.length; / 表長增 1return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e)/ 在順序線性表 L 中刪除第 i 個元素，并用 e返回其值,i的合法值為1 i ListLength_Sq(L)int *p;int *q;if(iL.length) return ERROR;/ i 值不合法p=&(L.elemi-1); / p為被刪除元素的位置e=*p; II被刪除元素的值賦給

30、eq=L.elem+L.length-1; / 表尾元素的位置for(+p;p=q;+p)*(p-1)=*p; /被刪除元素之后的元素左移-L.length;/ 表長減 1return OK;main ()SqList L;int i,p,q;p=2,q=2;In itList_Sq(L);printf(請輸入您想構(gòu)建的順序表(元素為%d個):n,LIST_INIT_SIZE);for(i=0;iLIST_INIT_SIZE;i+)scan f(%d,&L.elemi);L.len gth+;printf(您構(gòu)建的順序表是:n);for(i=0;iLen gth;i+)prin tf(%d,L .elemi);prin tf(n);ElemType e;printf(請輸入您想在第幾個元素位置前插入元素:n,L.length);sea