数据的逻辑结构

港控/mmm° 2023-09-25 21:15 68阅读 0赞

## 场景： ##

数据的逻辑结构是指数据元素之间的关系和组织方式，包括线性结构、树形结构、图形结构等。它描述了数据元素之间的逻辑关系，而不是物理存储方式。不同的逻辑结构适用于不同的数据处理需求，可以提高数据的存储效率和访问效率。

--------------------

## 线性结构 ##

线性结构：数据元素之间是一对一的关系，如数组、链表、栈、队列等。

数组：数组是一种线性结构，它将相同类型的数据元素存储在一起，通过下标访问元素，具有随机访问的特点。

链表：链表是一种通过指针将数据元素按照一定顺序连接起来的线性结构，根据指针的不同，链表可以分为单向链表、双向链表和循环链表等。

栈：栈是一种具有后进先出（LIFO）特性的线性结构，只能在栈顶进行插入和删除操作。

队列：队列是一种具有先进先出（FIFO）特性的线性结构，只能在队尾插入元素，在队头删除元素。

哈希表：哈希表是一种通过哈希函数将数据元素映射到一个固定位置的线性结构，可以实现常数时间的查找、插入和删除操作。

--------------------

## 集合结构 ##

集合：无序的、不重复的元素集合。

散列表：通过哈希函数将数据元素映射到一个固定位置的集合结构。

树集：基于树形结构实现的集合，元素按照一定的排序规则排列。

#include <iostream>
    #include <unordered_set>
    
    using namespace std;
    
    int main() {
        
        unordered_set<int> s;  // 定义一个无序集合
        s.insert(1);  // 插入元素1
        s.insert(2);  // 插入元素2
        s.insert(3);  // 插入元素3
        cout << s.size() << endl;  // 输出集合大小，输出：3
        s.erase(2);  // 删除元素2
        cout << s.count(2) << endl;  // 判断元素2是否存在，输出：0
        for (auto x : s) {
        
            cout << x << " ";  // 遍历集合并输出所有元素，输出：1 3
        }
        return 0;
    }
    
    
    散列表
    #include <iostream>
    #include <unordered_map>
    
    using namespace std;
    
    int main() {
        
        unordered_map<string, int> m;  // 定义一个散列表
        m["apple"] = 1;  // 插入键值对
        m["banana"] = 2;
        m["orange"] = 3;
        cout << m.size() << endl;  // 输出散列表大小，输出：3
        m.erase("banana");  // 删除键为"banana"的键值对
        cout << m.count("banana") << endl;  // 判断键为"banana"的键值对是否存在，输出：0
        for (auto p : m) {
        
            cout << p.first << " " << p.second << endl;  // 遍历散列表并输出所有键值对
        }
        return 0;
    }
    
    
    
    树集
    #include <iostream>
    #include <set>
    
    using namespace std;
    
    int main() {
        
        set<int> s;  // 定义一个树集
        s.insert(3);  // 插入元素3
        s.insert(1);  // 插入元素1
        s.insert(2);  // 插入元素2
        cout << s.size() << endl;  // 输出树集大小，输出：3
        s.erase(2);  // 删除元素2
        cout << s.count(2) << endl;  // 判断元素2是否存在，输出：0
        for (auto x : s) {
        
            cout << x << " ";  // 遍历树集并输出所有元素，输出：1 3
        }
        return 0;
    }

## 树结构 ##

常见的树结构有以下几种：

二叉树：每个节点最多有两个子节点的树结构。

平衡树：具有平衡性质的树结构，如AVL树、红黑树等。

B树/B+树：一种多路搜索树，常用于磁盘等外部存储器的数据结构。

--------------------

## 图结构 ##

在数据结构中，图是一种由节点（顶点）和连接它们的边组成的数据结构。图可以用来表示现实生活中的许多问题，例如社交网络、路线规划、电路设计等。图的节点可以表示任何对象，例如人、城市、电子元器件等。边则表示节点之间的联系或关系，例如人与人之间的关系、城市之间的道路、电子元器件之间的电路连接等。图可以是有向的或无向的，可以是带权重的或不带权重的。在计算机科学中，图的应用非常广泛，例如图搜索、最短路径算法、最小生成树算法等。

无向图：图中的边没有方向，可以从一个顶点到另一个顶点，也可以从另一个顶点到一个顶点。

有向图：图中的边有方向，只能从一个顶点到另一个顶点，不能反向。

加权图：图中的边有权值，表示两个顶点之间的距离或者代价。

无权图：图中的边没有权值，只表示两个顶点之间有连接。

完全图：图中的任意两个顶点之间都有连接的图。

稠密图：图中边的数量接近于顶点数量的平方。

稀疏图：图中边的数量远小于顶点数量的平方。

树：一种特殊的无向图，没有环，每个顶点都有且仅有一个父节点，除了根节点没有父节点。

有向无环图（DAG）：一种特殊的有向图，没有环，每个顶点都有一个有向路径从起点到达。

--------------------