数据结构线性表的顺序表示和实现.docx
数据结构实验报告实验一 线性表的顺序表示和实现实验人：学号： Xb09620125 时间：实验目的1 .掌握线性表的动态分配顺序存储结构.掌握线性表合并算法。一、 实验内容已知顺序线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的 顺序线性表Lc, Lc的元素也按值非递减排列。（算法2.7）实验步骤：1 .创建线性表La和Lbo.合并La和Lb得到Lc。2 .输出 La、Lb、Leo算法说明先建立线性表La与Lb,然后合并两线性表。二、 测试结果六、 分析与探讨合并两线性表时，数据元素按非递减排列。七、 附录：源代码源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%0#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE -2数据结构实验报告#define OVERFLOW -2/Status是函数的类型，其值是函数结果状态代码typedef int Status;typedefintElemType; 元素类型定义为整型#include<iostream.h>#define LISTJNIT_SIZE 100 存储空间的初始分配量#define LISTINCREMENT 10 /存储空间的分配增量typedef struct ElemType *elem; 指向存储空间的基地址int length;线性表的当前长度int listsize;当前分配的存储容量SqList;StatusInitList_Sq(SqList&L) / 算法 2.3构造一个空的线性表LoL.elem = new(ElemTypeLIST_INIT_SIZE*sizeof(ElemType);if(!L.elem) return OVERFLOW; / 存储分配失败L.length = 0;/空表长度为0L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; / InitList_SqStatus DestroyList_Sq(SqList &L)if (L.elem) delete(L.elem);释放线性表的存储空间L.elem=NULL;return OK;/Destroy List_SqElemType*realloc(SqListL) 再申请 LISTINCREMENT 个空间ElemType *p,*q,*r;p = new(ElemType (L. listsize+LI STINCREM ENT) *sizeof(ElemType);if(!p) return NULL; q=p; r=L.elem;for(int i= 1 ;i<=L.length;i+) *q=*r; q+; r+；delete L.elem;return p;)StatusListInsert_Sq(SqList&L,inti,ElemTypee) / 算法 2.4/在顺序线性表L的第i个元素之前插入新的元素e, i的合法值为 l<i<ListLength_Sq(L)+lElemType *p;if(i < 1 11 i >L.length+l) return ERROR; /i 值不合法if(L.length >= L.listsize) /当前存储空间已满，增加容量 ElemType *newbase = realloc(L);if (inewbase) return ERROR; / / 存储分配失败L.elem = newbase;/ 新基址L.listsize += LISTINCREMENT; / 增加存储容量数据结构实验报告ElemType*q =&(L.elemi-1 ); / q 为插入位置for (p = &(L.elemL.length-l); p>=q; p) *(p+l) = *p;/插入位置及之后的元素右移*q = e; / 插入 e+L.length; / 表长增 1 return OK; / ListInsert_SqStatus ListInsert(SqList &L,ElemTypee) if(!L.length)L.elemO=e;int i=L.length;while(e<=L.elemi-1 &&i>0)L. elemi=L. elem i-1;i-；L.elemi=e;L.length+;return OK;)StatusMergeList_Sq(SqListLa, SqListLb, SqList&Lc) / 算法 2.7/已知顺序线性表La和Lb的元素按值非递减排列。/归并La和Lb得到新的顺序线性表Lc, Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;使pa、pb分别指向La和Lb的第一个元素pa=La.elem; pb = Lb.elem;为Lc申请空间Lc.listsize = Lc. length = La. length+Lb. length;pc = Lc.elem = new(ElemTypeLc.listsize*sizeof(ElemType);if (ILc.elem)return OVERFLOW; 存储分配失败使pa_last、pbast分别指向La和Lb的最后一个元素pa_last = La. elem+La. length-1;pb_last = Lb.elem+Lb.length-1;while (pa <= pa_last && pb <= pb_last) 归并if (*pa <= *pb) *pc+ = *pa+; else *pc+ = *pb+;while (pa <= pa_last) *pc+ =*pa+; / La 的乘U余元素 while (pb <= pb_last) *pc+ =*pb+; / 插入 Lb 的乘U余元素 return(OK);l; / MergeListvoid ListTraverse_Sq(SqList L)int i;for(i= 1 ;i<=L.length;i+) cout<<L,elemi-l<<H n;cout<<endl;数据结构实验报告voidmain()int i;建立两个元素按值非递减排列的顺序线性表La和Lb,并将它们合并为一个有序顺序 表Lc显示La、Lb和Lc的内容SqList La,Lb,Lc;ElemTypezl,z2;InitList_Sq(La);coutvv”读入3个元素并插入到顺序表La中"vvendl;fbr(i=l;i<=3;i+) cin>>zl;ListInsert(La,zl);coutvv”顺序表La中所有元素如下:“vvendl;ListTraverse_Sq(La);InitList_Sq(Lb);cout<<”读入3个元素并插入到顺序表Lb中”<<endl;for(i=l;i<=3;i+) cin>>z2; ListInsert(Lb,z2);coutvv”顺序表Lb中所有元素如下:"vvendl;ListTraverse_Sq(Lb);MergeList_Sq(La, Lb, Lc);coutvv”顺序表Lc中所有元素如下:“<<endl;ListTraverse_Sq(Lc);
