写在前面：本文章来自于在学习过程中的总结，供大家参考。因水平有限，博客中难免会有不足，恳请大佬们不吝赐教！

线性表的定义

线性表：由零个或多个数据元素组成的有限序列。简单的说，就像排队一样，具有先一样性质的结构。

关键：

• 首先它是一个序列，也就是说元素之间是有个先来后到的。
• 若元素存在多个，则第一个无前驱，而最后一个元素无后继，其他元素有且只有一个前驱和后继。
• 另外，线性表强调是有限的，事实上无论计算机发展到多强大，它所处理的元素都是有限的。

数据元素的个数称为线性表的长度，当线性表长度为零时，称为空表。

表起始位置称表头，表结束位置称表尾。

线性表的顺序存储结构

线性表有两种物理存储结构 ：顺序存储结构和链式存储结构。

线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。

物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;	//线性表当前长度
}SqList;

这里封装了一个结构，事实上就是对数组进行封装，增加了当前长度的变量罢了。

顺序存储结构的封装需要三个属性：

• 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
• 线性表的最大存储容量：数组的长度MAXSIZE
• 线性表的当前长度：length

注意：数组的长度与线性表的当前长度要区分一下：数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的。

线性表顺序存储结构的优缺点

线性表的顺序存储结构，在存、读数据时，不管是在哪个位置时，时间复杂度都是O(1)。而在插入或删除时，时间复杂度都是O(n)。

这就说明，它比较适合元素个数比较稳定，不经常插入和删除元素，而更多的操作是存取数据的应用。

优点：

• 无须为表示元素之间的逻辑关系而增加额外的存储空间。
• 可以快速存取表中任意位置的元素。
  缺点：
• 插入和删除操作需要移动大量元素。
• 当线性表长度变化较大时，难以确定存储空间的容量。
• 容易遭成存储空间的“碎片”。

为什么当插入和删除时，就要移动大量的元素？因为在相邻两元素的存储位置也具有邻居关系，它们在内存中的位置是紧挨着的，中间没有间隙，当然就无法快速插入和删除。

线性表的基本操作

顺序存储结构数据的插入和删除

数据的插入：

//数据元素的插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	int k;
	if (L->length == MAXSIZE)	//顺序线性表已满
		return ERROR;
	if (i<1 || i>L->length - 1)	//当i不在范围内时
		return ERROR;
	if (i <= L->length)	//若插入数据位置不在表尾
	{
		for (k = L->length - 1; k >= i - 1; k--)
			L->data[k + 1] = L->data[k];
	}
	L->data[i - 1] = e;
	L->length++;
	return OK;
}

数据的删除：

//数据元素的删除
Status ListDelete(SqList* L, int i)
{
	int k;
	if (L->length == 0)	//线性表为空
		return ERROR;
	if (i<1 || i>L->length)	//当i不在范围时
		return ERROR;
	if (i < L->length)	//如果删除不是最后位置
	{
		for (k = i; k < L->length; k++)	//将删除位置后继元素前移
			L->data[k - 1] = L->data[k];
	}
	L->length--;
	return OK;
}

完整代码：

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];
	int length;
}SqList;

#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
typedef int Status;

//数据元素的获取
Status GetElem(SqList L, int i, ElemType* e)
{
	if (L.length == 0 || i<1 || i>L.length)
		return ERROR;
	*e = L.data[i - 1];
	return OK;
}

//数据元素的插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	int k;
	if (L->length == MAXSIZE)	//顺序线性表已满
		return ERROR;
	if (i<1 || i>L->length - 1)	//当i不在范围内时
		return ERROR;
	if (i <= L->length)	//若插入数据位置不在表尾
	{
		for (k = L->length - 1; k >= i - 1; k--)
			L->data[k + 1] = L->data[k];
	}
	L->data[i - 1] = e;
	L->length++;
	return OK;
}

//数据元素的删除
Status ListDelete(SqList* L, int i)
{
	int k;
	if (L->length == 0)	//线性表为空
		return ERROR;
	if (i<1 || i>L->length)	//当i不在范围时
		return ERROR;
	if (i < L->length)	//如果删除不是最后位置
	{
		for (k = i; k < L->length; k++)	//将删除位置后继元素前移
			L->data[k - 1] = L->data[k];
	}
	L->length--;
	return OK;
}
int main()
{
	SqList *L;
	int i = 0;

	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0;

	for (i = 0; i < 3; i++)
	{
		scanf("%d", &L->data[i]);
		L->length++;
	}
	//ListInsert(L, 1, 4);
	ListDelete(L, 1);
	printf("%d\n", L->length);
	
	for (i = 0; i < L->length; i++)
	{
		printf("%d\n", L->data[i]);
	}
	return 0;
}

