线性表之一：顺序表

文章目录

• 前言
• 一、顺序表的概念
• 二、顺序表的实现
• • 1.静态顺序表
  • 2.动态顺序表
  • • 有关增容的代码
• 三、有关动态顺序表的函数
• 总结-顺序表问题与思考

前言

线性表（linearlist），是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

一、顺序表的概念

1. 顺序表是一种线性表的存储结构，它采用一段连续的存储空间来存储数据元素，顺序表的特点是元素在物理上是连续存储，在逻辑上不一定是连续存储。一般情况下采用数组存储。
2. 它可以通过下标来访问每个元素，因此支持随机访问。

顺序表和数组的区别顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

二、顺序表的实现

顺序表的实现方式有两种：静态顺序表和动态顺序表

1.静态顺序表

概念：使用定长数组存储元素

//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList{
SLDataType a[N],//定长数组
int size;//有效数据个数
}SL:

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

为了改善这种缺陷，我们引入了动态顺序表的概念。

2.动态顺序表

动态顺序表按需申请
typedef struct SeqList{
SLDataType* a;
int size      //有效数据个数
intcapacity;  //空间容量
}SL;

动态顺序表的优点：可增容

有关增容的代码

 //检查是否为空，如果是，则增容
void SeqLCheak(SeqList* ps)    
{
	if (ps->size == ps->Capacity)		
	{
		int new_capacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;	
		//如果size等于capacity并且不空，则说明顺序表已满
		//一般采用扩大二倍的方式来进行扩容，这样比较适合
		SLDateType* temp = (SLDateType*)realloc(ps->arr, sizeof(SLDateType) * new_capacity);
		if (temp == NULL)
		{
			perror("fail!");
		}
		ps->arr = temp;
		ps->Capacity = new_capacity;
	}
	return 0;
}

三、有关动态顺序表的函数

动态顺序表的实现可以有多种方式，增删查改等等都有所涉及，可以试着编写一下。

// 初始化
void SeqListInit(SeqList* ps);
//销毁
void SeqListDestroy(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
//头删
void SeqListPopFront(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

总结-顺序表问题与思考

1. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
2. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200,
   我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

如何解决以上问题呢？那就是接下来要讲到的单链表了。