C语言顺序表 逐行解析！！！

1、顺序表的概念及结构

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 案例：蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合

2、顺序表分类

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

• 顺序表分类

◦ 静态顺序表

概念：使⽤定⻓数组存储元素

struct SeqList
{
int a[5];//定长数组
int size;//有效数据个数

}；

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

动态顺序表

#define int SLDataType
typedef struct SeqList
{
  SLDataType*a;
  int size;
  int capacity;
//按需申请空间
}SL;

3、动态顺序表的实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType   //int也可以调整为其他类型
typedef struct SeqList
{
	SLDataType* arr;
	int size;        //有效数据个数
	int capacity;     //空间容量
}SL;//将struct SeqList改名为SL

//顺序表初始化及销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);


int main()
{

	printf("%d", sizeof(SL));
	return 0;
}//输出16，在x64环境下，指针大小是8个字节

struct SeqList解析

解释：动态顺序表的空间容量是相对于有效数据个数的，并不是指结构体本身所占的字节个数，你可以把size理解为单位1，而capacity就是单位1的空间容量

void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}//对顺序表的初始化

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);

	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}//顺序表的销毁

void SLCheckcapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{

		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (int*)realloc(ps->arr, newcapacity * sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}

		ps->arr = tmp;
		ps->capacity = newcapacity;
	}

}

SLCheckcapacity解析

if (ps->size == ps->capacity); 如果单位1和设定好的容量相等，则空间不够，就要扩容(后续每次插入都只是插入1个单位1)

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

三目操作符，判断ps指向的capacity是否为0，为0则赋值为4，否则ps指向的capacity*2

SLDataType* tmp = (int*)realloc(ps->arr, newcapacity * sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
    ps->arr = tmp;
		ps->capacity = newcapacity;

realloc的使用，为ps指向的arr申请空间，大小为newcapacity * sizeof(int)

解释：capacity为单位1的总容量，当size=4，capacity=4时，ps->capacity * 2，capacity就变为了8，所以当判断if (ps->size == ps->capacity)成立时，原来空间大小是16字节(capacity*4)新的空间就是newcapacity * sizeof(int)=32

因为使用realloc，当是情况2时，原有空间之后没有足够空间就要返回新的内存地址 tmp接收

ps->capacity = newcapacity;把newcapacity的值赋给capacity

尾插

void SLPushBack(SL* ps, SLDataType x)
{
  SLCheckcapacity(ps);
  assert(ps);
  ps->arr[ps->size++] = x;
//当size=3，前面3个单位1分别是1，2，3时想要在尾部插入一个4
//                       下标是ps->arr[0],arr[1],arr[2]
//把ps指向的arr下标为size的值赋为4后，size+1.（ps->arr[3]=x）
}

头插

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckcapacity(ps);
	for (int i = ps->arr; i > 0; i++)
	{
		ps->arr[i] = ps->arr[i - 1];

	}
	ps->arr[0] = x;
	ps->size++;
}

删除指定位置的数据

void SLEraze(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i+1];

	}
	
	ps->size--;
}

 顺序表中还有很多方法就不一一列举了，希望本文可以帮助你更好的理解顺序表中的知识。