// 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<=q; 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<=L。length;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<=Lb_len;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<=La_len && j<=Lb_len)
{
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if(ai<=bj)
{
ListInsert(Lc, k,ai);
i;
}
else
{
ListInsert(Lc, k,bj);
j;
}
}
while(i<=La_len)
{
GetElem(La,i ,ai);
ListInsert(Lc, k,ai);
}
while(j<=Lb_len)
{
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<=pa_last && pb<=pb_last)
{
if(*pa <= *pb)
*pc = *pa ;
else
*pc = *pb ;
}
while(pa<=pa_last)
{
*pc = *pa ;
}
while(pb<=pb_last)
{
*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<=5;j ) // 在表La中插入5个元素
i=ListInsert(La,j,j);
printf("La= "); // 输出表La的内容
ListTraverse(La,print);
InitList(Lb); // 也可不判断是否创建成功
for(j=1;j<=5;j ) // 在表Lb中插入5个元素
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团队招人！！！欢迎各位加入！！！走过路过不要错过！！！迅猛发展中！！！。
全部
