顺序表的基本操作。
顺序表的基本操作
编写一个完整的程序，实现顺序表的建立、插入、删除、输出等基本运算。
- 建立一个顺序表，含有n个数据元素。
- 输出顺序表及顺序表的长度。
- 在顺序表中删除值为x的结点或者删除给定位置i的结点。
- 将顺序表就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。
- 将顺序表按升序排序。
- 设顺序表中的数据元素递增有序，将x插入到顺序表的适当位置上，以保持该表的有序性。
- 将两个顺序有序表A和B合并为一个有序表C。
- 在主函数中设计一个简单的菜单，分别测试上述算法。
程序
#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;
}