数据结构-实验2 单链表

【问题描述】
设计一个单链表操作演示程序。
【基本要求】
设计实现一个带头结点的单链表的操作演示程序，提供一个用户界面，可演
示的基本功能包括：
（1）初始化单链表；
（2）输入并建立单链表；（头插入法、尾插入法均可）
（3）输出单链表中的元素；
（4）在单链表指定位置插入元素；
（5）在单链表指定元素之前插入元素；
（6）删除单链表指定位置的元素；
（7）删除单链表指定元素之前的元素；
（8）删除单链表所有指定值的元素。
代码实现:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>

#define OK 1
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

typedef struct LNode
{
 ElemType data;
 struct LNode *next;
}LNode,*LinkList;

Status Create(LinkList &L)
{
 L=(LinkList)malloc(sizeof(LNode));
 if(L==NULL)
 {
  printf("申请空间失败!\n");
  printf("创建失败!\n");
 }
 printf("申请空间成功!\n");
 printf("创建成功!\n");
 L->next=NULL;
 return OK;
}

LNode *GetElem(LinkList L,int i)
{
 LNode *p=L;
 int j;
 for(j=0;j<i;j++)
 {
  p=p->next;
 }
 return p;
}

Status Length(LinkList L)
{
 LNode *p=L;
 int i=0;
 while(p->next!=NULL)
 {
  p=p->next;
  ++i;
 }
 return i;
}

Status Insert(LinkList &L,int i,ElemType e)//指定位置插入 
{
 LNode *p=L;
 int j=0;
 while(p&&j<i-1)
 {
  p=p->next;
  ++j;
 }
 if(!p||j>i-1)
 {
  return ERROR;
 }
 LNode *s;
 s=(LinkList)malloc(sizeof(LNode));
 s->data=e;
 s->next=p->next;
 p->next=s;
 return OK;
}

Status TInsert(LinkList &L,ElemType x,ElemType e)//指定元素前插入 
{
 LNode *p=L;
 int t=0;
 if(p->data==x)
 {
  LNode *s;
  s=(LinkList)malloc(sizeof(LNode));
  s->data=e;
  s->next=p;
  p->next=s;
  t=1;
  if(t==1)
  {
   printf("插入成功!\n");
  }
  else
  {
   printf("插入失败!\n");
  }
  return OK;
 }
 while(p->next!=NULL)
 {
  if(p->next->data!=x)
  {
   p=p->next;
  }
  else
  {
   LNode *s;
   s=(LinkList)malloc(sizeof(LNode));
   s->data=e;
   s->next=p->next;
   p->next=s;
   t=1;
   break;
  }
 }
 if(t==1)
 {
  printf("插入成功!\n");
 }
 else
 {
  printf("表中没有%d!\n",x);
  printf("插入失败!\n");
 }
 return OK;
}

Status Delete(LinkList &L,ElemType e,int flag)//删除某一元素 
{
 if(!L)
 {
  printf("表为空!\n");
  return ERROR;
 }
 LNode *p=L;
 int t=0;
 LNode *q;
 while(p!=NULL)
 {
  if(p->data!=e)
  {
   q=p;
   p=p->next;
  }
  else
  {
   t=1;
   LNode *s;
   s=(LinkList)malloc(sizeof(LNode));
   s->next=p;
   p=p->next;
   q->next=p;
   free(s);
   //1为全部删除，0为只删除一个 
   if(flag==0)
   {
    break;
   }
   else
   {
    continue;
   }
  }
 }
 if(t==1)
 {
  printf("删除成功!\n");
 }
 else
 {
  printf("删除失败!\n");
 }
 return OK;
}

Status LocateDelete(LinkList &L,int i,ElemType &e)//删除某一位置元素 
{
 if(!L)
 {
  printf("表为空!\n");
  return ERROR;
 }
 LNode *p,*q;
 if(i<1||i>Length(L)+1)
 {
  printf("删除位置错误!\n");
  return ERROR;
 }
 p=GetElem(L,i-1);
 q=p->next;
 p->next=q->next;
 e=q->data;
 free(q);
 printf("删除的元素为%d\n",e);
 printf("删除成功!\n");
 return OK;
}

