C++实现线性表的顺序存储结构

article/2025/9/23 7:18:38

C++实现线性表的顺序存储结构

      线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表的特点

  • 除第一个元素外，其他每一个元素有且仅有一个直接前驱。
  • 除最后一个元素外，其他每一个元素有且仅有一个直接后继。
  • 直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）。

      顺序表是以数组的形式保存的线性表，将线性表中的元素相继存放在一个连续的存储空间中，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
      顺序表的特点：所有元素的逻辑先后顺序与其物理存放顺序一致。

线性表顺序存储结构的优缺点：

  • 优点：可以快速的得到表中任意位置的元素
  • 缺点：1.插入和删除操作需要移动大量元素
               2.当线性表长度变化较大时，难以确定存储空间容量

顺序表的基本操作：

  • 插入：在表头、表尾和第pos个位置插入数据

  • 删除：删除表头、表尾和第pos个位置的数据

  • 修改：修改表头、表尾和第pos个位置的数据

  • 得到数据：得到表头、表尾和第pos个位置的数据

  • 查找：在顺序表中查找数据p，返回位置

  • 计算长度：返回顺序表的长度

  • 打印

一、顺序表类的定义

template<class T>
class SeqList {
public:T *data;int maxSize{};       //能存储的最大数据量int last{};          //当前存储的元素个数（并非元素下标）
public:SeqList();                               //构造函数SeqList(SeqList<T> &list);               //拷贝构造函数~SeqList();                              //析构函数void reSize();                           //增加空间大小void push_first(T p);                    //头插法，在顺序表头插入数据void push_last(T p);                     //尾插法，在顺序表尾插入数据bool push_pos(int pos, T p);             //在顺序表第pos个位置插入数据void pop_first();                        //删除顺序表头数据void pop_last();                         //删除顺序表尾数据bool pop_pos(int pos);                   //删除顺序表第pos个数据void change_first(T p);                  //修改顺序表头数据void change_last(T p);                   //修改顺序表尾数据bool change_pos(int pos, T p);           //修改顺序表第pos个数据bool get_first(T &p);                    //得到顺序表头数据bool get_last(T &p);                     //得到顺序表为数据bool get_pos(int pos, T &p);             //得到顺序表第pos个数据int search(T p);                         //返回顺序表中p相同的第一个元素的下标pos，若不存在则返回-1bool isEmpty();                          //判断顺序表是否为空int size();                              //返回顺序表能存储的最大数据量int length();                            //返回顺序表的长度void print();                            //打印顺序表void clear();                            //清空顺序表void delete_link();                      //摧毁顺序表
};

二、顺序表中函数的实现

1. 基本函数（构造函数、析构函数、判空等函数）：

//构造函数
template<class T>
SeqList<T>::SeqList() {maxSize = 50;       //初始最大存储量为50last = 0;data = new T[maxSize];   //给数组分配空间if (data == NULL)           //动态分配失败{cerr << "存储分配错误！" << endl;exit(1);}
}//拷贝构造函数
template<class T>
SeqList<T>::SeqList(SeqList<T> &list) {maxSize = list.maxSize;last = list.last;data = new T[maxSize];if (data == NULL)           //动态分配失败{cerr << "存储分配错误！" << endl;exit(1);}for (int i = 0; i < maxSize; i++)data[i] = list.data[i];
}//析构函数
template<class T>
SeqList<T>::~SeqList() {delete_link();
}//判断顺序表是否为空
template<class T>
bool SeqList<T>::isEmpty() {return last == 0;
}//返回顺序表能存储的最大数据量
template<class T>
int SeqList<T>::size() {return maxSize;
}//清空顺序表
template<class T>
void SeqList<T>::clear() {delete data;maxSize = 50;last = 0;data = new T[maxSize];
}//摧毁顺序表
template<class T>
void SeqList<T>::delete_link() {delete data;
}

2. 打印函数

      打印顺序表中的数据

