/*已知一个非纯集合 B,试构造一个纯集合 A,使 A中只包含 B 中所有值各
/ B6 L3 {- t3 X3 S3 h3 `. |' P 不相同的数据元素。*/0 [% E$ F: `* Y: K- D. T
/*算法:逐个比较。将B表的第一个元素存入A表,然后用B表的每一个元素逐个6 C2 c' {- E6 I* t7 a
和A表中的元素进行比较,相等的元素不存入A表,不相等的元素存入A表*/2 w2 Y0 Z. i/ G* b: Q6 X( G
#include <stdio.h>
: i0 i8 ?8 [2 {#include <stdlib.h>
& i# k/ O9 D* ~8 Y4 J: Z( {* {typedef int ElemType; /* 定义元素类型 */
+ m9 k6 M1 F$ ~6 _#define Max 1000 u; L: J8 P% q8 [1 @/ ]/ k
#define Increment 10/ }2 n8 ]8 T7 y0 ]& O3 N
typedef struct: t( z2 W% _3 Y: k+ L
{
5 b, m5 d/ t, B+ V/ g3 x ElemType *elem; /* 定义存储空间的基地址 */* z+ O$ i2 i! A* Z# {8 T
int length; /* 定义表的长度 */
1 ~1 W$ m! Y3 L* n9 N! Y- A+ G int listsize; /* 定义空间容量 */
: v+ z6 S. m0 U: V5 P}Sqlist; /* 定义顺序存储结构 */
& B* v5 v; {! ^* v' v6 ^0 R: T1 USqlist InitList() /* 初始化顺序表 */
: H' R! j: C% g4 x{
' q6 y8 {0 O4 ` Sqlist L;/ S" R' u3 b! [% m' T: C6 \: G
L.elem=(ElemType *)malloc(Max*sizeof(ElemType)); ( D) A) S, F: f
/* 使用malloc()申请空间,空间大小是Max*sizeof(ElemType)个字节,共Max个单元 */9 f4 k. N% W7 l5 n
if(!L.elem)$ @4 o8 J# _& p0 a
exit(!0); /* 判断申请空间是否成功,如失败,则返回;否则开辟空间成功 */2 G; t* D5 S5 x2 N/ d
/* exit(int status)功能是结束程序,status用来保存调用进程的出口状态, */; d/ ]7 W7 x i8 ]
/* 一般的,0表示正常退出,非0表示发生错误。 */# w: Q5 Z! h' N' }% W
L.length=0;
9 v/ a4 _- j! k$ P# ]( @0 R L.listsize=Max;
5 P" n" s; R) [* g return L;/ c, u# b+ O4 ?5 o5 s
}
* s4 h9 V) R: L: D8 s/ g) e; A" svoid CreateList(Sqlist &L) /* 创建顺序表 */
5 H1 G" @+ [# J* J$ O L- F+ V{: B; ~9 d9 O0 h, [8 n
int i,number; /* 元素的个数是number个 */
5 x5 a; y- D) K! U printf("\\n请输入顺序表的元素的个数:");! v) y6 f# l4 K d* U3 W. \% a
scanf("%d",&number);
- W7 }( |$ K7 b) a( [5 O printf("\\n创建顺序表:");1 j* f0 s2 ^ ]0 W
for(i=1;i<=number;i++)) _4 M) x6 S. C$ C
{
6 q1 W1 j4 |8 O8 W printf("\\n请输入第%d个元素的值:",i);4 v# Z9 Z8 X! K4 B! _! f
scanf("%d",&L.elem[i-1]);& d* R, r# F+ B/ f! `0 P
}
" c0 J# Q0 u4 s7 \) t3 {- ~ L.length=number;$ L4 u9 g8 ]1 {9 \6 h3 K$ Y" ]
}
: b* E9 r, s$ X# }* K7 M& m3 Q qvoid GetElem(Sqlist L,int i,ElemType &e) ) ]5 a/ i1 j; H8 T- R& t
/* 用e返回L中第i个元素的值 */( ~: @. i7 ^& O* P) ~) z! z! }
{ ^! ?! W$ e `" v2 [5 o
if(!L.elem)
8 y: N3 l* u' t3 b2 j1 F exit(!0); /* 判断L是否存在,若不存在,操作失败;否则,可以进行操作 */
- m' m- m; G5 g% [0 R( { if(i>=1&&i<=L.length)
' l; m& h: Y1 u: g( X, m e=L.elem[i-1]; /* 取元素 */
8 A4 P f" E; A9 V" d}, N: }5 Y6 t" @# A# Z$ h3 a
int Equal(Sqlist L,ElemType e) 0 }5 ]2 L2 J2 w( f. B8 G. P
/* 在L表中检测与e值相等的元素,若有,返回1;否则返回0 */
2 F* I) T! n) x$ L; G{% V: M- v- |- q# c" u8 |2 G
int i=0;" g# ] L0 m" G3 u. W! W. ~
while(i<L.length)
: C2 i7 e% I/ z, [1 ?* W {
- x; Q- S6 u+ m5 I$ g if(e!=L.elem)i++;9 F( m+ t% D: T" J
else+ R, K% ]. f9 F6 T
return 1;
; V1 M* E$ _$ \( x' X: F }
" F4 n$ D& z9 t& f4 @; _ return 0; 9 ?$ s$ v, J1 o! m" i" a8 R' ^
}! E% o, C3 C0 J9 H: l0 A
void Insert(Sqlist &L,int i,ElemType e)
0 E' ~' I6 P; @( N/* 在表L中的第i个位置插入元素e */. l+ p3 a; V% V- V9 `$ m: B3 n
{
+ S1 h! D5 B! v. E9 G1 I1 z L.elem[i-1]=e;
. h4 f! k7 j7 d) B0 g L.length++;
. X: }1 M" Q; V- z}. ^: [% r" ~) t8 i3 `$ j
void Union(Sqlist &La,Sqlist Lb)
2 h: T3 h+ X0 f; c) I" H; p* B/* 在非纯集合Lb转化为纯集合La */
. O. A; q6 F# J& q{0 K* f1 Y( d6 v2 w1 S, s
int i,k=1; w4 e t7 b3 B, T# [4 }" F
ElemType e;
! f; w, Q+ b0 w" v La.elem[0]=Lb.elem[0];
! \! Q! {8 S8 E3 W8 z La.length=1;( \( q: i* g* e- e+ k% k# [
for(i=1;i<=Lb.length;i++)
% Z' b6 R& Z$ | V0 |6 E7 `9 Z {
# o# n D6 y. L# ` Q; y GetElem(Lb,i,e);
5 p( z9 ^" [' t8 h) U if(!Equal(La,e))
" V% I' e# A5 E t3 U7 j Insert(La,++k,e);
% G: ^) d: {) q& s- y: a6 P& P }8 M! D! ?# k' Y5 c: B8 Q+ t
}+ @+ O' H1 {) @& T6 W: z
void Print(Sqlist L) /* 输出顺序表 */8 t/ O% S6 j; Y5 f# {
{! d5 d5 e% @' }6 ]; G: ]8 _) E
int i=0;
! r9 t2 S4 U" w% _* l& p1 [% t- W while(i<=L.length-1)! v% g- x- @# n- [; f3 u/ D
printf("%3d",L.elem[i++]);( U) s" A" C+ L: t: N/ \
}! q( O' Y8 C) L N
void main()4 d& t2 H; X8 t
{
( b9 `2 F8 ]8 Y3 D. i W6 e3 ] Sqlist La,Lb;' f$ |+ D7 e# @, O
Lb=InitList();) W; ~5 X/ _: k" j I- f, h
La=InitList(); K# z3 Y) w3 G
CreateList(Lb);
& M& r' q" N2 P6 U% ?7 h printf("\\n输出Lb顺序表:");/ J3 o* g+ N$ u; Q' g- g
Print(Lb);
- a! r+ k) b0 n" B% S& p Union(La,Lb);
4 {5 i; f5 s, ?; C% R printf("\\n输出La顺序表:");+ w# F- M: K* i
Print(La);
; J: n: @) e' m; v+ n printf("\\n");
2 M! {) v% U) U9 B X7 a Y$ d} |