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

数据结构与算法—顺序表

7月前 作者：Han同学 分类：Toy博客 阅读(27) 违法举报

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

目录

一、线性表

二、顺序表概念

 三、实现顺序表

1、声明结构体

2、初始化

3、打印数据 

4、销毁 

5、尾插&头插

尾插

判断是否扩容 

 头插

6、尾删&头删

尾删

头删

7、 指定位置插入元素

8、 删除指定位置元素

9、 查找指定元素位置

10、修改指定位置元素

完整版附上：

Seqlist.h

Seqlist.c

 text.c

一、线性表

  • 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
  • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
  • 线性表在物理上存储时，通常以数组和链式结构的形式存储。
数据结构与算法—顺序表,数据结构,数据结构

二、顺序表概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。数据结构与算法—顺序表,数据结构,数据结构

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

数据结构与算法—顺序表,数据结构,数据结构

 三、实现顺序表

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

 我们创建三个文件：

  1. Seqlist.h用于存放头文件、结构体和函数的声明
  2. text.c作为主程序进行运行和测试
  3. Seqlist.c存放函数主体

1、声明结构体

#include <stdio.h>

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;
  • 在头文件中声明结构体struct SeqList，由于名字太长，我们用typedef自定义结构体名称的别名为SL。
  • 将顺序表的数据类型用SLDatatype这个别名代替int，以后程序中使用到元素数据类型时都替换成SLDatatype，方便日后修改顺序表数据类型。
  • 定义size存储当前元素个数，capacity存储顺序表容量。

2、初始化

void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}
  • 需要改变结构体变量，则将其地址传入函数。
  • assert检测传参顺序表指针是否合法，如果传入参数为空则报错（具体哪行出错）。
  • 然后为结构体成员a分配4个成员类型空间，顺便检查是否分配成功。
  • 对成员size和capacity分别复制为0（当前元素个数）和4（顺序表容量）。

3、打印数据 

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

  • assert检测传参顺序表指针是否合法，然后循环遍历输出。

4、销毁 

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

  • assert检测传参顺序表指针是否合法。

  • 释放动态开辟a的空间，同时赋值为空，不置空可能会造成野指针的访问。

  • size和capacity分别赋值为0。

5、尾插&头插

尾插

void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
    SLCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作我们在函数SLCheckCapacity内进行。

  • 将 x 赋值给 psl->a 数组中下一个可用的位置，即 psl->size 索引处。

  • 递增 psl->size，以便记录新元素的加入。

 接下来我们来讲解函数SLCheckCapacity：

判断是否扩容 

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}

  •  判断当前元素个数size与顺序表容量capacity是否相等，相等则对结构体成员指针a进行扩容。

  • 通过realloc函数对a的内存进行扩容，每次增加一倍容量，并将reallocd的返回值新空间的起始地址赋值给SLDatatype类型指针 tmp，这样避免直接对a开辟空间时发生错误丢失数据。

  • 检测是否成功扩容。

  • 最后将存放新空间地址的tmp赋值给a。

  • 顺序表的容量也随之扩大为原来的两倍。

我们还可以优化一下尾插函数，具体如下： 

void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;
}

 头插

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

  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

  • 将新元素 x 插入到顺序表的开头

  • 顺序表元素个数 size 增加1

6、尾删&头删

尾删

void SLPopBack(SL* psl)
{
	assert(psl);

	//暴力判断
	assert(psl->size == 0);

	//常规判断
	//if (psl->size == 0)
	//	return;

	psl->a[psl->size - 1] = 0;
	psl->size--;
}

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

  • 我们还可以通过顺序表元素个数判断，if语句判断size为0时，函数停止运行。

  • 顺序表大小不为空，则对最后一个元素进行删除，赋值为0。

  • 顺序表大小size减1.

头删

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

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

  • 定义变量start为首元素下标.

  • 头删不用赋值为0，直接从第一个元素开始后项赋值给前项。

7、指定位置插入元素

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

  • 参数pos为要在第几个元素后插入。

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

  • 顺序表元素个数 size 增加1。

  • 将新元素 x 插入到顺序表指定元素位置之后。

 SLInsert这个函数可以代替头插尾插函数进行顺序表元素的增加。

8、删除指定位置元素

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

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 定义变量start存储pos位置后一项的下标。

  • 将删除元素后一项位置的值开始从pos+1向后依次前移一位，顶替pos位置。

  • 顺序表元素个数减一。

这个函数就可以完全代替头删尾删了。

9、查找指定元素位置

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;
}

  •  assert检测传参顺序表指针是否合法。

  • 循环遍历顺序表找出于x相等的元素，返回其下标。

  • 找不到返回-1。

10、修改指定位置元素

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

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 将pos位置的值修改为x。

完整版附上：

Seqlist.h

#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* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SLFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"

void SLInit(SL* psl)//初始化
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;//每次开辟的容量为四个
}

void SLPrint(SL* psl)//打印数据
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->a[i]);
	}
}

