#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
using namespace std;
#define Maxsize 100
#define ElemType int 
#define Status int 
typedef long long ll;
typedef struct Node
{int data;//数据存储struct Node *next;//指针域
}Node,*List;List Init_List()
{Node *ls;ls=(Node*)malloc(sizeof(Node));//申请结点空间if(ls==NULL) exit(0);//如果失败则退出程序ls->next=NULL;return ls;
}
//头插法创建链表
List Creat_ls_head()
{Node *ls;ls=(Node*)malloc(sizeof(Node));ls->next=NULL;int x;while(scanf("%d",&x)){if(x==-1) break;Node *p;p=(Node*)malloc(sizeof(Node));p->data=x;//将该节点赋值为x//ls-NULL--L-p--NULLp->next=ls->next;ls->next=p;//更新一下L的指针永远指向头部cout<<"结点创建完成!"<<endl;}return ls; 
}//尾插法创建链表
List Creat_ls_tail()
{Node *ls;ls=(Node*)malloc(sizeof(Node));ls->next=NULL;int x;//设置一个尾节点rNode *r;r=ls;while(scanf("%d",&x)){if(x==-1) break;Node *p;p=(Node*)malloc(sizeof(Node));p->data=x;//将该节点赋值为xr->next=p;//r要永远代表最后一个节点r=p;cout<<"结点创建完成!"<<endl;}r->next=NULL;//cout<<"OK"<<endl;return ls; 
}
//打印链表
void ls_display(List L)
{Node *p=L->next;int cnt=0;while(p){cnt++;cout<<"第"<<cnt<<"个元素的值为:"<<p->data<<endl;//p指针下移一个p=p->next;}
}
//对于元素进行修改
List ls_replace(List ls,int x,int y)
{Node *p=ls->next;int cnt=0;while(p){if(p->data==x) p->data=y;//将所有的x替换成y;p=p->next;}return ls;
}
List ls_insert(List ls,int i,int x)
{Node *p;p=ls;//将指针指第i个位置的前驱	for(int ti=0;ti<i;ti++)  p=p->next;Node *q;q=(Node*)malloc(sizeof(Node));//插入的结点为qq->data=x;q->next=p->next;p->next=q;return ls;
}
//删除值为x的元素
List ls_delete(List ls,int x)
{Node *p,*q;p=ls->next;while(p->data!=x){q=p;p=p->next;}//此时已经找到的话q->next=p->next;free(p);return ls;
}
int main()
{//①利用尾插法进行创建链表List ls1;cout<<"****************************************"<<endl;cout<<"请输入单链表的数据：以-1结尾"<<endl;ls1=Creat_ls_tail();ls_display(ls1);cout<<"****************************************"<<endl;//②利用头插法进行创建链表List ls2;cout<<"****************************************"<<endl;cout<<"请输入单链表的数据：以-1结尾"<<endl;ls2=Creat_ls_head();ls_display(ls2);cout<<"****************************************"<<endl;//执行插入操作int i;int x;cout<<"****************************************"<<endl;cout<<"请输入插入数据的位置:";cin>>i;cout<<"请输入插入的数值大小:";cin>>x;cout<<"原序列的表示如下所示:"<<endl;ls_display(ls2);cout<<"现序列的表示如下所示:"<<endl;ls_insert(ls2,i,x);ls_display(ls2);cout<<"****************************************"<<endl;//执行修改操作cout<<"****************************************"<<endl;cout<<"请输入原来数据的值:";cin>>i;cout<<"请输入修改的数值大小:";cin>>x;cout<<"原序列的表示如下所示:"<<endl;ls_display(ls2);cout<<"现序列的表示如下所示:"<<endl;ls_replace(ls2,i,x);ls_display(ls2);cout<<"****************************************"<<endl;//执行删除操作cout<<"****************************************"<<endl;cout<<"请输入需要删除的数据的值:";cin>>x;cout<<"原序列的表示如下所示:"<<endl;ls_display(ls2);cout<<"现序列的表示如下所示:"<<endl;ls_delete(ls2,x);ls_display(ls2);cout<<"****************************************"<<endl;cout<<"完成所有链表的操作!"<<endl;return 0;
}