顺序表如何实现两个集合的交并差集
为什么case2，3，4都运行不出来
#include
using namespace std;
#include"SqList.h"
char pause;
void dispmenu()
{
cout << endl;
cout << "1-创建集合\n";
cout << "2-集合A、B交\n";
cout << "3-集合A、B并\n";
cout << "4-集合A、B差\n";
cout << "0-退出\n";
}
//交
template<class DT>
void InterSet(SqList La, SqList Lb, SqList & Lc) //两个集合的交
{
int j = 0;
char e = ' ';
for (int i = 1; i <= La.length; i++)
{
if (GetElem_i(La, i, e))
if (LocateElem_e(Lb, e))
InsertElem_i(Lc, i, e);
}
Lc.length = j;
}
//并
template<class DT>
void Union(SqList & La, SqList Lb) //两个集合的并
{
for (int i = 1; i < Lb.length; i++)
{
char e = ' ';
GetElem_i(Lb, i, e);
if (!LocateElem_e(La, e))
{
int k = La.length + 1;
InsertElem_i(La, k, e);
}
}
}
//cha
template<class DT>
void SubSet(SqList La, SqList Lb, SqList & Lc) //两个集合的差
{
int j = 0;
char e = ' ';
for (int i = 1; i <= La.length; i++)
{
if (GetElem_i(La, i, e))
if (!LocateElem_e(Lb, e))
InsertElem_i(Lc, j++, e);
}
Lc.length = j;
}
int main()
{
int na, nb;
int i = 0, j = 0;
char e = ' ';
SqList<char> La; //建立容量为20、元素类型为字符型的空顺序表
SqList<char> Lb;
SqList<char> Lc;
system("cls");
int choice;
do
{
dispmenu(); //显示主菜单
cout << "Enter choice(1~4，0 退出):";
cin >> choice;
switch (choice)
{
case 1: //初始化线性表 La,Lb
cout << "请输入要创建的顺序表La的长度：";
cin >> na;
InitList(La, na);
cout << endl << "创建成功！" << endl;
cout << "请输入要创建的元素个数:";
cin >> na;
CreateList(La, na);
cout << "创建的顺序表La元素为：\n"; //显示表元素La
DispList(La);
cout << endl;
cout << "请输入要创建的顺序表Lb的长度：";
cin >> nb;
InitList(Lb, nb);
cout << endl << "创建成功！" << endl;
cout << "请输入要创建的元素个数:";
cin >> nb;
CreateList(Lb, nb);
cout << "创建的顺序表Lb元素为：\n"; //显示表元素Lb
DispList(Lb);
cout << endl;
break;
case 2: //两个集合的交
InitList(Lc,na);
InterSet(La, Lb, Lc);
cout << "A与B的交集为：" << endl;
DispList(Lc);
cout << endl;
ClearList(La);
ClearList(Lb);
ClearList(Lc);
break;
case 3:
Union(La, Lb);
cout << "A与B的并集为：" << endl;
DispList(La);
cout << endl;
ClearList(La);
ClearList(Lb);
break;
case 4:
InitList(Lc, na+nb);
SubSet(La, Lb, Lc);
cout << "A与B的差为：" << endl;
DispList(Lc);
cout << endl;
ClearList(La);
ClearList(Lb);
ClearList(Lc);
break;
case 0: //退出
cout << "结束运行bye-bye!" << endl;
break;
default: //无效选择
cout << "无效选择!\n";
break;
}
} while (choice != 0);
return 1;
};
这个是头文件
template <class DT>
struct SqList // 顺序表
{
DT *elem; // 表首址
int length; // 表长
int size; // 表容量
};
//算法2.1
template <class DT>
bool PriorElem_e(SqList<DT> L, DT e, DT &pre_e) // 求值为e的元素前驱
{
int k;
k=LocateElem_e(L,e); //
if(k>1)
{
GetElem_i(L,k-1,pre_e);
return true;
}
else
return false;
}
//【算法2.2】 初始化
template <class DT>
bool InitList(SqList<DT> &L, int m)
{
L.elem=new DT[m]; // 申请表空间
if(L.elem==NULL)
{
cout<<"未创建成功！"; // 申请不成功，退出
exit (1);
}
L.length=0; // 申请成功，属性赋值。空表，表长为0
L.size=m; // 表容量为m
return true;
}
//【算法2.3】 创建表元素
template <class DT>
bool CreateList(SqList<DT> &L,int n)
{
int i;
if(n>L.size) // 1.元素个数大于表容量，不能创建。
{
cout<<"元素个数大于表长，不能创建！"<return true;
}
cout<<"请依次输入"<"个元素值："<// 2.依位序输入各元素值
for(i=1;i<=n;i++)
cin>>L.elem[i-1];
L.length=n; // 3.表长为创建的元素个数
return false;
}
//【算法2.4】 销毁顺序表
template <class DT>
void DestroyList(SqList<DT> &L)
{
delete [] L.elem; // 1.释放表空间
L.length=0; // 2.属性赋值
L.size=0;
}
//【算法2.5】 获取第i个元素值
template<class DT>
bool GetElem_i(SqList<DT> L,int i, DT &e)
{
if(i<1 || i>L.length) // 1.位序不合理，返回false
{
cout<<"该元素不存在！"<return false;
}
e=L.elem[i-1]; // 2. 否则，获取第i个元素值
return true; // 返回true
}
//【算法2.6】 按值查找
template<class DT>
int LocateElem_e(SqList<DT> L, DT e)
{
for(int i=0; i// 顺序查找
if(L.elem[i]==e) // 1.找到
return i+1; // 返回元素位序
return 0; // 2.未找到，返回0
}
//【算法2.7】
template<class DT>
bool InsertElem_i(SqList<DT> &L,int i, DT e)
{
if(L.length>=L.size) // 1.表满，不能插入
return false;
if(i<1 || i>L.length+1) // 2.插入位置不合理，不能插入
return false;
for (int j=L.length; j>=i; j--) // 3. an~ai依次后移
L.elem[j]=L.elem[j-1];
L.elem[i-1]=e;
L.length++;
return true; // 插入成功，返回true
}
//【算法2.8】 删除第i个元素
template<class DT>
bool DeleElem_i(SqList<DT> &L,int i)
{
if(L.length==0) // 1.表空，不能删除
return false;
if(i<1 || i>L.length) // 2.删除位置不合理，不能插入
return false;
for (int j=i; j// 3. ai+1~an依次前移
L.elem[j-1]=L.elem[j];
L.length--;
return true; // 删除成功，返回true
}
//【算法2.9】
template<class DT>
bool PutElem(SqList<DT> &L,int i, DT e) // 修改第i个元素的值
{
if(i<1 || i>L.length) // 1.位序不合理，不能修改，
return false; // 返回false
L.elem[i-1]=e; // 2.重置第i个元素值
return true; // 3.修改成功，返回true
}
// 清空顺序表
template<class DT>
void ClearList(SqList<DT> &L)
{
L.length=0; // 空表，表长为0
}
// 测表长
template<class DT>
int ListLength(SqList<DT> L)
{
return L.length;
}
template<class DT>
bool ListEmpty(SqList<DT> L) // 测表空
{
if(L.length==0) // 空表，返回true
return true;
else
return false; // 非空表，返回false
}
template<class DT>
bool ListFull(SqList<DT> L)
{
if(L.length==L.size) // 表满，返回true
return true;
else
return false; // 表不满，返回false
}
//【算法2.10】 遍历输出
template <class DT>
void DispList(SqList<DT> L)
{
int i;
for(i=0;i// 依位序输出元素值
{
cout<"\t";
}
cout< 回答：你这个是采用C++模板写的，具体代码我也没有仔细看，我这里也写了一个求交集、并集、差集的，采用链表和顺序表的都有，代码如下：希望能对你有一些帮助
第一个是：链表表示集合，求解集合的并集
# include <iostream>
# include <stdlib.h>
using namespace std;
#define OK 1
#define ERROR 0
typedef int elementType;
struct Node
{
elementType val;
Node* next;
};
class LinkList
{
public:
LinkList();
int add(elementType val);
Node* getHead();
LinkList unionSet(LinkList list);
void printList();
private:
Node* head;
};
int main()
{
LinkList list1;
int temp1[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8 };
int length1 = sizeof(temp1) / sizeof(temp1[0]);
for (int i = 0; i < length1; i++)
{
list1.add(temp1[i]);
}
list1.printList();
LinkList list2;
int temp2[] = { 10, 0, 3, 6, 9 };
int length2 = sizeof(temp2) / sizeof(temp2[0]);
for (int i = 0; i < length2; i++)
{
list2.add(temp2[i]);
}
list2.printList();
LinkList list3 = list1.unionSet(list2);
list3.printList();
}
LinkList::LinkList()
{
head = (Node*)malloc(sizeof(Node));
head->next = NULL;
}
int LinkList::add(elementType val)
{
if (head->next == NULL)
{
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
head->next = node;
node->next = NULL;
return OK;
}
Node* cur = getHead();
while (cur->next != NULL)
{
if (cur->val == val)
{
return ERROR;
}
cur = cur->next;
}
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
cur->next = node;
node->next = NULL;
return OK;
}
Node* LinkList::getHead()
{
return head->next;
}
LinkList LinkList::unionSet(LinkList list)
{
LinkList res;
Node* cur1 = getHead();
Node* cur2 = list.getHead();
while (cur1 != NULL)
{
res.add(cur1->val);
cur1 = cur1->next;
}
while (cur2 != NULL)
{
res.add(cur2->val);
cur2 = cur2->next;
}
return res;
}
void LinkList::printList()
{
Node* cur = head->next;
while (cur != NULL)
{
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
/*
测试数据一:
1 3 5 7 9 2 4 6 8
10 0 3 6 9
预期结果:
1 3 5 7 9 2 4 6 8 10 0
*/
第2个是：对递增有序的顺序表表示的集合，求解差集
# include <iostream>
# include <stdlib.h>
using namespace std;
#define MAX_LENGTH 20
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNDERFLOW -2
typedef int elementType;
class Seq
{
public:
Seq();
int add(elementType val);
elementType* getA();
int getCount();
Seq differSet(Seq seq);
void printSeq();
private:
elementType A[MAX_LENGTH];
// count表示当前元素个数
int count;
};
int main()
{
Seq seq1;
for (int i = 0; i < 7; i++)
{
seq1.add(i + 1);
}
seq1.printSeq();
Seq seq2;
for (int i = 2; i < 6; i++)
{
seq2.add(i + 1);
}
seq2.printSeq();
Seq seq3 = seq1.differSet(seq2);
seq3.printSeq();
}
Seq::Seq()
{
count = 0;
}
int Seq::add(elementType val)
{
if (count == MAX_LENGTH)
{
return OVERFLOW;
}
for (int i = 0; i < count; i++)
{
if (A[i] == val)
{
return ERROR;
}
}
A[count] = val;
count++;
return OK;
}
elementType* Seq::getA()
{
elementType* temp = new int[getCount()];
for (int i = 0; i < count; i++)
{
temp[i] = A[i];
}
return temp;
}
int Seq::getCount()
{
return count;
}
Seq Seq::differSet(Seq seq)
{
Seq res;
elementType* c1 = getA();
elementType* c2 = seq.getA();
int count1 = getCount();
int count2 = seq.getCount();
int index1 = 0;
int index2 = 0;
while (index1 < count1 && index2 < count2)
{
if (c1[index1] < c2[index2])
{
res.add(c1[index1]);
index1++;
}
else if (c1[index1] == c2[index2])
{
index1++;
index2++;
}
else
{
index2++;
}
}
while (index1 < count1)
{
res.add(c1[index1++]);
}
return res;
}
void Seq::printSeq()
{
for (int i = 0; i < count; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
/*
测试数据一:
1 2 3 4 5 6 7
3 4 5 6
预期结果:
1 2 7
*/
第3个是：求递增有序链表表示集合的交集
# include <iostream>
# include <stdlib.h>
using namespace std;
#define OK 1
#define ERROR 0
typedef int elementType;
struct Node
{
elementType val;
Node* next;
};
class LinkList
{
public:
LinkList();
int add(elementType val);
Node* getHead();
LinkList interSet(LinkList list);
void printList();
private:
Node* head;
};
int main()
{
LinkList list1;
int temp1[] = { 1, 3, 5, 7, 9 };
int length1 = sizeof(temp1) / sizeof(temp1[0]);
for (int i = 0; i < length1; i++)
{
list1.add(temp1[i]);
}
list1.printList();
LinkList list2;
//int temp2[] = { 1, 3, 5 };
int temp2[] = { 3, 5, 7, 9, 11 };
int length2 = sizeof(temp2) / sizeof(temp2[0]);
for (int i = 0; i < length2; i++)
{
list2.add(temp2[i]);
}
list2.printList();
LinkList list3 = list1.interSet(list2);
list3.printList();
}
LinkList::LinkList()
{
head = (Node*)malloc(sizeof(Node));
head->next = NULL;
}
int LinkList::add(elementType val)
{
if (head->next == NULL)
{
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
head->next = node;
node->next = NULL;
return OK;
}
Node* cur = getHead();
while (cur->next != NULL)
{
if (cur->val == val)
{
return ERROR;
}
cur = cur->next;
}
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
cur->next = node;
node->next = NULL;
return OK;
}
Node* LinkList::getHead()
{
return head->next;
}
LinkList LinkList::interSet(LinkList list)
{
LinkList res;
Node* cur1 = getHead();
Node* cur2 = list.getHead();
while (cur1 != NULL && cur2 != NULL)
{
if (cur1->val == cur2->val)
{
res.add(cur1->val);
cur1 = cur1->next;
cur2 = cur2->next;
}
else if (cur1->val < cur2->val)
{
cur1 = cur1->next;
}
else if (cur1->val > cur2->val)
{
cur2 = cur2->next;
}
}
return res;
}
void LinkList::printList()
{
Node* cur = head->next;
while (cur != NULL)
{
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
/*
测试数据一:
1 3 5 7 9
3 5 7 9 11
预期结果:
3 5 7 9
*/
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/1058873
- 这篇博客也不错, 你可以看下苹果手机怎么备份所有数据，2个步骤轻松解决（免费）
- 除此之外, 这篇博客: 【指针笔试题(3)(完结篇)】中的 笔试题2 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
题目：下列代码假设p 的值为0x100000。 如下表表达式的值分别为多少？
已知，结构体Test类型的变量大小是20个字节struct Test { int Num; char *pcName; short sDate; char cha[2]; short sBa[4]; }*p; int main() { printf("%p\n", p + 0x1); printf("%p\n", (unsigned long)p + 0x1); printf("%p\n", (unsigned int*)p + 0x1); return 0; }解答环节：因为p是结构体指针,0x1是一个16进制的数字为1，p+1即跳过一个结构体
所以第一个表达式p+1=0x100020，第二个表达式中，p被强制转换成了一个整型数字
再加上0x1,所以第二个表示为0x100001，第三个表达式与第一个相似，只不过是将
结构体类型指针转化为整形指针,此时p访问权限为4个字节，所以第三个表达式为
0x100004（0x100014 0x100001 0x100004）.
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^