数据结构之线性表（2）

顺序表中的动态存储

上文我们了解到了顺序表中的静态顺序表的相关操作，今天我们来学习动态顺序表的知识。
为什么会存在动态顺序表呢？？

原因：静态顺序表给定的数据容量固定，多了浪费，少了不够用。

首先我们对动态顺序表的结构体声明如下：

typedef struct SeqList
{
	datatype * array;//指向动态开辟的数组
	size_t size;//有效数据的个数 
	size_t capacity;//容量空间的大小
}SL;

在这里插入图片描述

动态顺序表的相关操作：

1.初始化

void SeqListInit(SL *ps)
{
	ps->array=NULL;
	ps->size=0;
	ps->capacity=0;
}

2.尾插

void SeqListPushBack(SL* ps,datatype x)
{
	Buymemory(ps);
	ps->array[ps->size] = x;
	ps->size++;
}

3.头插

void SeqListPushFront(SL* ps, datatype x)
{
	Buymemory(ps);
	int i = p->size;
	while (i)
	{
		ps->array[i] = ps->array[i-1];
		i--;
	}
	ps->array[0] = x;
	ps->size++;
}

图解：在这里插入图片描述

4.尾删

#include<stdio.h>
void SeqListPopBack(SL *ps)
{
	//ps->array[ps->size]=0;  error 因为可能要删除的数据本来就是0，所以可以直接size--
	ps->size--;
}

5.头删

void SeqListPopFront(SL *ps)
{
	for(int i=0;i<ps->size;++i)
	{
		ps->array[i]=ps->array[i+1];
	}
}

6.指定位置删除数据

#include<stdio.h>
void SeqListDelete(SL *ps,int pos)
{
	for(int i=pos;i<ps->size;i++)
	{
		ps->array[i]=ps->array[i+1];
	}
	ps->size--;
}

7.指定位置添加数据

void SeqListincrease(SL *ps,int pos,datatype x)
{
	for(int i=ps->size;i>pos;i--)
	{
		ps->array[i+1]=ps->array[i];
	}
	ps->array[pos]=x;
	ps->size++;
}

对头插和尾插操作中，可能都会造成空间大小不够需要增容的操作，每次写起来非常麻烦，我们可以将增容的过程写成一个函数，以后在头插和尾插操作中，只要调用该函数即可。

8.增容函数

void Buymemory(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//可能开始空间为0；对0*2还是等于0，如果开始空间为0，则给4个空间大小
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		datatype* tmp = (datatype*)realloc(ps->array, newcapacity * 2 * sizeof(datatype));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->array = tmp;
			ps->capacity = newcapacity;
		}
	}
}

9.顺序表的销毁

void SLDestroy(SL* ps)
{
	if (ps->array)
		free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->size = 0;
}

10.顺序表的打印

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

11.查找指定数据

int SeqListfind(SL* ps, datatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
			return i;
	}
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct SeqList
{
	datatype* array;//指向动态开辟的数组
	size_t size;//有效数据的个数 
	size_t capacity;//容量空间的大小
}SL;
//初始化
void SeqListInit(SL* ps)
{
	ps->array = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//增容
void Buymemory(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//可能开始空间为0；对0*2还是等于0，如果开始空间为0，则给4个空间大小
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		datatype* tmp = (datatype*)realloc(ps->array, newcapacity * 2 * sizeof(datatype));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->array = tmp;
			ps->capacity = newcapacity;
		}
	}
}
//尾插
void SeqListPushBack(SL* ps,datatype x)
{
	Buymemory(ps);
	ps->array[ps->size] = x;
	ps->size++;
}
//头插
void SeqListPushFront(SL* ps, datatype x)
{
	Buymemory(ps);
	int i = ps->size;
	while (i)
	{
		ps->array[i] = ps->array[i-1];
		i--;
	}
	ps->array[0] = x;
	ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
	//ps->array[ps->size]=0;  error 因为可能要删除的数据本来就是0，所以可以直接size--
	ps->size--;
}
//头删
void SeqListPopFront(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		ps->array[i] = ps->array[i + 1];
	}
}
//指定位置删除数据
void SeqListDelete(SL* ps, int pos)
{
	for (int i = pos; i < ps->size; i++)
	{
		ps->array[i] = ps->array[i + 1];
	}
	ps->size--;
}
//指定位置添加数据
void SeqListincrease(SL* ps, int pos, datatype x)
{
	for (int i = ps->size; i > pos; i--)
	{
		ps->array[i + 1] = ps->array[i];
	}
	ps->array[pos] = x;
	ps->size++;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->array)
		free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->size = 0;
}
//顺序表的打印
void SLPrint(SL  s)
{
	for (int i = 0; i < s.size; i++)
		printf("%d ", s.array[i]);
}
int main()
{
	SL s;
	SeqListInit(&s);
	SeqListPushFront(&s, 1);
	SeqListPushFront(&s, 3);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 5);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 10);
	SeqListPushBack(&s, 8);
	SLPrint(s);
	SLDestroy(&s);
	return 0;
}