3、线性表的顺序存储结构（顺序表）

线性表的顺序存储结构简称为顺序表。线性表的顺序存储结构是把线性表中的元素中的元素按照其逻辑顺序依次存储到计算机存储器中指定位置开始的一块连续的存储空间中，它直接将线性表的逻辑结构映射到存储结构上，既方便理解，又容易实现。
在C/C++语言中，借助数组类型来实现顺序表，也就是说，用数组存放线性表的元素及其逻辑关系，数组的基本类型就是线性表中元素的类型，数组的大小要大于等于线性表的长度，否则该数组不能存放对应线性表的所有元素。所以当线性表长度小于数组大小时，该数组有一部分空闲空间。
顺序表的实现：
1.设置顺序表的长度

#include<stdio.h>
#include<stdlib.h>
//定义线性表最长长度
#define MaxSize 50

2.声明线性表的顺序存储类型

typedef int ElementType;
typedef struct SquentialListStruct
{
	ElementType data[MaxSize];
	int length;
} SqList;

3.初始化顺序表

void InitList(SqList * &L)
{
	L = (SqList*)malloc(sizeof(SqList));				//分配存放顺序表的空间
	L->length = 0;										//将顺序表长度设置为0
}

4.创建顺序表

void CreateList(SqList * &L, ElementType a[], int n)	//由a中的第n个元素建立顺序表
{
	int i = 0, k = 0;									//k表示L中的元素的个数，初始值为0
	L = (SqList*)malloc(sizeof(SqList));				//分配存放顺序表的空间
	while (i<n)											//i扫描数组a
	{
		L->data[i] = a[i];								//将元素a[i]存放到L中
		k++;
		i++;
	}
	L->length = k;										//设置L的长度为k
}

5.销毁顺序表

void destoryList(SqList * &L)
{
	free(L);											//释放L所指的顺序表空间
}

6.判断顺序表是否为空

bool ListEmpty(SqList *L)
{
	return (L->length ==0);
}

7.输出顺序表

void DispList(SqList *L)
{
	for (int i=0;i<L->length;i++)						//扫描顺序表输出各元素的值
	{
		printf("%d ",L->data[i]);
	}
	printf("\n");
}

8.求顺序表的长度

int ListLength(SqList *L)
{
	return (L->length);
}

9.获取顺序表中某个元素值

bool GetElem(SqList *L, int i, ElementType &e)
{
	if (i<1 || i>L->length)
		return false;									//参数i错误时返回false
	e = L->data[i - 1];									//取出元素
	return true;										//成功找到元素时返回true
}

10.按元素值查找

int LocateElem(SqList *L,ElementType e)
{
	int i = 0;
	while (i < L->length && L->data[i] != e)
		i++;											//查找元素e
	if (i >= L->length)
		return 0;										//未找到时返回0
	else
		return i + 1;									//找到后返回其逻辑序号
}

11.插入数据元素

bool ListInsert(SqList * &L,int i,ElementType e)
{
	int j;
	if (i<1 || i>L->length + 1)
		return false;								//参数i错误时返回false
	i--;											//将顺序表逻辑序号转化为物理序号
	for (j = L->length; j > i; j--)
		L->data[j] = L->data[j - 1];				//将data[i]及其后面的元素向后移动一个位置
	L->data[i] = e;									//插入元素e
	L->length++;									//顺序表长度+1
	return true;									//成功插入返回true

}

12.删除数据元素

bool ListDelete(SqList * &L, int i, ElementType &e)
{
	int j;
	if (i<1 || i>L->length + 1)
		return false;								//参数i错误时返回false
	i--;											//将顺序表逻辑序号转化为物理序号
	e = L->data[i];
	for (j = i; j < L->length - 1; j++)
		L->data[j] = L->data[j + 1];				//将data[i]及其后面的元素向前移动一个位置
	L->length--;									//顺序表长度-1
	return true;									//成功删除返回true
}

13.主函数

int main()
{
	SqList *Li;
	ElementType e1,e2;
	ElementType dat[] = {1,4,6,8,34,78,342};
	InitList(Li);
	CreateList(Li, dat, 7);
	printf("顺序表元素：");
	DispList(Li);
	printf("顺序表长度：%d\n", ListLength(Li));
	GetElem(Li, 2, e1);
	printf("顺序表第 2 个元素为：%d\n", e1);
	printf("顺序表是否为空：%s\n", ListEmpty(Li) ? "true" : "false");
	printf("顺序表元素 6 在第 %d 位\n", LocateElem(Li,6));
	ListInsert(Li,2,86);
	printf("在第 2 位插入元素 86 后顺序表：");
	DispList(Li);
	ListDelete(Li, 8, e2);
	printf("删除顺序表第 8 位后顺序表：");
	DispList(Li);
	getchar();
	return 0;
}

程序运行结果：

顺序表元素：1 4 6 8 34 78 342
顺序表长度：7
顺序表第2个元素为：4
顺序表是否为空：false
顺序表元素 6 在第 3 位
在第2位插入元素 86 后顺序表：1 86 4 6 8 34 78 342
删除顺序表第8位后顺序表：1 86 4 6 8 34 78 

下一篇：4、线性表的链式存储结构（单链表）