#include <cstdlib>
#include <iostream.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
void InitList(LinkList *&L) //构造一个空的线性表L
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL; //L为空
}
void CreateListR(LinkList *&L,int n) //选择个数(n) ,即链表的长度。
{
LinkList *s,*r,*p;
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
r=L;
for(int i=0;i<n;i++)
{
s=(LinkList *)malloc(sizeof(LinkList)); //创建新结点
s->data=rand()%100; //随机产生一组数据（0-100）
r->next=s;
r->data=s->data;
r=s;
}
r->next =NULL;
p=(LinkList *)malloc(sizeof(LinkList));
s=L->next;
/* for(p->data=s->data;p==NULL;s=s->next)
{
if(s->data>p->data)
r->data=s->data;
s->data=p->data;
p->data=r->data;
};*/
//else:(r->data==s->data)或(r->data<s->data)
}
void show1(LinkList *&L)
{
LinkList *s;
s=L;
while(s->next!=NULL)
{
cout<<s->data<<endl;
s=s->next;
}
}
//查找数据元素e
bool seek(LinkList *&L,ElemType e)
{
LinkList *p=L->next,*r=L;
cout<<"请输入需要查找的元素"<<endl;
cin>>e;
while(p!=NULL && p->data <e)
{
r=p;p=p->next; //后移
}
if(p->data==e) //查找到值为e的数据元素
{
cout<<"找到该元素"<<endl;
return 1;
}
else //没有值为e的数据元素
{
cout<<"没有找到该元素"<<endl;
return 0;
cout<<"*****************************"<<endl;
}
}
//数据元素e插入到顺序表L中，使之仍有序。
int Insert(LinkList *&L,ElemType e)
{
LinkList *p=L->next,*r=L ,*s; //p指向第一个节点，L指向头结点，定义指针s
cout<<"请输入需要插入的元素e"<<endl;
cin>>e;
while(p!=NULL && p->data <e) //当第一个点上的不为空，且其值小于e
{
r=p;p=p->next; //r变为p，p变为下一个结点
}
if(p->data>e) //如果p的值大于e
s=(LinkList * )malloc(sizeof(LinkList)); //创建新的节点s
s->data=e; //s=e
s->next=r->next;
r->next=s;
s->next=p;
return 1;
{ //e大于L中的全部值
s=(LinkList * )malloc(sizeof(LinkList));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
}
void show2(LinkList *&L)
{
LinkList *s;
s=L;
cout<<"*****************************"<<endl;
while(s->next!=NULL)
{
cout<<s->data<<endl;
s=s->next;
}
}
//删除顺序列表中值为e的数据元素
int Delete(LinkList * &L,ElemType e )
{
LinkList *p=L->next,*r=L; //p指向第一个节点，L指向头结点，
cout<<"请输入需要删除的元素e"<<endl;
cin>>e;
while(p->data!=e && p->data<e) //当p的值不等于e的值，且p的值小于e
{
r=p;
p=p->next;
}
if(p->next==NULL) //如果p为尾节点
return 0;
else //p->data==e
{
r->next=p->next;
free(p); //删除P
return 1;
}
}
void show3(LinkList *&L)
{
LinkList *s;
s=L;
cout<<"*****************************"<<endl;
while(s->next!=NULL)
{
cout<<s->data<<endl;
s=s->next;
}
}
//将值为e的数据元素修改为e1
int revise(LinkList * &L,ElemType e,ElemType e1)
{
LinkList *p=L->next,*r=L;
cout<<"请输入需要修改的元素e，和要需要修改后的值e1"<<endl;
cin>>e;
cin>>e1;
while(p->data!=e && p->data<e)
{
r=p;p=p->next;
}
if(p->next==NULL) //如果p为尾节点
return 0;
else //p->data==e
{
p->data=e1;//把e1的值赋给p
return 1;
}
}
void show4(LinkList *&L)
{
cout<<"*****************************"<<endl;
LinkList *s;
s=L;
while(s->next!=NULL)
{
cout<<s->data<<endl;
s=s->next;
}
cout<<"*****************************"<<endl;
}
void main()
{
LinkList *L;
int e;
int e1;
CreateListR(L,3);
show1(L);
seek(L,e);
Insert(L,e);
show2(L);
Delete(L,e);
show3(L);
revise(L,e,e1);
show4(L);
}
/*2. 有序单链表的操作
要求：
（1） 随机产生一组整数并排序。
（2） 主要功能：
查找值为e的数据元素。
插入值为e的数据元素。（保持仍然有序）
删除值为e的数据元素。
将值为e的数据元素修改为e1。（保持仍然有序）*/
相关分类