当前位置：文档库 › 数据结构实验一答案

数据结构实验一答案

[问题描述]

线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算或并运算。

[实验目的]

（1）掌握线性表的两种存储结构，即顺序表和链表。

（2）掌握在顺序表和单链表上基本操作的实现。

（3）在掌握顺序表和单链表的基本操作上进行综合题的实现。

[实验内容及要求]

（1）集合的元素限定为十进制数。

（2）任意输入两个集合的元素。

（3）显示两个集合的内容及其运算结果。

（4）要求用链表实现。

[测试数据]

（1） set1={3, 5, 8, 11}，set2={2, 6, 8, 9, 11, 15, 20}

set1∪set2＝？

set1∩set2＝？

（2） set1={9, 3, 14, 6}，set2={1, 30, 3, 7, 14, 25, 6, 3, 19, 9}

set1∪set2＝？

set1∩set2=？

#include <iostream>
using namespace std;
class List;
class ListNode //节点类的定义
{
friend class List; //声明为友员
private :
double data;
ListNode *link;
public :
ListNode (): link(NULL) {}
ListNode (const double &item):data(item),link(NULL){}

};
class List //单链表的定义
{ private :
ListNode *first,*current;
public :
List(){ first=current=new ListNode;}
~List(){ MakeEmpty(); delete first;}
void MakeEmpty();
ListNode *Firster(){ current=first; return first;}
int Find(double &value);
int append(double &value);
int Remove() ; //删除当前元素
double First(); //取当前指针的第一元素
double Next(); //返回当前元素的下一个元素
void print();
ListNode *getNode( double &item,ListNode *next);
void Union(List &LA,List &LB); //取并集
void intersection(List &LA,List &LB); //取交集

};
ListNode *List::getNode( double &item,ListNode *next)
{ //建立一个新节点
ListNode *newnode =new ListNode(item);
newnode->link =next;
return newnode;
}
void List:: MakeEmpty()
{ //将链表置为空表
ListNode *q;
while(first->link!=NULL)
{ q=first->link; first->link=q->link;
delete q;
}
current =first;
}
int List::Find(double &value)
{ //搜索value
int i=0;
current =first;
//cout<<"#####"<<current->data<<endl;
while(current !=NULL)
{
if(current->data==value){
//return 1;
i=1;
break;
}
else current=current->link;
}
return i;
}
int List::append(double &value)
{ //实现追加
if(current==NULL)
{
return 0;
}
ListNode *newnode =getNode( value ,current->link );
current =current->link=newnode;
return 1;
}
int List::Remove()
{ //删除当前元素
if(current==first) return 0;
ListNode *p=first;
while( p->link!=current) p=p->link;
p->link=current->link;
//double val=current->data;
delete current; current = p;
if(current ==NULL) current =first;
return 1;

}

double List:: First()
{ //返回当前指针的第一元素
if(first->link!=NULL) { current = first->link; return current->data; }
else {current =NULL; return NULL; }
}
double List:: Next()
{ //返回当前元素的下一个元素
if(current!=NULL&&current->link!=NULL)
{ current =current->link; return current ->data;
}
else {current = NULL; return NULL; }
}

void List::print()
{ //实现打印
cout<<"The List:"<<endl;
Firster(); //将表当前指针置为表头
while(current->link!=NULL)
{ if(current==first) cout<<"{"<<" ";
current=current->link;
if(current->link==NULL) break;
cout<<current->data<<" , ";
}
if(current->link==NULL)
cout<<current->data<<" }"<<endl;
}
void List::Union(List &LA,List &LB)
{ //取并集
List list;
ListNode *q;
double x=LA.First();
while(x!=NULL)
{ list.append(x);
x=LA.Next();
}
q=list.current;
LA.Firster();
x=LB.First();
while(x!=NULL)
{
int k=LA.Find(x);
if(k==0) list.append(x);
x=LB.Next();
}
cout<<"取并集后的集合："<<endl;
list.print();
}
void List::intersection(List &LA,List &LB)
{ //取交集
double x=LA.First();
while(x!=NULL)
{ int k=LB.Find(x);
if(k==0) LA.Remove();
x=LA.Next();
}
cout<<"取交集后的集合："<<endl;
LA.print();
}
void main()
{ double a;
List list1,list2;
while(1)
{ cout<<"Please input a number (input 999 to quit) :"<<endl;
cin>>a;
if(a==999) break;
list1.append(a);
}

cout<<"Create another list."<<endl;
while(1)
{ cout<<"Please input a number (input 999 to quit) :"<<endl;
cin>>a;
if(a==999) break;
list2.append(a);
}
list1.print();
list2.print();
list1.Union(list1,list2);
list1.intersection(list1,list2);
}

