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

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

阅读量：5752 次

发布时间：2019-06-18

本文共 5056 字，大约阅读时间需要 16 分钟。

每个函数都做了很清晰的注释，适合初学数据结构的朋友。

表中在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);

}

//Microsoft Visual C++ 6.0 运行成功

转载于:https://blog.51cto.com/liam2199/1039186

你可能感兴趣的文章

读书笔记-高标管事低调管人

查看>>

Master带给世界的思考：是“失控”还是进化

查看>>

用户和开发者不满苹果iCloud问题多多

查看>>

java.lang.UnsatisfiedLinkError：no dll in java.library.path终极解决之道

【跃迁之路】【460天】程序员高效学习方法论探索系列（实验阶段217-2018.05.11）...

查看>>

C++入门读物推荐

查看>>

TiDB 源码阅读系列文章（七）基于规则的优化

查看>>

Spring之旅第八站：Spring MVC Spittr舞台的搭建、基本的控制器、请求的输入、表单验证、测试(重点)...

查看>>

数据结构与算法——常用排序算法及其Java实现

查看>>

你所不知的Webpack-多种配置方法

查看>>

webpack+typescript+threejs+vscode开发

查看>>

python读excel写入mysql小工具