纯C语言实现数据结构顺序表

一、顺序表的概念及结构

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

顺序表一般可以分为：

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

// 顺序表的静态存储
#define N 7
typedef int DataType;
typedef struct SeqList
{
	DataType array[N]; // 定长数组
 	size_t size; 	   // 有效数据的个数
}SeqList;
// 顺序表的动态存储
typedef struct SeqList
{
	DataType* array;  // 指向动态开辟的数组
	size_t size ; 	  // 有效数据个数
	size_t capicity ; // 容量空间的大小
}SeqList;

二、顺序表的实现

1.顺序表的创建

typedef int DateType;	//为了方便的改变数据的类型

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

2.顺序表初始化

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

3.顺序表销毁

void SeqListDestory(SeqList* ps)
{
	assert(ps);				//判断指针是否为空
	assert(ps->capacity);	//判断容量空间大小是否为0

	free(ps->array);
	ps->array = NULL;//使用free后，随时置空，养成好习惯
	ps->size = 0;
	ps->capacity = 0;
}

4.顺序表打印

void SeqListPrint(SeqList* ps)
{
	assert(ps);			//判断指针是否为空
	assert(ps->size);	//判断有效数据个数是否为0

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

5.检查空间，如果满了，进行增容

void SeqListCheckCapacity(SeqList* ps)//不作为接口，在函数内部调用
{
	assert(ps);//判断指针是否为空

	if (ps->size == ps->capacity)//当有效数据个数==容量空间大小时，进行增容
	{
        //新容量大小一般扩大为二倍，当容量为0时，设置大小为4个结构体，当容量不为0时，扩大二倍。
		int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);
        //使用realloc在原数组后增容，即使没有原数组，realloc也会新创建一个数组
		DateType* newArray = (DateType*)realloc(ps->array, sizeof(DateType) * newCapacity);
		if (newArray == NULL)//使用realloc后判断指针是否为空，增容是否成功
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		ps->array = newArray;//更新数组地址
		ps->capacity = newCapacity;//更新容量空间大小
	}
}

6.尾部插入一个数据

void SeqListPushBack(SeqList* ps, DateType x)
{
	assert(ps);//判断指针是否为空

	SeqListCheckCapacity(ps);//判断是否增容
	//由于数组的下标是由0开始，则size为下标处的位置就是插入数据的位置
	ps->array[ps->size] = x;//在尾部插入数据
	++ps->size;//插入数据后，有效数据个数增大1
}

7.头部插入一个数据

void SeqListPushFront(SeqList* ps, DateType x)
{
	assert(ps);//判断指针是否为空

	SeqListCheckCapacity(ps);//判断是否增容
	//在头部插入一个数据，需要把数组的内容整体往后移动一个位置
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->array[end + 1] = ps->array[end];
		--end;
	}
	ps->array[0] = x;//在头部插入数据
	++ps->size;//插入数据后，有效数据个数增大1
}

8.尾部删除一个数据

void SeqListPopBack(SeqList* ps)
{
	assert(ps);			//判断指针是否为空
	assert(ps->size);	//判断有效数据个数是否为0

	--ps->size;//删除一个数据，直接让有效数据个数减1，即（减小下标，使无法访问）。
}

9.头部删除一个数据

void SeqListPopFront(SeqList* ps)
{
	assert(ps);			//判断指针是否为空
	assert(ps->size);	//判断有效数据个数是否为0
	//在头部删除一个数据，需要把数组中下标为0向后的内容整体往前移动一个位置
	int begin = 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		++begin;
	}
	--ps->size;//删除一个数据，直接让有效数据个数减1，即（减小下标，使无法访问）。
}

10.顺序表的查找

