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

1、長(zhǎng)春理工大學(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)： 姓 名： 1、 實(shí)驗(yàn)?zāi)康募耙? 、掌握用 Visual C+6.0 上機(jī)調(diào)試順序表的基本方法2、掌握順序表的基本操作，插入、刪除、查找等算法的實(shí)現(xiàn)基本要求 要求生成順序表時(shí)，可以鍵盤上讀取元素，用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)。2、 實(shí)驗(yàn)意義及原理當(dāng)我們要在順序表的第i個(gè)位置上插入一個(gè)元素時(shí)，必須先將順序表中第i個(gè)元素之后的所有元素依次后移一個(gè)位置， 以便騰空一個(gè)位置， 再把新元素插入到該位置。 若是欲刪除第 i 個(gè)元素時(shí)，也必須把第i 個(gè)元素之后的所有元素前移一個(gè)位置。3、 算法分析( 1)以下為

2、函數(shù)運(yùn)行結(jié)果狀態(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 structElemType *elem;/存

3、儲(chǔ)空間基址int length;/當(dāng)前長(zhǎ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);if(L.elem=NULL)exit(OVERFLOW);elseL.length=0;L.listsize=LISTINCREMENT;return OK;( 3)插入函數(shù)/函數(shù)名： ListInsert()/參數(shù)： S

4、qList 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+1)return ERROR;if(L.length>=L.listsize)newbase=(ElemType*)realloc(L.elem,L.listsize+LIS

5、TINCREMENT*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/初始條件：線性表L 已存在， 1<=i<=ListLength(L)/ 功能：將線性表L 中第 i 個(gè)數(shù)據(jù)元素刪除Stat

6、us ListDelet(Sqlist L,int i,ElemType e)if(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)=*p;-L.length; return OK;四、源代碼#include <iostream>using namespace std;#define MAXSIZE 20typedef int ElemType;typedef structElemType da

7、taMAXSIZE;int length;int listsize;SqList;/構(gòu)造空線性表Listbool InitList(SqList &L)for(int i=0;i<MAXSIZE;i+)L.datai=0;L.length=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,

8、int pos,ElemType &ptr) if(L.length<=0 | pos<1 | pos>L.length)return false;elseptr=L.datapos-1;return ptr;/查詢第 location 位置上的元素void locate(SqList L,int location)if(L.length>=location)cout<<" 查詢的元素為："<<L.datalocation-1<<endl;elsecout<<" 該位置沒有元素!&qu

9、ot;<<endl;/*在Sq中第pos2個(gè)位置插入新的數(shù)據(jù)元素Elem, L的長(zhǎng)度加1*/bool ListInsert(SqList &L, int pos2,ElemType Elem )/線性表空間不足，無法插入if (L.length = MAXSIZE)cout << " 空間不足，無法插入！ " << endl;return false;if (pos2 < 1 | pos2 > L.length + 1)cout << " 插入位置錯(cuò)誤！ " << endl;

10、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.datapos2 - 1 = Elem; /* 將新元素插入 */if(L.datapos2-1=Elem)/cout << " 添加元素成功 " << endl;L.length+;return true;elsecout << " 添加元素失敗*" &l

11、t;< endl;return false;刪除ps的第pos個(gè)數(shù)據(jù)元素，并用 pe返回其值，ps的長(zhǎng)度減1bool ListDelete(SqList &L, int pos, ElemType *pe)if (pos < 1 | pos > L.length)cout << " 刪除位置錯(cuò)誤！ " << endl; return false;else*pe = L.datapos - 1;/* 將刪除位置后繼元素前移*/for (int i = pos; i < L.length; i+)L.datai - 1 =

12、 L.datai;L.length-;return true;int ListLength(SqList Sq)return Sq.length;/主函數(shù)int main()SqList list;cout << " 構(gòu)造線性表List" << endl;InitList(list);/ 構(gòu)造線性表if(ListEmpty(list)/判斷是否為空cout << " 線性表為空" << endl;elsecout << " 線性表不為空"int num; / 要添加的元素的個(gè)

13、數(shù)cout<<" 輸入值的個(gè)數(shù)： "cin>>num;cout << " 輸入添加元素： " ;ElemType Elem;for (int i = 1 ; i < num+1; i+)/添加元素cin>>Elem;ListInsert(list, i, Elem);if(list.length<=list.listsize) cout<<" 添加元素成功 !"<<endl;if (!ListEmpty(list) /展示表內(nèi)容cout <<

14、; "list: " << endl;for (int i = 0 ; i < ListLength(list); i+) cout << list.datai << ' 'cout << endl;cout << " 請(qǐng)輸入要查詢?cè)氐奈恢茫?"int ele;int pre;cin >> ele;locate(list, ele);int result;cout << " 輸入要?jiǎng)h除元素的位置： "cin >> p

15、re;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

16、 ; i < ListLength(list); i+) cout << list.datai << ' ' cout<<endl<<" 插入新的數(shù)據(jù)元素 !n 請(qǐng)輸入插入位置： " int location;/插入元素的位置cin>>location;ElemType Elem1;cout<<" 輸入要插入的元素： "cin>>Elem1;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