#include <iostream>
using namespace std;
class List;
class ListNode //节点类的定义
{
friend class List; //声明为友员
private :
double data;
ListNode *link;
public :
ListNode (): link(NULL) {}
ListNode (const double &item):data(item),link(NULL){}

};
class List //单链表的定义
{ private :
ListNode *first,*current;
public :
List()
{
first=current=new ListNode;
}
~List()
{
MakeEmpty();
delete first;
}
void MakeEmpty();
ListNode *Firster()
{
current=first;
return first;
}
int Find(double &value);
int append(double &value);
int Remove() ; //删除当前元素
double First(); //取当前指针的第一元素
double Next(); //返回当前元素的下一个元素
void print();
ListNode *getNode( double &item,ListNode *next);
void Union(List &LA,List &LB); //取并集
void i

ntersection(List &LA,List &LB); //取交集

};
ListNode *List::getNode( double &item,ListNode
*next)
{ //建立一个新节点
ListNode *newnode =new ListNode(item);
newnode->link =next;
return newnode;
}
void List:: MakeEmpty()
{ //将链表置为空表
ListNode *q;
while(first->link!=NULL)
{
q=first->link;
first->link=q->link;
delete q;
}
current =first;
}
int List::Find(double &value)
{ //搜索value
int i=0;
current =first;

while(current !=NULL)
{
if(current->data==value){

i=1;
break;
}
else current=current->link;
}
return i;
}
int List::append(double &value)
{ //实现追加
if(current==NULL)
{
return 0;
}
ListNode *newnode =getNode( value ,current->link );
current =current->link=newnode;
return 1;
}
int List::Remove()
{ //删除当前元素
if(current==first) return 0;
ListNode *p=first;
while( p->link!=current) p=p->link;
p->link=current->link;

delete current; current = p;
if(current ==NULL) current =first;
return 1;

}
double List:: First()
{ //返回当前指针的第一元素
if(first->link!=NULL) { current = first->link; return current->data; }
else {current =NULL; return NULL; }
}
double List:: Next()
{ //返回当前元素的下一个元素
if(current!=NULL&&current->link!=NULL)
{
current =current->link;
return current ->data;
}
else {current = NULL; return NULL; }
}

void List::print()
{ //实现打印
cout<<"The List:"<<endl;
Firster(); //将表当前指针置为表头
while(current->link!=NULL)
{
if(current==first)
cout<<"{"<<" ";
current=current->link;
if(current->link==NULL)
break;
cout<<current->data<<" , ";
}
if(current->link==NULL)
cout<<current->data<<" }"<<endl;
}
void List::Union(List &LA,List &LB)
{ //取并集
List list;
ListNode *q;
double x=LA.First();
while(x!=NULL)
{ list.append(x);
x=LA.Next();
}
q=list.current;
LA.Firster();
x=LB.First();
while(x!=NULL)
{
int k=LA.Find(x);
if(k==0) list.append(x);
x=LB.Next();
}
cout<<"取并集后的集合："<<endl;
list.print();
}
void List::intersection(List &LA,List &LB)
{ //取交集
double x=LA.First();
while(x!=NULL)
{ int k=LB.Find(x);
if(k==0)
LA.Remove();
x=LA.Next();
}
cout<<"取交集后的集合："<<endl;
LA.print();
}
void main()
{ double a;
List list1,list2;
while(1)
{ cout<<"Please input a number (input 0 to quit) :"<<endl;
cin>>a;
if(a==0) break;
list1.append(a);
}

cout<<"Create another list."<<endl;
while(1)
{
cout<<"Please input a number

(input 0 to quit) :"<<endl;
cin>>a;
if(a==0)
break;
list2.append(a);
}
list1.print();
list2.print();
list1.Union(list1,list2);
list1.intersection(list1,list
2);
}