数据结构之顺序表-扩容插入基本框架

线性表和顺序表

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列，是一种很常见的数据结构

线性表在逻辑上是线性结构，但是在物理结构上并不一定是连续的

常见的线性表有：顺序表、链表、栈、队列、字符串等

顺序表

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

可以认为，顺序表的本质就是数组

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。    

静态顺序表

使用定长数组存储元素。

例子：静态通讯录

#define BOOK_MAX 100
typedef int DataType //这样可以随时改变内容的类型

typedef struct address_book //通讯录内容
{
	struct perinfmt p[BOOK_MAX];//每个人信息,数组一共100个人
	DataType ID;//统计每个人编号
}SeqlistContact;//顺序表

动态顺序表

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

例子：动态通讯录

typedef struct PeopleInfo
{
    struct People* a;//指向动态开辟的结构体成员数组
    int size;//标记成员个数(有效成员个数)
    int capacity;//容量，如果不够可以增容
}PeopleInfo;

2.1.基本架构

使用typedef，类型可以不固定，后序想要更改存储的数据类型更方便

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity; // unsigned int
}SeqList;

size是有效数字个数，同时也是最后一个数据的下一个位置的下标

2.2初始化

指针置空，一开始可以不给容量，也可以给一定的容量

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

2.3扩容

realloc ：如果传空指针，相当于malloc

realloc原理
    1.原地扩容：如果后面空间足够则在后面扩
    2.异地扩容：如果后面空间不够，则重新找一块空间开辟，把原来的数组拷贝过去，然后释放原来空间

最初就是空指针，所以最开始使用realloc时相当于是malloc

扩容每次扩两倍，要判断realloc是否成功

最后还要把新容量赋给ps->capacity，把新开辟空间的地址赋给ps->a

void CheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容
		//如果最初容量为0，就把容量设置为4
		//如果最初容量不为0，那就两倍扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//直接结束进程
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

2.4打印

遍历数组打印即可,ps->size标志的就是有效数字的个数

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

2.5尾插

尾插：即插入到size位置

size：标志元素个数，size下标是数组最后一个元素的下一个位置

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.6头插

把元素往后移动，然后在0位置插入元素

注意：防止元素覆盖，要从数组最后一个元素往后移动，0位置的元素也要后移

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	
	//写法2
	/*
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	*/

	ps->a[0] = x;
	ps->size++;
}

2.7尾删

注意:要考虑数组中是否还有元素可以被删除

只需让ps->size–即可，因为size标志的就是元素个数。最后一个元素虽然空间还在，但是我们已经没有权限访问了

void SeqListPopBack(SeqList* ps)
{
	//温柔处理
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	//暴力处理：assert(ps->size >0)
	ps->size--;
}