线性表（linearlist）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。

但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。简单来说顺序表是线性表的一种,而且逻辑和物理都是线性结构

2、顺序表分类

顺序表和数组的区别

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

2.1 静态顺序表

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

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


 静态顺序表(这里拿里面存储的整形举例)
 typedef int SLDataType;
 #define N 100
 typedef struct SeqList
 {
     SLDatatype arr[N];
     int size;//size是有效数据的个数
 }SL;
  
 解释一下为什么要把存储的类型变为SLDataType
 这么做是为了方便以后修改 使用 不同 的类型 
 还有把数组存储的数据容量N 便于修改

2.2 动态顺序表

前言：

动态顺序表的结构更加灵活, 可以对结构进行增删查改，所以我们下面的接口都是通过动态顺序表实现的

二、动态顺序表的实现(重要！)

1.准备工作及其注意事项

1.1 先创建三个文件

 解释这三个文件的作用
 1、头文件SeqList.h  是来声明接口函数，定义顺序表，将几个公共用到的库函数集合起来
 2、源文件SeqList.c  是用来具体实现接口
 3、源文件test.c  用于接口的测试工作 ，即具体的使用场景

1.2 注意事项：帮助高效记忆和理解

 1.不管写任意一种接口函数，我们在处理之前都要进行断言，避免穿过来的是NULL指针  assert(ps->arr) ;
 2.在进行扩容操作 的时候别忘记了 realloc要将新空间的地址和容量 更新给 自己的数组 和 容量变量(在下文)
 3.进行插入操作之后  要把size++;  在进行删除操作的时候要进行size--;(很重要的一点)
 4、插入操作 和 删除操作 用到循环 数据整体后移 或 前移 一定要注意 边界！！！

2.顺序表的基本功能接口

2.0 创建一个顺序表


//动态顺序表
typedef int SLDataType;// 定义一个 类型名字，方便快速修改 类型
typedef struct SeqList
{
	SLDataType* arr;
	int capacity; // 记录动态顺序表 申请空间的大小 
	int size;// 记录 顺序表 当前有效的数据个数
}SL;
// 给 结构体命名，翻遍方便使用：直接写在下面也可以
// typedef struct SeqList SL;

2.1 顺序表的初始化


void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.2 顺序表的销毁


void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.3 顺序表的打印


// 打印顺序表：这里可以 传值 也可 传址 ，
// 因为不需要对数据进行修改(可以传值)，但是 为了保持接口一致性(其他接口都是传址)，这里直接使用 传址
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i) printf("%d ", ps->arr[i]);
	printf("\n");
}

3.顺序表的扩容检查接口


// 公共的扩容判断
void SLCheckCapacity(SL* ps)
{
	//当容量capacity 大小 == 标记点size 时，说明 已经满了：需要 扩容
	if (ps->size == ps->capacity)
	{
		// 开辟空间时注意，当capacity初始化为 0 时，直接相乘的结果还是 0 ！！
		// 所以要先判断一下, 并且需要做 申请空间是否成功的判断，
        // 还不能直接将申请的空间赋值给 目标数组，先给一个 临时变量
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; 
        // 每次 两倍空间扩容(tip：这里推荐2倍的倍数扩容，可以自行查找为什么倍数扩容 较好！)
		SLDataType* ptmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (ptmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		// 扩容成功
		ps->arr = ptmp;
		ps->capacity = newCapacity;
	}
}

4.顺序表的增加功能接口

4.1 尾插接口


// （1）尾插法：有三种情况：1) 头部非空，尾部还有空间；2)全部为空；3)全部满了
void SLPushBack(SL* ps, SLDataType x)
{
	// 先判断指针是否非空
	assert(ps);
	// 空间不够，扩容 : 3）
	SLCheckCapacity(ps);
	// 空间足够，直接插入：1 ) ; 2 )
	// 在 size 这个位置插入数据: size 是标记第一个空位置
	ps->arr[ps->size++] = x;
	// ps->size++; // 标记点size 需要即使更新：size++ 也可以合并在上面
}

4.2 头插接口


// 头插法
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	// 空间不够，扩容 : 3）
	SLCheckCapacity(ps);
 
	// 将数据向后挪动：注意边界问题！！！
	for (int i = ps->size; i > 0; --i) ps->arr[i] = ps->arr[i - 1];
	
	ps->arr[0] = x; // 将插入数据 放在头部
	ps->size++; // 别忘 了 更新 size
}

4.3 指定位置插入接口


// 指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	// 注意 ： 可以指定位置插入 说明 指定的位置pos 可能不合理，可能越界, 必须要断言判断一下
	assert(0 <= pos && pos < ps->size); // 注意 不能等于 size！！！！
	// 判断是否有足够的空间
	SLCheckCapacity(ps);
 
	// 在 pos 位置中 插入 数据 x ：就要将 pos 位置 起的 后面数据向后挪动
	for (int i = ps->size; i >= pos + 1; --i) // 让 pos 这个位置 空出来
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

