数据结构（顺序表）

1.线性表

线性表是n个相同特性的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就是说是一条直线。但物理结构上可能并不是连续的，线性表在物
理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。

#define N 7
typedef int Data

typedef struct Seqlist
{
   Data arr[N];  //定长数组
   size_t size;  //有效个数
}Seqlist

2. 动态顺序表：使用动态开辟的数组存储。

typedef int Data

typedef struct Seqlist
{
   Data arr*;  //变长数组
   size_t size;  //有效个数
   size_t capacity //容量
}Seqlist

3.顺序表的接口实现

静态顺序表只适合数据个数已经确定的场合，如果不是，则顺序表的N给大了会造成空间浪费，给小了也不够用的情况，所以我们使用更加灵活的动态顺序表。

顺序表头文件（函数声明）：

#pragma once
#include<stdio.h>
typedef int Data;
typedef struct Stu
{
	Data* a;
	int size;
	int capacity;
}stu;
stu p;
//初始化和销毁
void SLInit(stu* ps);
void SLDestroy(stu* ps);
//打印顺序表数据
void SLPrint(stu* ps);
//扩容
void SLCheckCapacity(stu* ps);

//头部插入删除 / 尾部插入删除
void SLPushBack(stu* ps, Data x);
void SLPopBack(stu* ps);
void SLPushFront(stu* ps, Data x);
void SLPopFront(stu* ps);

//指定位置之前插入/删除数据
void SLInsert(stu* ps, int pos, Data x);
void SLErase(stu* ps, int pos);

初始化和销毁：

//初始化销毁
void SLInit(stu* ps)
 {
	ps->a = NULL;
	ps->size = ps->capacity = 0;
	Data* b;
	b = (Data*)malloc(sizeof(Data) * 4);
	if (b == NULL)
		return 1;
	ps->a = b;
	ps->capacity = 4;
}
//销毁
void SLDestroy(stu* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

打印顺序表数据：

//打印
void SLPrint(stu* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
}

扩容：

//扩容
void SLCheckCapacity(stu* ps)
{
	Data* b;
	b = (Data*)realloc(ps->a, sizeof(Data) * ps->capacity * 2);
	ps->capacity = ps->capacity * 2;
	if (b == NULL)
		return 1;
	ps->a = b;
}

 尾部插入删除：

//尾插
void SLPushBack(stu* ps, Data x)
{
	if (ps->size == ps->capacity)
	{
		SLCheckCapacity(&p);
	}
	ps->a[ps->size] = x;
	ps->size++;
}
//尾删
void SLPopBack(stu* ps)
{
	ps->size--;
}

头部插入删除：

//头插
void SLPushFront(stu* ps, Data x)
{
	if (ps->size == ps->capacity)
	{
		SLCheckCapacity(&p);
	}
	for (int i = ps->size; i>0; i--)
	{
		 ps -> a[i] =ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}
//头删
void SLPopFront(stu* ps)
{
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	ps->size--;
}

指定位置之前插入/删除数据：

//指定位置之前插入
void SLInsert(stu* ps, int pos, Data x)
{
	if (ps->size < pos)
		return 1;
	if (ps->capacity == 0 || ps->size == ps->capacity)
	{
		SLCheckCapacity(&p);
	}
	for (int i = 0; i < ps->size - pos + 1; i++)
	{
		ps->a[ps->size-i] = ps->a[ps->size-1-i];
	}
	ps->a[pos] = x;
	ps->size++;
}
//指定位置删除
void SLErase(stu* ps, int pos)
{
	for (int i = 0; i < ps->size - pos; i++)
	{
		ps->a[pos + i] = ps->a[pos + i+1];
	}
	ps->size--;
}