C语言深入浅出讲解顺序表的实现

目录

• 1.线性表
• 2.顺序表
• 2.1 概念及结构
• 2.2 提供接口
• 2.3 接口实现

今天起开始编写数据结构中的各种数据结构及算法的实现，说到顺序表，我们首先得了解下线性表。

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

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

1.静态顺序表：使用定长数组存储。

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

//顺序表的静态存储
#define N 100
struct SeqList
{
	int a[N];//定长存储
	int size;//有效数据的个数
};

//顺序表的动态存储
typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

顺序表本质上是数组，在数组上增加了两个要求：

1.插入数据的过程中，可以动态增长

2.并且要求里面存储的数据必须是从左往右，是连续的

顺序表的缺陷

1.动态增容有性能消耗

2.头部插入数据时，需要挪动数据

2.2 提供接口

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

首先在头文件<SeqList.h>中提供接口：

typedef int SeqDataType; //需要插入什么类型的数据，就改成对应类型

typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

//内存中管理数据结构 提供增删查改的接口
//顺序表初始化
void SeqListInit(SeqList* pq);
//顺序表销毁
void SeqListDestory(SeqList* pq);
//顺序表打印
void SeqListPrint(SeqList* pq);//打印数组
//检查空间，如果满了，进行增容
void SeqCheckCapacity(SeqList* pq)
//顺序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//顺序表头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* pq);
//顺序表头删
void SeqListPopFront(SeqList* pq);
//顺序表查找x
int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下标，没查到返回-1
//顺序表在指定位置插入数据
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下标pos位置处插入数据
//顺序表在指定位置删除数据
void SeqListErase(SeqList* pq, int pos);//把下标为pos位置处的数据删除
//顺序表在指定位置替换数据
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小标为pos位置的值改为x

2.3 接口实现

在源文件SeqList.c中实现接口功能

（1）顺序表初始化

void SeqListInit(SeqList* pq)
{
	assert(pq != NULL);//或者 assert(pq); 断言 防止传入空指针
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

（2）顺序表销毁

void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

（3）顺序表打印

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

（4）检查空间，如果满了，进行增容

//检查是否需要扩容
void SeqCheckCapacity(SeqList* pq)
{
	//满了，需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);

		//realloc接收的地址如果为空，将像malloc一样，开辟一块新空间
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 开辟的新空间的地址
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//失败了就退出
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

（5）顺序表尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

（6）顺序表头插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

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

（7）顺序表尾删

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	pq->size--;
}

（8）顺序表头删

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

	int begin = 0;
	while (begin < pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

（9）顺序表查找x

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return x;
		}
	}
	return -1;//没找到
}

（10）顺序表在指定位置插入数据

void SeqListInsert(SeqList* pq, int pos, SeqDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->assert(pq);assert(pos >= 0 && pos < pq->size);SeqCheckCapacity(pq);//检查是否需要扩容int end = pq->size - 1;while (end >= pos){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->pq->a[end + 1] = pq->a[end];end--;}pq->a[pos] = x;pq->size++;}void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	SeqCheckCapacity(pq);//检查是否需要扩容

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

（11）顺序表在指定位置删除数据

void SeqListErase(SeqList* pq, int pos)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);
	int begin = pos;
	while (begin <= pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

（12）顺序表在指定位置替换数据

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	pq->a[pos] = x;
}

主函数的设计大家可以自由发挥，做个简单的测试功能调用函数或是创建菜单栏实现交互都可以。我水平有限，请朋友们谅解！写的不好的地方还请大佬们指出。

下期预告——单链表

到此这篇关于C语言深入浅出讲解顺序表的实现的文章就介绍到这了,更多相关C语言 顺序表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！