数据结构——顺序表

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1概念及结构

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

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

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

void SLInit(SL* psl) {
	assert(psl);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}
void SLDestroy(SL* psl) {
	assert(psl);
	if (psl -> a != NULL) {
		free(psl);
		psl->a = NULL;
		psl->capacity = 0;
		psl->size = 0;
	}
}
void SLPrint(SL* psl) {
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
void SLCheckCapacity(SL* psl) {
	assert(psl);
	if (psl->size == psl->capacity) {
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType)*newCapacity);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity = newCapacity;
	}
}
void SLPushBack(SL* psl, SLDataType x) {
	assert(psl);
	SLCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}
void SLPushFront(SL* psl, SLDataType x) {
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end+1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
void SLPopBack(SL* psl) {
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
}
void SLPopFront(SL* psl) {
	assert(psl);
	assert(psl->size > 0);
	int begin = 0;
	while (begin < psl->size) {
		psl->a[begin - 1] = psl->a[begin];
		begin++;
	}
	psl->size--;
}
void SLFind(SL* psl, SLDataType x) {
	assert(psl);
	int begin = 0;
	while (begin < psl->size) {
		if (psl->a[begin] == x) {
			printf("ҵ±:%d\n", begin);
			return;
		}
		begin++;
	}
		printf("Ҳ\n");
}
void SLInsert(SL* psl, int pos, SLDataType x) {
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end>=pos) {
		psl->a[end+1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}
void SLErase(SL* psl, int pos) {
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	int begin = pos;
	while (begin < psl->size) {
		psl->a[begin - 1] = psl->a[begin];
		begin++;
	}
	psl->size--;
}

#include<stdio.h>
#include"SeqList.h"
void TestSL1() {
	SL sl;
	SLInit(&sl);
	//SLCheckCapacity(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	//SLCheckCapacity(&sl);
	SLPrint(&sl);
	SLPushFront(&sl, 8);
	SLPushFront(&sl, 7);
	SLPushFront(&sl, 6);
	SLPrint(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLFind(&sl, 1);
	SLInsert(&sl, 2, 10);
	SLInsert(&sl, 2, 11);
	SLInsert(&sl, 2, 12);
	SLPrint(&sl);
	SLErase(&sl, 3);
	SLPrint(&sl);
	//SLDestroy(&sl);
}
int main() {
	TestSL1();
	return 0;
}