【数据结构】顺序表

2024-06-06 09:50:03
开发
8

顺序表概览

SeqList.h

数据类型定义

顺序表概览

SeqList.h

这个头文件定义了顺序列表的数据结构和相关操作函数的原型声明。

//SeqList.h

#pragma once

#include<stddef.h>//NULL
#include<stdlib.h>//free
#include<assert.h>//assert

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int capacity;
	int size;
} SeqList;	

void SLInit(SeqList* pSL);
void SLDestroy(SeqList* pSL);
void SLPushBack(SeqList* pSL, SLDataType x);
SLDataType SLPopBack(SeqList* pSL);
void SLPushFront(SeqList* pSL, SLDataType x);
SLDataType SLPopFront(SeqList* pSL);
void SLInsert(SeqList* pSL, int pos, SLDataType x);
SLDataType SLErase(SeqList* pSL, int pos);

数据类型定义

SLDataType: 作为顺序表中存储元素的数据类型，这里被定义为整型int。

SeqList: 结构体类型，包含三个成员：

a: 指向动态数组的指针，用于存储数据。

capacity: 当前分配的容量。

size: 实际已存储元素的数量。

函数原型声明

SLInit: 初始化顺序表，分配初始内存并设置初始状态。

SLDestroy: 释放顺序表所占用的内存资源。

SLPushBack: 在顺序表末尾添加元素。

SLPopBack: 移除并返回顺序表末尾的元素。

SLPushFront: 在顺序表开头添加元素。

SLPopFront: 移除并返回顺序表开头的元素。

SLInsert: 在指定位置插入元素。

SLErase: 删除指定位置的元素并返回它。

SeqList.c

这个文件实现了头文件中声明的所有函数。

//SeqList.c

#include"SeqList.h"

static void checkcapacity(SeqList* pSL)
{
	if (pSL->capacity == pSL->size)
	{
		int newcapacity = pSL->capacity == 0 ? 4 : 2 * pSL->capacity;
		SLDataType* temp = realloc(pSL->a, sizeof(SLDataType) * newcapacity);
		if (NULL == temp)
		{
			perror("realloc failed");
			exit(-1);
		}
		pSL->a = temp;
		pSL->capacity = newcapacity;
	}
}

void SLInit(SeqList* pSL)
{
	pSL->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (NULL == pSL->a)
	{
		perror("malloc failed");
		exit(-1);
	}
	pSL->capacity = 0;
	pSL->size = 0;
}

void SLDestroy(SeqList* pSL)
{
	free(pSL->a);
	pSL->a = NULL;
	pSL->capacity = pSL->size = 0;
}


void SLInsert(SeqList* pSL, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= pSL->size);
	checkcapacity(pSL);
	for (int i = pSL->size - 1; i >= pos; --i)
		pSL->a[i + 1] = pSL->a[i];
	pSL->a[pos] = x;
	++pSL->size;
}

SLDataType SLErase(SeqList* pSL, int pos)
{
	assert(pos >= 0 && pos < pSL->size);
	assert(pSL->size);
	SLDataType ret = pSL->a[pos];
	for (int i = pos; i < pSL->size - 1; ++i)
		pSL->a[i] = pSL->a[i + 1];
	--pSL->size;
	return ret;
}

void SLPushBack(SeqList* pSL, SLDataType x)
{
	SLInsert(pSL, pSL->size, x);
}

SLDataType SLPopBack(SeqList* pSL)
{
	return SLErase(pSL, pSL->size - 1);
}

void SLPushFront(SeqList* pSL, SLDataType x)
{
	SLInsert(pSL, 0, x);
}

SLDataType SLPopFront(SeqList* pSL)
{
	return SLErase(pSL, 0);
}

主要函数实现

SLInit: 分配初始内存，初始化容量和大小为0。

SLDestroy: 释放内存并重置顺序表的状态。

SLInsert: 扩容检查后，在指定位置插入元素，移动后续元素。

SLErase: 删除指定位置的元素，移动后续元素并返回删除的值。

SLPushBack, SLPopBack, SLPushFront, SLPopFront: 分别是SLInsert和SLErase的特例，分别处理表尾和表头的插入与删除。

辅助函数

checkcapacity: 检查顺序表的当前容量，如果需要扩展，则会加倍当前容量（首次扩展到4）。使用realloc来调整数组大小.

test.c

这是测试顺序表功能的主程序文件。整体上，这段代码展示了顺序表的基本操作和管理，包括初始化、元素的增删改查以及内存管理，通过测试函数test1验证了这些操作的正确性。

//test.c

#include"SeqList.h"
#include<stdio.h>

static void print(SeqList SL);

//快捷测试
/*
SeqList sl; 
SLInit(&sl);
SLDestroy(&sl);
//尾插
SLPushBack(&sl, 6);print(sl);
//尾删
SLPopBack(&sl);print(sl);
//前插
SLPushFront(&sl, 6);print(sl);
//头删
SLPopFront(&sl);print(sl);
//插入
SLInsert(&sl, 3, 88);print(sl);
//删除
SLErase(&sl, 2);print(sl);
*/

void test1()
{
	SeqList sl; 
	SLInit(&sl);

	SLPushBack(&sl, 6); print(sl);
	SLPushBack(&sl, 1); print(sl);
	SLPushBack(&sl, 2); print(sl);
	SLPushFront(&sl, 3); print(sl);
	printf("SLPopFront = %d\n", SLPopFront(&sl)); print(sl);
	printf("SLPopBack = %d\n", SLPopBack(&sl));  print(sl);
	SLInsert(&sl, 1, 88); print(sl);
	printf("SLErase = %d\n", SLErase(&sl, 1));  print(sl);

	SLDestroy(&sl);
}

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



