線性表的順序表示和實(shí)現(xiàn)

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) 日 期 2013.10.17 班 級(jí) 信計(jì)1201 學(xué) 號(hào) 201253100109 姓 名 成 績 一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹恳弧⒘私饩€性表的邏輯結(jié)構(gòu)特征：總存在第一個(gè)和最后一個(gè)元素；除第一個(gè)元素以外，每個(gè)元素總存在唯一一個(gè)直接前驅(qū)元素；除最后一個(gè)元素以外，每個(gè)元素總有唯一一個(gè)直接后繼元素。二、掌握線性表的基本操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)【實(shí)驗(yàn)原理】1、順序表的特點(diǎn)：邏輯上相鄰物理上相鄰；是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，其存儲(chǔ)位置可以用一個(gè)簡單、直觀的公式表示。2、線性表的動(dòng)態(tài)分配順

2、序存儲(chǔ)結(jié)構(gòu)：#define LIST_INIT_SIZE 6 /線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 2 /線性表存儲(chǔ)空間的分配增量Typedef structElemTYpe *elem; /存儲(chǔ)空間基址Int length; /當(dāng)前長度Int listsize; /當(dāng)前分配的存儲(chǔ)容量SqList;【實(shí)驗(yàn)環(huán)境】VC + 6.0二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】編寫主函數(shù)，調(diào)用順序表的初始化建空表、插入和刪除算法，調(diào)制運(yùn)行，得出結(jié)果?！緦?shí)驗(yàn)過程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）1、輸入順序表的初始化建空表、插入、刪除算法以及主函數(shù)：/線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)#defi

3、ne LIST_INIT_SIZE 6/線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 2/線性表存儲(chǔ)空間的分配增量typedef structElemType *elem;/存儲(chǔ)空間基址int length;/當(dāng)前長度int listsize;/當(dāng)前分配的存儲(chǔ)容量SqList;Status InitList_Sq(SqList &L)/構(gòu)造一個(gè)空的線性表L。/ InitList_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在順序線性表L中第i個(gè)位置之前插入新的元素e/ ListInsert_SqS

4、tatus ListDelete_Sq(SqList &L,int i,ElemType &e)/在線性順序表L中刪除第i個(gè)元素，并用e返回其值/ ListDelete_Sqvoid main()SqList L;int i; InitList_Sq(L); for(i=0;i<List_INIT_SIZE,i+)scanf("%d",&L.elemi);L.length+;for(i=0;i<L.length;i+)printf("%d ",L.elemi); printf("n"); ElemT

5、ype 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("%d",&i); ListDelete_Sq(L,i,e); for(i=0;i<L.length;i+)printf("%d ",L.elem(i);2、調(diào)試：發(fā)現(xiàn)在下列代碼中出現(xiàn)錯(cuò)誤：Status ListInsert_Sq(SqLis

6、t &L,int i,ElemType e)ListLength_Sq(L)+1if(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.elem

7、L.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ ListInsert_Sq出現(xiàn)的錯(cuò)誤為：error C2065: 'newbase' : undeclared identifier error C2065: 'q' : undeclared identifier error C2065: 'p' : undeclared identifier即newbase,q,p無定義，需要在Status ListInsert_Sq(SqList &L,int i,Elem

8、Type e) 給它們進(jìn)行定義為int *newbase;int *q;int *p;修改之后，繼續(xù)進(jìn)行調(diào)試，發(fā)現(xiàn)出現(xiàn)的錯(cuò)誤跟上述錯(cuò)誤類似，在使用它們之前忘記定義，修改的方法就是在前面給它們先定義后使用。另外，在調(diào)試過程中，還有一些小錯(cuò)誤，如：在for循環(huán)語句中，少了一個(gè)“)”及“；”等，依次修改過來。3.保存，運(yùn)行：在運(yùn)行框中依次輸入隨意六個(gè)數(shù)字，每個(gè)數(shù)字間用空格分開，按回車，則實(shí)現(xiàn)了順序表的建立；再輸入兩個(gè)數(shù)字，數(shù)字用空格隔開，前一數(shù)字（應(yīng)不大于六）表示在第幾個(gè)元素前插入，后一個(gè)數(shù)字表示插入的元素，按回車，由此實(shí)現(xiàn)了順序表的插入算法；再輸入一個(gè)數(shù)字（應(yīng)不大于七）表示把第幾個(gè)元素刪除，再回車

9、，則實(shí)現(xiàn)了順序表的刪除算法，最終，完成了運(yùn)行?！緦?shí)驗(yàn)結(jié)論】（結(jié)果）【實(shí)驗(yàn)小結(jié)】（收獲體會(huì)）在此次上機(jī)操作中，編寫主函數(shù)和相關(guān)算法完成線性表的順序表示和實(shí)現(xiàn)，慢慢地學(xué)會(huì)一些基本的調(diào)試，也加深了順序表的創(chuàng)建，插入，刪除算法的理解。三、指導(dǎo)教師評(píng)語及成績：評(píng) 語評(píng)語等級(jí)優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)告按時(shí)完成,字跡清楚,文字?jǐn)⑹隽鲿?邏輯性強(qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟詳細(xì),記錄完整,數(shù)據(jù)合理,分析透徹）4實(shí)驗(yàn)結(jié)論正確. 成 績： 指導(dǎo)教師簽名： 批閱日期：附錄1：源 程 序#include<stdio.h>#include<stdlib.h>#define TUR

10、E 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 6#define LISTINCREMENT 2typedef structElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList &L)/構(gòu)造一個(gè)空的線性表L。L.elem=(ElemType *)mall

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

12、1) return ERROR; /i值不合法if(L.length>=L.listsize) /當(dāng)前存儲(chǔ)空間已滿，增加分配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;-

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

14、L.length-1; /表尾元素的位置for(+p;p<=q;+p)*(p-1)=*p; /被刪除元素之后的元素左移-L.length; /表長減1return OK;/ ListDelete_Sqvoid main()SqList L;int i;InitList_Sq(L);for(i=0;i<LIST_INIT_SIZE;i+)scanf("%d",&L.elemi);L.length+;for(i=0;i<L.length;i+)printf("%d ",L.elemi);printf("n");E

15、lemType 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("%d",&i);ListDelete_Sq(L,i,e);for(i=0;i<L.length;i+)printf("%d ",*(L.elem+i);printf("n");附錄2：實(shí)驗(yàn)報(bào)告填寫說明 1實(shí)驗(yàn)項(xiàng)目名稱：要求與實(shí)驗(yàn)教學(xué)大綱一致。2實(shí)驗(yàn)?zāi)康模耗康囊鞔_，要抓住重點(diǎn)，符合實(shí)驗(yàn)教學(xué)大綱要求。3實(shí)驗(yàn)原理：簡要說明本實(shí)驗(yàn)項(xiàng)目所涉及的理論知識(shí)。4實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)用的軟、硬件環(huán)境。5實(shí)驗(yàn)方案（思路、步驟和方法等）：這是實(shí)驗(yàn)報(bào)告極其重要的內(nèi)容。概括整個(gè)實(shí)驗(yàn)過程。對(duì)于驗(yàn)證性實(shí)驗(yàn)，要寫明依據(jù)何種原理、操