数据结构之表中在Lb中但不在La中的元素插入到La中

90 阅读 0 评论 60 点赞

我是靠谱客的博主俭朴电话，最近开发中收集的这篇文章主要介绍数据结构之表中在Lb中但不在La中的元素插入到La中，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*
每个函数都做了很清晰的注释，适合初学数据结构的朋友。
表中在Lb中但不在La中的元素插入到La中
*/
//c_1.h
# include <string.h>
# include <ctype.h>
# include <malloc.h>
# include <limits.h> //INT_MAX
# include <stdio.h>
# include <stdlib.h> //atoi()
# include <io.h> //eof()
# include <math.h>
# include <process.h>
# include <iostream.h>
//函数结果状态保存码
# define OK 1
# define TRUE 1
# define FLASE 0
# define ERROR 0
# define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
typedef int ElemType;
//c_2.h 线性表的动态分配顺序存储结构
# define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
# define LIST_INCREMENT 2 //线性表存储空间的分配增量
struct SqList
{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量以sizeof(ElemType)为单位
};
//base_operation.cpp
//顺序表示的线性表包括算法，2.3,2.4,2.5,2.6
void InitList(SqList &L) //算法2.3
{
//操作结果：构造一个空的顺序线性表L
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(! L.elem)
{
exit(OVERFLOW);
}
L.length = 0;//空表长度为0
L.listsize = LIST_INIT_SIZE; //初始化存储分量
}
void DestoryList(SqList &L)
{
//初始条件：顺序线性表L已存在
//操作结果：销毁顺序线性表L
free(L.elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
}
void ClearList(SqList &L)
{
//初始条件；顺序表L已存在
//操作结果：将L置为空表
L.length = 0;
}
Status ListEmpty(SqList L)
{
//初始条件：顺序表L已存在
//操作结果：若L表为空表，则返回TRUE，否则返回FALSE
if(L.length == 0)
{
return TRUE;
}
else
{
return FLASE;
}
}
int ListLength(SqList L)
{
//初始条件：顺序线性表L已存在
//操作结果：返回L中数据元素的个数
return L.length;
}
Status GetElem(SqList L,int i,ElemType &e)
{
//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值
if(i < 1 || i > L.length)
{
return ERROR;
}
e = *(L.elem + i - 1);
return OK;
}
int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType , ElemType))
{
//初始条件：顺序线性表L已存在compare()是数据元素判定函数,满足为1，否则为0
//操作结果：返回L中第1个与e满足关系compare 的数据元素的位序
ElemType *p;
int i = 1; //i的初始值为第1个元素的位序
p = L.elem; //p的初值为第1个元素的存储位置
while(i <= L.length && !compare(*p++,e))
{
++i;
}
if(i <= L.length)
{
return i;
}
else
{
return 0;
}
}
Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{
//初始条件：顺序线性表L已存在
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意义
int i = 2;
ElemType *p = L.elem + 1;
while(i <= L.length && *p != cur_e)
{
p++;
i++;
}
if(i > L.length)
{
return INFEASIBLE; //操作失败
}
else
{
pre_e = *--p;
return OK;
}
}
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{
//初始条件：顺序线性表L已存在
//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败
int i = 1;
ElemType *p = L.elem;
while(i < L.length && *p != cur_e)
{
i++;
p++;
}
if(i == L.length)
{
return INFEASIBLE;//操作失败
}
else
{
//next_e = *p++;
next_e = *++p;
return OK;
}
}
Status ListInsert(SqList &L,int i,ElemType e) //算法2.4
{
//初始条件：顺序线性表已存在，且1<=i<=ListLength(L)+1
//操作结果：在L中的第i个元素位置之前插入新的数据元素e,L的长度加1
ElemType *newbase ,*q, *p;
if(i < 1 || i > L.length + 1)
{
return ERROR;
}
if(L.length >= L.listsize)//当前存储空间已满，增加分配
{
if(!(newbase = (ElemType *)realloc(L.elem,(L.listsize + LIST_INCREMENT) * sizeof(ElemType))))
{
exit(OVERFLOW);//存储分配失败
}
L.elem = newbase;//新基址
L.listsize += LIST_INCREMENT; //增加存储容量
}
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 OK;
}
Status ListDelete(SqList &L,int i, ElemType &e)
{
//初始条件：顺序线性表已存在，1<=i<=L.length(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ElemType *p,*q;
if(i < 1 || i > L.length)
{
return ERROR;
}
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 OK;
}
void ListTraverse(SqList L,void (*vi)(ElemType&))
{
//初始条件：顺序线性表L已存在
//操作结果：依次对L的每个数据元素调用vi()，vi()的形参加&，表明可以通过vi()改变元素的值
ElemType *p;
int i;
p = L.elem;
for(i = 1; i <= L.length; i++)
{
vi(*p++);
}
printf("n");
}
// function_1.cpp
Status equal(ElemType c1,ElemType c2)
{
//判断是否相等的函数
if(c1 == c2)
{
return OK;
}
else
{
return FLASE;
}
}
int comp(ElemType a,ElemType b)
{
//根据a< = > b 分别返回-1,0,1
if(a == b)
{
return 0;
}
else
{
return (a - b)/abs(a - b);
}
}
void print(ElemType c)
{
printf("%d",c);
}
void print2(ElemType c)
{
printf("%c",c);
}
void print1(ElemType &c)
{
printf("%d ",c);
}
Status sq(ElemType c1, ElemType c2)
{
//数据元素判定函数平方关系，LocateElem()调用的函数
if(c1 == c2*c2)
{
return TRUE;
}
else
{
return FLASE;
}
}
void db1(ElemType &c)
{
//ListTraverse()调用的另一函数
c *= 2;
}
//# include "c_1.h"
//typedef int ElemType;
//# include "c_2.h"
//# include " base_operation.cpp "
//# include "function_1.cpp"
void Union(SqList &La, SqList Lb)
{
//讲表中在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,equal))
{
ListInsert(La,++La_len,e);
}
}
}
void main()
{
SqList La,Lb;
int j;
InitList(La); //创建空表La。如不成功，则会退出程序的运行
for(j = 1; j <= 5; j++)
{
ListInsert(La,j,j);
}
printf("La = "); //输出La的内容
ListTraverse(La,print1);
InitList(Lb);
for(j = 1; j <= 5; j++)
{
ListInsert(Lb,j,2*j);
}
printf("Lb = ");//输出Lb的内容
ListTraverse(Lb,print1);
Union(La,Lb);
printf("new La = ");//输出新的La的内容
ListTraverse(La,print1);
}