2.顺序表（C语言）

数据结构（顺序表）

一、线性表
二、顺序表
- 1. 概念及结构
- - 1.1 静态顺序表
  - 1.2 动态顺序表
- 2. 数据操作
- - 2.1 功能接口
  - 2.2 接口实现
  - - （1）初始化
    - （2）销毁
    - （3）检查容量
    - （4）尾插
    - （5）头插
    - （6）尾删
    - （7）头删
    - （8）查找
    - （9）插入
    - （10）删除
    - （11）修改
- 3. 顺序表的问题

一、线性表

线性表（linear list）：具有相同特征的数据元素的有限序列。

线性表在逻辑结构上时线性结构、是一条连续的线，但是物理结构上不一定是连续的。

常见的线性表：顺序表、链表、栈、队列、字符串等

二、顺序表 1. 概念及结构

顺序表（sequence list）：用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般使用数组存储。在数组上完成增删查改

顺序表一般分为静态顺序表和动态顺序表

1.1 静态顺序表

使用定长数组存储元素，容量不够时提醒用户不能存储

#define NUMBER 1000

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType data[NUMBER];	 //定长数组
    size_t size;				//有效数据个数
} SeqList;

1.2 动态顺序表

使用动态开辟数组的存储，容量不够时可以增容

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType *data;	//指向动态开辟的数组
    size_t size;		//有效数据个数
    size_t capacity;	//容量空间的大小
}

2. 数据操作

现实中基本使用动态顺序表，所以我们对动态顺序表进行操作

2.1 功能接口

//初始化 Init
void SeqListInit(SeqList* psl);

//检查容量 Check Capacity
void CheckCapacity(SeqList* psl);

//尾插 Push Back
void SeqListPushBack(SeqList* psl, SLDataType x);

//尾删 Pop Back
void SeqListPopBack(SeqList* psl);

//头插 Push Front
void SeqListPushFront(SeqList* psl, SLDataType x);

//头删 Pop Front
void SeqListPopFront(SeqList* psl);

//查找 Find
int SeqListFind(SeqList* psl, SLDataType x);

//插入 Insert
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);

//删除 Erase
void SeqListErase(SeqList* psl, size_t pos);

//修改 Modify
extern void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

//销毁 Destory
extern void SeqListDestory(SeqList* psl);

//打印 Print
void SeqListPrint(const SeqList* const psl);

2.2 接口实现（1）初始化

初始化SeqListInit
- 初始化时可以不分配空间，在插入时检查并分配空间，不够了就重新申请

void SeqListInit(SeqList* psl)
{
	assert(psl != NULL);
    
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

（2）销毁

销毁SeqListDestory
- 顺序表销毁的是data申请的空间，断言时只需断言顺序表是否存在即可，NULL被free时不报错
- 释放完空间时，记得将data置为NULL，容量和有效个数置为0

void SeqListDestory(SeqList* psl)
{
	assert(psl != NULL);

	free(psl->data);
	psl->data = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

（3）检查容量

检查容量CheckCapacity
1. 在插入操作之前（头插、尾插、下标插入），都要进行容量检查，所以单独成为一个函数
2. 检查顺序表是否满了，判断有效数据个数和最大容量是否相等
3. 判断有效数据个数和最大容量相等时，还要判断空间是为0(未使用)时给空间一个初始值，不为0时让容量按指定值增长(这里是*2了)
4. 使用realloc函数时，要注意返回值的判断和赋值

void CheckCapacity(SeqList* psl)
{
	assert(psl != NULL);

	if (psl->size == psl->capacity)
	{
        //初始值判断，从4开始，不够就*2
		int newCapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
        
        //申请空间
		SLDataType* temp = (SLDataType*)realloc(psl->data, newCapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc failn");
			exit(-1);
		}
        
        //将重新申请的空间赋值给data，并改变最大容量
		psl->data = temp;
		psl->capacity = newCapacity;
	}
}

（4）尾插

尾插法插入数据SeqListPushBack
1. 插入之前检查容量
2. 插入时直接将size位置的data赋值就行，size加一

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl != NULL);

	CheckCapacity(psl);

	psl->data[psl->size] = x;
	psl->size++;
}

（5）头插

头插法插入数据SeqListPushFront
1. 插入之前检查容量
2. 插入前要移动数据，从后面开始移动
3. 插入时将0位置的data赋值，size加一

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl != NULL);

	CheckCapacity(psl);

	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->data[end + 1] = psl->data[end];
		--end;
	}

	psl->data[0] = x;
	psl->size++;
}

（6）尾删

