【初阶数据结构之顺序表实现】

每天都要进步呀

发布于 2023-03-28 11:22:17

2210

发布于 2023-03-28 11:22:17

文章被收录于专栏：C++/Linux

初阶数据结构之动态顺序表实现

顺序表

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

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

提示：由于静态功能有限，这里主要讨论动态顺序表

一、顺序表的构造VS功能

1.顺序表的构造

示例：

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

这里使用SeqDataType定义是由于我们不知道a是什么类型的数组，因此我们要灵活运用功能就要事先定义SeqDataType的类型（此例为int），以便后续结构类型改变时容易操作

2.接口实现（功能）

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);

二、功能具体分析

1.初始化

在实现具体项目功能之前，要事先做好准备，即初始化，将其置空，assert函数下文讲解代码如下（示例）：

void SeqListInit(SeqList* pq)//初始化
{
	assert(pq);//断言，判断是否可以执行1/0
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

2.销毁

销毁是在结束之后需要进行的操作，因为这里是动态，需要考虑空间释放，以免造成空间泄露。（先提到销毁是因为其与初始化为首位）代码如下（示例）：

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

3.检查size与capacity是否溢出

动态进行就是根据输入的数据改变自身数组的大小，故我们需要对溢出的情况进行正确的规避，至于为什么会溢出，因为我们在初始化的时候将其空间为0，无论第一次输入多少数据都会溢出。

void SeqCheckCapacity(SeqList* pq)
{
	if (pq->size == pq->capacity)//满了，需要增容
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
	//SeqDataType* newA = malloc(sizeof(SeqDataType) * newcapacity);
	  SeqDataType* newA  =realloc(pq->a,sizeof(SeqDataType)* newcapacity);//或者直接扩容
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

习惯上在扩容时我们习惯将其放大二倍的操作，由于realloc扩容分为两种情况（这里暂时不讨论），故如果扩容失败我们需要截止，并打印错误。

4.尾增功能（实现）

先上代码：

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);
	pq->a[pq->size] = x;
	pq->size++;
}

顾名思义就是在尾部增添内容，size正对应有效数组下标的下一位，对该位置进行赋值，最后有效数组size应+1，由于尾增之前我们不知道其capacity是否等于size 故我们需要进行检查seqCheckCapacity，如果相等，则需要扩容。

5.打印

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

这里具体就没什么了，只是为了保证程序功能能够具体完整实现 其他功能看下面代码

三。实现具体功能代码页（SeqList.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
#include<assert.h>
void SeqListInit(SeqList* pq)//初始化
{
	assert(pq);//断言，判断是否可以执行1/0
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}
void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}
void SeqCheckCapacity(SeqList* pq)
{
	if (pq->size == pq->capacity)//满了，需要增容
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
	//SeqDataType* newA = malloc(sizeof(SeqDataType) * newcapacity);
	  SeqDataType* newA  =realloc(pq->a,sizeof(SeqDataType)* newcapacity);//或者直接扩容
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}
void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	assert(pq);
	SeqCheckCapacity(pq);
	pq->a[pq->size] = x;
	pq->size++;
}

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

}
void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	--pq->size;
}
void SeqListPopFront(SeqList* pq)
{
    assert(pq);
	for (int i = 0; i < pq->size - 1; i++)
	{
		pq->a[i] = pq->a[i + 1];
	}
	if(pq->size)
	  pq->size--;
}

三(补）.test.c主函数代码页

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include"SeqList.h"

void TestSeqList1()
{
	SeqList s;
	SeqListInit(&s);//ʼ


	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, 0);

	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);
	SeqListPopBack(&s);


	SeqListPrint(&s);

	

	



	SeqListDestory(&s);//

}
int main()
{
	TestSeqList1();
	return 0;
}