Status TLocateDelete(LinkList &L,ElemType x,ElemType &e)//删除指定元素前一个元素 
{
 if(!L)
 {
  printf("表为空!\n");
  return ERROR;
 }
 LNode *p=L->next;
 LNode *q=L;
 int t=0;
 if(p->data==x)
 {
  printf("%d元素前没有元素!\n",p->data);
  return OK;
 }
 while(p!=NULL)
 {
  if(p->data!=x)
  {
   q=q->next;
   p=p->next;
  }
  else
  {
   t=1;
   e=q->data;
   q->next=p->next;
   break;
  }
 }
 if(t==1)
 {
  printf("被删除元素为%d\n",e);
 }
 else
 {
  printf("表中无%d!\n",x);
 }
 return OK;
}

Status shuchu(LinkList L)//输出链表 
{
 printf("链表元素为:\n");
 LNode *p=L->next;
 int i;
 for(i=0;i<Length(L);i++)
 {
  printf("%d",p->data);
  p=p->next;
  if(i!=Length(L)-1)
  {
   printf(" ");
  }
 }
 printf("\n");
 return OK;
}

Status charu(LinkList &L)//链表插入操作的集合 
{
 int i;
 ElemType e;
 int len;
 int flag;
 ElemType x;
 printf("1为位置插入，0为某元素插入.输入:\n");
 scanf("%d",&flag);
 if(flag==1)
 {
  printf("输入你想要插入的位置:\n");
  scanf("%d",&i);
  printf("输入你想要插入的值:\n");
  scanf("%d",&e);
  Insert(L,i,e);
  len=Length(L);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
 else
 {
  printf("被插入某元素的值:\n");
  scanf("%d",&x);
  printf("想要插入的值:\n");
  scanf("%d",&e);
  TInsert(L,x,e);
  len=Length(L);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
}

Status shanchu(LinkList &L)//链表删除操作的集合 
{
 int flag;
 int len;
 ElemType e;
 int i;
 ElemType x;
 printf("0为删除某一位置，1为删除某一元素，2为删除指定元素的前一个元素.选择:\n");
 scanf("%d",&flag);
 if(flag==1)
 {
  printf("输入要删除的值:\n");
  scanf("%d",&e);
  printf("1为全部删除,0为删除一个,输入确定值1或0:\n");
  scanf("%d",&flag);
  Delete(L,e,flag);
  len=Length(L);
  if(len==0)
  {
   printf("此时链表为空!\n");
  }
  else
  {
   printf("此时表的长度为%d\n",len);
   printf("此时表的元素为:\n");
   shuchu(L);
  }
 }
 else if(flag==0)
 {
  printf("输入要删除的位置:\n");
  scanf("%d",&i);
  LocateDelete(L,i,e);
  len=Length(L);
  if(len==0)
  {
   printf("此时链表为空!\n");
  }
  else
  {
   printf("此时表的长度为%d\n",len);
   printf("此时表的元素为:\n");
   shuchu(L);
  }
 }
 else if(flag==2)
 {
  printf("指定元素是:\n");
  scanf("%d",&x);
  TLocateDelete(L,x,e);
  len=Length(L);
  if(len==0)
  {
   printf("此时链表为空!\n");
  }
  else
  {
   printf("此时表的长度为%d\n",len);
   printf("此时表的元素为:\n");
   shuchu(L);
  }
 }
 return OK;
}

int main()
{
 LinkList L;
 Create(L);
 int n;
 printf("输入想要输入数据的个数:\n");
 scanf("%d",&n);
 int i;
 ElemType e;
 printf("输入想要输入的数据:\n");
 for(i=1;i<=n;i++)
 {
  scanf("%d",&e);
  Insert(L,i,e);
 }
 printf("长度为:\n");
 int len;
 len=Length(L);
 printf("%d\n",len);
 shuchu(L);
 printf("*******************************\n");
 printf("* 插入元素    :1 *\n");
 printf("* 删除元素    :2 *\n");
 printf("* 退出        :0 *\n");
 printf("*******************************\n");
 int num;
 while(1)
 {
  scanf("%d",&num);
  switch(num)
  {
   case 1:charu(L);
     break;
   case 2:shanchu(L);
     break;
   case 0:break;//exit(0);
   default:printf("请输入正确的数字:\n");
  }
  if(num==0)
  {
   break;
  }
 }
 printf("退出成功!\n");
 return 0;
}