数据结构:顺序表(C实现)

这篇具有很好参考价值的文章主要介绍了数据结构:顺序表(C实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构:顺序表(C实现),数据结构,数据结构,c语言,算法

个人主页 水月梦镜花
个人专栏 C语言 ,数据结构



一、顺序表

顺序表是用一段物理结构连续的存储单元依次存储数据元素的线性结构,一般采用数组存储。
顺序表一般分为两种:

  • 静态顺序表:使用定长数组实现
  • 动态顺数表:使用动态开辟的数组实现

本篇文章,顺序表是使用动态开辟的数组实现(动态顺序表)。要实现的功能如下:

//初始化顺序表
void SeqListInit(SeqList* ps);

//销毁顺序表
void SeqListDestroty(SeqList* ps);

//打印顺序表
void SeqListPrint(SeqList* ps);

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);

//顺序表尾删
void SeqListPopBack(SeqList* ps);

//顺序表头删
void SeqListPopFront(SeqList* ps);

//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//检查容量
void SeqListCheckCapacity(SeqList* ps);

二、实现思路

画图理解起来更佳!!!

1.存储结构

我们重命名int类型为SLDataType,方便以后我们修改顺序表存储元素的类型。
指针data指向动态开辟的空间,变量sz记录有效的数据元素,变量capacity记录动态开辟空间的大小。

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* data;
	int sz;
	int capacity;
}SeqList;

2.初始化顺序表(SeqListInit)

动态开辟一块空间,用data指针保存空间首地址。
此时data指向空间中有效元素为0,使sz == 0,变量capacity在等于此时开辟空间的大小。

#define SIZE 4

void SeqListInit(SeqList* ps)
{
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->sz = 0;
	ps->capacity = SIZE;
}

3.销毁顺序表(SeqListDestroty)

free所开辟的空间,使data == NULL,此时数据有效元素为0,空间大小为0,那么sz = 0,capacity = 0;

//销毁顺序表
void SeqListDestroty(SeqList* ps)
{
	assert(ps);

	//free(ps);
	free(ps->data);
	ps->data = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}

4.打印顺序表(SeqListPrint)

这个函数非常简单,只要遍历一遍所开辟的空间即可,注意范围是(0,sz)。

//打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);

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

}

5.顺序表尾插(SeqListPushBack)and检查容量(SeqListCheckCapacity)

每次加入数据时,我们要先检查空间大小是否充足,再加入数据

  • 检查容量
    在尾插数据前,要检查空间大小是否充足(sz == capacity),如果空间大小不够,要扩大空间大小,capacity记录新的空间大小。

  • 尾插元素
    变量sz不仅代表空间有效元素个数,也代表了新数据元素将要放入的位置。所以尾插元素,只要空间大小充足,那么在data[sz]处放入数据即可,不要忘记sz要加一。

//检查容量
void SeqListCheckCapacity(SeqList* ps)
{
	SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2);
	if (tmp == NULL)
	{
		perror("realloc");
		exit(-1);
	}

	ps->data = tmp;
	ps->capacity *= 2;
}



//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	ps->data[ps->sz] = x;
	ps->sz++;
}

6.顺序表头插(SeqLsitPushFront)

顺序表除了尾插,尾删不用挪到数据,其它的增删都要挪到数据。
头插数据,要先检查空间大小,再向后挪到数据,将数据放入data[0]处,sz在加一。

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[0] = x;
	ps->sz++;
}

7.顺序表尾删(SeqListPopBack)

变量sz代表有效数据的个数,那么只要sz减一,就代表最后一个数据被删除了。

//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->sz != 0);

	ps->sz--;
}

8.顺序表头删(SeqListPopFront)

头删数据,要将数据从后向前挪到,覆盖掉第一个数据,sz要减一。

//顺序表头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->sz != 0);

	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

9.顺序表查找(SeqListFind)

遍历一遍动态开辟的数组,如果找到了就放回下标,没有就放回-1。

//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

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

	return -1;
}

10.在pos位置前插入元素(SeqListInsert)

要先检查空间容量是否充足和要插入的位置是否合法(要在顺序表的有效数据内),再将pos下标后的数据向后挪到,将数据放入data[pos]处,sz加一。
这个函数思路简单,但要注意下面两点:

  • 如果pos == 0,不就是要在顺序表第一个元素前插入元素,不就是顺序表的头插。
  • 如果pos == sz,我们知道sz还表示下一个数据要放入的位置,那么我在下一个数据要放入的位置前插入元素,不就是顺序表的尾插。

理解这点后,我们以后的头插,尾插都可以用该函数复用。方便我们手撕顺序表

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->sz);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->sz++;
}

11.删除pos位置的值(SeqListErase)

删除pos位置处的数据,先检查pos的合法性(要属于[0,sz-1]),要将数据从后向前挪到数据,sz减一。
这个函数思路简单,但要注意下面两点:

  • 如果pos == 0,不就是要删除第一个数据,不就是头删。
  • 如果pos == sz - 1,不就是要删除最后一个数据,不就是尾删。