删除结尾数据（尾删）SeqListPopBack
1. 删除之前要先判断size是否已经为0，若为0，则终止程序或不做处理（下面是不做处理的，终止程序可以用断言）
2. 删除数据直接将size减一即可

void SeqListPopBack(SeqList* psl)
{
	assert(psl != NULL);
    
	//不做处理，直接return
	if (psl->size == 0)
	{
		return;
	}
    
    //assert(psl->size != 0);	断言处理，终止程序

	psl->size--;
}

（7）头删

删除开头数据（头删）SeqListPopFront
1. 删除之前要先判断size是否已经为0，若为0，则终止程序或不做处理（下面是不做处理的，终止程序可以用断言）
2. 从下标为1的数据从前往后向前移动一位即可，再size减一

void SeqListPopFront(SeqList* psl)
{
	assert(psl != NULL);

	if (psl->size == 0)
	{
		return;
	}

	int begin = 0;
	while (begin < psl->size-1)
	{
		psl->data[begin] = psl->data[begin + 1];
		++begin;
	}
    
	psl->size--;
}

（8）查找

查找SeqListFind
1. 顺序查找指定值，返回下标，若是没有就返回-1
2. 不建议使用二分查找，排序会影响效率

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl != NULL);
    
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->data[i] == x)
		{
			return i;
		}
	}
    
	return -1;
}

（9）插入

插入数据SeqListInsert
1. 插入数据的下标位置一般声明为无符号整型
2. 从后往前移动数字，将指定位置空出来，插入指定数据
3. 检查下标不用检查负数，使用的是无符号整型，下标可以是size，插入到末尾

错误的移动方式：当从size-1开始移动时，每次使data[end+1] = data[end]来完成移动，会出现错误

如果pos为0，则end>=0时执行循环体，end=0时执行循环体end--，end为无符号整型值，减一后为整型最大值，无限循环
若是将end声明为int型，end与无符号pos比较依然按照无符号来，所以是死循环

size_t end = psl->size - 1;	//end从size-1开始移动
while (end >= pos)		//end>=pos执行循环体
{
	psl->data[end + 1] = psl->data[end];
	--end;
}

正确的移动方式：使移动从size开始，每次使data[end] = data[end-1]来完成移动，就不会出现错误

此时pos为0时，则end>0时执行循环体，end--后为0，循环停止，不会陷入死循环

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl != NULL);
	assert(pos <= (size_t)psl->size);	//检查pos，可以等于size，就是尾插

	CheckCapacity(psl);

	size_t end = psl->size;		//从size开始，end>pos时执行，pos为0时就不会出现死循环了
	while (end > pos)
	{
		psl->data[end] = psl->data[end-1];
		--end;
	}

	psl->data[pos] = x;
	psl->size++;
}

注意：头插法和尾插法可以调用插入函数实现
1. 头插法就是下标为0的插入
2. 尾插法就是下标为size的插入，尾插要传参size，所以要检查psl

//头插法
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	SeqListInsert(psl, 0, x);
}

//尾插法
void SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(psl != NULL);
	SeqListInsert(psl, psl->size, x);
}

（10）删除

删除数据SeqListErase
1. 从指定下标开始，从前往后将数据向前移动一格
2. 下标不能为size，必须是有效的数据

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl != NULL);
	assert(pos < (size_t)psl->size);

	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->data[begin] = psl->data[begin + 1];
		begin++;
	}

	psl->size--;
}

注意：头删和尾删可以调用删除函数实现
1. 头删就是下标为0的删除
2. 尾删就是下标为size-1的删除，尾删要传参size，所以要检查psl

//头删
void SeqListPopFront(SeqList* psl)
{
	SeqListErase(psl, 0);
}

//尾删
void SeqListPopBack(SeqList* psl)
{
    assert(psl != NULL);
	SeqListErase(psl, psl->size-1);
}

（11）修改

修改数据SeqListModify
- 修改就直接将值赋值给该位置即可

//修改 Modify
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl != NULL);
	assert(pos < (size_t)psl->size);

	psl->data[pos] = x;
}

3. 顺序表的问题

中间、头部、的插入时间复杂度为 O ( n ) O(n) O(n)，效率低
增容需要申请空间，拷贝数据，释放空间。消耗很大
若是数据少，申请的空间多，造成浪费

关于删除时为什么不缩容的相关疑问：

realloc函数可以实现缩容，所以不缩容与函数无关
缩容造成的时间浪费非常大，若是在扩容边界上反复插入、删除，就会导致空间反复扩容缩容，严重影响效率
不缩容是以空间换取时间，以现在的科技水平，空间成本低，空间上的要求并没有时间上的要求高

2.顺序表（C语言）

C/C++/C#相关栏目本月热门文章