【第二节】C/C++数据结构之线性表

2024-06-04 12:44
文章标签 c++ 数据结构 线性表 第二节

本文主要是介绍【第二节】C/C++数据结构之线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、线性表基本说明

1.1 基本概念

1.2 抽象数据类型

1.3 存储结构

1.4 插入与删除的区别

1.5 顺序存储和链式存储的优缺点

二、链表

2.1 基本概念

2.2 抽象数据类型

2.3 单链表的定义

2.4 单链表的基本操作

2.5 单链表模板形式的类定义与实现

三、单向循环链表

四、双链表、双向循环链表

一、线性表基本说明

1.1 基本概念

        线性表,零个或多个数据元素的有限序列称为线性表,例如一个字符串就是一个线性表比如一个结构体数组也是一个线性表。

1.2 抽象数据类型

ADT 线性表(List)
Data
除第一个元素外，每一个元素有且只有一个直接前驱元素,除了最后一个元素外，每个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系
Operation
初始化操作，建立一个空的线性表
若线性表为空，返回true，否则返回false
将线性表清空
将线性表中的第i个位置元素值返回给e在线性表中查找与给定值e相等的元素，成功返回序号，否则返回0在线性表中的第i个位置中插入新元素
在线性表中删除第i个位置的元素，并用e返回其值
返回线性表L的元素个数
endADT

1.3 存储结构

线性表的顺序存储

        线性表的顺序存储结构，是指使用一段地址连续的存储单元依次存储线性表的数据元素。这种存储方式通常通过数组（Array）来实现，其中数组的每个元素都对应线性表中的一个数据元素。

        在数组中，数据元素按照其在线性表中的逻辑顺序存储，即第一个数据元素存储在数组的第一个位置，第二个数据元素存储在第二个位置，依此类推。这种存储方式使得我们可以通过数组的索引直接访问线性表中的任何数据元素，而不需要遍历整个线性表。

        需要注意的是，数组的总长度（即数据空间的总长度）并不一定等于线性表的长度。线性表的长度是指线性表中实际存储的数据元素个数，而数组的长度是数组中可以存储的最大数据元素个数。因此，数组的长度通常大于线性表的长度，以便在需要时可以动态扩展。

        在实际编程中，我们通常会使用动态数组（Dynamic Array）来实现线性表的顺序存储结构，以便在需要时可以动态调整数组的大小。例如，当线性表的长度超过数组的长度时，可以创建一个新的更大的数组，并将原数组中的数据元素复制到新数组中。

线性表的链式存储

        线性表的链式存储结构，是指使用链表（Linked List）来存储线性表的数据元素。在链式存储结构中，每个数据元素都包含一个数据项和一个指向下一个数据元素的指针。这种存储方式可以灵活地进行插入和删除操作，而不需要移动大量的数据。

        链式存储结构的优点在于，当需要插入或删除元素时，只需要修改相关节点的指针，而不需要移动大量的数据。因此，链式存储结构在执行插入和删除操作时，通常比顺序存储结构更高效。

        然而，链式存储结构也有其缺点。由于每个数据元素都包含一个指针，因此存储空间的利用率不如顺序存储结构高。此外，链式存储结构在执行查找操作时，需要从头开始遍历链表，直到找到目标元素或到达链表的末尾。因此，如果需要频繁地执行查找操作，顺序存储结构可能更适合。

        总的来说，选择使用顺序存储结构还是链式存储结构，取决于具体的应用场景。如果需要频繁地执行插入和删除操作，并且数据量不大，那么链式存储结构可能更适合。如果需要频繁地执行查找操作，并且数据量较大，那么顺序存储结构可能更适合。

1.4 插入与删除的区别

顺序线性表的插入与删除:
在顺序存储结构下，线性表在插入新数据前需要将其插入点后面的数据依次后移一个单位，以空出位置让新数据插入
在顺序存储结构下，线性表在删除数据后需要将其删除点后面的数据依次前移一个单位，以补足删除后空出位置

链式线性表的插入与删除:
当我们想在链表中插入一个新数据的时候，只需要申请一段内存空间，然后将其前一个元素的指针指向自己，再将自己的指针指向下一个元素即可，无需操作其他元素
当我们想在链表中删除一个节点时，只需要将前一个节点指向后一个节点，并释放掉自己即可

1.5 顺序存储和链式存储的优缺点

顺序存储和链式存储是两种基本的数据结构，它们在存储和访问数据元素时各有优缺点。

顺序存储（顺序结构）：

  • 优点：顺序存储的优点在于存储效率高，存取速度快。由于数据元素存储在连续的内存空间中，因此可以通过下标直接访问任何元素，无需遍历整个数据结构。

  • 缺点：顺序存储的缺点在于空间大小固定，不易扩充。一旦定义了存储空间的大小，就无法改变。此外，在插入或删除元素时，需要移动大量元素，这会降低效率。

