SequenceList顺序表的实现

顺序表概念简单梳理与讨论

顺序表即表里的元素按顺序连续存储，c语言中的内置类型数组就可以说是一个顺序表，但它不支持动态增长，此类数据结构的优点是可以随机访问表内元素，通过下标就可以直接找到顺序表中的某一元素。由于在内存中存储紧密，一般来说访问顺序表会有较好的空间局部性，访问速度较快。缺点仍然由其在存储上紧密相连的特点导致，若顺序表较大，申请内存空间会相对较长，并且此类数据结构若较多，还会引发内存碎片问题，导致一些内存浪费。另外就是顺序表的大小很可能无法提前预估，而动态开辟内存若一次开辟的较少，就可能引发频繁的内存开辟导致运行速度较缓慢，而若一次开辟的较多，又有可能会浪费掉一些空间。

顺序表的实现

基本思想

通过数组来存储数据，一个记录当前顺序表大小和一个记录顺序表容量的变量。

以下是结构声明与操作的函数声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MINSIZE 4
typedef int DataType;
typedef struct SeqList SeqList;
typedef size_t Position;
struct SeqList
{
	DataType* data; 
	size_t size;
	size_t capacity;
};

void SeqListInit(SeqList* L, size_t S);
void SeqListPushBack(SeqList* L, DataType D);
void SeqListPopBack(SeqList* L);
void SeqListPushFront(SeqList* L, DataType D);
void SeqListPopFront(SeqList* L);
void SeqListInsert(SeqList* L, DataType D, Position P);
void SeqListErase(SeqList* L, Position P);
void SeqListPrint(SeqList* L);
void SeqListDestroy(SeqList* L);
DataType SeqListFind(SeqList* L, DataType D);
void ExpandCapacity(SeqList* L);
int IsEmpty(SeqList* L);
int IsFull(SeqList* L);

初始化：

void SeqListInit(SeqList* L,size_t S)
{
	L->capacity = S > MINSIZE ? S : MINSIZE;
	L->data = (DataType*)malloc(sizeof(DataType) * L->capacity);
	L->size = 0;
}

快速的判断 空和满 的函数：

int IsEmpty(SeqList* L)
{
	return L->size == 0;
}
int IsFull(SeqList* L)
{
	return L->size == L->capacity;
}

动态扩容：

void ExpandCapacity(SeqList* L)
{
	DataType* tmp;
	tmp = (DataType*)realloc(L->data, sizeof(DataType) * 2 * L->capacity);
	if (tmp == NULL)
	{
		printf("FatalError:expand capacity failed!\n");
		exit(-1);
	}
	else
	{
		L->data = tmp;
		L->capacity *= 2;
	}
}

尾插尾删：

void SeqListPushBack(SeqList* L, DataType D)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	L->data[L->size] = D;
	L->size++;
}
void SeqListPopBack(SeqList* L)
{
	assert(L);
	if (!IsEmpty(L))
		L->size--;
}

头插和头删：

void SeqListPushFront(SeqList* L, DataType D)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	size_t end = L->size;
	while (end > 0)
	{
		L->data[end] = L->data[end - 1];
		end--;
	}
	L->data[0] = D;
	L->size++;
}
void SeqListPopFront(SeqList* L)
{
	assert(L);
	if (!IsEmpty(L))
	{
		size_t begin = 0;
		while (begin < L->size)
		{
			L->data[begin] = L->data[begin + 1];
			begin++;
		}
		L->size--;
	}
}

随机访问插入和随机访问删除：

void SeqListInsert(SeqList* L, DataType D, Position P)
{
	assert(L);
	if (IsFull(L))
		ExpandCapacity(L);

	if (P<0 || P>L->size)
		printf("invaild position!\n");
	else
	{
		size_t end = L->size;
		while (end > P)
		{
			L->data[end] = L->data[end - 1];
		}
		L->data[P] = D;
		L->size++;
	}
}
void SeqListErase(SeqList* L, Position P)
{
	assert(L);
	if (!IsEmpty(L))
	{
		if (P<0 || P>L->size - 1)
			printf("invaild position!\n");
		else
		{
			while (P < L->size - 1)
			{
				L->data[P] = L->data[P + 1];
				P++;
			}
			L->size--;
		}
	}
}

查找值：

int SeqListFind(SeqList* L, DataType D)
{
	assert(L);
	int i;
	for (i = 0; i < L->size; i++)
	{
		if (L->data[i] == D)
			return i;
	}
	return -1;
}

打印与销毁表：

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

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

最后值得注意的是，例程与例程之间可以复用，比如头插尾插是随机位置插入的特殊情况，头删尾删是随机位置删除的特殊情况，可以利用这一点简化代码，增强可读性和方便调试