2-21实验报告.doc

东莞理工学院计算机学院
2015-2016第1学期算法与数据结构实验报告
姓名：陈映琼
学号：201441404142

题目：设带头结点的单链表L1和L2中分别存放着两个数据元素集合，编写算法判断集合L1是否是L2的子集，即判断集合L1中的数据元素是否都是集合L2中的数据元素。
问题描述：有两个带头结点的单链表L1和L2中分别存放着数据元素集合，判断集合L1是否是集合L2的子集。
模块划分：第一个模块，定义单链表结点的结构体，第二个模块，设计一个函数，创建头结点，第三个模块，编写一个将元素e插入到链表L的第i个位置的函数，第四个模块，编写一个输出带头结点单链表的数据元素的函数，第五个模块，首先编写一个输出带头结点单链表的长度的函数，再编写一个判断集合L1中的数据元素是否都是集合L2中的数据元素，这个函数需调用输出长度的函数，第六个模块，编写main函数，测试代码。
源程序：
#include<stdio.h>
#include <stdlib.h>

typedef int Status;
typedef int ElemType;
#define FALSE 0
#define TRUE 1

typedef struct Node
{
ElemType data;// 数据域
struct Node* next;
}Node,*LinkList;

LinkList InitList()//创建头结点
{
LinkList L;
L = (LinkList)malloc(sizeof(Node));
if(L==NULL)
{
printf("申请头结点失败!\n");
return NULL;
}
L->next = NULL;
return L;
}

Status ListInsert(LinkList *L,int i,ElemType e)//将元素e插入到链表L的第i个位置
{
int j = 1;
LinkList p,s;
p = *L;//p直接等于链表L，才有头结点
while (p && j<i)
{
p = p->next;
++j;
}
if(!p || j > i)
return FALSE;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;//这里p->next就是指向位置i
p->next = s;
return TRUE;
}

void PrintList(LinkList L)
{
LinkList p;
p = L->next;
while (p != NULL)
{
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}

Status Length(LinkList head)
{
LinkList p = head->next;
Status i = 0;
while(p != NULL)
{
i++;
p = p->next;
}
return i;
}

void Judge(LinkList head1,LinkList head2)
{
LinkList p1 = head1->next,p2 = head2->next;
if(Length(head1) > Length(head2))
{
printf("集合L1不是集合L2的子集。\n");
return;
}
while(p1 != NULL)
{
p2 = head2->next;
while(1)
{
if((p2 != NULL)&&(p1->data != p2->data))
p2 = p2->next;
if((p2 != NULL)&&(p1->data == p2->data))
break;
if(p2 == NULL)
{
printf("集合L1不是集合L2的子集。\n");
return;
}
}
p1 = p1->next;
}
printf("集合L1是集合L2的子集。\n");
}

int main()
{
LinkList head1,head2;
int len,i,num;
head1 = InitList();
head2 = InitList();

printf("请输入集合L1元素的个数。\n");
scanf("%d",&len);
printf("请输入元素：\n");
for(i = 1;i <= len;i++)
{

scanf(" %d",&num);
ListInsert(&head1,i,num);
}
PrintList(head1);

printf("请输入集合L2元素的个数。\n");
scanf("%d",&len);
printf("请输入元素：\n");
for(i = 1;i <= len;i++)
{

scanf(" %d",&num);
ListInsert(&head2,i,num);
}
PrintList(head2);

Judge(head1,head2);
return 0;
}
测试用例及结果：