【数据结构——顺序表的实现】

news/2024/11/29 7:47:17/

前言：
在之前我们已经对复杂度进行的相关了解，因此现在我们将直接进入数据结构的顺序表的相关知识的学习。

在这里插入图片描述

目录

  • 1.线性表
  • 2.顺序表
    • 2.1概念及结构
    • 2.2 接口实现
      • 2.2.1.打印顺序表
      • 2.2.2初始化顺序表
      • 2.2.3.容量的检查
      • 2.2.4.销毁顺序表
      • 2.2.5.尾插操作
      • 2.2.6.尾删操作
      • 2.2.7.头插操作
      • 2.2.8.头删操作
      • 2.2.9指定位置处插入数据
      • 2.2.10删除指定位置数据
      • 2.2.11begin查找x的起始位置

1.线性表

定义：

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

线性表的顺序存储示意图如下：
在这里插入图片描述

2.顺序表

2.1概念及结构

定义：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，顺序表中存放数据的特点和数组这种数据类型完全吻合，所以顺序表的实现使用的是数组。在数组上完成数据的增删查改。

注意事项：

数组实现顺序表的存储结构时，一定要注意预先申请足够大的内存空间，避免因存储空间不足，造成数据溢出，导致不必要的程序错误甚至崩溃

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储元素。
#define N  7
typedef int SLDataType;
typedef struct SeqList
{SLDataType a[N];int size; // 记录存储多少个有效数据
}SL;

在这里插入图片描述

静态的顺序表(相当于一个数组，数组长度固定的，存储有效个数据)

  1. 动态顺序表：使用动态开辟的数组存储。
// 动态顺序表 -- 按需扩空间
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size;       // 记录存储多少个有效数据int capacity;   // 空间容量大小 
}SL;

在这里插入图片描述
注意：

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

2.2 接口实现

通常有以下几种接口（接口其实就是实现功能的函数，数据结构以接口称之）

//打印顺序表
void SLPrint(SL* ps);
//初始哈顺序表
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);// 尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);// 头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);// 中间插入删除
// 在pos位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置数据
void SLErase(SL* ps, int pos);//int SLFind(SL* ps, SLDataType x);// begin查找x的起始位置
int SLFind(SL* ps, SLDataType x, int begin);

接下来我们便开始一一实现相应的功能：

2.2.1.打印顺序表

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

2.2.2初始化顺序表

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

assert函数断言传过来的指针是否为空，若为空就直接结束程序 。

2.2.3.容量的检查

void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}

我们在思考如何在顺序表的尾部插入数据时我们会想到一个问题，如果顺序表满了该怎么办呢？我们可以进行扩容，但是扩大多少呢？扩大的容量过大会导致空间的浪费，扩大的太小会导致频繁申请内存，拖慢程序运行速度

这里采用的是检查容量的方式来实现顺序表的动态存储，（size）是已经存入的数据个数，（capacity）是可以存储数据的个数，当存入和容量相等即空间满了的时候，这里采用realloc函数对顺序表进行扩容。因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍。

2.2.4.销毁顺序表

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

2.2.5.尾插操作

思想：在开始进行尾插操作时我们需要先对顺序表进行空间检查的操作来判断是否可以直接进行插入操作。

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

2.2.6.尾删操作

思想：尾删操作我们可以直接进行size–操作，size是我们存入数据的大小，

void SLPopBack(SL* ps)
{//assert(ps);// 温柔的检查///*if (ps->size == 0)//{//return;//}*/// 暴力的检查assert(ps->size > 0);ps->a[ps->size - 1] = 0;ps->size--;
}

2.2.7.头插操作

思想：首先我们还是先对容量进行检查，看线性表的容量是否充足。具体的思想就是每次插入就将第一个数据位置空出来，将每个元素依次向后移动一个位置，我们采用从后向前移动的方法，因为从前往后覆盖的话会导致我们后一个数据被覆盖。

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);// 挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

注意：
我们可以看出头插操作我们的时间复杂度为O(n)，而尾插操作的时间复杂度为O(1)。因此我们看出两种方法的优劣。

2.2.8.头删操作

思想：还是先检查我们线性表的容量大小，因为删除一个数据我们就需要进行相应的覆盖的操作，具体思路还是将线性表的第二个元素开始后继整体向前移动一个元素，这里是从前向后进行操作，如果从后向前依次挪动，则会造成顺序表中数据被覆盖导致内容未被修改。

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

2.2.9指定位置处插入数据

