有序单链表的交集
- 说明
- 2.26 假设两个元素依值递增有序排列的单链表A和B
说明
- 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
- 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
- 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。
2.26 假设两个元素依值递增有序排列的单链表A和B
分别表示两个集合，
且同一表中的元素值各不相同，
现要求另辟空间构成一个单链表C，
其元素为A和B中元素的交集，
且表C中的元素也依值递增有序排列。
试对单链表编写求C的算法。
解：
争取作最少比较就可以从两个递增单链表中提取仍然有序的交集：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;#define PASS 2
#define MAX_TEST_LENGTH 8
#define MAX_TEST_ELEM 20
typedef int ElemType;typedef struct SLNode{ // 结点类型ElemType data;struct SLNode *next;
} LNode, *Link;typedef struct{ // 链表类型Link head,tail; // 分别指向线性链表中的头结点和最后一个结点int len; // 指示线性链表中数据元素的个数
} LinkList;Status MakeNode(Link *pp,ElemType e){// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR*pp=(Link)malloc(sizeof(LNode));if(!*pp) return ERROR;(*pp)->data=e;(*pp)->next=NULL;return OK;
}void FreeNode(Link p){// 释放p所指结点if(NULL!=p){printf("free [%lld]=%d\n",(long long)p,p->data);free(p);}
}Status InitList(LinkList *pL){// 构造一个空的线性链表LLink p;if(ERROR==MakeNode(&p,0)) return ERROR;(*pL).head=p;(*pL).tail=NULL;(*pL).len=0;return OK;
}Status ClearList(LinkList *pL){// 将线性表L重置为空表，并释放原链表的结点空间Link p;if(NULL==pL) return ERROR;if(NULL!=(*pL).head) p=((*pL).head)->next;while(p){((*pL).head)->next=p->next;FreeNode(p);p=((*pL).head)->next;}(*pL).tail=NULL;(*pL).len=0;return OK;
}Status DestroyList(LinkList *pL){// 销毁线性链表Lif(ERROR==ClearList(pL)) return ERROR;if(NULL!=(*pL).head) FreeNode((*pL).head);(*pL).head=NULL;return OK;
}void print_list(LinkList L){// 显示链表的内容int c=0;Link p=(L.head)->next;while(p&&c<L.len){printf("->[%d].%d",++c,p->data);p=p->next;}if(L.tail)printf("\n%d elements and tail->[%d].%d\n",L.len,L.len,L.tail->data);elseprintf("\n%d elements and tail->NULL\n",L.len);
}Status InsOrderAsc(LinkList *pL,Link s){// 已知线性链表的尾结点，将s所指结点插入后保持链表有序// 如果插入到表尾，尾指针发生变化// 线性链表的元素个数加1Link p;if(NULL==pL||NULL==s) return ERROR;p=pL->head;while(p->next && (p->next->data) < (s->data)) p=p->next;s->next=p->next;p->next=s;if(NULL==s->next) pL->tail=s;pL->len++;return OK;
}//InsOrderAscStatus intersect_linked_sets(LinkList A,LinkList B,LinkList *pC){//元素递增排列的单链表A和B中元素交集合并存入单链表C中，仍保持有序Link p,q,r,t;if(NULL==pC) return INFEASIBLE;p=A.head->next;q=B.head->next;r=pC->head;while(p&&q){if(p->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else{t=NULL;if(ERROR==MakeNode(&t,p->data)) return ERROR;if(ERROR==InsOrderAsc(pC,t)) return ERROR;p=p->next;q=q->next;}}return OK;
}void sorted_list_to_set(LinkList *pL){//在顺序单链表中去除重复元素Link p,q;if(NULL==pL) return;p=pL->head->next;while(p){q=p->next;while(q&&q->data==p->data){p->next=q->next;FreeNode(q);q=p->next;pL->len--;}pL->tail=p;p=p->next;}
}Status rand_sorted_sets_intersect(LinkList *pA,LinkList *pB,LinkList *pC){Status result;int c,dupli_rand_count,dupli_rand_num;time_t t;Link p;srand((unsigned)time(&t)); //初始化随机数发生器c = rand()%MAX_TEST_LENGTH;while(c--){dupli_rand_count=rand()%10;dupli_rand_num=rand()%MAX_TEST_ELEM;while(dupli_rand_count--){p=NULL;if(ERROR==MakeNode(&p,dupli_rand_num)) return ERROR;if(ERROR==InsOrderAsc(pA,p)) return ERROR;}}printf("\nA:\n");print_list(*pA);sorted_list_to_set(pA);printf("\nLinked set A:\n");print_list(*pA);c = rand()%MAX_TEST_LENGTH;while(c--){dupli_rand_count=rand()%10;dupli_rand_num=rand()%MAX_TEST_ELEM;while(dupli_rand_count--){p=NULL;if(ERROR==MakeNode(&p,dupli_rand_num)) return ERROR;if(ERROR==InsOrderAsc(pB,p)) return ERROR;}}printf("\nB:\n");print_list(*pB);sorted_list_to_set(pB);printf("\nLinked set B:\n");print_list(*pB);result=intersect_linked_sets(*pA,*pB,pC);if(result==OK){printf("\nIntersect:\n");print_list(*pC);}else{printf("\nError...\n");}return result;
}int main(){LinkList La,Lb,Lc;if(ERROR==InitList(&La)) return ERROR;if(ERROR==InitList(&Lb)) return ERROR;if(ERROR==InitList(&Lc)) return ERROR;if(OK==rand_sorted_sets_intersect(&La,&Lb,&Lc)) printf("\nIntersect success\n");if(OK==DestroyList(&La)) printf("Free La success\n");if(OK==DestroyList(&Lb)) printf("Free Lb success\n");if(OK==DestroyList(&Lc)) printf("Free Lc success\n");return 0;
}
