数据结构线性表（1）顺序表C语言代码实现

57 阅读 0 评论 38 点赞

我是靠谱客的博主傲娇画笔，最近开发中收集的这篇文章主要介绍数据结构线性表（1）顺序表C语言代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序表C语言代码实现

实验要求：编写一个头文件SqList.h，实现顺序表的各种基本操作，并在此基础上设计一个主程序（exp2_1.cpp）完成如下功能：

（1）初始化顺序表L

（2）依次采用尾插法插入a,b,c,d,e元素

（3）输出顺序表L

（4）输出顺序表L的长度

（5）判断顺序表L是否为空

（6）输出顺序表L的第3个元素

（7）输出元素a的位置

（8）在第4个元素位置上插入f元素

（9）输出顺序表L

（10）删除L的第3个元素

（11）输出顺序表L

（12）释放顺序表L

注意：在exp2_1.cpp中用以下语句加入头文件：

# include “SqList.h”

我作为初学者，有很多错误与不足，望大家能够指出，我会很乐意接受大家的建议，谢谢大家！！！

头文件：

/*文件名：SqList.h*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//定义函数返回的类型
typedef int Status;
#define LIST_INIT_SIZE 100
//线性表存储空间的初始分配量
#define LISTINCREMENT 10
//线性表存储空间的分配增量
typedef char ElemType;
//定义数据元素的类型为字符型
//定义顺序表的存储结构
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList
&L)
//构造一个空的顺序表L
{
L.elem =(ElemType*)malloc(LIST_INIT_SIZE * sizeof (ElemType));
if(!L.elem)
exit (OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
void DestroyList(SqList &L)
//销毁顺序表L
{
if (!L.elem)
{
return ERROR;
//表不存在
}
free(L.elem);
//释放内存
}
Status
ListEmpty(SqList
&L)
//判断顺序表是否为空，为空返回ture，否则返回false
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if(L.length==0)
return TRUE;
else
return FALSE;
}
int ListLength(SqList &L)
//返回线性表L的长度
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i;
while (i<L.length)
{
i++;
}
return L.length;
}
void DispList (SqList &L)
//打印单链表中的元素
{
int i;
if (ListEmpty(L))
printf("数组为空");
for(i=0;i<10;i++)
printf("%c",L.elem[i]);
printf("%cn");
return;
}
Status GetElem(SqList L, int i, char &e)
//从顺序表L中查找第i个元素，由参数e返回其元素的值
{
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length - 1)
{
return ERROR;
//i值不合法
}
char * q = L.elem ;
e = *(q + i -1);
//把第i个元素给e
return OK;
}
int LocateElem(SqList L, int e)
//在顺序表L中查找元素e的位置，不存在则返回0
{
if (!L.elem)
{
return ERROR;
//表不存在
}
int i = 1;
char * p = L.elem ;
while (i < L.length && *p++ != e ) {//查找与e相等的值的位置
++i;
}
if (i <= L.length )
{
return i;
}
return 0;
}
Status ListInsert(SqList &L, int i, char e)
//在顺序表L中第i个位置前插入元素e
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i > L.length + 1 || i < 1)
{
//i值不合法
return ERROR;
}
if (L.length >= L.listsize)
{
char * newbase;
//空间不足，重新分配
newbase = (char *)realloc(L.elem,sizeof(char) * ( L.listsize+LISTINCREMENT));
L.elem = newbase;
if (!L.elem)
{
return OVERFLOW;
//分配失败
}
L.elem=newbase;
L.listsize += LISTINCREMENT;
//新空间容量
}
for(k=L.length-1;k>=i-1;k--)
L.elem [k+1]=L.elem[k];
L.elem[i-1]=e;
L.length++;
return OK;
}//ListInsert
Status ListDelete(SqList &L, int i, char &e)
//在顺序表L中删除第i个值并用e返回这个值
{
int k;
if (!L.elem)
{
return ERROR;
//表不存在
}
if (i < 1 || i > L.length )
{
return ERROR;
//i值不合法
}
e=L.elem[i-1];
for (k=i;k<L.length;k++)
L.elem[k-1]=L.elem[k];
--L.length;
//L的长度减1
return OK;
}

源程序：

#include "SqList.h"
int main ()
{
SqList(L);
ElemType e;
printf("初始化顺序表Ln");
InitList(L);
printf("依次采用尾插法插入a,b,c,d,e元素n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("输出顺序表L:");
DispList(L);
printf("顺序表长度L=%dn",L.length);
printf("顺序表L为%sn",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,e);
printf("顺序表的第3个元素=%cn",e);
printf ("元素a的位置=%dn",LocateElem(L,'a'));
printf("在第4个元素位置上插入f元素n");
ListInsert(L,4,'f');
printf("输出顺序表L:");
DispList(L);
printf("删除L的第3个元素n");
ListDelete(L,3,e);
printf("输出顺序表L:");
DispList(L);
printf("释放顺序表Ln");
free(L.elem);
}

用vc6.0运行后的结果：