实验报告 线性表的顺序存储.docx
- 文档编号:10294484
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:19
- 大小:18.05KB
实验报告 线性表的顺序存储.docx
《实验报告 线性表的顺序存储.docx》由会员分享,可在线阅读,更多相关《实验报告 线性表的顺序存储.docx(19页珍藏版)》请在冰点文库上搜索。
实验报告线性表的顺序存储
实验报告
试验项目名称线性表的顺序存储
结构上的操作
所属课程名称数据结构
实验类型验证试验
试验日期2010/11/21
学院:
数学与信息科学学院
专业:
信息与计算科学
班级:
082班
姓名:
李晓璐
学号:
0801214037
实验线性表的顺序存储结构上的操作
一、实验目的
1、掌握用上机调试线性表的基本方法;
2、掌握线性表的顺序存储结构的基本操作,插入、删除以及有序表合并等运算在顺序存储结构上的运算。
二、实验环境
硬件:
PC微型计算机、256M以上内存,40G以上硬盘。
软件:
WindowsXP,TurboC/C++
三、实验内容
线性表十二种基本操作的实现,其中线性表的插入、删除以及两个有序表的
合并操作在顺序存储结构上以如下形式体现:
当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表的第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。
若要删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置。
已知线形表La和Lb中的数据元素按值非递减排序.并归La和Lb得到新的线形表Lc,Lc的数据元素也按值非递减排序。
可设两个指针i和j分别指向La和Lb中的某个元素,若i当前所指的元素为a,j当前所指的元素为b,则当前应插入到Lc中的元素为c。
当a≤b时,c=a;当a>b时,c=b。
显然,指针i和j的初值均为1,在所指元素插入Lc之后,在La或Lb中顺序后移。
四、实验步骤
1、本实验的程序如下
“function.h”
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineOK1
#defineERROR0
#defineTURE1
#defineFALSE0
#defineOVERFLOW0
#defineINFEASIBLE0
typedefintStatus;
typedefintElemType;
typedefstruct{
ElemType*elem;
intlength;
intlistsize;
}SqList;
constintn=10;
“SqList.h”
StatusInitList_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);
StatusSort_Increase(SqList*L);
StatusSort_Reduce(SqList*L);
“SqListOperation.h”
StatusInitList_Sq(SqList*L)
{
L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L->elem)exit(ERROR);
L->length=0;
L->listsize=LIST_INIT_SIZE;
returnOK;
}
StatusEnterList_Sq(SqList*L)
{
inti,m;
ElemType*newbase;
cout<<"输入所需输入线形表元素的个数"< cin>>m; newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(! newbase)exit(OVERFLOW);//存储分配失败 L->elem=newbase;//新基址 L->listsize+=LISTINCREMENT;//增加存储容量 cout<<"依次输入所需元素: "< for(i=0;i { cin>>L->elem[i]; L->length++; } returnOK; } StatusDestroyList(SqList*L) { free(L->elem); L->elem=NULL; L->length=0; L->listsize=0; returnOK; } StatusClearList(SqList*L) { L->length=0; returnOK; } StatusListEmpty(SqList*L) { if(L->length==0) returnTURE; else returnFALSE; } intListLength(SqList*L) { returnL->length; } StatusGetElem(SqList*L,inti,ElemType*e) { if(i<1||i>L->length){exit(ERROR);} e=L->elem+i-1; returnOK; } ElemTypeGetElem(SqList*L,inti) { ElemTypee; if(i<1||i>L->length){exit(ERROR);} e=L->elem[i-1]; returne; } intLocateElem(SqList*L,ElemTypee,Status(*compare)(ElemTypea,ElemTypee)) { for(inti=0;i { if((*compare)(L->elem[i],e)) return++i; } returnERROR; } StatusPriorElem(SqList*L,ElemTypecur_e,ElemType*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) { 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) { inti=1; ElemType*p=L->elem; while(i =cur_e) { i++; p++; } if(i==L->length||L->length==0) returnINFEASIBLE; else { next_e=++p; returnOK; } } ElemTypeNextElem(SqList*L,ElemTypecur_e) { inti=1; ElemType*p=L->elem,next_e; while(i =cur_e) { i++; p++; } if(i==L->length||L->length==0) returnINFEASIBLE; else { next_e=*++p; returnnext_e; } } StatusListInsert_Sq(SqList*L,inti,ElemTypee) { ElemType*p,*q,*newbase; if(i<1||i>L->length+1)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]); for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*(p); *q=e; ++L->length; returnOK; } StatusListDelete_Sq(SqList*L,inti,ElemType*e) { ElemType*p,*q; if(i<1||i>L->length+1)returnERROR; p=&(L->elem[i-1]); e=p; q=&(L->elem[L->length-1]); for(++p;p<=q;++p)*(p-1)=*(p); --L->length; returnOK; } ElemTypeListDelete_Sq(SqList*L,inti) { ElemType*p,*q,e; if(i<1||i>L->length+1)returnERROR; p=&(L->elem[i-1]); e=*p; q=&(L->elem[L->length-1]); for(++p;p<=q;++p)*(p-1)=*(p); --L->length; returne; } voidPrintSqList(SqList*L) { ElemType*p; p=L->elem; for(inti=1;i<=L->length;i++) { cout<<*p++<<""; } cout< } StatusListTraverse(SqList*L,Status(*visit)(ElemType*a)) { ElemType*p; inti; p=L->elem; for(i=0;i (*visit)(p++); cout< returnOK; } Statuscompare(ElemTypea,ElemTypee) { if(a==e) { returnOK; } else returnERROR; } Statusvisit(ElemType*a) { returnOK; } StatusUnion(SqList*La,SqList*Lb) { 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); if(! LocateElem(La,e,compare)) { ListInsert_Sq(La,++La_len,e);} } returnOK; } StatusMergeList(SqList*La,SqList*Lb,SqList*Lc) {. 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 { for(j=0;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 { for(j=0;j { if(L->elem[j] { t=L->elem[j]; L->elem[j]=L->elem[j+1]; L->elem[j+1]=t; } } } returnOK; } “SqListMain.cpp” #include"iostream.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=3,*f=0; intm; InitList_Sq(La); InitList_Sq(Lb); cout<<"输入表a"< EnterList_Sq(La); cout<<"输出表a"< PrintSqList(La); cout<<"输出表a长: "< cout<<"检验表a是否空表(空为1,不空为0): "< cout<<"输入查询表a中元素的位置: "; cin>>m; cout<<"输出线形表a中第m个元素: "< cout<<"输入查询其上个元素的元素: "; cin>>m; cout<<"输出线形表a中第m个元素上个元素: "< cout<<"输入查询其下个元素的元素: "; cin>>m; cout<<"输出线形表a中第m个元素下个元素: "< cout<<"输入插入元素e及其位置m: "; cin>>m>>e; ListInsert_Sq(La,e,m); cout<<"输出插入元素后的表a: "< PrintSqList(La); cout<<"输入删除元素位置m: "; cin>>m; cout<<"删除线形表a中第"< "< cout<<"输出删除元素后的表: "< PrintSqList(La); cout<<"输入表b"< EnterList_Sq(Lb); cout<<"输出表b"< PrintSqList(Lb); cout<<"给线形表La按递增排序并输出: "< Sort_Increase(La); PrintSqList(La); cout<<"给线形表Lb按递增排序并输出: "< Sort_Increase(Lb); PrintSqList(Lb); cout<<"把表a和表b按非递减排列归并到表c,并输出表c: "< MergeList(La,Lb,Lc); PrintSqList(Lc); cout<<"删除线形表Lc"< ClearList(Lc); DestroyList(Lc); cout<<"输出删除线形表Lc后的表长: "< } 2、本程序运行的结果如下: 输入表a 输入所需输入线性表元素的个数 5 依次输入所需元素 39 74 24 63 99 输入表a 3974246399 输出表a长: 5 检验表a是否空表<空为1,不空为0>: 0 输入查询表a中元素的位置: 5 输出线性表a中第m个元素: 99 输入查询其上个元素的元素: 24 输出线性表a中第m个元素上个元素: 74 输入查询其下个元素的元素: 34 输入查询其下个元素的元素下个元素: 74 输入插入元素e及其位置m: 19 4 输出插入元素后的表a: 347424196399 输入删除元素位置m: 5 删除线性表a中第5个元素并输出其值: 63 输出删除元素后的表: 3474241999 输入表b 输入所需输入线性表元素的个数 3 依次输入所需元素: 2 71 14 输出表b 21714 给线性表La按递增排序并输出: 1924347499 给线性表Lb按递增排序并输出: 21471 把表a和表b按非递减排列归并到表c,并输出表c: 214192434717499 删除线性表Lc 输出删除线性表Lc后的表长: 0 五、实验小结 通过此次实验,使我更好的把握了线性表的顺序存储结构,更清楚的认识了线性表的十二种基本操作,特别是对线性表的插入删除操作以及两个有序表的合并有了更深刻的理解!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验报告 线性表的顺序存储 实验 报告 线性 顺序 存储