数据结构实验报告.docx

数据结构实验报告
设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。
源代码:
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node * next;
};
void createstack(struct Node **headp)
{
int n;
struct Node * p;
*headp=NULL;
cin>>n;
while(n!=0)
{
p=(struct Node *)malloc(sizeof(struct Node));
p->data=n;
p->next=*headp;
*headp=p;
cin>>n;
}
}
int outputNode(struct Node *head)
{
int length=0;
struct Node *p;
p=head;
while(p)
{
cout<<p->data<<"\t";
p=p->next;
length++;
}
cout<<endl;
return length;
}
void sortNod(struct Node ** head,int n)
{
int i,j,temp;
struct Node *p1,*p2;
p1=*head;
for(i=0;i<n;i++,p1=p1->next)
{
p2=p1->next;
for(j=i+1;j<n;j++,p2=p2->next)
{
if(p1->data>p2->data)
{
temp=p2->data;
p2->data=p1->data;
p1->data=temp;
}
}
}
}
bool isinclude(int n,struct Node **head)
{
struct Node *p;
p=*head;
while(p!=NULL)
{
if(n==p->data)
{
return true;
}
p=p->next;
}
return false;
}
struct Node * insertNode(int x,struct Node **headp)
{
struct Node *other,*last,*current;
other=(struct Node *)malloc(sizeof(struct Node));
other->data=x;
current=*headp;
while(x>current->data&&current->next!=NULL)
{
last=current;
current=current->next;
}
if(x<=current->data)
{
if(current==*headp)
{
other->next=*headp;
*headp=other;
}
else{
other->next=current;
last->next=other;
}
}
else{
other->next=NULL;
current->next=other;
}
return other;
}
void merge(struct Node **heada,struct Node **headb)
{
struct Node *pa,*pb;
pa=*heada;pb=*headb;
while(pb!=NULL)
{
if(!isinclude(pb->data,heada))
{
insertNode(pb->data,heada);
}
pb=pb->next;
}
}
int main()
{
struct Node *heada,*headb,*pa,*pb;
int lengtha,lengthb;
cout<<"input Node ha numbers end of 0:"<<endl;
createstack(&heada);
cout<<"input Node hb numbers end