數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告--112頁

1、長春理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告實(shí)驗(yà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í)，可以鍵盤上讀取元素，用順序存儲(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）線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)#define LIST_INIT_SIZE 100  /線性表存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10 /線性表存儲(chǔ)空間分配增量 typedef int Status; /函數(shù)類型，其值為為函數(shù)結(jié)果狀態(tài)代碼 typedef int ElemType; /假設(shè)數(shù)據(jù)元素為整型 typedef struct 

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

4、 if(L.elem=NULL)        exit(OVERFLOW);    else            L.length=0;        L.listsize=LISTINCREMENT;        return OK; 

5、60;  （3）插入函數(shù)/函數(shù)名：ListInsert()/參數(shù)：SqList L,int i,ElemType e/初始條件：線性表L已存在，1<=i<=ListLength(L)+1/功能：在線性表中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素eStatus ListInsert(Sqlist L,int i,ElemType e)    int *q=&(L.elemi-1);    ElemType *newbase,*p;    if(i<1|i>(L.length+

6、1)        return ERROR;    if(L.length>=L.listsize)            newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT*sizeof(ElemType);        if(newbase=NULL

7、)            exit(OVERFLOW);        L.elem=newbase;        L.listsize+=LISTINCREMENT;        for(p=&(L.elemL.length-1);p>=q;-p)  

8、;      *(p+1)=*p;    *q=e;    +L.length;    return OK;（4）刪除函數(shù)/函數(shù)名：ListDelete()/參數(shù)：SqList L,int i,Elemtype e/初始條件：線性表L已存在，1<=i<=ListLength(L)/功能：將線性表L中第i個(gè)數(shù)據(jù)元素刪除Status ListDelet(Sqlist L,int i,ElemType e)    if(

9、i<1|(i>L.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)=

10、*p;    -L.length;    return OK;四、 源代碼#include <iostream>using namespace std;#define MAXSIZE 20typedef int ElemType;typedef structElemType dataMAXSIZE;int length;int listsize;SqList;/構(gòu)造空線性表Listbool InitList(SqList &L)for(int i=0;i<MAXSIZE;i+)L.datai=0;L.leng

11、th=0;L.listsize = MAXSIZE;return true;/判斷線性表是否為空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 | pos<1 | pos>L.length)return false;elseptr=L.datapos-1;return ptr;/查詢第location位置上的

12、元素void locate(SqList L,int location) if(L.length>=location)cout<<"查詢的元素為："<<L.datalocation-1<<endl;elsecout<<"該位置沒有元素!"<<endl;/*在Sq中第pos2個(gè)位置插入新的數(shù)據(jù)元素Elem，L的長度加1*/bool ListInsert(SqList &L, int pos2,ElemType Elem )/線性表空間不足，無法插入if (L.length = MAX

13、SIZE)cout << "空間不足，無法插入！" << endl;return false; if (pos2 < 1 | pos2 > L.length + 1)cout << "插入位置錯(cuò)誤！" << endl;return false; if (pos2 <= L.length) /* 將要插入位置之后的數(shù)據(jù)元素向后移動(dòng)一位 */ for (int i = L.length - 1; i >= pos2 - 1; i-) L.datai + 1 = L.datai; L.da

14、tapos2 - 1 = Elem; /* 將新元素插入 */if(L.datapos2-1=Elem)/cout << "添加元素成功" << endl;L.length+;return true;elsecout << "添加元素失敗*" << endl;return false;/刪除ps的第pos個(gè)數(shù)據(jù)元素，并用pe返回其值，ps的長度減1bool ListDelete(SqList &L, int pos, ElemType *pe) if (pos < 1 | pos > L

15、.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)造線性表List" &l

16、t;< endl;InitList(list); /構(gòu)造線性表if(ListEmpty(list) /判斷是否為空cout << "線性表為空" << endl;elsecout << "線性表不為空"int num; /要添加的元素的個(gè)數(shù)cout<<"輸入值的個(gè)數(shù)："cin>>num;cout << "輸入添加元素：" ;ElemType Elem; for (int i = 1 ; i < num+1; i+) /添加元素cin

17、>>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 << list.datai << ' ' cout <<

18、 endl;cout << "請(qǐng)輸入要查詢?cè)氐奈恢茫?quot;int ele;int pre;cin >> ele;locate(list, ele);int result;cout << "輸入要?jiǎng)h除元素的位置："cin >> 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 << ' ' cout<<endl<<