void print(SeqList SL)
{
	for (int i = 0; i < SL.size; ++i)
	{
		printf("%d ", SL.a[i]);
	}
	printf("\n");
}

测试流程 (test1函数)

初始化一个顺序列表 sl。

向顺序表尾部添加元素6，打印当前列表。

继续向尾部添加元素1和2，打印列表。

向顺序表头部添加元素3，打印列表。

弹出并打印顺序表的第一个元素（此时应为3），打印列表。

弹出并打印顺序表的最后一个元素（此时应为2），打印列表。

在索引1处插入数字88，打印列表。

删除索引1处的元素（即刚插入的88）并打印出来，打印列表。

销毁顺序表，释放资源。

辅助函数

print(SeqList SL): 打印顺序表中的所有元素。

难点图解

头插函数（辅助理解插入函数）

void SLPushFront(SeqList* pSL, SLDataType x)
{
	checkcapacity(pSL);
	for (int i = pSL->size - 1; i >= 0; --i)
		pSL->a[i + 1] = pSL->a[i];
	pSL->a[0] = x;
	++pSL->size;
}

调用checkcapacity: 在尝试在顺序表前端插入元素之前，首先调用checkcapacity函数。这个函数会检查顺序表当前的容量是否足够容纳新的元素。如果当前的元素数量（size）已经等于分配的容量（capacity），则会执行扩容操作。扩容通常会使容量翻倍，以确保有足够的空间存放新元素。

元素右移: 为了在序列的最前面插入元素，代码通过一个从pSL->size - 1到0的逆向循环，将现有的每个元素向右移动一位。这意味着原数组的每个元素都将覆盖它右侧的元素，为新元素腾出位置pSL->a[0]。这个过程确保了列表中原有的元素顺序保持不变，只是整体向后移动了一位。

插入新元素: 在完成元素的移动后，将新元素x插入到数组的第一个位置pSL->a[0]。

增加size计数: 最后，增加顺序表的size属性，表示列表中元素数量增加了1。

头删函数（辅助理解删除函数）

SLDataType SLPopFront(SeqList* pSL)
{
	assert(pSL->size);
	SLDataType ret = pSL->a[0];
	for (int i = 0; i < pSL->size - 1; ++i)
		pSL->a[i] = pSL->a[i + 1];
	--pSL->size;
	return ret;
}

断言检查: 首先，使用assert(pSL->size);来确保顺序列表中至少有一个元素。如果pSL->size为0，即列表为空，assert会导致程序终止，并报告错误，这是一种在调试阶段检查逻辑错误的方法。

保存并返回第一个元素: 将顺序列表的第一个元素pSL->a[0]的值保存在变量ret中，这是待返回的结果。

元素左移: 通过一个从0到pSL->size - 2的循环，将顺序表中的每个元素向前移动一位，覆盖掉原来位于它前面的元素。这样做是为了填补被移除元素留下的空位，同时保持剩余元素的连续性和正确顺序。

减小列表大小: 在元素移动完毕后，将顺序列表的size属性减一，表示列表中少了一个元素。

返回结果: 最后，函数返回最初保存的ret，即被移除的顺序列表最前端的元素值。

插入函数的实现过程

void SLInsert(SeqList* pSL, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= pSL->size);
	checkcapacity(pSL);
	for (int i = pSL->size - 1; i >= pos; --i)
		pSL->a[i + 1] = pSL->a[i];
	pSL->a[pos] = x;
	++pSL->size;
}

容量检查: 首先调用checkcapacity静态函数检查顺序表当前的容量是否足够。如果当前元素数量等于容量（即满），则会触发扩容。扩容策略是：如果当前容量为0，则新容量设为4；否则，新容量翻倍。使用realloc函数完成数组的重新分配。

参数验证: 使用assert宏确保传入的位置pos是有效的，即它必须位于当前大小之内或正好等于当前大小（允许在末尾插入）。

元素移动: 为了在指定位置pos插入元素，需要将位置pos及其之后的所有元素向右移动一位。这通过一个从pSL->size - 1到pos的逆序循环实现，每次循环将当前元素赋值给下一个位置。

插入元素: 循环结束后，将新元素x插入到空出来的位置pos。

更新大小: 增加顺序表的大小pSL->size，表示已成功插入一个新元素。

删除函数的实现过程

SLDataType SLErase(SeqList* pSL, int pos)
{
	assert(pos >= 0 && pos < pSL->size);
	assert(pSL->size);
	SLDataType ret = pSL->a[pos];
	for (int i = pos; i < pSL->size - 1; ++i)
		pSL->a[i] = pSL->a[i + 1];
	--pSL->size;
	return ret;
}

参数验证: 使用assert宏确保位置pos有效且顺序表非空，即pos必须在有效范围内（0到pSL->size - 1之间）且顺序表中有元素。

保存并返回要删除的元素: 获取并存储即将被删除的元素pSL->a[pos]，这是要返回给调用者的值。

元素移动: 将位置pos + 1到pSL->size - 1之间的所有元素向左移动一位，覆盖掉被删除的元素。这通过一个从pos到pSL->size - 2的循环实现，每次循环将当前元素前移一位。

减小大小: 更新顺序表的大小pSL->size，减去1，以反映元素已被删除。

原文地址:https://blog.csdn.net/weixin_73483158/article/details/139480697 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1798532774064427008.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部