由于水平有限，博客难免会有不足，恳请大佬们不吝赐教！

在上一篇博客中我们只是简单得了解了线性表的一些基本的概念。那么这一篇博客我们就来说说线性表的两种物理结构中的第一种—顺序存储结构。
一、顺序存储定义
线性表的顺序存储结构指的是用一段地址连续的存储单元依次线性表的数据元素。顺序存储的示意图如下：

二、线性表的地址计算方法
由于c语言的数组的下标是从0开始的，所以线性表第i个元素存储在第i-1的位置。如下图所示：

由于每个数据元素，不管它是整型还是字符型。都占有一定的存储单元空间。假设占用的是c个单位的存储单元。那么线性表中第i+1个元素的存储位置和第i个元素的存储位置满足以下条件。

LOC(a(i+1)) = LOC(ai) + c

则可以推断出第i个元素ai的位置由a1计算得出：

LOC(ai) = LOC(a1) + (i-1)*c

三、顺序存储结构的插入和删除等操作
1、获取元素（GetElem）:既将线性表的第i个元素的下标返回。

int  GetElem (SqList L,int i,ElemType *e)
{
   if (L->length==0 || i<l || i>L->length)
   return 0;
   else
   return *e=L->data[i-1];

2、插入操作（ListInsert）：
（1）如果插入位置不合理，返回0;
（2）如果线性表长度大于等于数组长度，返回0；
（3）从最后一个元素开始向前遍 历到第i个位置，分别将它们都向后移动一个位置;
（4）将要插入元素填入位置i处;
（5）表长加1。
代码实现：

bool ListInsert ( SqList *L, int i, ElemType e )
{
  int k;
  if (L->length==MAXSIZE)/*顺序线性表已经满*/
  return false;
  if(i<1 || i>L->length+1) /*当i不在范围内时*/
  return false;
  if (i<=L->length) /*若插入数据位置不在表尾*/
  {
     for (k=L->length-1;k>=i-1;k--)/*将要插入位置后数据元素向后移动一位*/
     L->data[k+1]-L->data[k];
  }
   L->data[i-1]=e;/*将新元素插入*/
   L-> length++;
   return true;
}

3、删除操作（ListDelete）
(1)如果删除位置不合理，return 0;
(2)取出删除元素;
(3)从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置;
(4)表长减1。
代码实现：

bool ListDelete (SqList *L,int i, ElemType *e)
{
  int k;
  if (L->length==0 )//线性表为空
  return false;
  if (i<1 || i>L->length)//删除位置不对
  return false;
  *e-L->data(i-1];
  if ( i<L->length )//如果删除不是最后位置
  {
   for (k=i;k<L->length;k++) //将删除位置后继元素后移
   L->data[k-1]=L->data [k];
  }
   L-> length--;
   return true;
}

四、顺序存储结构的优缺点
优点：1、不用为表中的元素之间的逻辑关系而增加额外的存储空间。
2、可以快速存取表中任意位置的元素。
缺点：1、删除和插入需要移动大量的元素。
2、当长度变化较大时无法确定存储空间的容量。

顺序存储定义

说这么多的线性表，我们来看看线性表的两种物理结构的第一种——顺序存储结构。
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表（a1,a2……,an)的顺序存储示意图如下:

顺序存储方式

