数据结构顺序表C实现（14个用户接口）
将顺序表（ADT SqList）的数据对象，数据关系及基本操作（函数）用C语言实现，并测试。
手机用户点击代码移动可查看未显示内容
1.SqList.h头文件内容
C++
#define LIST_INIT_SIZE 100
#define LISTINCREASEMENT 10
typedef int ElemType;
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
//函数名：
void ListInit(SqList &L);
void ListOutput(SqList &L);
void Listvisit(ElemType e);
int ListInsert(SqList &L,int i,ElemType e);
int ListDelete(SqList &L,int i);
int ListGetLength(SqList L);
int ListClear(SqList &L);
int ListDestroy(SqList &L);
int ListIsEmpty(SqList L);
int ListLocateElem(SqList L,ElemType e);
int ListGetElem(SqList L,int i,ElemType &e);
int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e);
void ListTraverse(SqList L, void(*visit)(ElemType));
void ListSort(SqList &L,int t);
void ListMerge(SqList La, SqList Lb, SqList &Lc);函数实现
1.顺序表的初始化
C++
void ListInit(SqList &L){
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
}注释：为了检查顺序表是否初始化，本人调用了检查顺序表是否为空的函数 （bool ListIsEmpty(SqList L)）函数实现在下面会讲到。
2.顺序表的输出
C++
void ListOutput(SqList &L){
int i;
for (i = 0; i < L.length; i++)
printf("%d ", L.elem[i]);
printf("\n");
}3.顺序表的长度
C++
int ListGetLength(SqList L){
if(L.elem!=NULL)
return L.length;
else
return ERROR;
}4.插入一个值到顺序表中
C++
int ListInsert(SqList &L,int i,ElemType e){
ElemType *q,*p,*newbase;
if(i<1||i>L.length+1)return ERROR;
if(L.length>=L.listsize) {
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREASEMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREASEMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
++L.length;
return OK;
}5.删除顺序表中的一个值
C++
int ListDelete(SqList &L,int i){
ElemType *p,*q;
if(i<1||i>L.length+1)return ERROR;
p=&(L.elem[i-1]);
q=L.elem+L.length-1;
if (i == 1)*p = *(p + 1);
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
return OK;
}6.顺序表是否为空的判断函数
C++
bool ListIsEmpty(SqList L){
if(L.length==0)
return TRUE;
else
return FALSE;
}注释：空为TRUE 非空为FALUSE
7.顺序表数据的位置查询
C++
int ListLocateElem(SqList L, ElemType e){
int i,k=-1;
for(i=1;i<=L.length;i++)
{
if(*(L.elem+(i-1))==e)
{
k=i;
break;
}
}
return k;
}8.顺序表某个位置的数据查询
C++
int ListGetElem(SqList L, int i, ElemType &e){
if(i<1||i>L.length+1)return ERROR;
int j;
ElemType *p;
p=L.elem;
for(j=0;j<i-1;j++)
p++;
e=*p;
return OK;
}9.查询某个值的前驱和后继
前驱：
C++
int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{
int i;
for (i = 1; i <= L.length; i++)
{
if (L.elem[i-1] == cur_e)
break;
}
if (i < 1 || i > L.length+1)return ERROR;
else
{
pre_e = L.elem[i-2];
return OK;
}
}后继：
C++
int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e)
{
int i;
for (i = 1; i <= L.length; i++)
{
if (L.elem[i-1] == cur_e)
break;
}
if (i>L.length)return ERROR;
else
{
next_e = L.elem[i];
return OK;
}
}10.两个非递减顺序表的合并
C++
void ListMerge(SqList La, SqList Lb, SqList &Lc){
ElemType *pa, *pb,*pc;
pa = La.elem; pb = Lb.elem;
Lc.listsize =Lc.length= La.length + Lb.length;
pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if (!Lc.elem)exit(OVERFLOW);
ElemType *pa_last, *pb_last;
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.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++;
}//非递减归并11.顺序表的排序
C++
void ListSort(SqList &L,int t)
{
int i,j;
ElemType m;
if (t == 0)
{
for (i = 0; i < L.length-1; i++)
{
for (j = 0; j < L.length - 1 - i; j++)
{
if (L.elem[j]>L.elem[j + 1])
{
m = L.elem[j];
L.elem[j] = L.elem[j + 1];
L.elem[j + 1] = m;
}
}
}
}
else
{
for (i = 0; i < L.length - 1; i++)
{
for (j = 0; j < L.length - 1 - i; j++)
{
if (L.elem[j]<L.elem[j + 1])
{
m = L.elem[j];
L.elem[j] = L.elem[j + 1];
L.elem[j + 1] = m;
}
}
}
}
}//冒泡法排序12.顺序表的清除和销毁
清除：
C++
int ListClear(SqList &L)
{
if(L.elem==NULL)
return ERROR;
else
{
L.length=0;
return OK;
}
}销毁：
C++
int ListDestroy(SqList &L)
{
if(L.elem==NULL)
return ERROR;
else
{
free(L.elem);
return OK;
}
}注释：清除后使用LISTISEMPTY函数判断是否清空。
MAIN函数：
C++
int main()
{
printf("------------------------------------------\n");
SqList L;
printf("顺序表L初始化......\n");
ListInit(L);
printf("------------------------------------------\n");
printf("检查顺序表是否为空：\n");
if (ListIsEmpty(L) == TRUE)
printf("EMPTY\n");
else
printf("SUBFULL\n");
printf("------------------------------------------\n");
int i,n;
printf("输入顺序表的长度（小于100）：\n");
scanf("%d", &n);
printf("输入%d个值：\n",n);
for (i = 0; i < n; i++,L.length++)
scanf("%d", &L.elem[i]);
printf("检查顺序表：\n");
ListOutput(L);
printf("------------------------------------------\n");
printf("顺序表当前长度为%d。\n", ListGetLength(L));
printf("------------------------------------------\n");
printf("插入一个值到当前顺序表中：\n");
printf("输入插入的位置：\n");
int p;
scanf("%d", &p);
printf("输入插入的值：\n");
ElemType e;
scanf("%d", &e);
ListInsert(L, p, e);
printf("顺序表的值：\n");
ListOutput(L);
printf("顺序表当前长度为%d\n", ListGetLength(L));
printf("------------------------------------------\n");
printf("删除当前顺序表中的一个值：\n");
printf("输入删除的位置：\n");
scanf("%d", &p);
ListDelete(L, p);
printf("顺序表的值：\n");
ListOutput(L);
printf("顺序表当前长度为%d\n", ListGetLength(L));
printf("------------------------------------------\n");
printf("检查顺序表是否为空：\n");
if (ListIsEmpty(L) == TRUE)
printf("EMPTY\n");
else
printf("SUBFULL\n");
printf("------------------------------------------\n");
printf("顺序表数据的位置查询：\n");
printf("输入需要查询的值：\n");
ElemType d;
scanf("%d", &e);
if (ListLocateElem(L, e) >= 1)
printf("%d在第%d个位置。\n",e,ListLocateElem(L,e));
else
printf("ERROR");
printf("------------------------------------------\n");
printf("顺序表位置的数据查询：\n");
printf("输入需要查询的位置：\n");
scanf("%d", &p);
if (ListGetElem(L,p,e) == OK)
printf("第%d个元素是%d。\n",p,e);
else
printf("ERROR");
printf("------------------------------------------\n");
printf("查询某个值的前驱和后继：\n");
ElemType pre_e, next_e;
printf("输入此值：\n");
scanf("%d", &e);
ListPriorElem(L, e, pre_e);
ListNextElem(L, e, next_e);
printf("%d的前驱是%d，后继是%d。\n", e,pre_e,next_e);
printf("------------------------------------------\n");
printf("若顺序表L为非递减排列，\n请创建非递减顺序表M\n并使用非递减归并函数（Y/N)?\n");
char flag;
getchar();
scanf("%c", &flag);
if (flag == 'Y')
{
SqList M, N;
printf("顺序表M初始化......\n");
ListInit(M);
printf("输入顺序表的长度（小于100）：\n");
scanf("%d", &n);
printf("输入%d个值：\n", n);
for (i = 0; i < n; i++, M.length++)
scanf("%d", &M.elem[i]);
printf("检查顺序表L和M：\n");
printf("L: ");
ListOutput(L);
printf("M: ");
ListOutput(M);
printf("非递减归并后：\n");
ListMerge(L, M, N);
ListOutput(N);
}
system("pause");
printf("------------------------------------------\n");
printf("顺序表排序：\n");
printf("降序排列为：\n");
ListSort(L, -1);
ListOutput(L);
printf("升序排列为：\n");
ListSort(L, 0);
ListOutput(L);
printf("------------------------------------------\n");
printf("顺序表清除中......\n");
ListClear(L);
printf("检查顺序表是否为空：\n");
if (ListIsEmpty(L) == TRUE)
printf("EMPTY\n");
else
printf("SUBFULL\n");
printf("\n");
printf("顺序表销毁中......\n");
ListDestroy(L);
printf("------------------------------------------\n");
system("pause");
return 0;
}
小结：
1. 实验中使用工程文件使得代码文件更有可移植性并程序化，更加规范。 2. 试验中代码文件由VC++6.0转移到VS或Code::Blocks时应打开工程文件的.dsp文件使得代码自动导入。
3. 顺序表中Merge函数应注意要对新的归并顺序表进行实时的Malloc动态分配，且调用该函数时应注意两个顺序表必须是非递减的。 4. 在顺序表的输入时，for语句最好实时对L.length进行修改，同样地在Insert和Delete函数中也应采取同样地措施。 5. 在本人实现的顺序表中，要注意内部存储是从0开始的，但是在面向用户时是从1开始。 6. 对&引用标识符在函数调用时要注意。 7. 由于函数只能return一个值，可以使用地址来返回其它值（增加一个变量）如前驱函数后继函数等。 8. 由于ElemType在程序中被定义为int,因此可以使用scanf(%d) 类型不同时要注意。推荐使用C++ cin函数。
原创非商业转载请注明出处，商业转载请联系。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读