1、長(zhǎng)春理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目： 線(xiàn)性表順序存儲(chǔ)試驗(yàn) 實(shí)驗(yàn)時(shí)間： 實(shí)驗(yàn)地點(diǎn)： 班 級(jí)： 學(xué) 號(hào)： 姓 名： 一、 實(shí)驗(yàn)?zāi)康募耙?1、掌握用Visual C+6.0上機(jī)調(diào)試順序表的基本方法2、 掌握順序表的基本操作，插入、刪除、查找等算法的實(shí)現(xiàn)基本要求 要求生成順序表時(shí)，可以鍵盤(pán)上讀取元素，用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)。二、 實(shí)驗(yàn)意義及原理當(dāng)我們要在順序表的第i個(gè)位置上插入一個(gè)元素時(shí)，必須先將順序表中第i個(gè)元素之后的所有元素依次后移一個(gè)位置，以便騰空一個(gè)位置，再把新元素插入到該位置。若是欲刪除第i個(gè)元素時(shí)，也必須把第i個(gè)元素之后的所有元素前移一個(gè)位置。三、 算法分析（1）以下為函數(shù)運(yùn)行結(jié)

2、果狀態(tài)代碼 #define TRUE 1#define FALSE 0#define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 （2）線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)#define LIST_INIT_SIZE 100 /線(xiàn)性表存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10 /線(xiàn)性表存儲(chǔ)空間分配增量 typedef int Status; /函數(shù)類(lèi)型，其值為為函數(shù)結(jié)果狀態(tài)代碼 typedef int ElemType; /假設(shè)數(shù)據(jù)元素為整型 typedef struct ElemType *

3、elem; /存儲(chǔ)空間基址 int length; /當(dāng)前長(zhǎng)度 int listsize; /當(dāng)前分配的存儲(chǔ)容量 Sqlist; （2）構(gòu)造函數(shù)/函數(shù)名：InitList()/參數(shù)：SqList L/初始條件：無(wú)/功能：構(gòu)造一個(gè)空線(xiàn)性表Status InitList(Sqlist L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(L.elem=NULL) exit(OVERFLOW); else L.length=0; L.listsize=LISTINCREMENT; return OK; （3）插入函數(shù)/函數(shù)名：

4、ListInsert()/參數(shù)：SqList L,int i,ElemType e/初始條件：線(xiàn)性表L已存在，1=i=ListLength(L)+1/功能：在線(xiàn)性表中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素eStatus ListInsert(Sqlist L,int i,ElemType e) int *q=&(L.elemi-1); ElemType *newbase,*p; if(i(L.length+1) return ERROR; if(L.length=L.listsize) newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT

5、*sizeof(ElemType); if(newbase=NULL) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;（4）刪除函數(shù)/函數(shù)名：ListDelete()/參數(shù)：SqList L,int i,Elemtype e/初始條件：線(xiàn)性表L已存在，1=i=ListLength(L)/功能：將線(xiàn)性表L中第i個(gè)數(shù)據(jù)元素刪除Status ListDelet(Sqlist L,int

6、i,ElemType e) if(iL.length) return ERROR; ElemType *p,*q; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; -L.length; return OK;四、 源代碼#include using namespace std;#define MAXSIZE 20typedef int ElemType;typedef structElemType dataMAXSIZE;int length;int listsize;SqList;/構(gòu)造空線(xiàn)性表Listb

7、ool InitList(SqList &L)for(int i=0;iMAXSIZE;i+)L.datai=0;L.length=0;L.listsize = MAXSIZE;return true;/判斷線(xiàn)性表是否為空bool ListEmpty(SqList L)if(L.length=0)return true;elsereturn false; /用ptr返回sql4第pos個(gè)元素的值ElemType GetElem(SqList &L,int pos,ElemType &ptr)if(L.length=0 | posL.length)return false;elseptr=L.d

8、atapos-1;return ptr;/查詢(xún)第location位置上的元素void locate(SqList L,int location) if(L.length=location)cout查詢(xún)的元素為：L.datalocation-1endl;elsecout該位置沒(méi)有元素!endl;/*在Sq中第pos2個(gè)位置插入新的數(shù)據(jù)元素Elem，L的長(zhǎng)度加1*/bool ListInsert(SqList &L, int pos2,ElemType Elem )/線(xiàn)性表空間不足，無(wú)法插入if (L.length = MAXSIZE)cout 空間不足，無(wú)法插入！ endl;return fal

9、se; if (pos2 L.length + 1)cout 插入位置錯(cuò)誤！ endl;return false; if (pos2 = pos2 - 1; i-) L.datai + 1 = L.datai; L.datapos2 - 1 = Elem; /* 將新元素插入 */if(L.datapos2-1=Elem)/cout 添加元素成功 endl;L.length+;return true;elsecout 添加元素失敗* endl;return false;/刪除ps的第pos個(gè)數(shù)據(jù)元素，并用pe返回其值，ps的長(zhǎng)度減1bool ListDelete(SqList &L, int

10、pos, ElemType *pe) if (pos L.length)cout 刪除位置錯(cuò)誤！ endl;return false;else*pe = L.datapos - 1;/* 將刪除位置后繼元素前移 */for (int i = pos; i L.length; i+)L.datai - 1 = L.datai;L.length-;return true; int ListLength(SqList Sq) return Sq.length;/主函數(shù)int main()SqList list;cout 構(gòu)造線(xiàn)性表List endl;InitList(list); /構(gòu)造線(xiàn)性表if(

11、ListEmpty(list) /判斷是否為空cout 線(xiàn)性表為空 endl;elsecout 線(xiàn)性表不為空;int num; /要添加的元素的個(gè)數(shù)coutnum;cout 輸入添加元素： ;ElemType Elem; for (int i = 1 ; i Elem; ListInsert(list, i, Elem);if(list.length=list.listsize) cout添加元素成功!endl; if (!ListEmpty(list) /展示表內(nèi)容 cout list: endl; for (int i = 0 ; i ListLength(list); i+) cout

12、list.datai ; cout endl;cout ele;locate(list, ele);int result;cout pre;bool re = ListDelete(list, pre, &result); cout delete: result endl;if(re)cout 刪除成功！ endl;elsecout 刪除失??！ endl;if (!ListEmpty(list) cout list: endl; for (int i = 0 ; i ListLength(list); i+) cout list.datai ; coutendllocation;ElemType Elem1;coutElem1;int Length = list.length; /記錄插入之前的表長(zhǎng)度ListInsert(list,location,Elem1);if(list.length = Length+1) cout插入元素成功!endl;if (!ListEmpty(list) cout list: endl; for (int i = 0 ; i ListLength(list); i+)