【数据结构】—— 顺序表

目录

1、顺序表的概念和结构

1.1线性表

1.2顺序表的定义

1.3顺序表的分类

1.3.1 静态顺序表 

1.3.2 动态顺序表

2、顺序表的接口实现

2.1初始化

2.2销毁

2.3插入

准备知识：

2.3.1尾插

2.3.2头插

2.3.3指定位置插入

 2.4 删除      

2.4.1头删

2.4.2尾删

2.4.3指定位置删除

2.5查找

2.6打印

源代码 

---

1、顺序表的概念和结构

1.1线性表

 线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表在逻辑结构是线性的，但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.2顺序表的定义

         顺序表（Sequential List）是一种基本的数据结构，它通过一组连续的存储单元来存储具有相同类型的数据元素。

与数组的区别：

1. 大小变化：数组的大小在创建时确定，之后不能改变；而顺序表的大小可以动态变化。
2. 扩容机制：数组通常不支持直接扩容；顺序表在需要时可以通过重新分配内存空间来实现扩容。
3. 使用场景：数组适用于元素数量固定不变或变化不大的场景；顺序表则更适用于元素数量需要动态变化的场景。

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

           顺序表逻辑结构是线性的，物理结构也是连续的。

特点：随机访问快、插入删除慢（需要移动元素）、存储空间固定或动态扩展 。

1.3顺序表的分类

顺序表是一个存储结构，因此什么数据类型都可以存储。将int类型的名字替换成SLDataTYpe，后续如果向存储别的类型，如char，short，结构体等类型时，只需要将int修改为char，short，结构体等类型，使得操作更加简化。

1.3.1 静态顺序表 

typedef int SLdatetype;
#define N 100  
typedef struct SeqList
{
	SLdatetype arr[N];//定长数组：开辟空间大小为100的数组
	int size;//指有效数据的个数
}SL;

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

缺陷:  

1. 固定大小限制

2. 内存利用效率低

3. 插入/删除困难

4. 数据大小限制

5. 难以管理

空间给少了溢出，给多了造成空间浪费。实际应用中出现较少

1.3.2 动态顺序表

typedef struct Seqlist
{
	SldateType* arr;//存储数据的底层结构
	int capacity;//空间容量
	int size;//有效数据的个数
}SL;

概念：动态顺序表（Dynamic Array）是一种能够根据需要动态调整大小的数组结构，通常用于存储元素集合，并支持高效的随机访问和动态增删操作。

缺陷：

1. 内存浪费

2. 插入/删除效率低

3. 容量调整耗时

4. 不适合大对象存储

5. 频繁扩容导致性能下降

2、顺序表的接口实现

准备工作：

创建三个代码文件：

1）SeqListc.h（头文件）—— 接口声明文件

2)  SeqList.c（源文件）——接口实现文件

3)  test.c（测试文件）——功能测试文件

2.1初始化

void SlInit(SL *ps)
{
	assert(ps != NULL);//判断ps是否为空
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.2销毁

void Sldestory(SL* ps)
{
	assert(ps != NULL);//判断ps是否为空
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.3插入

中间/头部的插入删除，时间复杂度为O(n)

准备知识：

顺序表的头插和尾插
1）空间足够，直接插入
2）空间不够，扩容
扩容的原则：

 1）一次扩容一个空间   
 2）一次扩容固定的大小
 3）成倍数地增加 (推荐：按倍数增加效率高，空间浪费相对较少)————动态内存管理
（三者都是分配内存，都是stdlib.h库里的函数(多次分配会造成程序效率低下)
malloc :用于动态分配指定字节数的内存空间。
calloc : 函数用于动态分配指定数目和大小的内存空间，并将内存初始化为零。
realloc：函数用于重新分配之前分配的内存块大小。

perror的使用

assert的使用

扩容的完整代码：

一般采用1.5倍或2倍进行扩容（1.5倍或2倍扩容策略在内存管理中是一种折中方案，能够在保证性能的同时，有效地管理内存和提高程序运行效率。）

void SlCheckCapacity(SL *ps)
{
	if (ps->size == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目运算符（如果是0则赋值为4，否则capacity*2）
		int* tmp = (SldateType*)realloc(ps->arr, newcapacity * sizeof(SldateType));//空间申请(注意开辟的是字节数)
		//判断申请空间成功
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//free(ps->arr);//为什么注释掉：因为realloc已释放arr原来的空间，无需再次释放
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

2.3.1尾插

void pushBack(SL* ps, SldateType x)//将x插入顺序表的尾部
{
	//断言
	assert(ps != NULL);//如果为NULL直接报错
	SlCheckCapacity(ps);//判断是否需要扩容
	ps->arr[ps->size] = x;//尾插
	ps->size++;//有效数据个数 + 1
}

2.3.2头插

void pushFront(SL* ps, SldateType x)//将x插入顺序表的头部
{
	assert(ps != NULL);//如果为NULL直接报错
	SlCheckCapacity(ps);//判断是否需要扩容
	//旧数据向后挪一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//头插
	ps->size++;//有效数据个数 + 1
}

2.3.3指定位置插入

pos为插入的位置。用assert限定插入的位置，防止出现负数或者过大的数。

void Insert(SL* ps,int pos,SldateType x)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos <= ps->size);//检查pos下标的合法性
	SlCheckCapacity(ps);//判断是否需要扩容
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;//指定位置插入元素x
	ps->size++;//有效数据个数 + 1
}

• 功能测试

  

 2.4 删除      

2.4.1头删

void PopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);
	//不为空执行挪动
	for (int i = 0; i <ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//有效数据个数 - 1
}

• 功能测试

2.4.2尾删

void PopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);
	ps->size--; //有效数据个数 - 1
}