所以对于尾删,头删函数而言,我们也可以使用该函数复用。

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->sz);

	for (int i = pos; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

三、代码实现

头删,头插,尾删,尾插我都复用了SeqListInsert和SeqListErase。
SeqList.h 文件存放有关函数的声明以及结构体的声明
SeqList.c 文件存放函数的定义

//SeqList.h 文件

#pragma once

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

#define SIZE 4

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* data;
	int sz;
	int capacity;
}SeqList;



//初始化顺序表
void SeqListInit(SeqList* ps);

//销毁顺序表
void SeqListDestroty(SeqList* ps);

//打印顺序表
void SeqListPrint(SeqList* ps);

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);

//顺序表尾删
void SeqListPopBack(SeqList* ps);

//顺序表头删
void SeqListPopFront(SeqList* ps);

//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//检查容量
void SeqListCheckCapacity(SeqList* ps);
//SeqList.c 文件

#include "SeqList.h"


//初始化顺序表
void SeqListInit(SeqList* ps)
{
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->sz = 0;
	ps->capacity = SIZE;
}

//检查容量
void SeqListCheckCapacity(SeqList* ps)
{
	SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2);
	if (tmp == NULL)
	{
		perror("realloc");
		exit(-1);
	}

	ps->data = tmp;
	ps->capacity *= 2;
}



//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	/*assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	ps->data[ps->sz] = x;
	ps->sz++;*/

	SeqListInsert(ps, ps->sz, x);
}


//打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);

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

}


//销毁顺序表
void SeqListDestroty(SeqList* ps)
{
	assert(ps);

	//free(ps);
	free(ps->data);
	ps->data = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}


//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{
	/*assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[0] = x;
	ps->sz++;*/

	SeqListInsert(ps, 0, x);
}


//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	/*assert(ps);
	assert(ps->sz != 0);

	ps->sz--;*/

	SeqListErase(ps, ps->sz - 1);
}

//顺序表头删
void SeqListPopFront(SeqList* ps)
{
	/*assert(ps);
	assert(ps->sz != 0);

	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;*/

	SeqListErase(ps, 0);
}


//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

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

	return -1;
}


//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->sz);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->sz++;
}


//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->sz);

	for (int i = pos; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

总结

以上就是顺序表的实现。谢谢支持!!!

数据结构:顺序表(C实现),数据结构,数据结构,c语言,算法文章来源地址https://www.toymoban.com/news/detail-612662.html

到了这里,关于数据结构:顺序表(C实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】C语言实现顺序表

    顺序表是用顺序存储方式存放的线性表(可以理解为数组的存储方式),表中的元素在内存中彼此相邻。 静态存储:在定义时就确定了顺序表的大小,并且之后顺序表的大小不会改变(即使之后空间不够用了,也无法增加) 动态存储:线性表的大小可以根据需要更改(顺序

    2024年02月08日
    浏览(40)
  • 数据结构:定长顺序串(SString)基本操作的算法描述(C语言)

    作者在学习数据结构时,发现鲜有完全按照 C 语言描述的算法操作,这让习惯于写 .c 而不是 .cpp 的初学者很是头疼。本文将基于 C 语言描述算法操作,如有错漏还望大佬们指正。 本文将按照严惠敏所著《数据结构(C语言版)》所做的函数原型声明进行算法描述,由于C语言不支

    2024年02月07日
    浏览(70)
  • 【数据结构】C语言实现顺序表(超级详细)

    目录 概念及结构 接口函数实现 顺序表的初始化 容量判断  顺序表尾插  顺序表尾删 顺序表头插 顺序表头删 顺序表查找 顺序表指定位置插入 顺序表指定位置删除 打印顺序表 销毁顺序表 顺序表完整代码 顺序表作为线性表的一种,它是用一段 物理地址连续的存储单元依次

    2024年04月10日
    浏览(36)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(33)
  • 【C语言数据结构】模拟·顺序表·总项目实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 我在上一篇博客中,

    2024年02月15日
    浏览(41)
  • 【数据结构】:实现顺序表各种基本运算的算法

    领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。 编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能: 初始化顺序表L 依次插入a,b,c,d,e元素 输出顺序表L 输出顺

    2024年02月07日
    浏览(44)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(42)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(52)
  • 【数据结构】C语言实现顺序栈(附完整运行代码)

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 在本次项目中我们的目标是 实现一个 顺序栈 : 该 顺序栈 使用 动态内存分配空间 ,可以用来 存储任意数量的同类型数据 . 顺序栈 结构体 需要包含 三个要素 : 存放数据的数组arr,栈顶元素下标top

    2024年04月29日
    浏览(39)
  • 数据结构之顺序表的实现(C语言版)

         Hello, 大家好,我是一代,今天给大家带来有关顺序表的有关知识      所属专栏:数据结构      创作不易,望得到各位佬们的互三呦 1.首先在讲顺序表之前我们先来了解什么是数据结构 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据?常见的数值1、

    2024年04月25日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包