静态链表的集合运算（第二章 P33 算法2.17）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了静态链表的集合运算（第二章 P33 算法2.17），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3998字，纯文字阅读大概需要6分钟。
内容图文
静态链表的集合运算
题目：
使用静态链表的算法实现集合运算 （A-B）U （B-A）
例 2-3 ： 假设由终端输入集合元素，先建立表示集合 A 的静态链表 S，而后在输入集合 B 的元素的同时查找 S 表，若存在和 B 相同的元素，则从 S 表中删除之，否则将此元素插入 S 表。
这个算法设计得非常巧妙，算法中设置 r 一直指向输入集合 A 中的最后一个元素，保证 B 中的待插入元素只和 A中元素比较，和不会和后插入的 B 中元素比较。至此，还需要考虑细节， r 的移动，当删除的元素为 r 指向的元素（即 A 中最后一个元素）时，需将 r 前移。
另，B 中的元素插入是从插入作为 r 的后继，因此，应注意到，最后输出中，B 中的插入元素是逆序的。
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef char ElemType;
#include<malloc.h> /* malloc()等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//#define OVERFLOW -2
/* ----------------------- 线性表的静态单链表存储结构 ------------------------*/
//见课本 P31 下方的类型说明
#define MAXSIZE 100 /* 链表的最大长度 */
typedef struct
{
ElemType data;
int cur;
}component, SLinkList[MAXSIZE];
/* ---------------------------------------------------------------------------*/
void visit(ElemType c)
{
printf("%c ", c);
}
/* ---------------------------- 需要用到的线性表的静态单链表的基本操作实现 ---------------------------------*/
int Malloc(SLinkList space) /* 算法2.15 */
{ /* 若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回0 */
int i = space[0].cur;
if (i) /* 备用链表非空 */
space[0].cur = space[i].cur; /* 备用链表的头结点指向原备用链表的第二个结点 */
return i; /* 返回新开辟结点的坐标 */
}
void Free(SLinkList space, int k) /* 算法2.16 */
{ /* 将下标为k的空闲结点回收到备用链表(成为备用链表的第一个结点) */
space[k].cur = space[0].cur; /* 回收结点的＂游标＂指向备用链表的第一个结点 */
space[0].cur = k; /* 备用链表的头结点指向新回收的结点 */
}
void InitSpace(SLinkList L) /* 算法2.14。 */
{ /* 将一维数组L中各分量链成一个备用链表，L[0].cur为头指针。“0”表示空指针 */
int i;
for (i = 0; i < MAXSIZE - 1; i++)
L[i].cur = i + 1;
L[MAXSIZE - 1].cur = 0;
}
Status ListTraverse(SLinkList L, int n, void(*vi)(ElemType))
{ /* 依次对L中表头位序为n的链表的每个数据元素,调用函数vi()。一旦vi()失败,则操作失败 */
int i = L[n].cur; /* 指向第一个元素 */
while (i) /* 没到静态链表尾 */
{
vi(L[i].data); /* 调用vi() */
i = L[i].cur; /* 指向下一个元素 */
}
printf("\n");
return OK;
}
/* -----------------------------------------------------------------------------------------------------*/
void difference(SLinkList space, int *S) /* 算法2.17 */
{ /* 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)∪(B-A) */
/* 的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为备用空间的头指针 */
int r, p, m, n, i, j, k;
ElemType b;
InitSpace(space); /* 初始化备用空间 */
*S = Malloc(space); /* 生成S的头结点 */
r = *S; /* r指向S的当前最后结点 */
printf("请输入集合A和B的元素个数m,n:");
scanf_s("%d %d%*c", &m, &n); /* %*c吃掉回车符 */
printf("请输入集合A的元素（共%d个）:", m);
for (j = 1; j <= m; j++) /* 建立集合A的链表 */
{
i = Malloc(space); /* 分配结点 */
scanf_s("%c", &space[i].data); /* 输入A的元素值 */
space[r].cur = i; /* 插入到表尾 */
r = i;
}
scanf_s("%*c"); /* %*c吃掉回车符 */
space[r].cur = 0; /* 尾结点的指针为空 */
printf("请输入集合B的元素（共%d个）:", n);
for (j = 1; j <= n; j++)
{ /* 依次输入B的元素,若不在当前表中,则插入,否则删除 */
scanf_s("%c", &b);
p = *S;
k = space[*S].cur; /* k指向集合A中的第一个结点 */
while (k != space[r].cur&&space[k].data != b)
{ /* 在当前表中查找 */
p = k;
k = space[k].cur;
}
if (k == space[r].cur)
{ /* 当前表中不存在该元素，插入在r所指结点之后，且r的位置不变 */
i = Malloc(space);
space[i].data = b;
space[i].cur = space[r].cur;
space[r].cur = i;
}
else /* 该元素已在表中，删除之 */
{
space[p].cur = space[k].cur;
Free(space, k);
if (r == k)
r = p; /* 若删除的是尾元素，则需修改尾指针 */
}
}
}
void main()
{
int k;
SLinkList s;
difference(s, &k);
ListTraverse(s, k, visit);
}
运行结果：
内容总结
以上是互联网集市为您收集整理的静态链表的集合运算（第二章 P33 算法2.17）全部内容，希望文章能够帮你解决静态链表的集合运算（第二章 P33 算法2.17）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。