顺序表的基本操作。

顺序表的基本操作

编写一个完整的程序,实现顺序表的建立、插入、删除、输出等基本运算。 (1) 建立一个顺序表,含有n个数据元素。 (2) 输出顺序表及顺序表的长度。 (3) 在顺序表中删除值为x的结点或者删除给定位置i的结点。 (4) 将顺序表就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。

(5) 将顺序表按升序排序。 (6) 设顺序表中的数据元素递增有序,将x插入到顺序表的适当位置上,以保持该表的有序性。 (7) 将两个顺序有序表A和B合并为一个有序表C。 (8) 在主函数中设计一个简单的菜单,分别测试上述算法。

参考程序

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define OVERFLOW -2
#define ERROR 0
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}

//创建一个空表
int InitList(SqList &L)
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空间

if(!L.elem)
 return OVERFLOW;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
//在创建的空表中插入数据
int ListInsert(SqList &L,int i,ElemType e)
{
ElemType* newbase;
//ElemType* q;
if(i<0 ||
i>L.length+1)
 return ERROR;
if(L.length>=L.listsize)//当前空间已满,增加新空间

{
 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

 if(!newbase)
  return
OVERFLOW;
 L.elem=newbase;
 L.listsize+=LISTINCREMENT;

}

L.elem[i]=e;
//printf("%d ",L.elem[i]);
L.length++;
return OK;
}
//删除位置为i的节点
int ListDelete(SqList &L,int i)
{
ElemType* p;
ElemType* q;
if(i<0 ||
i>L.length)
 return ERROR;
p=&(L.elem[i-1]);
//e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;p++)
 *(p-1)=*p;
L.length--;
return OK;
}
//在顺序表中删除数据x
int DeleteX(SqList &L, int x)
{
ElemType* p;
int i;
for(i=0;i<L.length;i++)
 if(L.elem[i]==x)
 {
  break;
 }
 p=&L.elem[i];

 //free(p);
 for(int
j=i;j<L.length-1;j++)
 {
  L.elem[j]=L.elem[j+1];

 }
 L.length--;
 return OK;
}
//反转顺序表
int TurnArrond(SqList &L)//翻转顺序表
{
ElemType* p;
ElemType* q;
int t;
p=&(L.elem[0]);
q=L.elem+L.length-1;
for(p;p<q;p++,q--)
{
 t=*q;
 *q=*p;
 *p=t;
}
return OK;
}
//升序排列顺序表
int ABC(SqList &L)
{
int a[10000];
int i;
for(i=0;i<L.length;i++)
 a[i]=L.elem[i];
qsort(a,L.length,sizeof(a[0]),cmp);

for(i=0;i<L.length;i++)
 L.elem[i]=a[i];
return OK;
}
//把顺序表升序排列后插入元素e
int ListInsertABC(SqList &L,ElemType e)
{
ElemType* newbase;
int i,j;
if(L.length+1>=L.listsize)//当前空间已满,增加新空间

{
 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

 if(!newbase)
  return
OVERFLOW;
 L.elem=newbase;
 L.listsize+=LISTINCREMENT;

}

for(i=0;i<L.length;i++)
 if(e<L.elem[i])

  break;
 
 for(j=L.length;j>i;j--)

 {
  L.elem[j]=L.elem[j-1];

 }
 L.length++;
 L.elem[j]=e;
 //printf("%d
",L.elem[i]); 
 return OK;
}
//合并顺序表L,L1为L2
int MergeList(SqList L,SqList L1,SqList &L2)
{
ElemType* pa;
ElemType* pb;
ElemType* pc;
ElemType* pa_last;
ElemType* pb_last;
pa=L.elem;
pb=L1.elem;
// L2.elem=pc;
L2.listsize=L.listsize+L1.listsize;
pc=L.elem=(ElemType*)malloc(L2.listsize *
sizeof(ElemType));

pa_last=L.elem+L.length-1;
pb_last=L1.elem+L1.length-1;
while(pa<=pa_last && pb<=pb_last)
{
 if(*pa<=*pb)

  *pc++=*pa++;

 else
  *pc++=*pb++;

}
while(pa<=pa_last)
 *pc++=*pa++;
while(pb<=pb_last)
 *pc++=*pb++;
for(int
i=0;i<L2.length;i++)
 printf("%d ",L2.elem[i]);
return OK;
}
//打印菜单
void printScreen()
{
//printf("1.建立一个顺序表,含有n个数据元素。\n");
printf("1.输出顺序表L1及其长度\n");
printf("2.删除给定位置i的结点\n");
printf("3.在顺序表中删除值为x的结点\n");
printf("4.逆置顺序表\n");
printf("5.将顺序表按升序排序\n");
printf("6.设顺序表中的数据元素递增有序,将x插入到顺序表的适当位置上,以保持该表的有序性\n");

printf("7.将两个顺序有序表L和L1合并为一个有序表L2\n");
printf("0.退出操作系统。\n");
printf("请输入需要的操作序号:");
}
//输出顺序表L
void printSqList(SqList &L)
{
int i;
for(i=0;i<L.length;i++)
 printf("%d ",L.elem[i]);
printf("\n");
}
int main()
{
SqList L,L1,L2;
InitList(L);
InitList(L1);
InitList(L2);
int n,e,muse,i,x;
bool flag;
//建立第一个的顺序表
printf("请输入第一个数据表的长度:");
scanf("%d",&n);
printf("请以次输入长度为%d的顺序表:",n);
for(i=0;i<n;i++)
{
 scanf("%d",&e);

 ListInsert(L,i,e);//依次在第i个位置插入顺序表

}
printf("第一个顺序表的次序为:");
printSqList(L);

//建立第二个顺序表
printf("建立第二个顺序表,请输入要第二个建立数据表的长度:");
scanf("%d",&n);
printf("请以次输入长度为%d的顺序表:",n);
for(i=0;i<n;i++)
{
 scanf("%d",&e);

 ListInsert(L1,i,e);//依次在第i个位置插入顺序表

}
printf("第二个顺序表的次序为:");
printSqList(L1);

//打印菜单
printScreen();
scanf("%d",&muse);
flag=true;
while(1)
{
 switch(muse)
 {
 case 0:
  flag=false;

  break;
 case 1:
  printf("顺序表的长度为:");

  printf("%d\n",L.length);

  break;
 case 2:
  printf("请输入要删除的节点:");

  scanf("%d",&i);//删除顺序表的节点

  if(ListDelete(L,i))

  {
   printf("删除成功!\n");

   printSqList(L);

  }
  else
   printf("删除失败!\n");

  break;
 case 3:
  printf("请输入要删除的节点x的值:");

  scanf("%d",&x);

  if(DeleteX(L,x))

  {
   printf("删除成功!\n顺序表为:");

   printSqList(L);

  }
  else
   printf("删除失败!\n");

  break;
 case 4:
  //逆序顺序表
  if(TurnArrond(L))

  {
   printf("逆序成功!\n");

   printf("顺序表的次序为:");

   printSqList(L);

  }
  else
   printf("逆序失败!\n");

  break;
 case 5:
  //顺序表升序排列

  if(ABC(L))

  {
   printf("顺序表升序排列成功!\n");

   printf("顺序表的次序为:");

   printSqList(L);

  }
  else
   printf("顺序表升序排列失败!\n");

  
  printf("请输入要插入的数据:");

  scanf("%d",&e);

  if(ListInsertABC(L,e))

  {
   printf("顺序插入成功!\n");

   printf("顺序表的次序为:");

   printSqList(L);

  }
  else
   printf("顺序插入失败!\n");

  break;
 case 6:
  ABC(L);
  printf("请输入要插入的数字x的值:");

  scanf("%d",&x);

  if(ListInsertABC(L,x))

  {
   printf("操作成功!\n");

   printf("顺序表的次序为:");

   printSqList(L);

  }
  else
printf("操作失败!\n");
  break;
 case 7:
  if(MergeList(L,L1,L2))

  {
   printf("顺序表L,L1合并成功!\n");

   //printf("顺序表的次序为:");

   //printSqList(L2);

  }
  else
   printf("顺序表合并失败!\n");

  break;
 default:
  break;
 }
 if(!flag)
  break;
 printf("\n请输入你要的下一步操作序号:");

 scanf("%d",&muse);

}

if(L.elem)
 free(L.elem);
if(L1.elem)
 free(L1.elem);
if(L2.elem)
 free(L2.elem);

return 0;
}

参考

迁移自谢先斌的博客:http://blog.sina.com.cn/s/blog_002e20310100xmwj.html

完毕。