void SLDestroy(SL* psl)//结束使用需要销毁
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		//增加一倍容量
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
	
}

void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	assert(psl);
	//psl->a[psl->size] = x;
	//psl->size++;
	//插入需要判断a是否已满，已满需要扩容
	SLCheckCapacity(psl);
	//或者写成一句
	psl->a[psl->size++] = x;//后置自增
}

void SLPushFront(SL* psl, SLDatatype x)//头插
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
void SLPopBack(SL* psl)
{
	assert(psl);//尾删
	//暴力判断
	//assert(psl->size == 0);
	//常规判断
	if (psl->size == 0)
		return;
	psl->a[psl->size - 1] = 0;
	psl->size--;
}

void SLPopFront(SL* psl)//头删
{
	assert(psl);
	assert(psl->size > 0);
	int start = 0;
	while (start < psl->size) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}

void SLInsert(SL* psl, int pos, SLDatatype x)//指定位置插入元素,可代替头插尾插
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);//判读插入位置是否合法
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->size++;
	psl->a[pos] = x;
}

void SLErase(SL* psl, int pos)//删除指定位置元素，代替头删尾删
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	int start = pos + 1;
	while (start < psl->size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}

int SLFind(SL* psl, SLDatatype x)//查找指定元素位置
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;//找不到返回-1
}

void SLModify(SL* psl, int pos, SLDatatype x)//修改指定位置元素
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	psl->a[pos] = x;
}

 text.c

这里大家可以自行发挥！文章来源地址https://www.toymoban.com/news/detail-713020.html

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 5);
	SLPushBack(&s, 9);
	SLPushBack(&s, 50);
	SLPushFront(&s, 1);
	SLPushFront(&s, 15);
	SLPushFront(&s, 0);
	SLPopBack(&s, 50);
	SLPopFront(&s, 0);
	SLInsert(&s, 2, 555);
	SLErase(&s, 4);


	SLPrint(&s);

	int a=SLFind(&s, 15);
	printf("\n%d\n", a);
	if (a != -1)
		SLErase(&s, a);
	SLPrint(&s);

	SLDestroy(&s);
}

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

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

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

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

相关文章

  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(42)
  • 【数据结构与算法】之顺序表及其实现！

    【数据结构与算法】之顺序表及其实现！

    目录 ​编辑 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日
    浏览(27)

  • 数据结构与算法 --顺序表的创建

    1. 顺序表（Sequence List）是一种线性表的实现方式，通过连续的内存空间存储元素，按照顺序排列。 顺序表的特点包括： 元素在内存中的存储是连续的，通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(36)
  • 【数据结构】：实现顺序表各种基本运算的算法

    【数据结构】：实现顺序表各种基本运算的算法

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

    2024年02月07日
    浏览(34)
  • java数据结构与算法：顺序表SequentiaList

    java数据结构与算法：顺序表SequentiaList

    2024年02月02日
    浏览(32)

  • 数据结构与算法-头歌【1】顺序线性表--课上练

      本意是整理和复习，理解不深或者有错误的评论区提出即可。 只有第一关的代码里面有结构体的定义，其余我只放了功能函数。 任务描述 本关要求按照完成顺序表数据类型定义，并初始化一个顺序线性表。 编程要求 顺序线性表数据结构定义如下： 本关的编程任务是补全

    2023年04月25日
    浏览(28)

  • 数据结构与算法之查找: 顺序查找 (Javascript版)

    顺序查找 思路 遍历数组 找到跟目标值相等元素，就返回它的下标 没有找到，返回-1 算法实现 总结 非常低效，算是入门搜索 时间复杂度：O(n) 对于数组结构或链表结构而言，没什么太多可说的

    2024年02月05日
    浏览(39)
  • 【数据结构与算法】：手搓顺序表（Python篇）

    【数据结构与算法】：手搓顺序表（Python篇）

    一、顺序表的概念 顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从 0 开始递增。 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结

    2024年04月28日
    浏览(23)
  • 【数据结构与算法】掌握顺序栈：从入门到实践

    【数据结构与算法】掌握顺序栈：从入门到实践

       🌱博客主页：青竹雾色间. 🌱系列专栏：数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 顺序栈的实现 初始化栈 判断栈空 判断栈满 入（进）栈 出栈 获取栈顶元素 示例代码 顺序栈的应用前景 当你学习数据结构和算法时，顺序栈（Sequential

    2024年02月08日
    浏览(52)
  • 【数据结构与算法】二、线性表的顺序表示【硬核】

    【数据结构与算法】二、线性表的顺序表示【硬核】

    图书表的顺序存储结构类型定义： 在调用函数的过程中，当形参为引用类型时，实参和形参占用了相同的空间 2.4.1 线性表的基本操作： 2.4.2 线性表L的初始化 2.4.3 销毁和清空线性表L 2.4.4 求线性表L的长度以及判断线性表L是否为空 2.4.5 顺序表的取值（根据位置i获取相应位置

    2023年04月26日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包