int SeqListFind(SeqList* ps, DateType x)
{
	assert(ps);			//判断指针是否为空
	assert(ps->size);	//判断有效数据个数是否为0
	//遍历数组，找到了返回下标，找不到返回-1
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

11.顺序表在pos位置插入一个数据

void SeqListInsert(SeqList* ps, int pos, DateType x)
{
	assert(ps);//判断指针是否为空
	assert(pos >= 0 && pos <= ps->size);//需要插入的位置必须在[0,size]

	SeqListCheckCapacity(ps);//判断是否增容
	//在pos位置插入一个数据，需要把数组中pos位置及向后位置的内容整体往后移动一个位置
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->array[end + 1] = ps->array[end];
		--end;
	}
	ps->array[pos] = x;//在pos位置插入数据
	++ps->size;//插入数据后，有效数据个数增大1
}

注意：

当pos为0时，完全可以充当头部插入一个数据

当pos为size时，完全可以充当尾部插入一个数据

12.顺序表删除pos位置的数据

void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);//判断指针是否为空
	assert(ps->size);//判断有效数据个数是否为0
	assert(pos >= 0 && pos < ps->size);//需要插入的位置必须在[0,size)
	//删除pos位置的数据，需要把数组中pos位置向后的内容整体往前移动一个位置
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		++begin;
	}
	--ps->size;//删除一个数据，直接让有效数据个数减1，即（减小下标，使无法访问）。
}

注意：

当pos为0时，完全可以充当头部删除一个数据

当pos为size时，完全可以充当尾部删除一个数据

三、总结

1. 每个接口，都要判断指针是否为空（除初始化接口，创建接口）
2. 销毁时，需要判断容量空间大小是否为0
3. 打印时，需要判断有效数据个数是否为0
4. 查找时，需要判断有效数据个数是否为0
5. 插入数据时，需要判断是否增容，插入位置及向后位置整体向后挪动一个位置，size + 1
6. 删除数据时，需要判断有效数据个数是否为0，删除位置向后位置整体向前挪动一个位置，size - 1
7. 涉及到传入pos位置的函数，要判断pos的合法性
8. free后，要置空，养成好习惯
9. 每次扩容一般扩为二倍，在删除数据时，不会减小容量，只会减小有效数据个数
10. 为了方便的改变数组的类型，将int重命名为DateType

四、完整代码

#SeqList.h

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

typedef int DateType;

typedef struct SeqList
{
	DateType* array;
	int size;
	int capacity;
}SeqList;

void SeqListInit(SeqList* ps);
void SeqListDestory(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, DateType x);
void SeqListPushFront(SeqList* ps, DateType x);
void SeqListPopBack(SeqList* ps);
void SeqListPopFront(SeqList* ps);
int SeqListFind(SeqList* ps, DateType x);
void SeqListInsert(SeqList* ps, int pos, DateType x);
void SeqListErase(SeqList* ps, int pos);

//SeqList.c

#include "SeqList.h"

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

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	assert(ps->capacity);

	free(ps->array);
	ps->array = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	assert(ps->size);

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

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

	if (ps->size == ps->capacity)
	{
		int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity * 2);
		DateType* newArray = (DateType*)realloc(ps->array, sizeof(DateType) * newCapacity);
		if (newArray == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		ps->array = newArray;
		ps->capacity = newCapacity;
	}
}

void SeqListPushBack(SeqList* ps, DateType x)
{
	assert(ps);

	SeqListCheckCapacity(ps);

	ps->array[ps->size] = x;
	++ps->size;

	//SeqListInsert(ps, ps->size, x);
}

void SeqListPushFront(SeqList* ps, DateType x)
{
	assert(ps);

	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->array[end + 1] = ps->array[end];
		--end;
	}
	ps->array[0] = x;
	++ps->size;

	//SeqListInsert(ps, 0, x);
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size);

	--ps->size;

	//SeqListErase(ps, ps->size - 1);
}

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size);

	int begin = 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		++begin;
	}
	--ps->size;

	//SeqListErase(ps, 0);
}

int SeqListFind(SeqList* ps, DateType x)
{
	assert(ps);
	assert(ps->size);

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

void SeqListInsert(SeqList* ps, int pos, DateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->array[end + 1] = ps->array[end];
		--end;
	}
	ps->array[pos] = x;
	++ps->size;
}

void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);

	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->array[begin - 1] = ps->array[begin];
		++begin;
	}
	--ps->size;
}