//已知两个单链表 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 |