順序表實驗報告

實驗報告實驗項目名稱 實驗一線性表的操作所屬課程名稱數(shù)據(jù)結(jié)構(gòu)實驗類型 驗證實驗實驗日期 2010-11-19院系數(shù)學(xué)與信息科學(xué)學(xué)院實驗一線性表的操作一．實驗?zāi)康?、 掌握用上機調(diào)試線性表的基本方法；2、 掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等簡單操作在順序存儲結(jié)構(gòu)上的運算。二．實驗環(huán)境硬件：計算機、256M以上內(nèi)存，40G以上硬盤；軟件：WindowsXP,C++三．實驗內(nèi)容線性表基本操作的實現(xiàn)：構(gòu)造一空線性表，將線性表置空，對線性表進行判空，求線性表的長度，查詢線性表的第i個數(shù)據(jù)元素的值，查詢要查詢元素的上個元素的值，查詢要查詢元素的下個元素的值，刪除線性表中的某個元素，將某元素插入線性表，對線性表進行查訪并返回一特定的值。給出兩個線性表將其合并成一個線性表，銷毀線性表。四．實驗步驟1、本實驗的程序及頭文件如下：SqlistMain.cpp#include"iostream.h"#include"stdio.h"#include"malloc.h"#include"stdlib.h"#include"SqListOperation.h"#include"function.h"#include"SqList.h"voidmain(){SqListL1,L2,L3;SqList*La=&L1,*Lb=&L2,*Lc=&L3;ElemTypee;intm;InitList_Sq(La);InitList_Sq(Lb);coutvv'請輸入線性表a"vvendl;EnterList_Sq(La);cout<<"輸出線性表a"<<endl;PrintSqList(La);coutvv"輸出線性表a長:"vvListLength(La)vvendl;cout<<"驗線性表a是否空表(空為1,不空為0):"vvListEmpty(La)vvendl;coutvv"輸入查詢線性表a中元素的位置:";cin>>m;coutvv"輸出線性表a中第m個元素:"vvGetElem(La,m)vvendl;coutv<"輸入要查詢元素的上個元素:";cin>>m;coutvv"輸出性表a中第m個元素上個元素:"vvPriorElem(La,m)vvendl;coutvv"輸入要查詢元素的下個元素:";cin>>m;coutvv"輸出線性表a中第m個元素下個元素:"vvNextElem(La,m)vvendl;coutvv"輸入插入元素e及其位置m:";cin>>m>>e;ListInsert_Sq(La,e,m);coutvv"輸出插入元素后的線性表a:"vvendl;PrintSqList(La);coutvv"輸入刪除元素位置m:";cin>>m;coutvv"除線性表a中第"vvmvv"個元素并輸出其值:"vvListDelete_Sq(La,m)vvendl;coutvv"輸出刪除元素后的線性表a:"vvendl;PrintSqList(La);coutvv"輸入線性表b"vvendl;EnterList_Sq(Lb);coutvv"輸出線性表b"vvendl;PrintSqList(Lb);coutvv"給線性表La按遞增排序并輸出:"vvendl;Sort_Increase(La);PrintSqList(La);coutvv"給線性表La按遞增排序并輸出:"vvendl;Sort_Increase(Lb);PrintSqList(Lb);coutvv"把線性表a和線性表b按非遞減排列歸并到線性表c,并輸出線性表c:"vvendl;MergeList(La,Lb,Lc);PrintSqList(Lc);coutvv"刪除線性表Lc"vvendl;ClearList(Lc);DestroyList(Lc);coutvv"輸出刪除線性表Lc后的表長:"vvListLength(Lc)vvendl;}Function.hStatusInitList_Sq(SqList*L);StatusDestroyList(SqList*L);StatusClearList(SqList*L);StatusListEmpty(SqList*L);intListLength(SqList*L);StatusGetElem(SqList*L,inti,ElemType*e);ElemTypeGetElem(SqList*L,inti);intLocateElem(SqList*L,ElemTypee,Status(*compare)(ElemTypea,ElemTypee));StatusPriorElem(SqList*L,ElemTypecur_e,ElemType*pre_e);ElemTypePriorElem(SqList*L,ElemTypecur_e);StatusNextElem(SqList*L,ElemTypecur_e,ElemType*next_e);ElemTypeNextElem(SqList*L,ElemTypecur_e);StatusListInsert_Sq(SqList*L,inti,ElemTypee);StatusListDelete_Sq(SqList*L,inti,ElemType*e);ElemTypeListDelete_Sq(SqList*L,inti);voidPrintSqList(SqList*L);StatusListTraverse(SqList*L,Status(*visit)(ElemType*a));StatusEnterList_Sq(SqList*L);Statuscompare(ElemTypea,ElemTypee);Statusvisit(ElemType*a);StatusUnion(SqList*La,SqList*Lb);StatusMergeList(SqList*La,SqList*Lb,SqList*Lc);//StatusMergeList_Sq(SqList*La,SqList*Lb,SqList*Lc);StatusSort_Increase(SqList*L);StatusSort_Reduce(SqList*L);SqlistOperation.h#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineOK1#defineERROR0#defineTURE1#defineFALSE0#defineOVERFLOW0#defineINFEASIBLE0typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;constintn=10;Sqlist.h//初始條件：已申明線性表類型為SqListStatusInitList_Sq(SqList*L){//構(gòu)造一個空的順序表L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)exit(ERROR);//存儲分配失敗L->length=0;〃空表長度為零L->listsize=LIST_INIT_SIZE;〃初始存儲容量returnOK;}//InitList_SqStatusEnterList_Sq(SqList*L){//初始條件：已存在空的順序表//操作結(jié)果：給順序表輸入元素，并記錄元素個數(shù)inti,m;ElemType*newbase;coutv<"輸入所需輸入線性表元素的個數(shù)"vvendl;cin>>m;newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲分配失敗L->elem=newbase;〃新基址L->listsize+=LISTINCREMENT;//增加存儲容量coutvv"依次輸入所需元素:"vvendl;for(i=0;ivm;i++){cin>>L->elem[i];L->length++;}returnOK;}StatusDestroyList(SqList*L){〃初始條件：順序線性表L已存在。操作結(jié)果：銷毀線性順序表Lfree(L->elem);L->elem=NULL;L->length=0;L->listsize=0;returnOK;}StatusClearList(SqList*L){〃初始條件：順序線性表L已存在。操作結(jié)果：將L重置為空表L->length=0;returnOK;StatusListEmpty(SqList*L){〃初始條件：順序線性表L已存在if(L->length==0)returnTURE;elsereturnFALSE;}intListLength(SqList*L){〃初始條件：順序線性表L已存在?操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)returnL->length;}StatusGetElem(SqList*L,inti,ElemType*e){〃初始條件：順序線性表L已存在，lv=iv=l.length。操作結(jié)果：用e返回L中第i個元素的值if(ivl||i>L->length){exit(ERROR);}e=L->elem+i-l;returnOK;}ElemTypeGetElem(SqList*L,inti){〃初始條件：順序線性表L已存在，1v=iv=l.length。操作結(jié)果：用e返回L中第i個元素的值ElemTypee;if(iv1||i>L->length){exit(ERROR);}e=L->elem[i-1];returne;}intLocateElem(SqList*L,ElemTypee,Status(*compare)(ElemTypea,ElemTypee)){〃初始條件：順序線性表L已存在for(inti=0;ivL->length;i++){if((*compare)(L->elem[i],e))return++i;}returnERROR;}StatusPriorElem(SqList*L,ElemTypecur_e,ElemType*pre_e){〃初始條件：順序線性表L已存在〃操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義inti=2;ElemType*p=L->elem+1;while(i<=L->length&&*p!=cur_e){p++;i++;}if(i>L->length){returnINFEASIBLE;}else{pre_e=--p;returnOK;}}ElemTypePriorElem(SqList*L,ElemTypecur_e){〃初始條件：順序線性表L已存在〃操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義inti=2;ElemTypepre_e;ElemType*p=L->elem+1;while(i<=L->length&&*p!=cur_e){p++;i++;}if(i>L->length){returnINFEASIBLE;}else{pre_e=*--p;returnpre_e;}}StatusNextElem(SqList*L,ElemTypecur_e,ElemType*next_e){〃初始條件：順序線性表L已存在〃操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義inti=1;ElemType*p=L->elem;while(i<L->length&&*p!=cur_e){i++;p++;}if(i==L->length||L->length==0)returnINFEASIBLE;else{next_e=++p;returnOK;}}ElemTypeNextElem(SqList*L,ElemTypecur_e){〃初始條件：順序線性表L已存在〃操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義inti=1;ElemType*p=L->elem,next_e;while(i<L->length&&*p!=cur_e){i++;p++;}if(i==L->length||L->length==0)returnINFEASIBLE;else{next_e=*++p;returnnext_e;}}StatusListInsert_Sq(SqList*L,inti,ElemTypee){//在順序表L中第i個位置之前插入新的元素e〃i的合法值為lv=iv=ListLength.Sq(L)+lElemType*p,*q,*newbase;if(i<l||i>L->length+l)returnERROR;//i值不合法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->elem[i-1]);//q為插入位置for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*(p);//插入位置及之后的元素右移*q=e; //插入e++L->length;〃表長增1returnOK;}StatusListDelete_Sq(SqList*L,inti,ElemType*e){//在順序表L中刪除第i個元素，并用e返回其值〃i的合法值為1v=iv=ListLength.Sq(L)+1ElemType*p,*q;if(iv1lli>L->length+1)returnERROR;//i值不合法p=&(L->elem[i-1]);//p為被刪除位置e=p;//被刪除元素的地址賦給eq=&(L->elem[L->length-1]);for(++p;p<=q;++p)*(p-1)=*(p);//被刪除元素之后的元素左移--L->length;〃表長減1returnOK;}ElemTypeListDelete_Sq(SqList*L,inti){//在順序表L中刪除第i個元素，并用e返回其值//i的合法值為1v=iv=ListLength.Sq(L)+1ElemType*p,*q,e;if(iv1lli>L->length+1)returnERROR;//i值不合法p=&(L->elem[i-1]);//p為被刪除位置e=*p;//被刪除元素的地址賦給eq=&(L->elem[L->length-1]);for(++p;p<=q;++p)*(p-1)=*(p);//被刪除元素之后的元素左移--L->length;〃表長減1returne;}voidPrintSqList(SqList*L){〃初始條件：順序線性表L已存在〃操作結(jié)果：輸出線性表L中元素ElemType*p;p=L->elem;for(inti=1;i<=L->length;i++){cout<<*p++<<"";}cout<<endl;}StatusListTraverse(SqList*L,Status(*visit)(ElemType*a)){〃初始條件：順序線性表L已存在〃操作結(jié)果：依次對L的每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗〃vi()的形參加'&',表明可通過調(diào)用visit()改變元素的值ElemType*p;inti;p=L->elem;for(i=0;i<L->length;i++)(*visit)(p++);cout<<endl;returnOK;}Statuscompare(ElemTypea,ElemTypee)/比較兩個元素是否相等{if(a==e){returnOK;}elsereturnERROR;}Statusvisit(ElemType*a)/對元素進行操作{returnOK;}StatusUnion(SqList*La,SqList*Lb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中intLa_len,Lb_len,i;ElemTypee;La_len=ListLength(La);Lb_len=ListLength(Lb);〃求線性表的長度for(i=1;i<=Lb_len;i++){e=GetElem(Lb,i);〃取Lb中第i個數(shù)據(jù)元素賦值給eif(!LocateElem(La,e,compare)){ListInsert_Sq(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素,則插入之}}returnOK;}//unionStatusMergeList(SqList*La,SqList*Lb,SqList*Lc){//已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排序.〃并歸La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排序.inti=1,j=1,k=1;ElemTypea,b;InitList_Sq(Lc);while((i<=La->length)&&(j<=Lb->length)){a=GetElem(La,i);b=GetElem(Lb,j);if(a<=b){ListInsert_Sq(Lc,k,a);++i;++k;}else{ListInsert_Sq(Lc,k,b);++j;++k;}}while(i<=La->length){a=GetElem(La,i);ListInsert_Sq(Lc,k,a);++i;++k;}while(j<=Lb->length){b=GetElem(Lb,j);ListInsert_Sq(Lc,k,b);++j;++k;}returnOK;}StatusSort_Increase(SqList*L)〃纟合線性表按遞增排序{inti,j;ElemTypet;for(i=0;i<L->length-1;i++){for(j=0;j<L->length-i-1;j++){if(L->elem[j]>L->elem[j+1])t=L->elem[j];L->elem[j]=L->elem[j+1];L->elem[j+1]=t;}}}returnOK;}StatusSort_Reduce(SqList*L)〃給線性表按遞減排序{inti,j;ElemTypet;for(i=0;i<L->length-1;i++){for(j=0;j<L->length-i-1;j++){if(L->elem[j]<L->elem[j+1]){t=L->elem[j];L->elem[j]=L->elem[j+1];L->elem[j+1]=t;}}}returnOK;}本程序運行的結(jié)果如下：輸入線性表a輸入所需輸入線性表元素的個數(shù)3/依次輸入所需元素：9/8/輸出線性表a978輸出線性表a長：3驗證線性表a是否空表（空為1，不空為0）：0驗線性表戰(zhàn)是否空表<空為「不空為妙淖輸入查詢線性表a中元素的位置：3/輸出線性表a中第m個元素：8輸入查詢其上個元素的元素：8/輸出線性表a中第m個元素的上個元素：7輸入查詢其下個元素的元素：7/輸出線性表a中第m個元素的下個元素：8輸入插入元素e及其位置m：3/2/輸出插入元素后的線性表a：9378和人插入元素亡及其位置n汴了出插入元素后的線性表補78輸入山刪除元素的位置m：3/刪除線性表a中第4個元素并輸出其值：7輸出刪除元素后的線性表a：938輸入刪除元素位置力=3矗線性昴沖第M軍元素并輸出其值淚貓出刪除元素后的線性表即938輸入線性表b輸入所需輸入線性表元素的個數(shù)4/依次輸入所需