#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
ElemType date;//结点的数据域
struct LNode *next;//结点的指针域
} LNode,*LinkList; //LNode现在等价于struct LNode,LinkList为指向结构体LNode的指针类型
//单链表的初始化
void InitList(LinkList &L)
{
//构建一个空的单链表L
L=new LNode;//生成新的结点作为头结点,用头指针L指向头结点
L->next=NULL;//头结点的指针域置空
cout<<"单链表构建成功!"<<endl;
}
//单链表的插入
void ListInsert(LinkList &L,ElemType e)
{
LinkList s=new LNode;//生成一个新结点*s
s->date=e;//将结点的数据域置为e
s->next=L->next;//将结点的指针域指向插入结点的后一结点,这里是首元结点
L->next=s;//将头结点指针域修改为指向插入的结点*s
}
void ListInsert(LinkList &L,int i,ElemType e)
{
//在带头结点的单链表L中dii个位置插入值为e的新结点
LinkList p=L;//p指针指向头结点
int j=0;
while(p&&(j<i-1))
{
p=p->next;
++j;//查找第i-1个结点,p指向该结点
}
if(!p||j>i-1) //i>n+1或者i<1
{
cout<<"ERROR"<<endl;
}
LinkList s=new LNode;//生成一个新结点*s
s->date=e;//将结点的数据域置为e
s->next=p->next;//将新结点*s的指针域指向结点a(i)
p->next=s;//将结点*p的指针域指向结点*s
cout<<"插入成功!"<<endl;
}
//取值
int GetElem(LinkList L,int i,ElemType &e)
{
//在带头结点的单链表L中根据序号i获取元素的值,用e返回L中第i个数据元素的值
LinkList p=L->next;//初始化,p指向首元结点
int j=1;//计数器初值赋为1
while(p&&j<i)//顺链域扫描,直到p为空或p指向第i元素
{
p=p->next;//p指向下一结点
++j;//计数器j相应加1
}
if(!p||j>i)//i值不合法i>n或i<=0
{
cout<<"ERROR"<<endl;
}
e=p->date;//取第i个结点的数据域
cout<<"取值成功!"<<endl;
return e;
}
//求单链表长度
int ListLength(LinkList &L)//返回值类型为int
{
LinkList p=L;//p指针指向头结点
int i=0;//用于计数,初值为0
while(p->next!=NULL)//只要结点指针域不为空
{
i++;
p=p->next;//p指向下一结点
}
return i;
}
//删除
void DeleteElem(LinkList &L, ElemType e)
{
LinkList p = L;//p指向头结点
LinkList q = NULL;
while(p->next != NULL)
{
if(p->next->date == e) //从首元结点开始比对
{
q = p->next;//临时保存被删结点的地址以备释放
p->next = p->next->next;//改变删除结点前驱结点的指针域
break;
}
p = p->next;//p指向下一结点
}
if(q != NULL)
{
delete q;//释放删除结点的空间
}
}
//删除第i个元素
void deleteIndex(LinkList &L, int i)
{
LinkList p = L;
LinkList q = NULL;
int num = 0;
while(p->next != NULL)
{
num++;
if( num == i)
{
q = p->next;
p->next = p->next->next;
break;
}
p = p->next;
}
if(q != NULL)
{
delete q;
}
}
//删除
void ListDelete(LinkList &L,int i)
{
//在带头结点的单链表L中,删除第i个元素
LinkList p = L;//p指向头结点
LinkList q = NULL;
int j = 0;
while((p->next)&&(j<i-1))//查找第i-1个结点,p指向该结点
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1)) //当i>n或n<1时,删除位置不合理
{
cout<<"ERROR"<<endl;
}
q=p->next;//临时保存被删除结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
delete q;//释放删除结点的空间
cout<<"删除成功!"<<endl;
}
//查找数据是否存在
bool SearchList(LinkList &L,ElemType e)
{
LinkList p=L->next;//让p指向首元结点
while(p!=NULL)//p不为空时
{
if(p->date==e)//p结点的数据域与需要查询的数据进行比对
{
return true;//如果相等,返回true
}
p=p->next;//p指向下一节点
}
return false;
}
//查找位值
ElemType SearchIndex(LinkList &L,int index)
{
LinkList p=L;//p指针指向头结点
int i=0;//i用于比对是否到达指定位置index
while (p->next!=NULL)//p指向的结点指针域不为空
{
p=p->next;//p指向下一结点
i++;
if(i==index)//到指定位置
{
return p->date;//返回此时p所指结点的数据
}
}
return -1;//查找失败
}
//输出
void OutputList(LinkList &L)
{
LinkList p=L->next;//指向首元结点
while(p!=NULL)//当前结点不为空
{
cout<<p->date<<endl;//输出当前结点数据
p=p->next;//P指向下一结点
}
}
int main()
{
LinkList L=NULL;
InitList(L);
for(int i=1; i<=10; i++)
{
ListInsert(L,i*10);
}
OutputList(L);
cout<<"线性表长度为:"<<ListLength(L)<<endl;
//查找
//查找元素是否存在
// int e;
// cout<<"输入需查找元素值e:";
// cin>>e;
// cout<<"查找元素"<<e<<"的结果为:"<<SearchList(L,e)<<endl;
//查找位值
// int index;
// cout<<"输入查找的位值:";
// cin>>index;
// cout<<"查找位值"<<index<<"的结果为"<<SearchIndex(L, index)<<endl;
//取值
// int i;
// cout<<"输入需取元素的位置i:";
// cin>>i;
// int e=GetElem(L,i,e);
// cout<<"第i个位置元素是:"<<e<<endl;
//插入
// int i;
// cout<<"输入插入位置i:";
// cin>>i;
// int e;
// cout<<"输入插入数值e:";
// cin>>e;
// ListInsert(L,i,e);
// OutputList(L);
//删除元素
int e;
cout<<"输入需要删除的值:";
cin>>e;
DeleteElem(L, e);
//删除第i个元素
// int i;
// cout<<"输入需要删除元素的序号:";
// cin>>i;
// ListDelete(L,i);
// deleteIndex(L,i);
OutputList(L);
}