链式存储（链式结构）：

  • 优点：链式存储的优点在于空间利用率高，可以动态分配和释放存储空间。此外，在插入和删除元素时，只需要修改链接指针，而不需要移动数据元素，因此效率较高。

  • 缺点：链式存储的缺点在于存取元素时需要顺序查找，因此存取效率不高。此外，由于每个元素都包含一个指针，因此存储空间的利用率不如顺序存储高。

在实际应用中，选择顺序存储还是链式存储取决于具体的应用需求。如果需要频繁地插入和删除元素，并且数据量不大，那么链式存储可能更适合。如果需要频繁地查找元素，并且数据量较大，那么顺序存储可能更适合。

二、链表

2.1 基本概念

        链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。
        每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址
的指针域循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

2.2 抽象数据类型

ADT 链表(List)
Data
除第一个元素外，每一个元素有且只有一个直接前驱元素,除了最后一个元素外,每个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系
Operation
初始化操作，建立一个空的链表
若链表为空，返回true，否则返回false
将链表清空
将链表中的第i个位置元素值返回给e
在链表中查找与给定值e相等的元素，成功返回序号，否则返回0
在链表中的第i个位置中插入新元素
在链表中删除第i个位置的元素，并用e返回其值
返回链表的元素个数
endADT

2.3 单链表的定义

        链表中最简单的一种是单向链表，它包含两个域，一个数据域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
        单向链表通常由一个头指针(head)，用于指向链表头。单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL)。

2.4 单链表的基本操作

对链表的基本操作有:
创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。
检索操作是指,按给定的结点索引号或检索条件,查找某个结点。如果找到指定的结点则称为检索成功;否则，称为检索失败。
插入操作是指，在结点之间插入一个新的结点，使线性表的长度增1。
删除操作是指，删除结点ki，使线性表的长度减1
打印输出。

2.5 单链表模板形式的类定义与实现

代码示例：

#include <iostream>// 定义链表节点结构体
template <typename T>
struct Node {T data;Node* next;Node(const T& value) : data(value), next(nullptr) {}
};// 单链表类模板
template <typename T>
class SingleLinkedList {
private:Node<T>* head;int size;public:SingleLinkedList() : head(nullptr), size(0) {}~SingleLinkedList() {while (head != nullptr) {Node<T>* temp = head;head = head->next;delete temp;}}// 插入元素到链表头部void push_front(const T& value) {Node<T>* newNode = new Node<T>(value);newNode->next = head;head = newNode;size++;}// 删除链表头部元素void pop_front() {if (head != nullptr) {Node<T>* temp = head;head = head->next;delete temp;size--;}}// 查找元素Node<T>* find(const T& value) {Node<T>* current = head;while (current != nullptr) {if (current->data == value) {return current;}current = current->next;}return nullptr; // 未找到返回nullptr}// 删除指定元素void remove(const T& value) {if (head == nullptr) return;if (head->data == value) {pop_front();return;}Node<T>* current = head;while (current->next != nullptr) {if (current->next->data == value) {Node<T>* temp = current->next;current->next = current->next->next;delete temp;size--;return;}current = current->next;}}// 获取链表大小int getSize() const {return size;}// 显示链表元素void display() const {Node<T>* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}
};// 示例使用
int main() {SingleLinkedList<int> list;// 插入元素list.push_front(10);list.push_front(20);list.push_front(30);list.display(); // 输出: 30 20 10// 删除元素list.pop_front();list.display(); // 输出: 20 10// 查找元素Node<int>* foundNode = list.find(20);if (foundNode != nullptr) {std::cout << "Found: " << foundNode->data << std::endl;} else {std::cout << "Not found" << std::endl;}// 删除指定元素list.remove(10);list.display(); // 输出: 20// 获取链表大小std::cout << "Size: " << list.getSize() << std::endl; // 输出: Size: 1return 0;
}

        在这个代码中，我们定义了一个Node结构体模板来表示链表中的节点，每个节点包含一个数据项和一个指向下一个节点的指针。SingleLinkedList类模板定义了单链表的主要操作，包括构造函数、析构函数、push_front（在链表前端插入元素）、pop_front（从链表前端删除元素）、find（查找元素）、remove（删除指定元素）、getSize（获取链表大小）和display（显示链表中的所有元素）。

        在main函数中，我们创建了一个SingleLinkedList<int>对象，并进行了一些操作，以展示如何使用这个模板类。这些操作包括插入元素、删除元素、查找元素、显示链表和获取链表大小。

三、单向循环链表

