10. C Pro 线性表的应用：求两个集合的并集

1. File : list.h

#ifndef _LIST_H_

#define _LIST_H_
#include
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 10

typedef int ElemType;
typedef struct {
　　ElemType *elem; 　// 指针：表示数组
　　int length; 　　　　 // list length == 已经使用的空间
　　int size; 　　　　    // 全链表的可用空间
}　List;

int InitList(List &L);
void ListInsert(List &L, int i, ElemType e); 　　// 在第i个位置插入元素e
void ListDelete(List &L, int i, ElemType &e); 　// 删除第i个元素，并返回其值
void GetElem(List &L, int i, ElemType &e); 　  // 获取第i个元素值
void DestroyList(List &L); 　　　　　　　        // 销毁
void ClearList(List &L); 　　　　　　　　　　 // 清空
int LocateElem(List &L, ElemType e, int compare); //返回第一个满足某种关系的元素位置
int ListTempty(List &L); 　　　　　　　　　　 // 线性表是否为空

#endif

2. File : list.cpp

#include "list.h"

int InitList(List &L){
　　L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
　　if (L.elem == NULL) exit(0);
　　L.length = 0;
　　L.size = LIST_INIT_SIZE;
　　return 1;
}

void ListInsert(List &L, int i, ElemType e) {　　 // 在第i个位置插入元素e
　　ElemType *p = NULL, *q = NULL, *temp = NULL;
　　if (i<1 || i>L.length + 1) exit(0);
　　if (L.length >= L.size) {
　　　　temp = (ElemType*)realloc(L.elem, (L.size + LISTINCREMENT) * sizeof(ElemType));
　　　　if (temp == NULL) exit(0);
　　　　L.elem = temp;
　　　　L.size += LISTINCREMENT;
　　}
　　p = &L.elem[i - 1];
　　q = &L.elem[L.length - 1];
　　while (q >= p) {
　　　　*(q + 1) = *q;
　　　　q--;
　　}
　　*p = e;
　　++L.length;
}

void ListDelete(List &L, int i, ElemType &e) { 　　// 删除第i个元素，并返回其值
　　ElemType *p = NULL, *q = NULL;
　　if (i<1 || i>L.length + 1) exit(0);
　　p = &L.elem[i - 1];
　　e = *p;
　　q = &L.elem[L.length - 1];
　　while (p < q) {
　　　　*p = *(++p);
　　}
　　--L.length;
}

void GetElem(List &L, int i, ElemType &e) { 　　 // 获取第i个元素值
　　if (i<1 || i>L.length + 1) exit(0);
　　e = L.elem[i - 1];
}

void ClearList(List &L) {
　　memset(L.elem, 0, sizeof(List)*L.length);
　　L.length = 0;
}

int ListTempty(List &L) {
　　if (L.length == 0) return 1;
　　return 0;
}

void DestroyList(List &L) {
　　free(L.elem);
　　L.length = 0;
　　L.size = 0;
}

int LocateElem(List &L, ElemType e, int compare) {
　　for (int i = 0; i < L.length; i++) {
　　　　if (compare == 0 && e == L.elem[i]) return i + 1;
　　　　if (compare < 0 && L.elem[i] <= e) return i + 1;
　　　　if (compare > 0 && L.elem[i] >= e) return i + 1;
　　}
　　return 0;
}

3. File : combine.cpp

#include
#include
#include "list.h"
int main() {
　　int i = 0;
　　ElemType m = 0;
　　List La, Lb;
　　InitList(La);
　　InitList(Lb);
　　for (i = 1; i < 6; i++) {
　　　　ListInsert(La, i, i);
　　　　ListInsert(Lb, i, 2 * i);
　　}
　　for (i = 0; i < Lb.length; i++) {
　　　　GetElem(Lb, i + 1, m);
　　　　if (LocateElem(La, m, 0) == 0)
　　　　　　ListInsert(La, La.length + 1, m);
　　}

　　for (i = 0; i < La.length; i++)
　　　　printf("%d\t", La.elem[i]);

　　getchar(); return 0;
}