5.顺序表的删除功能接口

5.1 尾删接口


void SLPopBack(SL* ps)
{
	// 删除前 检查：顺序表非空才能执行删除，同时 size 不能为 0
	assert(ps);
	assert(ps->size);// 顺序表不为空
	ps->size--; 
    // 直接 size-- 将 size 位置的数值 丢出 我们的有效数据空间，那个位置不属于有效空间了，则类似达到删除的效果
}

5.2头删接口


void SLPopFront(SL* ps)
{
	// 删除前 检查：顺序表非空才能执行删除，同时 size 不能为 0
	assert(ps);
	assert(ps->size);
    
	// 将 后面的 数据 向前移动： 注意边界！！
	for (int i = 1; i < ps->size; ++i) ps->arr[i - 1] = ps->arr[i];
	ps->size--;
}

5.3指定位置删除接口


void SLErase(SL* ps, int pos)
{
	assert(ps);
	// 注意 ： 可以指定位置插入 说明 指定的位置可能不合理，可能越界, 必须要断言判断一下
	assert(0 <= pos && pos < ps->size); // 注意 不能等于 size
	for (int i = pos + 1; i < ps->size; ++i)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

6.顺序表的查找实现接口


int SLFind(SL* ps, int x)
{
	for (int i = 0;i < ps->size;++i)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

三.总代码

SeqList.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int Capacity;
	int size;
}SL;
 
// 一、初始化
void SLInit(SL* ps);
 
// 二、 尾插法
void SLPushBack(SL* ps, SLDataType x);
 
// 二、 头插法
void SLPushFront(SL* ps, SLDataType x);
 
// 三、尾删法
void SLPopBack(SL* ps);
 
// 四、头删法
void SLPopFront(SL* ps);
 
// 五、指定位置删除
void SLErase(SL* ps, int pos);
 
// 六、指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
 
//顺序表的扩容检查(扩容的原则,以及扩容的方法)
void SLCheckCapacity(SL* ps);
 
// 打印函数
void SLPrint(SL* ps);

SepList.c


#include"SeqList.h"
 
 
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->Capacity = ps->size = 0;
}
 
// 开辟空间函数
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->Capacity)
	{
		int NewCapacity = ps->Capacity == 0 ? 4 : 2 * (ps->Capacity);
		SLDataType* ptmp = realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		if (ptmp == NULL)
		{
			perror("realloc fail !");
			exit(1);
		}
		ps->arr = ptmp;
		ps->Capacity = NewCapacity;
	}
}
// 二、 尾插法
void SLPushBack(SL* ps, SLDataType x)
{
	// 先判断指针是否非空
	assert(ps); // 别忘了
	// 分两大类情况：空间足够 和 空间不够
	// (1) 空间不够：空间扩展
	SLCheckCapacity(ps);
	// 开始尾插
	ps->arr[ps->size++] = x;
}
 
// 二、 头插法
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps); // 别忘了
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; --i)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++; // 别忘记了
}
 
// 三、尾删法
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
 
// 四、头删法
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; ++i)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
 
// 五、指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(0 <= pos && pos < ps->size);
	for (int i = pos; i < ps->size - 1; ++i)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
 
// 六、指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps); // 别忘了
	assert(0 <= pos && pos < ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i >= pos + 1; --i)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++; // 别忘记了
}
 
// 打印函数
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

test.c


#include"SeqList.h"
void slTest01()
{
	SL sl;  // 创建一个结构体变量 sl
	SLInit(&sl); // 这里需要 传地址：才能真正被初始化
 
	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4); // ctrl + d == ctrl + c + v
	printf("测试尾插: ");
	SLPrint(&sl);
 
	// 测试头插
	SLPushFront(&sl, 10);
	printf("测试头插: ");
	SLPrint(&sl);
 
	// 测试 尾删
	SLPopBack(&sl);
	printf("测试尾删: ");
	SLPrint(&sl);
 
	// 测试 头删
	SLPopFront(&sl);
	printf("测试头删: ");
	SLPrint(&sl);
 
	// 测试 指定位置插入
	SLInsert(&sl, 1, 15);
	printf("指定插入: ");
	SLPrint(&sl);
 
	SLErase(&sl, 1);
	printf("指定删除: ");
	SLPrint(&sl);
}
int main()
{
	slTest01(); // 第一个测试函数
	return 0;
}

四、顺序表的问题及思考

问题：

1. 中间/头部的插⼊删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不⼩的消耗。

3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？

有没有这样一个数据结构

1、中间和头尾的数据插入不用挪动其他数据，而是一步到位

2、不需要直接扩充连续的空间（用不完容易浪费，像上面第 3 点所说）

3、不会造成空间浪费

这样的强大的数据结构即为【链表】

可以点击跳转讲解单链表的实现文章 ---->：【数据结构】单链表的实现

完。

若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/926376

【数据结构】顺序表 超详细！

一.顺序表定义

1 、顺序表的概念及结构

1.1线性表