• 功能测试

 2.4.3指定位置删除

pos为删除的位置。用assert限定插入的位置，防止出现负数或者过大的数。

void Erase(SL* ps, int pos)
{
	assert(ps != NULL);//如果为NULL直接报错
	assert(ps->size);//顺序表不能为空
	assert(pos >= 0 && pos < ps->size);//检查pos下标的合法性
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//有效数据个数 - 1
}

• 功能测试

2.5查找

int Find(SL* ps,SldateType x)//查找指定元素在顺序表的位置
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x) return i;//找到了返回pos
	}
	return -1;//没找到返回-1
}

• 功能测试

2.6打印

void SlPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)//打印顺序表
		printf("%d ", ps->arr[i]);
	printf("\n");
}

• 功能测试

源代码 

.h头文件

#pragma once//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h> /*realloc*/
#include<assert.h> /*assert*/
 
typedef int SldateType;
 
//动态顺序表
 
typedef struct Seqlist
{
	SldateType* arr;//存储数据的底层结构
	int capacity;//空间容量
	int size;//有效数据的个数
}SL;
//初始化
void SlInit(SL *ps);
 
//销毁
void Sldestory(SL* ps);
 
//打印顺序表
void SlPrint(SL* ps);//保持接口一致性
 
//顺序表的头插和尾插
void pushFront(SL* ps, SldateType x);//将x插入顺序表的头部
 
//将x插入顺序表的尾部
void pushBack(SL* ps, SldateType x);
 
//删除顺序表的最后一个数
void PopBack(SL* ps);
 
//删除顺序表的第一个数
void PopFront(SL* ps);
 
//从指定位置pos之前插入元素x
void Insert(SL* ps, int pos, SldateType x);
 
//从指定位置pos删除元素
void Erase(SL* ps, int pos);
 
//查找元素x在顺序表的下标
int Find(SL* ps, SldateType x);

.c文件

#include"SeqList.h"
 
//实现接口
//初始化
void SlInit(SL *ps)
{
	assert(ps != NULL);//判断ps是否为空
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
 
//销毁
void Sldestory(SL* ps)
{
	assert(ps != NULL);//判断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;//三目运算符（如果是0则赋值为4，否则capacity*2）
		int* tmp = (SldateType*)realloc(ps->arr, newcapacity * sizeof(SldateType));//空间申请(注意开辟的是字节数)
		//判断申请空间成功
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//free(ps->arr);//为什么注释掉：因为realloc已释放arr原来的空间，无需再次释放
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}
void pushBack(SL* ps, SldateType x)//将x插入顺序表的尾部
{
	//断言
	assert(ps != NULL);//如果为NULL直接报错
	SlCheckCapacity(ps);//判断是否需要扩容
	ps->arr[ps->size] = x;
	ps->size++;
}
 
void pushFront(SL* ps, SldateType x)//将x插入顺序表的头部
{
	assert(ps != NULL);//如果为NULL直接报错
	SlCheckCapacity(ps);//判断是否需要扩容
	//旧数据向后挪一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//头插数据
	ps->size++;//有效数据个数 + 1
}
 
void SlPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)//打印顺序表
		printf("%d ", ps->arr[i]);
	printf("\n");
}
 
void PopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);
	ps->size--; //有效数据个数 - 1
}
 
void PopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size);
	//不为空执行挪动
	for (int i = 0; i <ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//有效数据个数 - 1
}
 
void Insert(SL* ps,int pos,SldateType x)
{
	assert(ps != NULL);
	assert(pos >= 0 && pos <= ps->size);
	SlCheckCapacity(ps);//判断是否需要扩容
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
 
void Erase(SL* ps, int pos)
{
	assert(ps != NULL);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//有效数据个数 - 1
}
 
int Find(SL* ps,SldateType x)//查找指定元素在顺序表的位置
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x) return i;//找到了返回pos
	}
	return -1;//没找到返回-1
}