数据结构—表

一、介绍

早期的编程总是说程序就是算法加数据结构，这个有一定的道理。只不过随着后来编程技术的广泛应用，特别是互联网大爆发后，数据结构和算法被深埋到了后端和底层。这才使得很多的开发人员，对数据结构的理解大多停留在应用的层次上。
数据结构有很多种，随着编程技术的不断发展，又出现了不少新的数据结构。特别一些新思想和新概念的出现，新的数据结构也现的也越来越多。但从整体上看，数据结构的本质并没有变即数据集体的关系抽象。从另外一个角度看，数据结构就是降低数据的熵增。

二、表

在互联网的应用中，Table,表作为一种数据结构非常常见。但在实际的应用中，表往往与特定的应用场景或应用方式相绑定。可以这样认为，表作为数据结构没有一个严格的定义，它是一类数据结构的整体的描述即一个具有多重含义的集合的概念。
根据具体的结构、存储方式和约束机制的不同，可以把表为分线性表、哈希表和多维数组（矩阵）表。

三、说明

在上面的分析中知道了表可分为三大类：

  1. 线性表
    线性表是最常见的，它一般指具有相同的数据类型的数据元素的有限序列。如链表、一维数组等等。从物理存储机制来看，线性表分为两类，即顺序存储和离散（链式）存储。线性表的最主要特点就在于有限和有序性，其元素具有同质性和一对一性。。
  2. 哈希表
    有线性表就有非线性表，哈希表就是一种散列表，它是非线性的。一般来说，在开发提及的表往往是指的哈希表。它是通过哈希函数将关键字映射到有限地址集合的一种表。哈希表在互联网上的应用非常广泛，从分布式哈希到树的底层处理都有它的身影
  3. 广义表
    广义表是线性表的一种递归的扩展，虽然它是线程表的扩展，但从严格意义上讲它已经不属于线性表而属于非线性表了。可以理解为一个线性表的内部元素可以是单个元素也可以是元素集合（广义表）。
    在AI和大模型如此流行的现在，则可以从更抽象的层次看待表。体现到具体的应用中，它可以是矩阵也可以是多维数组

其实还有一些叫做表的数据结构，它不属于上面的任何一类，比如Redis中的跳表。可以把这些统统都划成非线性的数据结构中去。另外，还需要注意，往往从不同角度看待数据结构，就会出现不同的分类。这就需要开发者不必纠结于如何划分数据结构而是通过划分掌握数据结构的特点。这才是学习数据结构的目的。
对于传统的数据结构定义来说，非线性的数据结构（而不是非线性表）是普遍的表述，它一般是指图、树等数据结构，它的核心本质是数据结构中的元素是“一对多或多对多”。

四、应用场景

在明白了上述的线性表的分类和定义后，其实就会发现，其应用是非常广泛的。除了传统的链表、队列和栈等基础的数据结构应用。它们还可以组合实现更复杂的数据结构。包括经常使用的一些标准库中的数据结构如Map、树等等。
特别是线性表，其实复杂一些的数据结构底层几乎都需要它来配合实现。比如哈希表，它的冲突解决可以使用链表也可以使用扩大数组的方式。B+树的数据存储时，也可以考虑数组。正如侯老师的话：源码之前，了无秘密。有时间，还是要多看一下源码。

五、C++例程

下面看一个简单的广义表的源码：

#include<iostream>#include<memory>#include<variant>#include<vector>class GeneralizedList{public:using Elem=std::variant<int,std::shared_ptr<GeneralizedList>>;voidaddElemSingle(intv){elems_.push_back(v);}voidaddElemList(std::shared_ptr<GeneralizedList>list){elems_.push_back(list);}voiddisplay()const{std::cout<<"(";for(size_ti=0;i<elems_.size();++i){if(std::holds_alternative<int>(elems_[i])){std::cout<<std::get<int>(elems_[i]);}else{std::get<std::shared_ptr<GeneralizedList>>(elems_[i])->display();}if(i+1<elems_.size()){std::cout<<", ";}}std::cout<<")";}private:std::vector<Elem>elems_;};intmain(){autogList=std::make_shared<GeneralizedList>();gList->addElemSingle(3);gList->addElemSingle(4);autosList=std::make_shared<GeneralizedList>();sList->addElemSingle(7);sList->addElemSingle(8);gList->addElemList(sList);gList->addElemSingle(5);gList->display();std::cout<<std::endl;return0;}

代码没有什么难度，不再分析展开。其它如线性表或哈希表的例子太多了，也不再给出。

六、总结

把基础的知识整理成体系，既可以方便的整理分析，又可以从不同角度来掌握不同技术点间的逻辑关系。这样，在不同的应用场景下就可以灵活的对多种技术进行组合重组，实现更强大的功能。