1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

2.顺序表

2.1.概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：静态顺序表和动态顺序表

1. 静态顺序表：使用定长数组存储元素

要求：存储的数据从0开始，依次连续存储

问题：内存开小了不够用，开大了存在浪费（不实用）

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

要求：存储的数据从0开始，依次连续存储

?注：指针a负责接收动态开辟出来的空间地址

2.2.接口实现

test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void TestSeqList1()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 0);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListPushBack(&s, 10);
	SeqListPushBack(&s, 20);
	SeqListPrint(&s);

}

void TestSeqList2()
{

	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);
}

void TestSeqList3()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPrint(&s);

	SeqListInsert(&s, 10, 100);
	SeqListInsert(&s, 1, 20);
	SeqListInsert(&s, 5, 50);
	SeqListInsert(&s, 0, 50);

	SeqListPrint(&s);

	SeqListDestroy(&s);
}

void TestSeqList4()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(&s);

	SeqListErase(&s, 4);
	SeqListPrint(&s);

	SeqListErase(&s, 0);
	SeqListPrint(&s);

	SeqListErase(&s, 1);
	SeqListPrint(&s);
}

void TestSeqList5()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushFront(&s, -1);
	SeqListPushFront(&s, -2);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListDestroy(&s);
}

int main()
{

	TestSeqList5();

	return 0;
}

SeqList.h文件：

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

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;     // 存储数据个数
	int capacity; // 存储空间大小
}SL, SeqList;


//打印内存数据
void SeqListPrint(SeqList* psl);


//初始化内存数据
void SeqListInit(SeqList* psl);
//释放内存数据
void SeqListDestroy(SeqList* psl);


//检查内存容量
void SeqListCheckCapacity(SeqList* psl);


//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);


//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);


// 任意插
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 任意删
void SeqListErase(SeqList* psl, size_t pos);


// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);

SeqList.c文件：

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void SeqListPrint(SeqList* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}


void SeqListInit(SeqList* psl)
{
	assert(psl);

	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}


void SeqListDestroy(SeqList* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}


void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	// 如果满了，我们要扩容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}


void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//方法1：尾插功能实现代码
	/*SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;*/

	//方法2：用任意插功能实现尾插
	SeqListInsert(psl, psl->size, x);
}


void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	//方法1：尾删功能实现代码
	//psl->a[psl->size - 1] = 0;
	/*if (psl->size > 0)
	{
		psl->size--;
	}*/

	//方法2：用任意删功能实现尾删
	SeqListErase(psl, psl->size - 1);
}


void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	//方法1：头插功能实现代码
	//SeqListCheckCapacity(psl);
	 挪动数据，腾出头部空间
	//int end = psl->size - 1;
	//while (end >= 0)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}
	//psl->a[0] = x;
	//psl->size++;

	//方法2：用任意插功能实现头插
	SeqListInsert(psl, 0, x);
}

void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	//方法1：头删功能实现代码
	// 挪动数据覆盖删除
	/*if (psl->size > 0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}

		--psl->size;
	}*/

	//方法2：用任意删功能实现头删
	SeqListErase(psl, 0);
}


void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);

	// pos数值温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d\n", pos);
		return;
		//exit(-1);
	}
	// pos数值暴力检查
	//assert(pos <= psl->size);

	SeqListCheckCapacity(psl);

	//交换方法1(pos必须强制类型转换)
	//int end = psl->size - 1;
	//while (end >= (int)pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}

	//交换方法2
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}


void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}


int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

注：

1.传参数的时候不要传值调用（如下图所示），因为形参是实参的一份临时拷贝，对形参修改并不会影响实参，并且结构体传值调用会消耗大量的内存空间，因此要传值调用