实验一线性表的创建与访问算法设计_实验一简单算法设计
实验一线性表的创建与访问算法设计由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验一简单算法设计”。
内蒙古工业大学信息工程学院
四、编译程序：
#include #include #define MAXSIZE 100
typedef char ElemType;typedef struct LNode
//定义单链表结点类型 {
ElemType data;
struct LNode *next;}LinkList;
LinkList *CreatlinkR(LinkList *L)
//用尾插法建立带头结点的单链表 {
LinkList *s, *r;char ch;r =(LinkList *)malloc(sizeof(LinkList));
//创建头结点
L = r;s = r;r->next = NULL;printf(“单链表元素值为单个字符, 连续输入，$为结束字符:”);while((ch = getchar())!= '$'){
r =(LinkList *)malloc(sizeof(LinkList));
//创建新结点
r->data = ch;
r->next = NULL;
s->next = r;
s = r;
} r->next=NULL;
//终端结点
return(L);}
void Sort(LinkList *h)
//单链表元素排序 { LinkList *p=h->next,*q,*t;
if(p!=NULL){
t=p->next;
p->next=NULL;
p=t;
while(p!=NULL)
{
t=p->next;
q=h;
第 页
内蒙古工业大学信息工程学院
while(q->next!=NULL&&q->next->data
data)
q=q->next;
//在有序表中找插入*p的前驱结点*q
p->next=q->next;
//将*p插到*q之后
q->next=p;
p=t;
} } }
void DispList(LinkList *L)
//输出单链表L {
LinkList *p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);
p=p->next;} }
LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)
{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;while(pa!=NULL&&pb!=NULL){
if(pa->data
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;return(Lc);}
LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的交集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(pb!=NULL&&pb->data==pa->data)
//若pa结点值在pb中
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;}
tc->next=NULL;return(Lc);
第页
内蒙古工业大学信息工程学院
}
LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的差集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(!(pb!=NULL&&pb->data==pa->data))
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;} tc->next=NULL;return(Lc);}
void main(){
LinkList *La,*Lb,*Lc;
int num=0,loop,j;loop=1;La=CreatlinkR(La);Lb=CreatlinkR(Lb);Sort(La);Sort(Lb);
printf(“有序集合A＝{ ”);
DispList(La);
printf(“}n”);
printf(“有序集合B＝{ ”);
DispList(Lb);printf(“}n”);while(loop){
printf(“请选择您要执行的操作：1.求并集
scanf(”%d“,&j);printf(”n%d“,j);
第页
//若pa结点值不在pb中 2.求交集
3.求差集n”);
内蒙古工业大学信息工程学院
if(j>=1&&j
switch(j)
{
case 1: Lc=Union(La,La,Lc);
printf(“集合A与集合B的并集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 2: Lc=InsterSect(La,Lb,Lc);
printf(“集合A与集合B的交集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 3: Lc=Subs(La,Lb,Lc);
printf(“集合A与集合B的差集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
} printf(“0.结束
1.继续n”);scanf(“%d”,&loop);printf(“n”);} }
五、运行结果：
1．输入两个无序集合，排序后输出：
第页
内蒙古工业大学信息工程学院
2．求集合的并集：
3．选1继续：
第页
内蒙古工业大学信息工程学院
4．求集合的交集：
5．求集合的差集：
第页
内蒙古工业大学信息工程学院
6．选0结束：
第页
