线性表（线性存储）

2.1线性表

这是一种线性结构，含有n>=0个结点的有序列，其中的结点，有且只有一个开始结点，它没有前驱但有一个后继结点；有且只有一个终端结点，它没有后继但有一个前驱结点；其他结点都有一个前驱和一个后继。

线性表在计算机的存储基本上都是采用顺序存储和链式存储两种方式。

2顺序表

2.2.1基本概念及描述

线性表采用顺序存储的方式存储。将表中的结点依次存放在计算机内存中一组连续的存储单元中 ，只需找到顺序表中第一个结点的存储地址，就可以访问顺序表中的任意结点。而数组中的元素是可以随机访问的，所以可以使用数组来表示顺序表。

2.2.2顺序表的实现

数组的下标是从0开始的，下标为i的元素对应的是第i+1个结点.

顺序表又分为静态顺序表和动态顺序表，静态顺序表使用了定长数组存储元素

typedef int datatype;
#define N 7
typedef struct
{
    datatype a[N];
    int size;
}Sqlist;

缺陷:空间少了不够用，给多了会造成空间浪费

所以这里我们使用动态顺序表，按需申请，避免空间浪费

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

typedef int datatype;
typedef struct
{
	datatype* a;
	int size;
	int capacity;
}Sqlist;

void display(Sqlist slt);//打印顺序表
void init(Sqlist* slt);//初始化
void CheckCapacity(Sqlist* slt);//扩容
void append(Sqlist* slt, datatype x);//尾插
void insert(Sqlist* slt, datatype x,int position);//在指定位置插入数据x
void del(Sqlist* slt, int postion);//删除指定位置的数据
int find(Sqlist slt, datatype x);//查找x在顺序表中的位置，返回其位置
void Destroy(Sqlist* slt);//销毁顺序表

（1）打印顺序表

void display(Sqlist slt)
{
	if (!slt.size)
		printf("顺序表是空的\n");
	else
	{
		for (size_t i = 0; i < slt.size; i++)
		{
			printf("%d ", slt.a[i]);
		}
		printf("\n");
	}
}

（2）初始化

void init(Sqlist* slt)
{
	slt->a = NULL;
	slt->size =slt->capacity= 0;
}

（3）扩容

void CheckCapacity(Sqlist* slt)
{
	if (slt->size == slt->capacity)//扩容
	{
		int newcapacity = slt->capacity == 0 ? 4 : 2 * slt->capacity;
		datatype* tmp = (datatype*)realloc(slt->a, sizeof(datatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		slt->a = tmp;
		slt->capacity = newcapacity;
	}
}

（4）尾插

void append(Sqlist* slt, datatype x)
{
	CheckCapacity(slt);
	slt->a[slt->size++] = x;
}

（5）指定位置插入

花费的时间主要是元素后移操作，将position以及以后的元素向后移动一位，在position上插入x，该算法最好的情况是数据没有移动，就是尾插，最坏就是全部移动，时间复杂度取平均为n/2，时间复杂度为O（n）。

void insert(Sqlist* slt, datatype x, int position)
{
	assert(slt);
	assert(position >= 0 && position < slt->size);
	CheckCapacity(slt);
	for (int i = slt->size; i > position; i--)
	{
		slt->a[i] = slt->a[i - 1];
	}
	slt->a[position] = x;
	slt->size++;
}

（6）指定位置删除

将pos位置之后的元素整体向前移动一位，时间复杂度为O（n）。

void del(Sqlist* slt, int position)
{
	assert(slt);
	assert(position >= 0 && position < slt->size);
	for (int i = position; i < slt->size - 1; i++)
	{
		slt->a[i] = slt->a[i + 1];
	}
	slt->size--;
}

（7）查找

int find(Sqlist slt, datatype x)
{
	for (int i = 0; i < slt.size; i++)
	{
		if (slt.a[i] == x)
			return i;
	}
	return -1;
}

（8）销毁

void Destroy(Sqlist* slt)
{
	if (slt->a)
	{
		free(slt->a);
	}
	slt->a = NULL;
	slt->capacity = slt->size = 0;
}