//打印顺序表
template<class T>
void SeqList<T>::print() {if (isEmpty())        //空表直接返回return;cout << "线性表数据为： ";for (int i = 0; i < last - 1; i++)cout << data[i] << " ----> ";cout << data[last - 1] << endl;
}

3. 增加空间大小

      当顺序表的空间不足时，调用该函数

//增加空间大小
template<class T>
void SeqList<T>::reSize() {maxSize += 10;T *temp = new T[maxSize];if (data == NULL)           //动态分配失败{cerr << "存储分配错误！" << endl;exit(1);}for (int i = 0; i < maxSize; i++)temp[i] = data[i];delete data;data = temp;
}

4. 插入

  • 头插法

  1. 判断顺序表是否满了，满了则增加空间大小；
  2. 顺序表中的所有元素用for循环进行向后移动一位；
  3. 要插入的元素赋值给数组首元素；
  4. 顺序表当前元素个数加1（ last++ )。

  • 尾插法

  1. 判断顺序表是否满了，满了则增加空间大小；
  2. 要插入的元素赋值给数组第 last 个位置的元素；
  3. 顺序表当前元素个数加1（ last++ )。

  • 在顺序表的第pos个位置插入数据

  1. 判断顺序表是否满了，满了则增加空间大小；
  2. 顺序表中的从第pos-1个位置开始用for循环进行向后移动一位；
  3. 要插入的元素赋值给数组第 pos-1 个位置的元素；
  4. 顺序表当前元素个数加1（ last++ )。

三种插入法代码：

//头插法，在顺序表头插入数据
template<class T>
void SeqList<T>::push_first(T p) {if (last + 1 > maxSize)    //空间不足reSize();last++;for (int i = last - 1; i > 0; i--)   //全部数据后移一位data[i] = data[i - 1];data[0] = p;
}//尾插法，在顺序表尾插入数据
template<class T>
void SeqList<T>::push_last(T p) {if (last + 1 > maxSize)    //空间不足reSize();data[last++] = p;
}//在顺序表第pos个位置插入数据
template<class T>
bool SeqList<T>::push_pos(int pos, T p) {if (pos > last + 1 || pos <= 0)      //不存在第pos个数据return false;if (last + 1 > maxSize)    //空间不足reSize();last++;for (int i = last - 1; i >= pos; i--)   //第pos个数据后面的数据全部后移一位data[i] = data[i - 1];data[pos - 1] = p;return true;
}

5. 删除

头删

  1. 顺序表不为空；
  2. 顺序表中的从第 1 个位置的元素开始用for循环进行向前移动一位；
  3. 顺序表当前元素个数减1（ last - - )。

尾删

  1. 顺序表不为空；
  2. 顺序表当前元素个数减1（ last - - )，覆盖最后一个元素。

删除第pos个数据

  1. 存在第 pos 个数据（即pos <= last && pos > 0）；
  2. 顺序表中的从第 pos-1 个位置的元素开始用for循环进行向前移动一位；
  3. 顺序表当前元素个数减1（ last - - )。

三种删除法的代码：

//删除顺序表头数据
template<class T>
void SeqList<T>::pop_first() {if (isEmpty())        //空表直接返回return;for (int i = 0; i < last - 1; i++)       //从第2个数据开始全部前移一位data[i] = data[i + 1];last--;     //数据个数-1
}//删除顺序表尾数据
template<class T>
void SeqList<T>::pop_last() {if (isEmpty())        //空表直接返回return;last--;     //数据个数-1
}//删除顺序表第pos个数据
template<class T>
bool SeqList<T>::pop_pos(int pos) {if (pos > last || pos <= 0)      //不存在第pos个数据return false;for (int i = pos - 1; i < last - 1; i++)       //从第pos个数据开始全部前移一位data[i] = data[i + 1];last--;     //数据个数-1return true;
}

6. 修改

