数据结构线性顺序表的C语言实现
说明：线性表是一种最简单的线性结构，也是最基本的一种线性结构，所以他不仅是学习中的重点，也是应用开发非常常用的一种数据结构。它的主要操作是数据元素的插入，删除，以及排序等。接下来，本篇文章将对线性顺序表的基本操作和运用进行详细的说明（包含在源代码的注释中），并给予可运行的程序源代码。
线性顺序表运用时和数组十分相似，不同之处是顺序表是一种构造类型的数据结构，而数组则是一种基本的数据类型，所以在顺序表的各种操作中与对数组的操作十分相似，将两者作对比着有助于对顺序表的理解与学习。
程序分析：由于抱着是程序执行起来时操作尽量简单化，使人一看就能明白，所以本程序是用了不少的提示性语句。主函数的结构是while循环和switch函数相结合的方法，使每种能够用到的基本操作尽量明白的显示在主显示函数中，这样能使每种基本操作的作用效果更加突出明了。这样不仅能使程序的模块化尽量明显，也可以让源代码的可读性增强。而且程序运用了CLS清屏函数，可以使每一次操作的输入输出结果更加清晰。
源代码：
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 10 //线性顺序表初始动态分配内存大小
#define LISTINCREMENT 2 //线性表扩容一次性增量
#define OK 1
#define ERROW -1
#define OVERFLOW -2
typedef int ElemType; //线性表的数据类型
typedef int Status; // 状态数据类型
/***定义线性顺序表数据结构***/
typedef struct
{
ElemType *elem; //定义线性表内数据元素的数据类型
int Length; //表当前长度
int listsize; //表当前空间容量大小
}Sqlist; //表名
/***初始化一个空表，即创建一个空表***/
Status InitList(Sqlist &L)
{
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//内存动态分配
if(!L.elem)//对内存分配的结果判断
exit(OVERFLOW);
L.Length=0; //对表长初始化归0
return OK;
}
/***清空表***/
void Clearlist(Sqlist &L)
{
if(L.Length!=0)
L.Length=0; //由于顺序表的用得是与数组一样的内存空间，所以标的清空
//只要将表长归零即可，由此可见，表长是线性表非常重要的部分
}
/***取表长***/
int GetLength(Sqlist L)
{
if(L.Length!=0)
return L.Length ;
}
/***判断表空否***/
int IsEmpty(Sqlist L)
{
if(L.Length==0)
return 1;
else
return 0;
}
/***销毁表***/
void DestoryList(Sqlist &L)
{
if(L.elem!=0)
free(L.elem); //将顺序表所需空间释放，不同于清空
}
/***取定位元素值***/
Status GetElem(Sqlist L,int i,ElemType &e)
{
if(i<1||i>L.Length)
return ERROW;
e=L.elem[i-1];
return OK;
}
/***定位元素位置***/
Status LocateElem(Sqlist L,int &i,ElemType e)
{
for(i=1;i-1<L.Length;i++)
if(L.elem[i-1]==e)
return OK;
return ERROW;
}
/***创建表***/
Status ScanList(Sqlist &L)
{
int i;
InitList(L);
printf("请输入元素个数：\n");
scanf("%d",&L.Length);
printf("\n请输入您要输入的元素\n");
for(i=0;i<L.Length;i++)
{
scanf("%d",&L.elem[i]);
}
printf("顺序表已创建成功，打印表请选择功能 *3\n");
return OK;
}
/***输出表中元素***/
void PrintList(Sqlist L)
{
int i;
printf("表中元素为：\n");
for(i=0;i<L.Length;i++)
printf("%d ",L.elem[i]);
printf("\n\n顺序表输出完毕！\n");
}
/***定位插入元素***/
Status ListInsert(Sqlist &L,int i,ElemType e)
{
int j;
if(i<1||i>L.Length+1)
return ERROW;
if(L.Length==LIST_INIT_SIZE)
L.elem=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));
if(L.elem==0)
exit(OVERFLOW);
else
L.listsize+=2;
for(j=L.Length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];
L.elem[i-1]=e;
L.Length++;
return OK;
}
/***定位删除元素***/
Status ListDelete_1(Sqlist &L,int i)
{
if(i<1||i>L.Length)
return ERROW;
for(;i<L.Length;i++)
L.elem[i-1]=L.elem[i];
L.Length--;
return OK;
}
/***定值删除元素***/
Status ListDelete_2(Sqlist &L,ElemType e)
{
int i,j;
j=LocateElem(L,i,e);
if(j==-1)
printf("输入元素在表中不存在！\n");
return ERROW;
ListDelete_1(L,i);
return OK;
}
/***对表中元素进行非递减有序排序***/
void maopao(Sqlist &L) //冒泡排序
{
int n,i,j,t;
n=GetLength(L);
for(j=1;j<=n-1;j++)
for(i=0;i<=n-j-i;i++)
if(L.elem[i]>L.elem[i+1])
{
t=L.elem[i];
L.elem[i]=L.elem[i+1];
L.elem[i+1]=t;
}
}
/***主提示输出函数***/
void printlin()
{
printf("\n");
printf("\t\t\t线性顺序表基本操作学习系统\n");
printf("\t\t\t ***主菜单***\n\n");
printf("\t\t\t *1 创建一个顺序表\n");
printf("\t\t\t *2 定位输出一个数据元素\n");
printf("\t\t\t *3 输出顺序表中所有元素\n");
printf("\t\t\t *4 定位插入一个数据元素\n");
printf("\t\t\t *5 定位删除一个数据元素\n");
printf("\t\t\t *6 定值删除一个数据元素\n");
printf("\t\t\t *7 清空顺序表\n");
printf("\t\t\t *8 销毁顺序表\n");
printf("\t\t\t *9 对表内数据元素进行非递减排序\n");
printf("\t\t\t *0 结束程序\n");
}
int main()
{
int i,j,k;
Sqlist L;
L.Length=0;
printf("编写此程序目的是自我学习线性表顺序表\n");
printlin();
while(1)
{
int t;
scanf("%d",&t);
if(t!=0)
if(t==1||L.Length!=0)
{
switch(t)
{
case 1: if(L.Length!=0)
{
printf("顺序表已存在，是否重新创建顺序表？\n");
printf("*1 是 *2 否\n");
scanf("%d",&i);
if(i==1)
ScanList(L);
}
else
ScanList(L);
break;
case 2: {
k=GetLength(L);
printf("请输入数据位置\n");
scanf("%d",&i);
if(i<1||i>k)
printf("输入位置错误\n");
else
{
GetElem(L,i,j);
printf("第%d个数为%d\n",i,j);
}
break;
}
case 3: PrintList(L);break;
case 4: {
printf("输入要插入的位置\n");
scanf("%d",&i);
printf("请输入要插入的数据\n");
scanf("%d",&j);
k=ListInsert(L,i,j);
if(k==-1)
printf("插入位置不合法，插入数据操作失败！\n\n");
else
printf("插入数据成功\n\n");
break;
}
case 5:{
printf("请输入要删除数据位置\n");
scanf("%d",&i);
k=ListDelete_1(L,i);
if(k==-1)
printf("输入位置错误,删除操作失败！\n\n");
else
printf("删除成功!\n\n");
break;
}
case 6:{
printf("请输入需要删除的元素：\n");
scanf("%d",&j);
k=LocateElem(L,i,j);
if(k==-1)
printf("未找到该元素，删除操作失败！\n\n");
else
{
ListDelete_1(L,i);
printf("删除成功！\n\n");
}
break;
}
case 7: {
Clearlist(L);
printf("清空完毕，返回主菜单\n\n");
break;
}
case 8: {
DestoryList(L);
printf("销毁成功，返回主菜单\n\n");
break;
}
case 9: {
maopao(L);
printf("已成功排序,返回主菜单\n\n");
break;
}
case 0: break;
default: {
printf("输入有误，可以重新选择，退出按0！\n");
}
}
}
else
printf("顺序表未创建或已清空或销毁，请先创建顺序表\n");
system("pause");
system("CLS");
printlin();
if(t==0)
break;
}
return 0;
}
程序运行效果图（部分）：
图 1
图 2
图 3
结束语：希望这篇文章能对看到它的人有所帮助！
原文：http://www.cnblogs.com/hechuxunni/p/5180589.html