江西理工大學(xué)軟件學(xué)院計(jì)算機(jī)類課程實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：姓名：學(xué)號(hào)：江西理工大學(xué)軟件學(xué)院實(shí)驗(yàn)二：順序表2012年11月10日一.實(shí)驗(yàn)?zāi)康恼莆枕樞虮淼倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、以及操作。二.問題描述線性表是由n(n≥0)個(gè)元素（結(jié)點(diǎn)）a1,a2,…,an組成的有限序列，其中ai中的i稱為該數(shù)據(jù)元素的位置（序號(hào)），n為數(shù)據(jù)元素的個(gè)數(shù)（表的長度），當(dāng)n等于0時(shí)稱為空表。按邏輯次序依次把數(shù)據(jù)元素存放在一組連續(xù)的地址存儲(chǔ)單元里的線性表稱為順序表。在這里，我們通過C++中的動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)順序表的存放，并通過建立順序表類實(shí)現(xiàn)它的各種操作。三.實(shí)驗(yàn)要求實(shí)現(xiàn)順序表的三個(gè)框架操作：隨機(jī)生成，用已有順序表初始化另一個(gè)順序表，輸入順序表。以及十個(gè)基本操作：在第i個(gè)元素之前插入元素，判斷是否為空，求元素個(gè)數(shù)，取第i個(gè)元素，查找第一個(gè)與e滿足compare()關(guān)系的元素，返回元素的前驅(qū)，返回后繼，刪除第i個(gè)元素，把一個(gè)順序表賦值給另一個(gè)順序表，置空順序表。四.實(shí)驗(yàn)環(huán)境3323機(jī)房OS：WxpC環(huán)境：1、TC2.02、VC++6.0五．運(yùn)行結(jié)果 程序開始界面框架操作：隨機(jī)生成順序表（元素值為0到99之間的整數(shù)）2.用已有的順序表初始化另一個(gè)順序表3.輸入順序表基本操作：在第i個(gè)元素之前插入一個(gè)元素2.判斷順序表是否為空3.求順序表中元素的個(gè)數(shù)4.取第i個(gè)元素5.查找第一個(gè)與之滿足compare()關(guān)系的元素序號(hào)6.返回某元素的前驅(qū)7.返回某元素的后繼8.刪除第i個(gè)元素9.把一個(gè)順序表復(fù)制給另一個(gè)順序表10.把順序表置空11.順序表的運(yùn)用六．實(shí)驗(yàn)心得 熟悉最基本的數(shù)據(jù)類型——順序表，同時(shí)我們讓我們熟練C++的基本操作，模板的使用，以及模塊化的設(shè)計(jì)思想。同時(shí)也運(yùn)用順序表做一些簡單的運(yùn)用，比如順序表的并交差運(yùn)算，學(xué)生管理系統(tǒng)等等。 在這次的實(shí)驗(yàn)中，我掌握了很多C++的特性，在運(yùn)用順序表時(shí)，由于水平的原因，只是把簡單的并交差運(yùn)算寫完，我想通過以后的學(xué)習(xí)，我們能夠?qū)⑵鋵?shí)現(xiàn)學(xué)生管理系統(tǒng)。 在實(shí)驗(yàn)中我也遇到很多的問題，輸入輸出的重載，輸出格式的控制等等，在以后的實(shí)驗(yàn)中吸取經(jīng)驗(yàn)和教訓(xùn)，提高自己的水平。五．實(shí)驗(yàn)代碼 基類：SqList.h//myhead.h包含自己設(shè)定的一些常量和類型#ifndefMYHEAD_H#defineMYHEAD_H//#include"D:\數(shù)據(jù)結(jié)構(gòu)C++\實(shí)驗(yàn)2\myhead.h"#include"D:\Users\fclz\Documents\VisualStudio2010\Projects\數(shù)據(jù)結(jié)構(gòu)C++\實(shí)驗(yàn)2\myhead.h"#endif//順序表的一些常量說明#defineLIST_MAX_SIZE100#defineLISTINCERMENT10//隨機(jī)數(shù)生成必須#define_CRT_RAND_S#include<stdlib.h>#include<stdio.h>#include<limits.h>//順序表數(shù)據(jù)結(jié)構(gòu)的C++類的聲明（基類）template<typenameElemType>classSqList{protected: ElemType*elem; intlistSize; intn;public: //構(gòu)造函數(shù)，析構(gòu)函數(shù)，拷貝構(gòu)造函數(shù)的聲明 SqList(); virtual~SqList(); SqList(constSqList<ElemType>&otherL); //順序表的方法 //有序順序表的折半查找 intbin_Search(ElemTypekey); //把順序表置空 voidclear(); //刪除第i個(gè)元素 StatusdeleteElem(inti,ElemType&e); //取第i個(gè)元素 intgetElem(inti,ElemType&e); //求順序表中元素的個(gè)數(shù) intgetLength(); //求順序表存儲(chǔ)空間的大小 intgetListSize(); //在第i個(gè)元素之前插入一個(gè)元素 Statusinsert(inti,ElemTypee); //判斷順序表是否為空 boolisEmpty(); //查找第1個(gè)與e滿足compare關(guān)系的元素的序號(hào) intlocateElem(ElemTypee,Status(*compare)(ElemType,ElemType)); //返回某個(gè)元素的后繼 StatusnextElem(ElemTypee,ElemType&next_e); //重載復(fù)制運(yùn)算符 SqList<ElemType>operator=(SqList<ElemType>rightL); //返回某個(gè)元素的前驅(qū) StatuspriorElem(ElemTypee,ElemType&prior_e); //在順序表中順序查找某個(gè)元素、 intsequentialSearch(ElemTypee);};//順序表的方法//有序順序表的折半查找template<typenameElemType>intSqList<ElemType>::bin_Search(ElemTypekey){ intlow,mid,high;//查找區(qū)域的起始、中間以及最后一個(gè)元素的下標(biāo) low=0,high=n-1; while(low<=high) { mid=(low+high)/2; if(elem[mid]==key) returnmid+1; elseif(elem[mid]<key) low=mid+1; elsehigh=mid-1; } return0;}//把順序表置空template<typenameElemType>voidSqList<ElemType>::clear(){ n=0;}//刪除第i個(gè)元素template<typenameElemType>StatusSqList<ElemType>::deleteElem(inti,ElemType&e){ if(i<1||i>n)returnERROR; e=elem[i-1]; for(intj=i+1;j<=n;++j) elem[j-2]=elem[j-1]; --n; returnOK;}//取第i個(gè)元素template<typenameElemType>StatusSqList<ElemType>::getElem(inti,ElemType&e){ if(i<1||i>n)returnERROR; e=elem[i-1]; returnOK;}//求順序表中元素的個(gè)數(shù)template<typenameElemType>intSqList<ElemType>::getLength(){ returnn;}//取順序表存儲(chǔ)空間的大小template<typenameElemType>intSqList<ElemType>::getListSize(){ returnlistSize;}//在第i元素之前插入一個(gè)元素template<typenameElemType>StatusSqList<ElemType>::insert(inti,ElemTypee){ ElemType*newbase; if(i<1||i>n+1) returnERROR; if(n>=listSize) { newbase=newElemType[listSize+LISTINCERMENT]; assert(newbase!=0); for(intj=1;j<n;++j) newbase[j-1]=elem[j-1]; delete[]elem; elem=newbase; listSize+=LISTINCERMENT; } for(intj=n;j>=i;--j) elem[j]=elem[j-1]; elem[i-1]=e; ++n; returnOK;}//判斷順序表是否為空template<typenameElemType>boolSqList<ElemType>::isEmpty(){ returnn?false:true;}//查找第1個(gè)與某元素e滿足compare()關(guān)系元素template<typenameElemType>intSqList<ElemType>::locateElem(ElemTypee,Status(*compare)(ElemType,ElemType)){ inti; for(i=1;i<=n&&!(*compare)(elem[i-1],e);++i); if(i<=n) returni; else return0;}//返回某個(gè)元素的后繼template<typenameElemType>StatusSqList<ElemType>::nextElem(ElemTypee,ElemType&next_e){ inti=locateElem(e,equal); if(i<1||i==n) returnERROR; else getElem(i+1,next_e); returnOK;}//重載運(yùn)算符的定義template<typenameElemType>SqList<ElemType>SqList<ElemType>::operator=(SqList<ElemType>rightL){ if(this!=&rightL) { if(listSize<rightL.listSize) { delete[]elem; elem=newElemType[rightL.listSize]; assert(elem!=0); listSize=rightL.listSize; } n=rightL.n; for(inti=1;i<=n;++i) elem[i-1]=rightL.elem[i-1]; } return*this;}//返回某個(gè)元素的前驅(qū)template<typenameElemType>StatusSqList<ElemType>::priorElem(ElemTypee,ElemType&prior_e){ inti=locateElem(e,equal); if(i<=1) returnERROR; else getElem(i-1,prior_e); returnOK;}//在順序表中順序查找某個(gè)元素template<typenameElemType>intSqList<ElemType>::sequentialSearch(ElemTypekey){ for(inti=1;i<n&&key!=elem[i-1];i++); if(i<=n) returni; else return0;}//構(gòu)造函數(shù)的實(shí)現(xiàn)template<typenameElemType>SqList<ElemType>::SqList(){ elem=newElemType[LIST_MAX_SIZE]; assert(elem!=0); listSize=LIST_MAX_SIZE; n=0;}//析構(gòu)函數(shù)的實(shí)現(xiàn)template<typenameElemType>SqList<ElemType>::~SqList(){ delete[]elem;}//拷貝構(gòu)造函數(shù)的實(shí)現(xiàn)template<typenameElemType>SqList<ElemType>::SqList(constSqList<ElemType>&otherL){ elem=newElemType[otherL.listSize]; assert(elem!=0); listSize=otherL.listSize; n=otherL.n; for(inti=1;i<=n;i++) elem[i-1]=otherL.elem[i-1];}派生類MySqList.h#ifndefSQLIST_H#defineSQLIST_H#include"SqList.h"#endif#include<iosfwd>template<typenameElemType>classMySqList:publicSqList<ElemType>{public: //讀輸入數(shù)據(jù) voidread(istream&in); //顯示數(shù)據(jù) voiddisplay(ostream&out)const; //生成隨機(jī)順序表 StatusrandSql(intn,MySqList<ElemType>&otherS);};//派生類的實(shí)現(xiàn)//輸入template<typenameElemType>voidMySqList<ElemType>::read(istream&in){ cout<<"請輸入要建立的順序表的元素個(gè)數(shù)："; cin>>n; for(inti=0;i<n;i++) { //cout<<n<<endl; cout<<"請輸入順序表的第"<<i+1<<"個(gè)元素："; in>>elem[i]; //n++; } cout<<endl;}template<typenameElemType>istream&operator>>(istream&in,MySqList<ElemType>&iL){ iL.read(in); returnin;}//輸出template<typenameElemType>voidMySqList<ElemType>::display(ostream&out)const{ for(inti=0;i<n;i++) out<<"["<<i+1<<"]"<<"\t"; out<<