修改表头数据

  1. 顺序表不为空；
  2. 修改表头数据。

修改表为数据

  1. 顺序表不为空；
  2. 修改表尾数据。

修改第pos个数据

  1. 存在第 pos 个数据（即pos <= last && pos > 0）；
  2. 修改第pos个数据

三种修改法的代码：

//修改顺序表头数据
template<class T>
void SeqList<T>::change_first(T p) {if (isEmpty())        //空表直接返回return;data[0] = p;
}//修改顺序表尾数据
template<class T>
void SeqList<T>::change_last(T p) {if (isEmpty())        //空表直接返回return;data[last - 1] = p;
}//修改顺序表第pos个数据
template<class T>
bool SeqList<T>::change_pos(int pos, T p) {if (pos > last || pos <= 0)      //不存在第pos个数据return false;data[pos - 1] = p;return true;
}

7. 得到数据

得到表头数据

  1. 顺序表不为空；
  2. 返回表头数据。

得到表为数据

  1. 顺序表不为空；
  2. 返回表尾数据。

得到第pos个数据

  1. 存在第 pos 个数据（即pos <= last && pos > 0）；
  2. 返回第pos个数据。

三种方法的代码：

//得到顺序表头数据
template<class T>
bool SeqList<T>::get_first(T &p) {if (isEmpty())        //空表直接返回return false;p = data[0];return true;
}//得到顺序表尾数据
template<class T>
bool SeqList<T>::get_last(T &p) {if (isEmpty())        //空表直接返回return false;p = data[last - 1];return true;
}//得到顺序表第pos个数据
template<class T>
bool SeqList<T>::get_pos(int pos, T &p) {if (pos > last || pos <= 0)      //不存在第pos个数据return false;p = data[pos - 1];return true;
}

8. 查找

返回顺序表中与p相同的第一个元素的下标 pos ，若不存在则返回 -1

