//已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列。请编写程序求集合
//A 和 B 的交集 C = A∩B，要求单链表C 按其元素递增排列，并利用原表（即表A
//和表B）的结点空间存放表C。

#include<stdio.h>
#include<stdlib.h>
#include<test2.h>
#include<string.h>
#define Max 100

int main()
{
	int i,len1,len2;
	char str[Max];
	LinkList *A,*B;
	A=CreateLinkList(); //为栈A创建一个链表指针
	B=CreateLinkList(); //为栈B创建一个链表指针
	InitLinkList(A);//初始化栈A
	InitLinkList(B);//初始化栈B

	printf("输入单链表A的数据元素:\n");
	gets(str);
	len1=strlen(str);
	for(i=0;i<len1;i++)
		InsertLinkList(A,str[i]);//将数据元素插入栈A

	printf("将单链表A的数据元素排序:\n");
	Order(A,len1);//为栈A的数据元素排序
	Display(A);//输出栈A的数据元素

	printf("输入单链表B中的数据元素:\n");
	gets(str);
	len2=strlen(str);
	for(i=0;i<len2;i++)
		InsertLinkList(B,str[i]);//将数据元素插入栈B

	printf("将单链表B的数据元素排序:\n");
	Order(B,len2);//为栈B排序
	Display(B);//输出栈B的数据元素

	printf("求集合单链表C:\n");
    ConnetLinkList(A,B,len1,len2);//联接栈A和栈B
	Display(A);//输出联接后的栈的数据元素

	return 0;
}






///////////////////////////////////////////
/*        test2.cpp                      */
/*    filename:test2.cpp                 */
/*    description:test2的实现文件        */
/*    designer:zhu jian                  */
/*    data:12-10-26                      */
////////////////////////////////////////////


#include"stdio.h"
#include"stdlib.h"
#include"test2.h"
#include"string.h"


LinkList *CreateLinkList(void)//创建一个结点
{
	LinkList *L;
	L=(LinkList *)malloc(sizeof(LinkList));
	if(!L)
		return NULL;

	L->next=NULL;
	return L;
}

void InitLinkList(LinkList *L)//初始化链表
{
	LinkList *p;
	p=L;
	if(!L)
		return ;

	p->data=0;
}

unsigned char InsertLinkList(LinkList *L,elemtype e)//插入结点元素
{
	LinkList *p,*q;
	p=L;
	if(!L)
		return ERROR;

	while(p->next!=NULL)
		p=p->next;
	q=(LinkList *)malloc(sizeof(LinkList));
	q->data=e;
	p->next=q;
	q->next=NULL;
	return OK;
}

unsigned char Order(LinkList *L,int len)//排序
{
	int i=0;
	elemtype k;
	LinkList *p,*q;
	p=L;
	if(!L)
		return ERROR;

    q=p->next;
	while(i<len)
	{
		p=L;
		q=p->next;
		while(p->next != NULL)
			if(p->data > q->data)
			{
			    k=p->data;
			    p->data=q->data;
			    q->data=k;
			    p=p->next;
			    q=q->next;
			}
			else
			{
				p=p->next;
				q=q->next;
			}
		i++;
	}

	return OK;
}

unsigned char ConnetLinkList(LinkList *L,LinkList *S,int len1,int len2)//联接单链表A和单链表B
{
	int len;
	LinkList *p,*q;
	p=L;
	q=S;
	if(!L || !S)
		return ERROR;

	len=len1+len2;
	while(p->next != NULL)
		p=p->next;
	p->next=q->next;
	Order(L,len);
	return OK;
}

unsigned char Display(LinkList *L)//输出单链表的数据元素
{
	LinkList *p;
	p=L->next;
	if(!L)
		return ERROR;

	while(p->next != NULL)
	{
		printf("%c",p->data);
		p=p->next;
	}
	printf("%c\n",p->data);
    return OK;
}


///////////////////////////////////////////
/*        test2.h                        */
/*    filename:test2.h                   */
/*    description:test2的头文件          */
/*    designer:zhu jian                  */
/*    data:12-10-26                      */
////////////////////////////////////////////


#ifndef _DATA_STRUCTURE_TEST2_H_
#define _DATA_STRUCTURE_TEST2_H_


#ifndef OK
#define OK 1
#endif

#ifndef ERROR
#define ERROR -1
#endif

#ifndef NULL
#define NULL 0
#endif 


typedef char elemtype; //定义用elemtype取代char


typedef struct node{
	elemtype data;
	struct node *next;
}LinkList;


LinkList *CreateLinkList(void);//创建一个结点

void InitLinkList(LinkList *L);//初始化链表

unsigned char InsertLinkList(LinkList *L,elemtype e);//插入结点元素

unsigned char Order(LinkList *L,int len);//排序

unsigned char ConnetLinkList(LinkList *L,LinkList *S,int len1,int len2);//联接单链表A和单链表B

unsigned char Display(LinkList *L);//输出单链表的数据元素


#endif