数据结构：顺序表

数据结构是由“数据”和“结构”两词组合⽽来。

什么是数据？常⻅的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等

等）、⽹⻚⾥⾁眼可以看到的信息（⽂字、图⽚、视频等等），这些都是数据

什么是结构？

当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性 ⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的⽅式。

想要找到草原上名叫“咩咩”的⽺很难，但是从⽺圈⾥找到1号⽺就很简单，⽺圈这样的结构有效将 ⽺群组织起来。

---

前言

概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系

的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。

总结：

1）能够存储数据（如顺序表、链表等结构）

2）存储的数据能够⽅便查找

一、顺序表的分类

1.顺序表与数组的区别

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

2.顺序表的分类 

2.1 静态顺序表

2.2 动态顺序表 

 

二、动态顺序表的实现

1.头文件Seqlist.h：顺序表结构，声明顺序表的方法

1.1定义

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构
 
//#define N 100
//
静态顺序表
//struct SeqList
//{
//	int arr[N];
//	int size;//有效数据个数
//};
 
typedef int SLDataType;
//动态顺序表
typedef struct SeqList 
{
	SLDataType* arr;
	int size; //有效数据个数
	int capacity; //空间大小
}SL;
//typedef struct SeqList SL;

 对数组的类型进行重命名，方便后期修改

1.2 声明方法 

//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);
 
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
 
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
 
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

2.Seqlist.c:实现顺序表的方法（增删查改）

2.1 初始化

注：包含头文件

#include"SeqList.h"
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

 2.2 销毁

//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr) //等价于  if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

此处参数传地址 

 2.3 判断空间大小，申请空间

申请多大的空间？事实上都是成倍增加，一般是二倍或者三倍，有数学（概率论）推导而来

void SLCheckCapacity(SL* ps)
{
	//插入数据之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//malloc calloc realloc  int arr[100] --->增容realloc
		//三目表达式
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序，不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

2.4 尾插

//头插
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];//arr[1] = arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}

2.5 头插

//头插
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];//arr[1] = arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}

2.6 尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	--ps->size;
}

2.7头删

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]; //arr[size-2] = arr[size-1]
	}
	ps->size--;
}

注意循环条件，小心越界 

总结

1. 顺序存储：顺序表使用一块连续的存储空间来存储元素，可以方便地进行插入、删除和查找操作。

2. 快速访问：由于元素在内存中是连续存储的，所以可以通过下标来快速访问表中的元素，时间复杂度为O(1)。

3. 动态扩容：顺序表可以根据需要动态扩容，可以在插入元素时动态分配内存空间，不需要预先指定容量。

4. 空间效率高：相对于链表等其他数据结构，顺序表的存储空间利用率更高，不需要额外的指针存储关系。