用順序表求集合的交集、並集和差集
使用順序表時, 需要定義一個數組來存儲順序表中的所有元素和定義一個整型變數來存儲順序表的長度。假定數組用data[MaxSize]表示，長度整型變數用length表示，並採用結構體類型表示，元素類型採用通用類型標識符ElemType，則順序表的存儲結構定義如下：
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
1
2
3
4
5
6
7
1) 用順序表，求集合A與B交集
思路：求C=A?BC=A?B, CC中元素是A、BA、B中的公共元素。掃描AA中的元素A.data[i]A.data[i]，若它與BB中某個元素相同，表示是交集元素，將其放到CC中，演算法如下：
//求A∩B
void Intersection(SqList *&A,SqList *&B,SqList *&C){
int i,j,k=0;
for (i=0;i<A->length;i++)
{
j=0;
while(j<B->length && B->data[j]!=A->data[i])
j++;
if (j<B->length) //表示A->data[i]在B中，將其放到C中
{
C->data[k++]=A->data[i];
}
}
C->length=k;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2) 用順序表，求集合A與B的並集
思路：求C=A?BC=A?B中元素為AA和BB中非重複出現的所有元素。現將AA複製到CC中，然後掃描BB中的元素B.data[i]B.data[i], 若它與AA中所有元素均不相同，表示是並集元素，將其放到CC中。演算法如下：
//求A∪B
void Union(SqList *&A,SqList *&B,SqList *&C){
int i,j,k=0;
for(i=0;i< A->length;i++)
C->data[i]=A->data[i];
C->length=A->length;
for (i=0;i< B->length;i++)
{
j=0;
while(j< A->length && B->data[i] != A->data[j])
j++;
if(j==A->length)
C->data[C->length+k++] = B->data[i];
//k++;
}
C->length += k; //修改集合長度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3) 用順序表，求集合A與B之間的差集
思路：求C=A?BC=A?B, CC中元素為AA中所有不屬於BB的元素, 然後掃描AA中的元素A.data[i]A.data[i], 若它與BB中所有元素均不相同，表示是差集元素，將其放到CC中。演算法如下：
//求A-B
void Different(SqList *&A, SqList *&B,SqList *&C){
int i,j,k=0;
for (i=0;i<A->length;i++)
{
j=0;
while(j< B->length && B->data[j] != A->data[i])
j++;
if(j==B->length) //表示A->data[i]不在B中，將其放到C中
C->data[k++]=A->data[i];
}
C->length=k; //修改集合長度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
完整代碼如下：
//ShunBase.h
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList *&L){
L=(SqList*)malloc(sizeof(SqList));
L->length=0;
}
void DestroyList(SqList *L){
free(L);
}
int ListEmpty(SqList *L){
return (L->length==0);
}
int ListLength(SqList *L){
return (L->length);
}
void DispList(SqList *L){
int i;
if(ListEmpty(L)) return;
for(i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf("
");
}
int GetElem(SqList *L,int i,ElemType &e){
if(i<1 || i>L->length)
return 0;
e=L->data[i-1];
return 1;
}
int LocateElem(SqList *L,ElemType e){
int i=0;
while (i<L->length && L->data[i]!=e) i++;
if(i>=L->length)
return 0;
else
return i+1;
}
int ListInsert(SqList *&L,int i,ElemType e){
int j;
if(i<1 || i>L->length+1)
return 0;
i--; //將邏輯序號轉化為存儲序號
for(j=L->length;j>i;j--) //將data[i]及其以後元素，依次後移
L->data[j]=L->data[j-1];
L->data[i]=e; //在i處插入元素e
L->length++; //順序表長度加1
return 1;
}
int ListDelete(SqList *&L,int i,ElemType &e){
int j;
if(i<1 || i>L->length)
return 0;
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return 1;
}
//主函數.cpp
#include "ShunBase.h"
#include <stdio.h>
//求A∩B
void Intersection(SqList *&A,SqList *&B,SqList *&C){
int i,j,k=0;
for (i=0;i<A->length;i++)
{
j=0;
while(j< B->length && B->data[j]!=A->data[i])
j++;
if (j< B->length) //表示A->data[i]在B中，將其放到C中
{
C->data[k++]=A->data[i];
}
}
C->length=k;
}
//求A∪B
void Union(SqList *&A,SqList *&B,SqList *&C){
int i,j,k=0;
for(i=0;i< A->length;i++)
C->data[i]=A->data[i];
C->length=A->length;
for (i=0;i< B->length;i++)
{
j=0;
while(j< A->length && B->data[i] != A->data[j])
j++;
if(j==A->length)
C->data[C->length+k++] = B->data[i];
//k++;
}
C->length += k; //修改集合長度
}
//求A-B
void Different(SqList *&A, SqList *&B,SqList *&C){
int i,j,k=0;
for (i=0;i<A->length;i++)
{
j=0;
while(j< B->length && B->data[j] != A->data[i])
j++;
if(j==B->length) //表示A->data[i]不在B中，將其放到C中
C->data[k++]=A->data[i];
}
C->length=k; //修改集合長度
}
void main()
{
//printf("1+2=3
");
SqList *Ls = (SqList *)malloc(sizeof(SqList));
Ls->length=0;
//printf("%d
",Ls->length);
//插入元素
// int i=0;
// for (i=0;i<10;i++)
// {
// ListInsert(Ls,i,i);
// }
// DispList(Ls);
// ElemType e;
// //獲取第一個元素
// GetElem(Ls,1,e);
// printf("
%d
",e);
// //獲取第三個元素
// GetElem(Ls,3,e);
// printf("%d
",e);
// //在第3個元素之後，插入15
// ListInsert(Ls,3,15);
// DispList(Ls);
SqList *A = (SqList*)malloc(sizeof(SqList));
A->length=0;
A->data[0]=2;
A->data[1]=5;
A->data[2]=10;
A->data[3]=7;
A->data[4]=16;
A->length=5;
SqList *B = (SqList*)malloc(sizeof(SqList));
B->data[0]=3;
B->data[1]=5;
B->data[2]=7;
B->length=3;
SqList *C = (SqList*)malloc(sizeof(SqList));
C->length=0;
DispList(A);
DispList(B);
//1) C=A∩B
//Intersection(A,B,C);
//2) C=A∪B
Union(A,B,C);
//3) C=A-B
//Different(A,B,C);
DispList(C);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
效果如下：
圖(1) 交集C=A?BC=A?B
圖(2) 並集C=A?BC=A?B
圖(3) 差集C=A?BC=A?B
圖示操作如下：
圖(4) C=A?BC=A?B
圖(5) C=A?BC=A?B
圖(6) C=A?B
※對大數據系統的了解
※sql語句的使用&mysql單表練習（小白專用版之二）
TAG:程序員小新人學習 |