四、双链表、双向循环链表

        单向链表、单向循环链表、双向链表和双向循环链表都是链表数据结构的不同类型，它们在结构和操作上有所不同。以下是这些链表类型之间的主要区别：

  1. 单向链表:

    • 每个节点包含一个数据项和一个指向下一个节点的指针。

    • 链表的末尾节点的指针通常设置为NULL，表示链表的结束。

    • 单向链表不是循环的，它只能从头到尾遍历。

  2. 单向循环链表:

    • 与单向链表类似，但链表的最后一个节点的指针指向链表的第一个节点，形成一个循环。

    • 这种类型的链表可以从任何节点开始遍历，并且可以无限期地继续。

  3. 双向链表:

    • 每个节点包含一个数据项、一个指向下一个节点的指针和一个指向前一个节点的指针。

    • 链表的第一个节点的前向指针通常设置为NULL，表示链表的开始。

    • 链表的最后一个节点的后向指针通常设置为NULL，表示链表的结束。

    • 双向链表可以从任意节点开始向前或向后遍历。

  4. 双向循环链表:

    • 与双向链表类似，但链表的第一个节点的后向指针指向链表的最后一个节点，形成一个循环。

    • 链表的最后一个节点的前向指针指向链表的第一个节点，形成另一个循环。

    • 双向循环链表可以从任意节点开始向前或向后遍历，并且可以无限期地继续。

        选择哪种链表类型取决于你的具体需求。例如，如果你需要频繁地在链表的两端插入和删除元素，双向链表可能是一个好的选择。如果你需要在链表中进行循环遍历，那么单向循环链表或双向循环链表可能更适合。

关于它们的更具体实现和应用后面再详细讲解。

这篇关于【第二节】C/C++数据结构之线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1030120。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
C++的模板(八)：子系统

C++的模板(八)：子系统

平常所见的大部分模板代码，模板所传的参数类型，到了模板里面，或实例化为对象，或嵌入模板内部结构中，或在模板内又派生了子类。不管怎样，最终他们在模板内，直接或间接，都实例化成对象了。 但这不是唯一的用法。试想一下。如果在模板内限制调用参数类型的构造函数会发生什么?参数类的对象在模板内无法构造。他们只能从模板的成员函数传入。模板不保存这些对象或者只保存他们的指针。因为构造函数被分离，这些指针在模板外
阅读更多...
C++工程编译链接错误汇总VisualStudio

C++工程编译链接错误汇总VisualStudio

目录 一些小的知识点 make工具 可以使用windows下的事件查看器崩溃的地方 dumpbin工具查看dll是32位还是64位的 _MSC_VER .cc 和.cpp 【VC++目录中的包含目录】 vs 【C/C++常规中的附加包含目录】——头文件所在目录如何怎么添加，添加了以后搜索头文件就会到这些个路径下搜索了 include<> 和 include"" WinMain 和
阅读更多...
C/C++的编译和链接过程

C/C++的编译和链接过程

目录 从源文件生成可执行文件（书中第2章） 1.Preprocessing预处理——预处理器cpp 2.Compilation编译——编译器cll ps：vs中优化选项设置 3.Assembly汇编——汇编器as ps：vs中汇编输出文件设置 4.Linking链接——链接器ld 符号 模块，库 链接过程——链接器 链接过程 1.简单链接的例子 2.链接过程 3.地址和
阅读更多...
C++必修：模版的入门到实践

C++必修：模版的入门到实践

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯，先赞后看哦~🎈🎈 所属专栏：C++学习 贝蒂的主页：Betty’s blog 1. 泛型编程 首先让我们来思考一个问题，如何实现一个交换函数？ void swap(int& x, int& y){int tmp = x;x = y;y = tmp;} 相信大家很快就能写出上面这段代码，但是如果要求这个交换函数支持字符型
阅读更多...
C++入门01

C++入门01

1、.h和.cpp 源文件 (.cpp)源文件是C++程序的实际实现代码文件，其中包含了具体的函数和类的定义、实现以及其他相关的代码。主要特点如下：实现代码: 源文件中包含了函数、类的具体实现代码，用于实现程序的功能。编译单元: 源文件通常是一个编译单元，即单独编译的基本单位。每个源文件都会经过编译器的处理，生成对应的目标文件。包含头文件: 源文件可以通过#include指令引入头文件，以使
阅读更多...
C++面试八股文：std::deque用过吗？

C++面试八股文：std::deque用过吗？

100编程书屋_孔夫子旧书网 某日二师兄参加XXX科技公司的C++工程师开发岗位第26面： 面试官：deque用过吗？ 二师兄：说实话，很少用，基本没用过。 面试官：为什么？ 二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。 面试官：那你知道STL中的stack是如何实现的吗？ 二师兄：默认情况下，stack使
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2