/*已知一个非纯集合 B,试构造一个纯集合 A,使 A中只包含 B 中所有值各2 @4 C+ s8 b, k3 c
不相同的数据元素。*/
/ X; h J" W0 ^% h/*算法:逐个比较。将B表的第一个元素存入A表,然后用B表的每一个元素逐个
9 b( b, n6 }: k: r: { 和A表中的元素进行比较,相等的元素不存入A表,不相等的元素存入A表*/
5 l. }* k$ C, v O9 v$ K7 q#include <stdio.h>
7 n% H4 X6 N; z7 |9 |6 U#include <stdlib.h>
! ^5 e9 W6 M* G9 P& I% W: Ftypedef int ElemType; /* 定义元素类型 */5 b7 W3 ^) e/ n0 r2 b5 b, H
#define Max 100! \* }; u( b; [! u; f
#define Increment 10
5 L: `1 ^8 B* P+ E8 ?typedef struct6 k Z4 j. Y/ k6 P s6 f( Y
{
( z( ]/ B8 |4 y$ t: H: U3 Z ElemType *elem; /* 定义存储空间的基地址 */
: N. R/ |/ I2 A& _& p int length; /* 定义表的长度 */+ T2 i8 `6 D; {2 H6 J
int listsize; /* 定义空间容量 */4 }8 b* b) H7 L/ _6 c
}Sqlist; /* 定义顺序存储结构 */
6 Z- {- S! N! T2 Y; w) N' y. m P+ TSqlist InitList() /* 初始化顺序表 */4 R: N7 i* c) [2 u% a9 b
{( R5 |" D# l Q
Sqlist L;
( M i; V% Q7 F, n2 p# J L.elem=(ElemType *)malloc(Max*sizeof(ElemType)); - R/ Y9 v, U( k7 U* }, x2 ^8 @/ x
/* 使用malloc()申请空间,空间大小是Max*sizeof(ElemType)个字节,共Max个单元 */4 l9 D1 Z, L/ U( X
if(!L.elem)
! b; k. t; A0 `( D. B exit(!0); /* 判断申请空间是否成功,如失败,则返回;否则开辟空间成功 */
% b0 n7 t1 Z) x/ z' i/ c /* exit(int status)功能是结束程序,status用来保存调用进程的出口状态, */
( c# T* V6 A! {4 f6 U' u6 e0 m /* 一般的,0表示正常退出,非0表示发生错误。 */* H( ?( r' I1 g% {' q' H7 C7 N
L.length=0;3 ?6 B: |4 H) _% F% F
L.listsize=Max;
! V5 }& S+ g, x+ [( y return L;% t9 E& ]/ R, z
} x/ }: i+ y. {' c" f! D
void CreateList(Sqlist &L) /* 创建顺序表 */
( W7 c0 I" i* Q{6 L8 o* \( P5 `( B' `5 [) `$ n# ~4 v
int i,number; /* 元素的个数是number个 */
2 t- G/ ~* ^' X2 x printf("\\n请输入顺序表的元素的个数:");
$ O# F- v p) {( b2 w3 g, _+ H scanf("%d",&number);
# D' Z- G. J3 w$ n, o0 k printf("\\n创建顺序表:");( a1 _" d: B- c2 j& T
for(i=1;i<=number;i++)
# M* k% w7 s0 h$ a- E+ S {
4 e$ {6 |5 q* F9 _& { printf("\\n请输入第%d个元素的值:",i);3 ^; }) _6 v4 H. r$ b4 a* q! e
scanf("%d",&L.elem[i-1]);
8 m, t! V9 G8 N( s; O- W }- R6 k. P) \: m4 Y2 P! |( I6 ]# X
L.length=number;, E: Y3 A7 W8 k7 Y
}
; S4 R5 u: e" v% ?void GetElem(Sqlist L,int i,ElemType &e) 2 S9 J, \# j) M6 I0 I; ?! _
/* 用e返回L中第i个元素的值 */
. I. E; C; Q T( w{
( V* m% M7 m g& ] if(!L.elem)
. Y# o& E. X2 A" O" c9 q5 |8 j exit(!0); /* 判断L是否存在,若不存在,操作失败;否则,可以进行操作 */
$ i5 K& ` K: {+ Q* v5 X if(i>=1&&i<=L.length)
3 W `# e$ N9 s1 N* i5 ], S+ X% n e=L.elem[i-1]; /* 取元素 */6 z8 ]) H& V, ~8 ?8 D" i
}+ N+ M3 T0 L2 t# j' ]
int Equal(Sqlist L,ElemType e) 0 G6 _9 ]/ X) M
/* 在L表中检测与e值相等的元素,若有,返回1;否则返回0 */$ z5 g/ F: K( T' v- f- W2 x
{
4 f- G& k( c6 U3 ? int i=0;
- U( j: d( N) X, G# g+ Y while(i<L.length) P y; a% v# E4 k% }1 q# G
{7 C6 e5 V6 G7 {. ^( K
if(e!=L.elem)i++;* a- r/ b* M/ K: ` ~& {3 g
else
+ p. s h. H9 B! i return 1;' R% s* E2 ^: u% x4 F/ j
}6 @% L& Q% ^, Z( ~) B) j/ R1 l
return 0; * ~3 ^) n, u' ]: C' U: Y2 K' _& e
}
3 g. |# H6 G6 @$ Q% G2 xvoid Insert(Sqlist &L,int i,ElemType e)
1 D# Y% z) B" V& W7 `; O/* 在表L中的第i个位置插入元素e */
; P* I7 m/ y* N2 ?% p3 t{; a$ e" P" B; Y3 h
L.elem[i-1]=e; & y# u7 I J( i3 P" Y% @( _
L.length++;6 W( N$ w r5 j+ {9 f
}
' D [$ A9 t/ i& P3 E2 r# F4 \3 x6 qvoid Union(Sqlist &La,Sqlist Lb)" C7 q2 N3 { s' I" n
/* 在非纯集合Lb转化为纯集合La */! C$ |! s- r# o3 x. ^* D
{8 Q" l0 s' u; h, I; L
int i,k=1;
* e, m5 C4 S, T ElemType e;
9 n1 t0 s& T3 i& I, D La.elem[0]=Lb.elem[0];
3 I3 Z/ J' m1 B5 o7 O* D La.length=1;$ H A$ d* U% n4 r1 {
for(i=1;i<=Lb.length;i++)" f2 n% b/ _3 J3 U5 P
{ , l1 f9 j ~ z! F& l) x
GetElem(Lb,i,e);
$ g7 t% o& \$ d; E7 [& N0 y) V N if(!Equal(La,e))4 u" ]; b3 @7 m/ z5 _) E) x% x
Insert(La,++k,e);/ m$ r# ^* W& J+ J1 a) e6 q
}
" G. b4 E7 d7 b; ?3 R1 X& P% Z}! V$ q! H; }1 n7 A% `6 W( _$ H
void Print(Sqlist L) /* 输出顺序表 */
. d& S9 [! Y1 {9 c* S* Q{( F' F# {+ R5 c- ^# Z% x) N( M' p
int i=0;
& @: R1 [, K8 I u2 G' c while(i<=L.length-1): A/ E! [! \6 H) _; N/ H/ L
printf("%3d",L.elem[i++]);
/ q( r/ B2 \" M( ]- u}
) E/ z$ |7 ^2 ^! Qvoid main()
. b% P" q' q8 `- T& |6 C{
2 N3 T' [4 `" p5 V/ R4 i Sqlist La,Lb;: @- e" ^+ w2 j; b; O" \8 v
Lb=InitList();8 p. ?. t: V* @" {
La=InitList();
" n3 S G. M P2 b" _1 I' T* _1 _ CreateList(Lb);4 l$ y0 c1 C j+ O8 c. k
printf("\\n输出Lb顺序表:");
; T/ a, j% z+ T Print(Lb);6 D' f2 F2 q S/ t& ^' G% R
Union(La,Lb);/ j5 F6 e( v( b# U
printf("\\n输出La顺序表:");
+ O5 ~' C& Q# z/ t- s Print(La);
2 v h$ d8 R! ] printf("\\n");
1 H* L5 c* o1 B! F) {6 w} |