社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
1. 采用递增有序的顺序表表示集合,求解两个集合的交集
(1)定义顺序表的存储结构;
(2)实现存储递增有序集合的顺序表的建立、求交集运算;
2. 采用递增有序的链表表示集合,求解两个集合的交集
(1)定义链表的存储结构;
(2)实现存储递增有序集合的链表的建立、求交集运算;
3. 比较顺序表和链表的优缺点和适用场合
1.顺序表
#include<stdio.h>
#include<iostream>
using namespace std;
#define InitSize 20//表长度的初始定义
typedef int ElemType;
typedef struct {
ElemType* data;//指示动态分配数组的指针
int MaxSize;//数组的最大容量
int Length;//数组当前个数
}SqList;//动态分配数组顺序表的类型定义
//初始化顺序表
SqList InitList(SqList& L) {
L.data = new ElemType[InitSize];//C++的初始动态分配语句
if (!L.data) {
printf("初始化失败");
exit(OVERFLOW);
}
L.Length = 0;
L.MaxSize = InitSize;
return L;
}
//创建顺序表
SqList CreateList(SqList& L) {
int n;
printf("需要输入的顺序表的个数为:");
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
scanf_s("%d",&L.data[i]);
L.Length++;
}
return L;
}
//显示顺序表
void DisplayList(SqList L) {
for (int i = 0; i < L.Length; i++) {
printf("%d", L.data[i]);
printf(" ");
}
printf("\n\n");
}
//求交集
void InterSection(SqList &L1, SqList &L2,SqList &L3) {
int i = 0,j = 0,k=0;
while (i < L1.Length && j < L2.Length) {
if (L1.data[i] == L2.data[j]) { //如果L1和L2的元素相等,则记录到L3
L3.data[k] = L1.data[i];
i++;
j++;
k++;
}
else {
if (L1.data[i] < L2.data[j])//如果L1的元素<L2的元素,则记录L1的i值加一
i++;
else //如果L1的元素>L2的元素,则记录L2的j值加一
j++;
}
L3.Length = k; //重新定义下L3的长度
}
}
//主函数
int main() {
SqList L1,L2,L3;
//初始化并创建顺序表L1
InitList(L1);
CreateList(L1);
printf("创建的第一个顺序表L1为:");
DisplayList(L1);
//初始化并创建顺序表L2
InitList(L2);
CreateList(L2);
printf("创建的第二个顺序表L2为:");
DisplayList(L2);
//求顺序表L1和顺序表L2的交集
InitList(L3);
InterSection(L1, L2, L3);
printf("顺序表L1和顺序表L2的交集为:");
DisplayList(L3);
return 0;
}
2.单链表
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode {//定义单链表结点类型
ElemType data;//数据域
struct LNode* next;//指针域
}LNode,*LinkList;
//初始化单链表
LinkList InitList() {
LinkList L;
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) {
printf("初始化失败!\n");
exit(1);
}
L->next = NULL;
return L;
}
//用尾插法建立单链表
LinkList List_TailInsert(LinkList& L) {
//从表头到表尾正向建立单链表L,每次均在表尾插入元素
int x;//设元素类型为整型
L = (LinkList)malloc(sizeof(LNode));
LNode* s, * r = L;//r为表尾指针
scanf_s("%d", &x);//输入结点的值
while (x != -1) {//输入-1表示结束
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;//r指向新的表尾结点
scanf_s("%d", &x);
}
r->next = NULL;//尾结点指针置空
return L;
}
//打印单链表
void PrintList(LinkList L) {
LNode* p;
p = L->next;
while (p != NULL) {
printf("%d->", p->data);
p = p->next;
}
printf("\n");
}
//单链表求交集
void InterSection(LinkList A, LinkList B, LinkList &C) {
//本算法产生单链表A和B的公共元素的单链表C
C = InitList();
LNode* p = A->next, * q = B->next, * r, * s;
C = (LinkList)malloc(sizeof(LNode));//建立表C
r = C;//r始终指向C的尾结点
while (p != NULL && q != NULL) {//循环跳出条件
if (p->data < q->data)
p = p->next;//若A的当前元素较小,后移指针
else if (p->data > q->data)
q = q->next;//若B的当前元素较小,后移指针
else {//找到公共元素结点
s = (LNode*)malloc(sizeof(LNode));
s->data = p->data;//复制产生结点*s
r->next = s;//将*s链接到C上(尾插法)
r = s;
p = p->next;//表A和B继续向后扫描
q = q->next;
}
}
r->next = NULL;//置C尾结点指针为空
}
//主函数
int main() {
LinkList L1,L2,L3;//单链表的头指针
//创建第一个单链表
L1 = InitList();
printf("以输入-1结束,用头插法创建的第一个单链表为:");
L1 = List_TailInsert(L1);
PrintList(L1);
//创建第二个单链表
L2 = InitList();
printf("以输入-1结束,用头插法创建的第一个单链表为:");
L2 = List_TailInsert(L2);
PrintList(L2);
//求交集
L3 = InitList();
printf("两个单链表的交集为:");
InterSection(L1, L2, L3);
PrintList(L3);
}
1.顺序表
2.单链表
1.线性表的顺序存储类型描述中有ElemType的元素类型,但是在VC中需要typedef int ElemType,才能使用,否则会出现未定义标识符ElemType
2.出现C6031 返回值被忽略: "scanf"的原因是因为在ANSI C中没有scanf_s(),只有scanf(),但是scanf()在读取时不检查边界,所以可能会造成内存泄露。于是Microsoft公司在VS中提供了scanf_s(),所以只需要把把scanf换为scanf_s就可以解决问题了
3.出现引发了未经处理的异常:写入访问权限冲突的问题是因为没有初始化顺序表,所以只需要InitList(L);就可以解决这个问题了
4.LinkList和LNode*不同名字的同一个指针类型,LinkList类型的指针变量head表示他是单链表的头指针,LNode *类型的指针变量p表示它是指向某一结点的指针
5.求单链表的交集时打印的结果一直出不来,困扰了好久,后来上网查找,比对了别人的代码,发现自己缺少了一个&,导致对链表修改的失败,打印不出来结果
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!