//返回顺序表中p相同的第一个元素的下标pos，若不存在则返回-1
template<class T>
int SeqList<T>::search(T p) {for (int i = 0; i < last; i++) {if (data[i] == p)       //与p相同的第一个元素的下标posreturn i;}return -1;      //不存在则返回-1
}

9. 计算长度

返回顺序表的长度

//返回顺序表的长度
template<class T>
int SeqList<T>::length() {return last;
}

三、运行结果

在这里插入图片描述
在这里插入图片描述

四、小结

      C++线性表的顺序存储结构较链式存储结构简单一些，但是顺序存储结构可能会存在较大的空间浪费和数据移动。
      C++顺序表的定义和测试代码都push到github上了，需要的朋友可自行下载：C++线性表的顺序存储结构。欢迎大家来我的博客交流。


http://chatgpt.dhexx.cn/article/eGrL9hiD.shtml

相关文章

顺序表（详解）- C++（线性表顺序存储结构）

顺序表（详解）- C++（线性表顺序存储结构）

问题引入 在数据结构中&#xff0c;线性表是一种很重要的线性结构。线性表分为多种类型&#xff0c;常见的如顺序表、链表等&#xff0c;如果此时此刻你对“顺序表&#xff08;顺序存储&#xff09;”感到困惑&#xff0c;那就继续看下去&#xff0c;我们一步一步去剖析。 如果…
阅读更多...
顺序存储结构的线性表

顺序存储结构的线性表

1.0. 什么是线性表&#xff1f; 所谓线性&#xff0c;即一条线&#xff0c;这条线可以是直线&#xff0c;也可以是曲线。 所谓表&#xff0c;肯定都不陌生&#xff0c;生活中有各种各样的表或者表格。我们在表格中填写各种各样的信息&#xff0c;通过表格&#xff0c;能够很好…
阅读更多...
数据结构线性表顺序存储结构和主要算法实现

数据结构线性表顺序存储结构和主要算法实现

(1) 线性表的定义。 零个或多个数据元素的有限序列 序列线性表中有直接后继元素&#xff0c;有且仅有一个直接后继&#xff0c;有且仅有一个直接前驱&#xff0c;数据元素之间的关系是一对一的关系 常用的List操作&#xff1a; Operation InitList&#xff08;*L&#xf…
阅读更多...
线性表顺序存储结构

线性表顺序存储结构

1.什么是线性表? 线性表可以看作一条链子除了第一个元素和最后一个元素&#xff0c;其他每个元素都有一个前驱 元素和一个后继元素有且只有一个。 若一个元素都没有&#xff0c;则称为空表。 元素之间的关系是一一对应的关系。(就比如a2的前驱元素只有一个并且一定是a1&#…
阅读更多...
线性表的顺序存储结构

线性表的顺序存储结构

线性表的基本概念 线性结构习惯称为线性表&#xff0c;线性表是n(n>0)个数据元素构成的有限序列&#xff0c;表中除第一个元素外的每一个元素&#xff0c;有且只有一个一个前件&#xff1b;除最后一个元素外&#xff0c;有且只有一个后件。 非空数据表具有&#xff1a; 只…
阅读更多...
【数据结构】线性表的顺序存储结构及实现——C语言版

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

文章目录 顺序表1. 顺序表的存储结构定义2. 顺序表的实现2.1 初始化顺序表2.2 建立顺序表2.3 销毁顺序表2.4 判空操作2.5 求顺序表的长度2.6 遍历操作2.7 按值查找2.8 按位查找2.9 插入操作2.10 删除操作 3. 顺序表的使用4. 暖暖树洞 顺序表 线性表的顺序存储结构称为顺序表&a…
阅读更多...
VUE activated,deactivated使用

VUE activated,deactivated使用

项目中keepalive用得不多&#xff0c;记录一下以免遗忘。 页面第一次进入&#xff0c;钩子的触发顺序created-> mounted-> activated&#xff0c;退出时触发deactivated。当再次进入&#xff08;前进或者后退&#xff09;时&#xff0c;只触发activated。 事件挂载的方…
阅读更多...
vue activated，deactivated生命周期的使用

vue activated，deactivated生命周期的使用

1.当组件在 内被切换&#xff0c;它的 activated 和 deactivated 这两个生命周期钩子函数将会被对应执行。 2.activated()&#xff1a;在vue对象存活的情况下&#xff0c;进入当前存在activated()函数的页面时&#xff0c;一进入页面就触发&#xff1b;可用于初始化页面数据等…
阅读更多...
vue 中 keep-alive，activated，deactivated

vue 中 keep-alive，activated，deactivated

keep-alive 在组件反复切换时&#xff0c;会反复渲染&#xff0c;造成性能问题。用一个 <keep-alive></keep-alive> 标签将他包裹起来&#xff0c;组件会在第一次被创建的时候缓存下来。避免性能问题。 首先准备好组件&#xff0c;配置好路由。准备了Home,Keep,Abo…
阅读更多...
【Vue】学习笔记-Vue Router activated deactivated 路由守卫

【Vue】学习笔记-Vue Router activated deactivated 路由守卫

Vue Router activated deactivated 路由守卫 activated deactivated路由守卫1.全局守卫2.独享守卫3.组件内守卫全局路由守卫路由器的两种工作模式 activated deactivated activated 和 deactivated 是路由组件所独有的两个钩子&#xff0c;用于捕获路由组件的激活状态 具体使用…
阅读更多...
vue 生命周期图 + activated + deactivated

vue 生命周期图 + activated + deactivated

一、vue 生命周期图 From the network 二、activated deactivated 除此之外&#xff0c;简单介绍一下在被keep-alive包含的组件/路由中&#xff0c;会多出两个生命周期的钩子:activated 与 deactivated。在 2.2.0 及其更高版本中&#xff0c;activated 和 deactivated 将会…
阅读更多...
[Vue]缓存路由组件 activated()与deactivated()

[Vue]缓存路由组件 activated()与deactivated()

前言 系列文章目录&#xff1a; [Vue]目录 老师的课件笔记&#xff0c;不含视频 https://www.aliyundrive.com/s/B8sDe5u56BU 笔记在线版&#xff1a; https://note.youdao.com/s/5vP46EPC 视频&#xff1a;尚硅谷Vue2.0Vue3.0全套教程丨vuejs从入门到精通 文章目录 前言1. 缓存…
阅读更多...
Vue 钩子函数activated未触发

Vue 钩子函数activated未触发

activated()和deactivated()只有在<keep-alive></keep-alive>包裹的时候才有效&#xff1b;
阅读更多...
搞明白activated和deactivated

搞明白activated和deactivated

文章目录 写到前面什么是activatedactivated解决了一个什么问题Demomain.vueassembly1(组件1)assembly2(组件2) 执行结果要点速记个人建议写到最后 写到前面 今天简单的将activated讲一下&#xff0c;前面有人问了&#xff0c;既然有问的&#xff0c;说明还有人不是很明白的&am…
阅读更多...
vue中activated

vue中activated

keep-alive <keep-alive>包裹动态组件的时候&#xff0c;会缓存不活动的组件实例&#xff0c;而不是摧毁他们。其是一个抽象的组件&#xff0c;自身不会渲染一个DOM元素&#xff0c;也不会出现在父组件链中。 说白了被<keep-alive>包裹的组件其会被缓存。 没有被…
阅读更多...
Vue学习之---动态组件中的activated与deactivated钩子函数

Vue学习之---动态组件中的activated与deactivated钩子函数

Vue学习之—动态组件中的activated与deactivated钩子函数 在学习这两个钩子函数之前呢&#xff0c;怎么需要先了解下Vue内置的动态组件< component >以及与之相配套的< keep-alive > 组件&#xff1a; 动态组件指的是动态切换组件的显示与隐藏&#xff1b; < …
阅读更多...
vue中keep-alive、activated的探讨和使用

vue中keep-alive、activated的探讨和使用

在修改公司的一个项目的时候发现了activated这个东西&#xff0c;一直觉得很疑惑&#xff0c;之前也没怎么用过啊&#xff01;官网的生命周期那也没说过这东西啊&#xff01;生命周期不就create mount update 和destory这几个东东么&#xff0c;怎么多了个activate出来。 百思不…
阅读更多...
html页面ajax提交数据,ajax请求提交form表单

html页面ajax提交数据,ajax请求提交form表单

AJAX表单提交以及数据接收 方式一 手工收集所有的用户输入&#xff0c;封装为大的“k1v1&k2v2…”键值对形式&#xff0c;使用$.post(url, data,fn)把数据提交给服务器 $.ajax({ type:post, url:Notice_noTipsNotice, data:k1v1&k2v2..., cache:false, dataType:json, …
阅读更多...
接上篇 jquery.form.js 的 $.ajaxForm()和 $.ajaxSubmit()

接上篇 jquery.form.js 的 $.ajaxForm()和 $.ajaxSubmit()

2019独角兽企业重金招聘Python工程师标准>>> AjaxSubmit 和AjaxForm区别 AjaxForm ajaxForm()不能提交表单。在document的ready函数中&#xff0c;使用ajaxForm来为AJAX提交表单进行准备。提交动作必须由submit开始 , ajaxForm()适用于以表单提交方式处理ajax技术&a…
阅读更多...
springboot ajax form json 请求方式

springboot ajax form json 请求方式

1.form请求的后台代码 1.定义实体 Student package com.bsx.test.entity;import com.bsx.test.constant.Gender; import com.bsx.test.constant.Nature;import javax.persistence.Column; import javax.persistence.Id; import javax.persistence.Table; import java.io.Seri…
阅读更多...
推荐文章

Copyright @ 2022~2023