数据结构之线性表的顺序存储——顺序表

线性表

线性表即零个或多个数据元素的有限序列。首先它是一个序列，其次它的元素之间是有顺序的，若存在多个元素，则首个元素无前驱，末尾元素无后继，除此之外，每个元素都有一个前驱和一个后继。用n来表示线性表元素的个数，当n=0时，即表明线性表中无元素，称为空表。

线性表又可分为动态线性表和静态线性表。静态线性表的容量大小是固定的，而动态线性表的容量可根据表中元素实现自动扩容。

线性表的顺序存储结构——顺序表，指的是用一段连续的存储单元一次存储线性表的数据元素。

顺序表的相关操作（以动态顺序表为例）：插入、删除等操作

声明部分：

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
typedef struct
{
	ElemType* data;
	int length;
	int capicity;
}SqList;
           

1.插入操作。由于动态线性表需要扩容，所以特意写一个扩容函数

//扩容

void ListAddCapicity(SqList* sl)
{
	int newcapicity;
	if (sl->capicity == 0)
	{
		newcapicity = 1;
	}
	else
	{
		newcapicity = 2 * sl->capicity;
	}
	sl->data = (ElemType*)realloc(sl->data, newcapicity*sizeof(ElemType));
	sl->capicity = newcapicity;
}
           

//初始化

void InitList(SqList* sl)
{
	sl->length = 0;		//长度为0
	sl->capicity = 0;	//容量为0
	sl->data = NULL;	//数据为空
	ListAddCapicity(sl);//调用扩容函数，自动扩容
}
           

//插入

void ListInsert(SqList* sl, int i, ElemType e)
{
	//如果要插入元素的位置小于下标或大于长度
	if (i < 0 || i > sl->length)
	{
		printf("插入位置非法！\n");
	}
	for (int j = sl->length-1; j >= i; j--)
	{
		sl->data[j + 1] = sl->data[j];
	}
	sl->data[i] = e;
	sl->length += 1;
}
           

2.删除。删除顺序表的第i个位置的元素，删除成功则返回true，否则返回false

bool DeleteList(SqList* sl, int i)
{
	bool bret = true;
	if (i < 0 || i >= sl->length)
	{
		bret = false;
	}
	else
	{
		for (int j = i; j < sl->length; j++)
		{
			sl->data[j] = sl->data[j + 1];
		}
		sl->length -= 1;
	}
	return bret;
}
           

3.判空。判断顺序表是否为空

void ListEmpty(SqList* sl)
{
	if (sl->data!=NULL)
	{
		if (0 == sl->length)
		{
			printf("此顺序表为空！\n");
		}
		else
		{
			printf("此顺序表不为空！\n");
		}
	}
	else
	{
		printf("此顺序表不存在！\n");
	}
}
           

4.计算线性表的长度。

int ListLength(SqList* sl)
{
	if (sl->data)
	{
		return sl->length;
	}
	else
	{
		return -1;
	}
}
           

5.定位。定位顺序表中某一元素的位置，若定位成功，则返回下标，否则返回-1

int LocateList(SqList* sl, ElemType e)
{
	for (int i = 0; i < sl->length; i++)
	{
		if (e == sl->data[i])
		{
			return i;
		}
	}
	return -1;
}
           

6.求后继元素。找出顺序表中某一元素的后一个元素（先得通过定位函数得到所找元素的下标）

void NextElem(SqList* sl, ElemType e)
{
	int i = LocateList(sl, e);
	if (i == -1)
	{
		printf("此顺序表中无此元素！\n");
	}
	else
	{
		if (i == sl->length-1)
		{
			printf("这是最后一个元素，没有后继！\n");
		}
		else
		{
			printf("此元素的后继是：%d\n", sl->data[i+1]);
		}
	}
}
           

7.求前驱元素。找出顺序表中某一元素的前驱元素（先得通过定位函数得到所找元素的下标）

void PriorElem(SqList* sl, ElemType e)
{
	int i = LocateList(sl, e);
	if (i == -1)
	{
		printf("此顺序表中无此元素！\n");
	}
	else
	{
		if (i == 0)
		{
			printf("这是第一个元素，没有前驱！\n");
		}
		else
		{
			printf("此元素的前驱是：%d\n", sl->data[i - 1]);
		}
	}
}
           

8.获取元素。获取所找下标的元素

ElemType GetList(SqList* sl, int i)
{
	if (i < 0 || i >= sl->length)
	{
		return -1;
	}
	else
	{
		return sl->data[i];
	}
}
           

9.销毁。销毁线性表，与清空不同

void DestoryList(SqList* sl)
{
	if (sl->data)
	{
		free(sl->data);
		printf("本线性表已被销毁！\n");
	}
}
           

10.清空。

void ClearList(SqList* sl)
{
	if (sl->data)
	{
		sl->length = 0;
	}
}
           

11.打印。

void ShowList(SqList* sl)
{
	for (int i = 0; i < sl->length; i++)
	{
		printf("%d,", sl->data[i]);
	}
	puts("\b;");
}
           

测试代码：

int main()
{
	SqList sl;
	InitList(&sl);		//先调用初始化函数
	ListInsert(&sl, 0, 1);
	ListInsert(&sl, 1, 2);
	ListInsert(&sl, 2, 3);
	ListInsert(&sl, 3, 4);
	ListInsert(&sl, 4, 5);
	ListInsert(&sl, 5, 6);
	ShowList(&sl);
	return 0;
}
           

线性表顺序存储的优点与缺点：

优点：

无须为表示元素之间的逻辑关系而增加额外的存储空间；

可以快速地存取表中任一位置的元素。

缺点：

插入和删除操作需要移动大量元素；

当线性表长度变化较大时，难以确定存储空间的容量；

造成存储空间的“碎片”。