数据结构-实验1 顺序表

【问题描述】
设计一个顺序表操作演示程序。
【基本要求】
顺序表操作演示程序提供一个用户界面，可演示的基本功能包括：
（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 

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int Status;
typedef int ElemType;

typedef struct
{
 ElemType *elem;
 int size;
 int length;
}SqList;

Status Init(SqList &L)//初始化顺序表
{
 L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空间 
 if(!L.elem)
 {
  printf("Init false!\n");//分配失败 
  return ERROR;
 }
 L.length=0;
 L.size=LIST_INIT_SIZE;
 printf("Init successful!\n");//分配成功 
 return OK;
}

Status Insert(SqList &L,int i,ElemType e)//在i位置插入数据 
{
 if(i<1||i>L.length+1)//位置不合理 
 {
  printf("The location you wanna insert is wrong!\n");
  return ERROR;
 }
 ElemType *newbase;
 if(L.length>=L.size)//顺序表长度不够 
 {
  newbase=(ElemType *)realloc(L.elem,(L.size+LISTINCREMENT)*sizeof(ElemType));//重新申请 
  if(!newbase)//重新申请失败 
  {
   printf("ERROR!\n");
   return ERROR;
  }
  L.elem=newbase;
  L.size+=LISTINCREMENT;
 }
 ElemType *p,*q;
 q=&(L.elem[i-1]);
 for(p=&(L.elem[L.length-1]);p>=q;--p)//数据的移动便于在给定位置的插入 
 {
  *(p+1)=*p;
 }
 *q=e;//在给定位置放入数据 
 L.length++;//表的长度加1 
 return OK;
}

Status TInsert(SqList &L,ElemType x,ElemType e,int flag)//在某元素前后插入数据 
{
 ElemType *newbase;
 if(L.length>=L.size)//顺序表长度不够 
 {
  newbase=(ElemType *)realloc(L.elem,(L.size+LISTINCREMENT)*sizeof(ElemType));//重新申请 
  if(!newbase)//重新申请失败 
  {
   printf("ERROR!\n");
   return ERROR;
  }
  L.elem=newbase;
  L.size+=LISTINCREMENT;
 }
 ElemType *p,*q;
 int i=0;
 int t=0;
 int k;
 while(i<L.length)
 {
  if(L.elem[i]!=x)//不等于要被插入某元素的值就移向下一位的比较 
  {
   i++;
  }
  else//等于要被插入某元素的值
  {
   t=1;
   if(flag==1)
   {
    q=&(L.elem[i]);
    for(p=&(L.elem[L.length-1]);p>=q;--p)//数据的移动便于在给定位置的插入 
    {
     *(p+1)=*p;
    }
    *q=e;
    L.length++;
   }
   else
   {
    q=&(L.elem[i]);
    for(p=&(L.elem[L.length-1]);p>q;--p)//数据的移动便于在给定位置的插入 
    {
     *(p+1)=*p;
    }
    *(q+1)=e;
    L.length++;
   }
   break;
  }
 }
 if(t==1)
 {
  printf("Insert successful!\n");
 }
 else
 {
  printf("Insert false!\nno %d\n",x);
 }
 return OK;
}

Status LocateDelete(SqList &L,int i,ElemType &e)//删除i位置的数据 
{ 
 if(L.length==0)
 {
  printf("List is empty!\n");
 }
 if(i<1||i>L.length)//位置不合理 
 {
  printf("The location you wanna insert is wrong!\n");
  return ERROR;
 }
 ElemType *p,*q;
 p=&L.elem[i-1];
 e=*p;//记录被删除的值 
 q=L.elem+L.length-1;
 for(++p;p<=q;++p)//数据的移动 
 {
  *(p-1)=*p;
 }
 L.length--;//长度减1 
 return OK;
}

Status TLocateDelete(SqList &L,ElemType x,ElemType &e)
{
 int t=0;
 int k;
 if(L.length==0)
 {
  printf("List is empty!\n");
 }
 ElemType *p,*q;
 int i=0;
 while(i<L.length)
 {
  if(L.elem[i]!=x)
  {
   i++;
  }
  else
  {
   if(i==0)
   {
    printf("该元素之前无元素!\n");
    break;
   }
   else
   {
    e=L.elem[i-1];
    for(k=i;k<L.length;k++)//数据的移动 
    {
     L.elem[k-1]=L.elem[k];
    }
    L.length--;
    t=1;
    break;
   }
  }
 }
 if(t==1)
 {
  printf("Delete sucessful!\n");
  printf("被删除的值为%d\n",e);
 }
 else
 {
  printf("Delete false!\nThere is no elem before %d\n",x);
 }
 return OK;
}

Status Length(SqList L)
{
 return L.length;
}

Status Clear(SqList &L)//清空表 
{
 L.length=0;
 printf("clear sucessful!\n");
 printf("The length of the list is %d\n",L.length);
 return OK;
}

Status Delete(SqList &L,ElemType e,int flag)//定值删除 
{
 int i=0;
 int t=0;
 int k;
 while(i<L.length)
 {
  if(L.elem[i]!=e)//不等于要删除的值就移向下一位的比较 
  {
   i++;
  }
  else//等于要删除的值
  {
   for(k=i+1;k<L.length;k++)//数据的移动 
   {
    L.elem[k-1]=L.elem[k];
   }
   L.length--;
   t=1;
   //01判断是否是只删除一个值，0就break，1就继续直到删除所有值为e的值 
   if(flag==0)
   {
    break;
   }
  }
 }
 if(t==1)
 {
  printf("delete sucessful!\n");
 }
 else
 {
  printf("delete false!\nno %d!\n",e);//没有指定元素时
 }
 return OK;
}

Status shuchu(SqList L)//表元素的输出
{
 int i;
 for(i=0;i<L.length;i++)
 {
  printf("%d",L.elem[i]);
  if(i!=L.length-1)
  {
   printf(" ");
  }
 }
 printf("\n");
 return OK;
}

Status charu(SqList &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);
  printf("1为前，0为后.将%d插入%d前还是后:\n",e,x);
  scanf("%d",&flag);
  TInsert(L,x,e,flag);
  len=Length(L);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
}

Status shanchu(SqList &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);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
 else if(flag==0)
 {
  printf("输入要删除的位置:\n");
  scanf("%d",&i);
  LocateDelete(L,i,e);
  printf("被删除的值为%d\n",e);
  len=Length(L);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
 else if(flag==2)
 {
  printf("要删除指定元素之前的元素的后一个元素是:\n");
  scanf("%d",&x);
  TLocateDelete(L,x,e);
  len=Length(L);
  printf("此时表的长度为%d\n",len);
  printf("此时表的元素为:\n");
  shuchu(L);
 }
}

int main()
{
 SqList L;
 Init(L);
 int i;
 int n;
 printf("输入想要添加数据的个数:\n");
 scanf("%d",&n);
 int x;
 printf("要添加的数据:\n");
 for(i=1;i<=n;i++)
 {
  scanf("%d",&x);
  Insert(L,i,x);
 }
 printf("添加成功!\n");
 int len;
 len=Length(L);
 printf("此时表的长度为%d\n",len);
 printf("此时表的元素为:\n");
 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;
  }
 }
 int flag; 
 printf("1为清空，0为不清空.是否要清空表:\n");
 scanf("%d",&flag);
 if(flag==1)
 {
  Clear(L);
 }
 return 0;
}