数据结构-线性表的顺序表示和实现.doc

实验一 线性表的顺序表示和实现 实验人： 学号: 时间： 20.03.09 实验目的 掌握线性表的动态分配顺序存储结构 掌握线性表合并算法。 实验内容 已知顺序线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。（算法2.7） 实验步骤： 创建线性表La和Lb。 合并La和Lb得到Lc。 输出La、Lb、Lc。 算法说明 先建立线性表La与Lb，然后合并两线性表。 测试结果 分析与探讨 合并两线性表时，数据元素按非递减排列。 附录：源代码 源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%。 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -2 #define OVERFLOW -2 //Status是函数的类型，其值是函数结果状态代码 typedef int Status; typedef int ElemType; //元素类型定义为整型 #includeiostream.h #define LIST_INIT_SIZE 100 //存储空间的初始分配量 #define LISTINCREMENT 10 //存储空间的分配增量 typedef struct { ElemType *elem; //指向存储空间的基地址 int length; //线性表的当前长度 int listsize; //当前分配的存储容量 }SqList; Status InitList_Sq(SqList L) { // 算法2.3 // 构造一个空的线性表L。 L.elem = new(ElemType[LIST_INIT_SIZE*sizeof(ElemType)]); if (!L.elem) return OVERFLOW; // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq Status DestroyList_Sq(SqList L) { if (L.elem) delete(L.elem); //释放线性表的存储空间 L.elem=NULL; return OK; }//DestroyList_Sq ElemType *realloc(SqList L) { //再申请LISTINCREMENT个空间 ElemType *p,*q,*r; p = new(ElemType[(L.listsize+LISTINCREMENT)*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; } Status ListInsert_Sq(SqList L, int i, ElemType e) { // 算法2.4 // 在顺序线性表L的第i个元素之前插入新的元素e， // i的合法值为1≤i≤ListLength_Sq(L)+1 ElemType *p; if (i 1 || i L.length+1) return ERROR; // i值不合法 if (L.length = L.listsize) { // 当前存储空间已满，增加容量 ElemType *newbase = realloc(L); if (!newbase) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } ElemType *q = (L.elem[i-1]); // q为插入位置 for (p = (L.elem[L.length-1]); p=q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e;