假设以顺序结构存储线性表
// practice31。cpp : Defines the entry point for the console application。 // #include "stdafx。h" #include #include #include #include // 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量 #define LISTINCREMENT 2 // 线性表存储空间的分配增量 typedef int ElemType; struct SqList { ElemType *elem...全部
// practice31。cpp : Defines the entry point for the console application。 // #include "stdafx。h" #include #include #include #include // 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量 #define LISTINCREMENT 2 // 线性表存储空间的分配增量 typedef int ElemType; struct SqList { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) }; int InitList(SqList &L) // 算法2。
3 { // 操作结果:构造一个空的顺序线性表 L。elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L。
elem) exit(1); // 存储分配失败 L。length=0; // 空表长度为0 L。listsize=LIST_INIT_SIZE; // 初始存储容量 return 1; } int DestroyList(SqList &L) { // 初始条件:顺序线性表L已存在。
操作结果:销毁顺序线性表L free(L。elem); L。elem=NULL; L。length=0; L。listsize=0; return 1; } int ClearList(SqList &L) { // 初始条件:顺序线性表L已存在。
操作结果:将L重置为空表 L。length=0; return 1; } int ListEmpty(SqList L) { // 初始条件:顺序线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE if(L。
length==0) return 0; else return 1; } int ListLength(SqList L) { // 初始条件:顺序线性表L已存在。
操作结果:返回L中数据元素个数 return L。length; } int GetElem(SqList L,int i,ElemType &e) { // 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) // 操作结果:用e返回L中第i个数据元素的值 if(iL。
length) exit(1); e=*(L。elem i-1); return 1; } int equal(ElemType c1,ElemType c2) { // 判断是否相等的函数,Union()用到 if(c1==c2) return 1; else return 0; } int LocateElem(SqList L,ElemType e) { // 初始条件:顺序线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) // 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在,则返回值为0。算法2。6 ElemType *p; int i=1; // i的初值为第1个元素的位序 p=L。elem; // p的初值为第1个元素的存储位置 while(iL。
length) return 0; else { pre_e=*--p; return 1; } } int NextElem(SqList L,ElemType cur_e,ElemType &next_e) { // 初始条件:顺序线性表L已存在 // 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, // 否则操作失败,next_e无定义 int i=1; ElemType *p=L。
elem; while(iL。length 1) // i值不合法 return 0; if(L。length>=L。listsize) // 当前存储空间已满,增加分配 { if(!(newbase=(ElemType *)realloc(L。
elem,(L。listsize LISTINCREMENT)*sizeof(ElemType)))) exit(1); // 存储分配失败 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; // 表长增1 return 1; } int ListDelete(SqList &L,int i,ElemType &e) // 算法2。5 { // 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) // 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 ElemType *p,*q; if(iL。
length) // i值不合法 return 0; p=L。elem i-1; // p为被删除元素的位置 e=*p; // 被删除元素的值赋给e q=L。elem L。
length-1; // 表尾元素的位置 for( p;p *(p-1)=*p; L。length--; // 表长减1 return 1; } int ListTraverse(SqList L,void(*vi)(ElemType&)) { // 初始条件:顺序线性表L已存在 // 操作结果:依次对L的每个数据元素调用函数vi()。
一旦vi()失败,则操作失败 // vi()的形参加'&',表明可通过调用vi()改变元素的值 ElemType *p; int i; p=L。elem; for(i=1;i vi(*p ); cout return 1; } void print(ElemType &c) { printf("%d ",c); } void Union(SqList &La,SqList Lb) // 算法2。
1 { // 将所有在线性表Lb中但不在La中的数据元素插入到La中 ElemType e; int La_len,Lb_len; int i; La_len=ListLength(La); // 求线性表的长度 Lb_len=ListLength(Lb); for(i=1;i { GetElem(Lb,i,e); // 取Lb中第i个数据元素赋给e if(!LocateElem(La,e)) // La中不存在和e相同的元素,则插入之 { ListInsert(La, La_len,e); } } } void MergeList(SqList La,SqList Lb,SqList &Lc) { // 已知线性表La和Lb中的数据元素按值非递减排列。
// 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列 int La_len; int Lb_len; InitList(Lc);//创建Lc ElemType ai,bj; La_len=ListLength(La); Lb_len=ListLength(Lb); int i=1, j=1, k=0; while(i { GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai { ListInsert(Lc, k,ai); i; } else { ListInsert(Lc, k,bj); j; } } while(i { GetElem(La,i ,ai); ListInsert(Lc, k,ai); } while(j { GetElem(Lb,j ,bj); ListInsert(Lc, k,bj); } } void MergeList2(SqList La,SqList Lb,SqList &Lc) { ElemType *pa, *pb, *pa_last, *pb_last, *pc; pa = La。
elem; pb = Lb。elem; pa_last = pa La。length - 1; pb_last = pb Lb。length - 1; Lc。length = Lc。
listsize = La。length Lb。length; pc = Lc。elem = (ElemType*)malloc(Lc。listsize*sizeof(ElemType)); if(!Lc。
elem) exit(1); while(pa { if(*pa *pc = *pa ; else *pc = *pb ; } while(pa { *pc = *pa ; } while(pb { *pc = *pb ; } } int main(int argc, char* argv[]) { SqList La,Lb; int i; int j; i=InitList(La); if(i==1) // 创建空表La成功 for(j=1;j i=ListInsert(La,j,j); printf("La= "); // 输出表La的内容 ListTraverse(La,print); InitList(Lb); // 也可不判断是否创建成功 for(j=1;j i=ListInsert(Lb,j,2*j); printf("Lb= "); // 输出表Lb的内容 ListTraverse(Lb,print); Union(La,Lb); printf("new La= "); // 输出新表La的内容 ListTraverse(La,print); SqList Lc; MergeList2(La,Lb,Lc); printf("new Lc= "); // 输出新表Lc的内容 ListTraverse(Lc,print); } 如果对您有帮助,请记得采纳为满意答案,谢谢!祝您生活愉快! Vae团队招人!!!欢迎各位加入!!!走过路过不要错过!!!迅猛发展中!!!。
收起