数据结构（1）顺序表

1、线性表

        线性表在逻辑上是线性结构，也就是一条连续的直线，但是在物理结构上不一定是连续的，线性表在物理上存储时，通常是以数组和链式结构的形式存储。常见的线性表有：顺序表、链表、栈、队列、字符串等。

2、顺序表

2.1  概念与结构

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的数据结构，一般情况下采用数组存储。

2.2  静态顺序表

        使用定长数组存储元素

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType a[N];
	int size;
}SL;

这里为什么要多此一举，将int类型重新定义为SLDataType呢？原因很简单，顺序表的类型有很多，不一定是int，也可以是char、double等等，重新定义的话方便我们后续修改代码。注意：不能用VS中的Crl+F一键替换，因为会把代码中无需替换的部分替换掉，导致代码出错。

静态顺序表的缺陷很明显：空间少了不够用，给多了又会造成空间浪费。因此我们用的更多的是动态顺序表。

2.3 动态顺序表

        按需申请空间，可以扩容。

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;        //有效数据个数
	int capacity;    //空间容量
}SL;

问题1：如何判断空间是否满了？     ——    size == capacity

问题2：如何增加空间？ —— 使用realloc函数，增容一般呈倍数增加，推荐二倍增容

完整代码实现如下：注：通常一个项目的实现分为三个文件——.h（头文件，用于声明函数、定义结构）、.c（实现文件，#include"xxx.h"）以及test.c（测试文件）

SeqList.h

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

//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;        //有效数据个数
	int capacity;    //空间容量
}SL;

void SLPrint(SL* ps);

//初始化
void SLInit(SL* ps);

//尾插
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);

//删除pos位置的数据
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDataType x);

//销毁
void SLDestroy(SL* ps);

SeqList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		//realloc 的第二个参数,单位是字节
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);

	//空间足够的情况下
	ps->arr[ps->size] = x;
	ps->size++;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	/*if (ps == NULL)
	{
		return;
	}*/
	assert(ps != NULL);
	//判断空间是否足够
	SLCheckCapacity(ps);

	//将顺序表中所有数据向后移动一位
	for (int i = ps->size;i > 0;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

void SLPrint(SL* ps)
{
	for (int i = 0;i < ps->size;i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0;i < ps->size - 1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);
	//pos及之后的数据整体向后挪动一位
	for (int i = ps->size;i > pos;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos之后的数据整体向前挪动一位
	for (int i = pos;i < ps->size - 1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0;i < ps->size;i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//未找到
	return -1;
}

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void test01()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);

	SLInsert(&sl, 1, 100);
	SLPrint(&sl);

	SLErase(&sl, 1);
	SLPrint(&sl);

	SLDestroy(&sl);
}

int main()
{
	test01();

	return 0;
}