思想：对指定的位置进行插入操作，如果我们进行插入的位置不符合我们的规范，检查顺序表的空间是否充足才能用来进行插入数据，在指定位置进行插入操作，将我们要插入位置向后进行移动，腾出相应的空间位置在进行插入操作，具体代码如下：

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

2.2.10删除指定位置数据

思想：我们进行指定位置删除操作，具体思想就是将指定位置之后的所有元素向前挪移一个元素，将我们要删除元素的位置覆盖掉，采用从后向前覆盖的方式，值得注意的是越界的问题。

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0);assert(pos < ps->size);//assert(ps->size > 0);// 挪动数据覆盖int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

2.2.11begin查找x的起始位置

思想：begin为我们查找的位置，查找到begin位置所对应的下标，即找到我们的所需，如果找不到则返回-1

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

总结：以上就是对于线性表的实现操作，大家认真整理，下期我们用相应的题目进行相应的练习加深认识，最后祝大家新年快乐！


http://www.ppmy.cn/news/18570.html

相关文章

bfs入门教程（广度优先搜索）（含图解）

bfs入门教程（广度优先搜索）（含图解）

源自《啊哈算法》 目录 bfs正文 题目 思路 完整代码1 完整代码2 再解炸弹人 题目 思路 完整代码1 完整代码2 总结 bfs正文 第四章--深度优先搜索中&#xff0c;我们用dfs找到了寻找小哈的最短路径 接下来&#xff0c;我们要用bfs&#xff08;Breadth First Sear…
阅读更多...
DPU网络开发SDK——DPDK(九)

DPU网络开发SDK——DPDK(九)

rte_eal_remote_launch() 在过去的几篇文章中&#xff0c;我们重点分析了DPDK初始化过程rte_eal_init()的主要流程&#xff0c;了解了其内存分配&#xff0c;primary和secondary之间如何实现数据共享。Hello world例子中&#xff0c;在DPDK初始化完成之后&#xff0c;调用rte_…
阅读更多...
软件测试复习10：测试文档

软件测试复习10：测试文档

专栏&#xff1a;《软件测试》 个性签&#xff1a;顺境不惰&#xff0c;逆境不馁&#xff0c;以心制境&#xff0c;万事可成。——曾国藩 测试大纲&#xff1a;招标用&#xff0c;总体策略&#xff0c;对软件的了解&#xff0c;测试人员&#xff0c;资质等。 测试计划&#…
阅读更多...
Python基础学习一

Python基础学习一

注释 单行注释 # 注释 # 后面直到行尾。 #!/usr/bin/python3# 第一个注释 print ("Hi, I love Python!") # 第二个注释执行以上的代码&#xff0c;结果输出如下&#xff1a; Hi, I love Python!多行注释 以 3 个单引号开头(‘’‘)&#xff0c;并在注释结束的位置…
阅读更多...
【数据结构与算法】详解二叉树以及模拟实现二叉树

【数据结构与算法】详解二叉树以及模拟实现二叉树

文章目录前言:1.二叉树的定义2.二叉树的相关术语3.二叉树的性质4.特殊的二叉树5.二叉树的遍历前序遍历中序遍历后序遍历层序遍历6.获取树中节点的个数方法1:遍历思想方法2:子问题的思想7.获取叶子节点的个数方法1:遍历思想方法2:子问题的思想8.获取第K层节点的个数9.获取二叉树…
阅读更多...
处理查询结果集

处理查询结果集

package com.bjpowernode.jdbc;import java.sql.*; /**处理查询结果集提醒&#xff1a;JDBC中所有的下标都是从1开始的。*/ public class 处理查询结果集 {public static void main(String[] args){Connection conn null;Statement stmt null;ResultSet rs null;try{//1、注…
阅读更多...
自增id用完怎么办？

自增id用完怎么办？

MySQL 里有很多自增的 id，每个自增 id 都是定义了初始值，然后不停地往上加步长。虽然自然数是没有上限的，但是在计算机里，只要定义了表示这个数的字节长度，那它就有上限。比如，无符号整型 (unsigned int) 是 4 个字节，上限就是 232-1。 既然自增 id 有上限，就有可能被…
阅读更多...
函数——“C”

函数——“C”

各位CSDN的uu们新年快乐呀&#xff0c;祝大家越来越开心&#xff0c;越来越优秀。那行&#xff0c;让我们进入今天的正题&#xff0c;来了解了解函数&#xff0c;函数是什么&#xff0c;C语言中函数是如何分类的&#xff0c;函数参数&#xff0c;函数调用等一系列小知识点&…
阅读更多...
最新文章

Copyright @ 2022~2023