(数据结构)实验一 线性表的有关操作
实验内容:
1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。
2、遍历单向链表(显示)。
3、把单向链表中元素逆置(不允许申请新的结点空间)。
4、在单向链表中删除所有的偶数元素(值为偶数)结点。
5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。
6、利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
7、利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表。
8、编写一个主函数,调试上述算法。
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
using namespace std;
typedef struct node{
int data;
struct node *next;
}Lnode,*Linklist;
Linklist CreateFromHead(){
Linklist L;
Lnode *s;
int x,n,num;
cout<<"请输入创建随机链表总个数:";
cin>>n;num=n;
L=(Linklist)malloc(sizeof(Lnode));
L->next=NULL;
srand((unsigned)time(NULL));
while(num>0){
x=rand()%100+1;
//printf("请输入第%d个数据元素:",n-num+1);
//cin>>x;
s=(Linklist)malloc(sizeof(Lnode));
s->data=x;
s->next=L->next;
L->next=s;
num--;
}
return L;
}
Linklist CreateFromHead_(){
Linklist L;
Lnode *s;
int x,n,num;
cout<<"请输入创建链表总个数:";
cin>>n;num=n;
L=(Linklist)malloc(sizeof(Lnode));
L->next=NULL;
srand((unsigned)time(NULL));
while(num>0){
//x=rand()%100+1;
//printf("请输入第%d个数据元素:",n-num+1);
cin>>x;
s=(Linklist)malloc(sizeof(Lnode));
s->data=x;
s->next=L->next;
L->next=s;
num--;
}
return L;
}
Linklist Daozhi(Linklist head){
Linklist p=NULL,q=NULL,t=NULL;
p=head;t=head;p=p->next;
while(p->next!=NULL){
q=p;
p=p->next;
q->next=t;
t=q;
}
head->next->next=NULL;
head->next=p;
p->next=q;
return head;
}
void Show(Linklist Head){
Linklist p=NULL;
p=Head;
while(p->next!=NULL){
p=p->next;
cout<<p->data<<" ";
}
cout<<endl;
}
Linklist Shanchu(Linklist head){
Linklist p=NULL,q=NULL;
p=head;
while(p->next!=NULL){
q=p;
p=p->next;
if(p->data%2==0){
q->next=q->next->next;
free(p);
p=q;
}
}
return head;
}
Linklist Charu(Linklist head,int x){
Linklist p=NULL,q=NULL,s;
int flag=1;
p=head;
s=(Linklist)malloc(sizeof(Lnode));
s->data=x;
while(p->next!=NULL){
q=p;
p=p->next;
if(p->data>=x){
s->next=p;
q->next=s;
flag=0;break;
}
}
if(flag) {p->next=s;s->next=NULL;}
return head;
}
Linklist Sort(Linklist head)
{
Linklist temp1,temp2,q,p;
for(q=head;q->next!=NULL;q=q->next)
for(p=q->next;p->next!=NULL;p=p->next)
{
if(p->next->data<q->next->data)
if(q->next==p)
{
temp1=p->next;
p->next=p->next->next;
temp1->next=q->next;
q->next=temp1;
p=temp1;
}
else
{
temp1=p->next;
temp2=q->next;
p->next=p->next->next;
q->next=q->next->next;
temp1->next=q->next;
q->next=temp1;
temp2->next=p->next;
p->next=temp2;
}
}
return head;
}
Linklist Hecheng(Linklist head1,Linklist head2){
Linklist p;
p=head2;
while(p->next!=NULL)
{
p=p->next;
Charu(head1,p->data);
}
return head1;
}
Linklist Sort_(Linklist head)
{
Linklist temp1,temp2,q,p;
for(q=head;q->next!=NULL;q=q->next)
for(p=q->next;p->next!=NULL;p=p->next)
{
if(p->next->data>q->next->data)
if(q->next==p)
{
temp1=p->next;
p->next=p->next->next;
temp1->next=q->next;
q->next=temp1;
p=temp1;
}
else
{
temp1=p->next;
temp2=q->next;
p->next=p->next->next;
q->next=q->next->next;
temp1->next=q->next;
q->next=temp1;
temp2->next=p->next;
p->next=temp2;
}
}
return head;
}
int main()
{
Linklist Head=NULL,p=NULL,Head1=NULL,Head2=NULL;
int x;
Head=CreateFromHead();
cout<<"随机产生的链表数据如下:"<<endl;
p=Head;
Show(p);
cout<<"*********逆置后链表*********"<<endl;
p=Head;
p=Daozhi(p);
Show(p);
cout<<"*****删除偶数元素后链表*****"<<endl;
p=Head;
p=Shanchu(p);
Show(p);
cout<<"*******非递减有序链表*******"<<endl;
p=Head;
Sort(p);
Show(p);
cout<<"请输入要插入的链表元素:";
cin>>x;
cout<<"******插入新元素后链表******"<<endl;
p=Head;
Charu(p,x);
Show(p);
cout<<"请键入两个非递减有序单向链表"<<endl;
Head1=CreateFromHead_();
p=Head1;
Sort(p);
Head2=CreateFromHead_();
p=Head2;
Sort(p);
cout<<"*****合并后的非递减序列*****"<<endl;
p=Hecheng(Head1,Head2);
Show(p);
cout<<"*****合并后的非递增序列*****"<<endl;
p=Daozhi(p);
Show(p);
return 0;
}
测试截图: