1. Toy模板网首页
  2. > Toy博客

【数据结构】实现顺序表

9月前 作者：～yY…s<#> 分类：Toy博客 阅读(69) 违法举报

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

一.介绍顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
【数据结构】实现顺序表,数据结构,c语言,开发语言
顺序表与通讯录类似，可以完成增删查改等功能。在此基础上，还可以实现头插、头删、尾插、尾删以及某位置的插入和删除

二.实现顺序表

1.创建多文件

用多文件的好处在通讯录一文中已经说明过了，所以这里直接进入正题：

SeqList.h——函数和类型的声明
SeqList.c——函数的实现
Test.c——测试顺序表

注：为了方便测试，所以没有Test.c没有菜单，直接进行测试

2.顺序表的存储方式

顺序表可以采用两种存储方式：静态存储和动态存储
本文使用的是动态存储，因为静态存储只适用于确定知道需要存多少数据的场景，空间开多了浪费，开少了不够用。现实中基本都是使用动态顺序表，根据需要动态的分配空间大小。

typedef int SLDataType;//重定义方便类型的修改
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//数据的个数
	int capacity;//容量的大小
}SL;

3.函数的声明

该顺序表要实现的函数有：
1.初始化顺序表
2.清理顺序表
3.打印顺序表
4.扩容
5.尾插
6.尾删
7.头插
8.头删
9.查找
10.修改
11.在pos位置插入
12.在pos位置删除

//初始化
void SLInit(SL* ps);
//清理
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//查找
void SLFind(SL* ps, SLDataType x);
//修改
void SLModify(SL* ps, int pos, SLDataType x);
//在pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
//在pos位置删除
void SLErase(SL* ps, int pos);

4.初始化顺序表

刚开始要对传过来的指针进行断言，防止为空（后面的也是）
使用malloc函数为数组开辟一块空间（容量大小自己定），数据个数初始化为0

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

5.清理顺序表

程序结束前，要对内存进行清理，因为使用了动态开辟函数，所以必须对使用的空间进行释放，防止内存泄漏

void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

6.打印顺序表

因为顺序表是连续的空间，所以打印顺序表的数据用for循环遍历出来就可以了

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

7.扩容

当顺序表的数据满了（等于刚开始开辟的空间大小），就要进行扩容。使用realloc函数，可以对容量进行修改。

void SLCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* ptr = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));
		if (ptr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			ps->a = ptr;
			ps->capacity *= 2;
		}
	}
}

8.尾插

进入尾插这个函数，首先要对检查容量是否已满，满了就扩容。
size是数据个数，数组a[ps->size]是下一个数据的下标，尾插一个数把这个数赋给a[ps->size]就行了，然后size++
【数据结构】实现顺序表,数据结构,c语言,开发语言

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

8.尾删

将最后一个元素置为0，然后size减1

注意：当size为0时就不能再减了，所以对size的范围要断言

【数据结构】实现顺序表,数据结构,c语言,开发语言

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
}

9.头插

头插数据，先要检查容量；定义一个变量end，指向的是最后一个元素的下一个位置，然后利用while循环，end的范围>=0（把原来的首元素挪动才能头插），将最后一个元素放进它的下个位置，循环一次end减1，依次将前一个元素置到后一个元素的地址去，直到将首元素的位置变成空的状态，然后头插，size加1
【数据结构】实现顺序表,数据结构,c语言,开发语言

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCapacity(ps);
	int end = ps->size;
	while (end >= 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

10.头删

定义一个变量begin等于0，指向首元素。用while循环，将后一个元素覆盖前一个元素，每次循环begin加1，直到最后一个元素向前覆盖完就结束，为头的元素就删除了，然后size减1

注意：当size为0时就不能再减了，所以对size的范围要断言

【数据结构】实现顺序表,数据结构,c语言,开发语言

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

11.查找

用for循环遍历顺序表，有与x相同的数就找到了，否则没找到

void SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			printf("找到了\n");
			return;
		}
	}
	printf("没找到\n");
}

12.修改

pos的值经过断言如果是在范围内就直接将pos位置的值修改为x，否则报错

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

13.在pos位置插入

首先对pos的值进行断言，确定其是否在范围内。插入数值，要考虑容量是否已满，所以要检查容量。接下来与头插类似，把pos位置的数据和后面的数据往后挪动，然后在pos位置插入x，size加1

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	SLCapacity(ps);
	int end = ps->size;
	while (end >= pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

13.在pos位置删除

与头删类似，直到最后一个元素向前覆盖完就结束

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

三.全部代码

1.SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;//重定义方便类型的修改
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//数据的个数
	int capacity;//容量的大小
}SL;
//初始化
void SLInit(SL* ps);
//清理
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//查找
void SLFind(SL* ps, SLDataType x);
//修改
void SLModify(SL* ps, int pos, SLDataType x);
//在pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
//在pos位置删除
void SLErase(SL* ps, int pos);

2.SeqList.c

#include "SeqList.h"
//初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}
//清理
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
//打印
void SLPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
//扩容
void SLCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* ptr = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));
		if (ptr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			ps->a = ptr;
			ps->capacity *= 2;
		}
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCapacity(ps);
	int end = ps->size;
	while (end >= 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}
//查找
void SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			printf("找到了\n");
			return;
		}
	}
	printf("没找到\n");
}
//修改
void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}
//在pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	SLCapacity(ps);
	int end = ps->size;
	while (end >= pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//在pos位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int begin = pos;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

3.Test.c

#include "SeqList.h"
void test()
{
	SL s1;
	SLInit(&s1);//初始化

	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushBack(&s1, 5);//测试尾插
	SLPrint(&s1);

	SLPopBack(&s1);
	SLPopBack(&s1);//测试尾删
	SLPrint(&s1);

	SLPushFront(&s1, 10);
	SLPushFront(&s1, 20);
	SLPushFront(&s1, 30);
	SLPushFront(&s1, 40);//测试头插
	SLPrint(&s1);

	SLPopFront(&s1);
	SLPopFront(&s1);//测试头删
	SLPrint(&s1);

	SLFind(&s1, 100);//测试查找

	SLModify(&s1, 2, 99);//测试修改
	SLPrint(&s1);

	SLInsert(&s1, 3, 77);//测试pos位置插入
	SLPrint(&s1);

	SLErase(&s1, 1);//测试pos位置删除
	SLPrint(&s1);

	SLDestroy(&s1);

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

~ ~
【数据结构】实现顺序表,数据结构,c语言,开发语言
感谢观看文章来源地址https://www.toymoban.com/news/detail-652701.html

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C语言数据结构】模拟·顺序表·总项目实现

    【C语言数据结构】模拟·顺序表·总项目实现

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

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

    【数据结构初阶】二、 线性表里的顺序表（C语言实现顺序表）

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

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

    【数据结构】线性表的顺序存储结构及实现——C语言版

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

    2024年03月15日
    浏览(54)
  • 【数据结构】顺序表基本操作的实现（C语言）

    【数据结构】顺序表基本操作的实现（C语言）

    🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。 🐌 个人主页：蜗牛牛啊 🔥 系列专栏：🛹数据结构、🛴C++ 📕 学习格言：博观而约取，厚积而薄发 🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与

    2024年02月16日
    浏览(56)
  • 数据结构之顺序表的实现（C语言版）

    数据结构之顺序表的实现（C语言版）

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

    2024年04月25日
    浏览(48)
  • 【数据结构】详谈队列的顺序存储及C语言实现

    【数据结构】详谈队列的顺序存储及C语言实现

    大家好，很高兴又和大家见面啦！！！ 在上一篇内容中，我们在介绍完队列的基本概念、重要术语以及基本操作后，又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义

    2024年01月21日
    浏览(74)
  • 【数据结构】链表OJ题（顺序表）（C语言实现）

    【数据结构】链表OJ题（顺序表）（C语言实现）

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年02月05日
    浏览(46)
  • 数据结构初阶之顺序表（C语言实现）

    数据结构初阶之顺序表（C语言实现）

    顺序表是数据结构里面很基础的一类，它是线性表的一种，其它线性表还有链表、栈和队列等，今天来和博主一起学习关于顺序表的知识吧。 顺序表，它分为两类： 动态顺序表 和 静态顺序表 ，这两个表的区别就是 前者的空间不固定 ，是 支持扩容 的，后者的 空间是固定

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

    【数据结构】C语言实现顺序栈(附完整运行代码)

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

    2024年04月29日
    浏览(39)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识，以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包