线性表的顺序存储结构，说白了，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言(其他语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是这个最大存储容量。但在实际使用中，我们并不是每个时刻都使用这最大的存储容量，我们希望能够更加高效的使用空间，因此我们使用malloc申请空间，realloc来调整空间大小，做到此点。可看空间分配与释放来具体了解函数作用。

来看线性表的顺序存储的结构代码。

#define INITSIZE 20  //初始化的大小
#define EXPANDTIMES 2 //每次的扩容倍数
typedef int ELemType; //用int来模拟数据项类型
typedef struct
{
	ElemType* data; //存储数据的初始位置
	int capacity; //容量（总共的:未使用的+已经使用的）
	int size;//已经使用的
}Sqlist;

关于数组和指针我在这就不多讲了，想要了解的可以去看我的数组与指针。

Init_List(*L)

bool Init_List(Sqlist *L)
{
	assert(L != NULL);//对输入也检测一下，使用空指针可能会导致程序奔溃，具体原因自己去搜，后续不解释
	L->data = (int*)malloc(sizeof(ELemType) * INITSIZE);//申请一段堆空间来存储元素
	//assert(L->data != NULL);//因为malloc可能会申请失败，判断一下
	if (L->data == NULL)
	{
		return false;
	}
	else
	{
		L->capacity = INITSIZE;//初始容量通过宏定义设定
		L->size = 0;//初始使用的大小当然是0喽
		return true;
	}
}

为了能够拥有动态空间大小，我们在这使用了堆空间作为存储空间，不用了记得free

Change_List(*L, flag)

bool Change_List(Sqlist* L,int flag)//改变容量
{
	assert(L != NULL);
	ELemType* temp = L->data;
	int newsize = flag == -1 ? L->capacity / EXPANDTIMES : L->capacity * EXPANDTIMES;//简单的判断，
	temp = (ELemType*)realloc(temp,newsize * sizeof(ELemType));//扩容也可能会失败，这样做是防止旧数据丢失
	if (temp == NULL)
	{
		return false;
	}
	else
	{
		L->data = temp;//将申请到的空间交给data
		L->capacity = newsize;//更改容量
		return true;
	}
}

Is_Empty(*L)

bool Is_Empty(Sqlist* L)
{
	assert(L != NULL);
	return L->size == 0;//只用检测一下使用的大小为不为0，就ok
}

Clear_List(*L)

bool Clear_List(Sqlist* L)
{
	assert(L != NULL);
	free(L->data);//因为空间是malloc来的，不用就free掉
	Init_List(L);//最简单的做法，重新给他初始化下，就消除了数据，也缩小了容量
	//L->size = 0;//最最最简单的方法因为数据是否有效，我们说了算，容量没变
	return true;
}

GetElem_List(*L,i)

ELemType GetElem_List(Sqlist* L, int i)
{
	assert(L != NULL && i < L->size && i >= 0);//保证改下标必须为有效下标，后续不解释
	return L->data[i];
}

LocateElem_List(*L,e)

int LocateElem_List(Sqlist* L, ELemType e)
{
	assert(L != NULL);
	int pos = -1;
	for (int i = 0; i < L->size; i++)//遍历是必须的
	{
		if (e == L->data[i])
		{
			pos = i;
			break;
		}
	}
	return pos;
}

Insert_List(*L,i,e)

bool Insert_List(Sqlist* L,int i,ELemType e)
{
	assert(L != NULL && i >= 0 && i <= L->size);//为满足线性表的定义，应对下标进行检测
	if (L->capacity == L->size)//容量不足是需要进行扩容
	{
		if (!Change_List(L,1)) //扩容成功才能继续放数据
		{
			return false;
		}
	}
	int pos = L->size;
	while (L->size != i)//向后挪动一位
	{
		L->data[pos] = L->data[pos - 1];
		pos--;
	}
	L->data[pos] = e;
	L->size++;
	return true;
}

尾插的话，i=L->size;头插i=0;

Delect_List(*L, i)

与插入反向操作

bool Delect_List(Sqlist* L, int i)//
{
	assert(L != NULL && i < L->size && i >= 0);
	while (i != L->size-1)//向前挪动一位
	{
		L->data[i] = L->data[i+1];
		i++;
	}
	L->size--;
	if (L->capacity > INITSIZE && L->size < L->capacity / EXPANDTIMES)
		Change_List(L, -1);
	return true;
}

Length_List(*L)

int Length_List(Sqlist* L)
{
	assert(L != NULL);
	return L->size;//我们有专门的数据项来记录长度，直接返回就行
}

Destory_List(*L)

因为clear只会清除数据(存储空间有一部分清不掉）,我们要专门free掉

bool Destroy_List(Sqlist* L)
{
	L->capacity = 0;
	L->size = 0;
	free(L->data);//Destroy以后就彻底不能用了，因为0乘以任何数还是0
	L->data = NULL;
	return true;
}

线性表顺序存储结构的优缺点

优点

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任位置的元素。（顺序读取快，O(1));

缺点

插入和删除操作需要移动大量元素 O(n)
当线性表长度变化较大时,难以确定存储空间的容量 (用数组就是这样，所以我们有扩容/缩容）
造成存储空间的“碎片”（绝大部分时间capacity > size，有一部分空间闲置）