#include"stdafx.h"
#include<stdio.h>
#include <iostream>
using namespace std;
#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int ElemType;
typedef struct LNode{ //存储结构
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; /*LinkList是指向LNode结构体的指针类型，可以通过这个指针类型定义LNode这个结构体的表 */
Status InitList(LinkList &L); //初始化
void CreateList_H(LinkList &L,int n);//头插法创建单链表
void CreateList_R(LinkList &L,int n);//后插法创建单链表
void TraverseList(LinkList L); //显示单链表
Status GetElem(LinkList L,int i,ElemType &e);//按位置查找值
LNode *LocateElem(LinkList L,ElemType);//按值查找地址
Status ListInsert(LinkList &L,int i,ElemType e);//单个数据插入
Status ListDelete(LinkList &L,int i);//删除第i个数据
int main(int argc, char** argv) {
LinkList L;
int n,i,op=1;
ElemType e,value;
InitList(L);
cout<<"<1>.前插法创建单链表"<<endl
<<"<2>.后插法创建单链表"<<endl
<<"<3>.显示"<<endl
<<"<4>.按位查询"<<endl
<<"<5>.按值查询"<<endl
<<"<6>.插入第i个数据"<<endl
<<"<7>.删除第i个数据"<<endl
<<"<0>.退出"<<endl
<<"--------------------"<<endl;
while(op){
cout<<"请输入你要进行的操作:\t";
cin>>op;
if(op>7)cout<<"对不起输入错误！"<<endl;
switch(op){
case 1://前插法创建单链表
cout<<"你想创建单链表的表长为：";
cin>>n;
CreateList_H(L,n);
break;
case 2://后插法创建单链表
cout<<"你想创建单链表的表长为：";
cin>>n;
CreateList_R(L,n);
break;
case 3://显示
if(!L->next){
cout<<"还未创建单链表，查询失败！"<<endl;
break;
}
TraverseList(L);
break;
case 4://按位查询
if(!L->next){
cout<<"还未创建单链表，查询失败！"<<endl;
break;
}
cout<<"你想查询的位置i是：";
cin>>i;
if(GetElem(L,i,e)) cout<<"该位置的值是:"<<e<<endl;
else cout<<"查询失败！";
break;
case 5://按值查询
if(!L->next){
cout<<"还未创建单链表，查询失败！"<<endl;
break;
}
cout<<"你想查询的值value为：";
cin>>value;
cout<<"该值的位置是:"<<LocateElem(L,value)<<endl;
break;
case 6://插入
if(!L->next){
cout<<"还未创建单链表，查询失败！"<<endl;
break;
}
cout<<"你想插入的位置和数字是：";
cin>>i>>e;
if(ListInsert(L,i,e))cout<<"插入成功！";
else cout<<"输入位置不合法！" ;
break;
case 7://删除
if(!L->next){
cout<<"还未创建单链表，查询失败！"<<endl;
break;
}
cout<<"你想删除的位置i是：";
cin>>i;
if(ListDelete(L,i))cout<<"删除成功!"<<endl;
else cout<<"删除失败，删除位置不合法！";
break;
case 0:
cout<<"退出单链表！"<<endl;
return 0;
}
}
return 0;
}
Status InitList(LinkList &L){
L=new LNode;
L->next=NULL;
return 1;
}
void CreateList_H(LinkList &L,int n){
L=new LNode;
L->next=NULL;
for(int i=0;i<n;i++){
LinkList p;
p=new LNode;
cout<<"请输入第"<<n-i<<"个数为:";
cin>>p->data;
p->next=L->next;
L->next=p;
}
cout<<"前插法创建成功！"<<endl;
}
void CreateList_R(LinkList &L,int n){
L=new LNode;
L->next=NULL;
LinkList p,r;
r=L;
for(int i=0;i<n;i++){
p=new LNode;
cout<<"请输入第"<<i+1<<"个数为:";
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
cout<<"后插法创建成功！"<<endl;
}
void TraverseList(LinkList L){
LinkList p;
p=L;
cout<<"显示结果：";
while(p->next!=NULL){
p=p->next;
cout<<p->data<<" ";
}
cout<<endl;
}
Status GetElem(LinkList L,int i,ElemType &e){
LinkList p;
p=L;
int j;
for(j=0;j<i&&p;j++)//防止系统停止运行
p=p->next;
if(!p||i<1)return ERROR;
e=p->data;
return OK;
}
LNode *LocateElem(LinkList L,ElemType e){
LinkList p=L->next;//初始化指向首元结点
while(p&&p->data!=e){
p=p->next;
}
return p;//1.p为NULL 2.p->data==e
}
Status ListInsert(LinkList &L,int i,ElemType e){
//带有头结点 在第i个位置插入新结点（计数时不包含头结点）。
LinkList p,q;
p=L;
int j=0;
q=new LNode;
q->next=NULL;
q->data=e;
while(p&&j<i-1)//找第i-1个结点
{
p=p->next;
j++;
}
if(!p&&i<1)return ERROR;/*p为空说明未找到第i-1个结点 或者说i-1个结点是n+1 */
q->next=p->next;
p->next=q;
return OK;
}
Status ListDelete(LinkList &L,int i){
//找到第i-1个结点
LinkList p,q;
p=L;
int j=0;
while(p->next&&j<i-1)//找第i-1个结点
{
p=p->next;
j++;
}
if(!p->next||i<1)return ERROR;/*p->next为空则证明第i-1个结点是最后一个结点n 第i个不存在 无法删除 */
q=p->next;
p->next=q->next;//用q过渡一下第i-1个和第i+1个
delete q;//将过渡的这个辅助q删除掉
return OK;
}
