#include <stdio.h> #include <malloc.h>
typedef char ElemType; typedef struct LNode // 定义单链表结点类型 { ElemType data; // 数据域 struct LNode *next; // 指向后继结点 }LinkList;
/*-------------------------输出单链表L----------------------------*/ void DispList(LinkList *L) { LinkList *p = L->next; while(p != NULL) { printf("%c ", p->data); p = p->next; } printf("\n"); }
/*-------------------------尾部插入法建表----------------------------*/ void CreateListR(LinkList *&L, ElemType a[], int n) // 指针的引用 { int i; LinkList *s, *r; L = (LinkList *)malloc(sizeof(LinkList)); // 创建头结点 L->next = NULL; r = L; // r始终指向终端结点,开始时指向头结点 for(i = 0; i < n; i++) { s = (LinkList *)malloc(sizeof(LinkList)); // 创建新结点 s->data = a[i]; r->next = s; // 将s插入到r之后 r = s; } r->next = NULL; // 终端结点next域设置为NULL }
/*-------------------------单链表元素排序----------------------------*/ void Sort(LinkList *&head) { LinkList *p = head->next, *q, *r; if(p != NULL) // 若原单链表中有一个或以上的数据结点 { r = p->next; // r指向p结点的后继结点 p->next = NULL; // 构造只含一个数据结点的有序表 p = r; while(p != NULL) { r = p->next; // r指向p结点的后继结点 q = head; while((q->next != NULL) && (q->next->data < p->data)) q = q->next; // 将p插入到q之后 p->next = q->next; q->next = p; p = r; } } }
/*-------------------------求两个有序集合的并----------------------------*/ void Union(LinkList *ha, LinkList *hb, LinkList *&hc) { LinkList *pa = ha->next; // pa指向集合ha中的第一个数据结点 LinkList *pb = hb->next; // pb指向集合hb中的第一个数据结点 LinkList *s; LinkList *tc; hc = (LinkList *)malloc(sizeof(LinkList)); // 创建头结点 tc = hc; while((pa != NULL) && (pb != NULL)) { if(pa->data < pb->data) { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pa->data; tc->next = s; tc = s; pa = pa->next; } else if(pa->data > pb->data) { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pb->data; tc->next = s; tc = s; pb = pb->next; } else { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pa->data; tc->next = s; tc = s; pa = pa->next; // 重复的元素只复制一个 pb = pb->next; } } if(pb != NULL) pa = pb; while(pa != NULL) { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pa->data; tc->next = s; tc = s; pa = pa->next; } tc->next = NULL; }
/*-------------------------求两个有序集合的交----------------------------*/ void InterSect(LinkList *ha, LinkList *hb, LinkList *&hc) { LinkList *pa = ha->next; // pa指向集合ha中的第一个数据结点 LinkList *pb, *s, *tc; hc = (LinkList *)malloc(sizeof(LinkList)); // 创建头结点 tc = hc; while(pa != NULL) { pb = hb->next; while((pb != NULL) && (pb->data < pa->data)) pb = pb->next; if((pb != NULL) && (pb->data == pa->data)) // 若pa结点值在B中 { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pa->data; tc->next = s; tc = s; } pa = pa->next; } tc->next = NULL; }
/*-------------------------求两个有序集合的差----------------------------*/ void Subs(LinkList *ha, LinkList *hb, LinkList *&hc) { LinkList *pa = ha->next; // pa指向集合ha中的第一个数据结点 LinkList *pb, *s, *tc; hc = (LinkList *)malloc(sizeof(LinkList)); // 创建头结点 tc = hc; while(pa != NULL) { pb = hb->next; while((pb != NULL) && (pb->data < pa->data)) pb = pb->next; if(!(pb != NULL && pb->data == pa->data)) // 若pa结点值不在B中 { s = (LinkList *)malloc(sizeof(LinkList)); // 复制结点 s->data = pa->data; tc->next = s; tc = s; } pa = pa->next; } tc->next = NULL; }
int main(void) { LinkList *ha, *hb, *hc; ElemType a[] = {'c', 'a', 'e', 'h'}; ElemType b[] = {'f', 'h', 'b', 'g', 'd', 'a'};
CreateListR(ha, a, 4); CreateListR(hb, b, 6); printf("原集合A:"); DispList(ha); printf("原集合B:"); DispList(hb); Sort(ha); Sort(hb); printf("有序集合A:"); DispList(ha); printf("有序集合B:"); DispList(hb); Union(ha, hb, hc); printf("集合的并C:"); DispList(hc); InterSect(ha, hb, hc); printf("集合的交C:"); DispList(hc); Subs(ha, hb, hc); printf("集合的差C:"); DispList(hc);
return 0; }
测试结果:
原集合A:c a e h 原集合B:f h b g d a 有序集合A:a c e h 有序集合B:a b d f g h 集合的并C:a b c d e f g h 集合的交C:a h 集合的差C:c e
