软件开发的数据结构

红太狼 2023-01-19 08:09 32阅读 0赞

常见数据结构，数组、链表、栈、队列、树、堆、图、哈希表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VqaW54aWFu_size_16_color_FFFFFF_t_70][]

**①、数组**

优点：

*  按照索引查询元素的速度很快；
 *  按照索引遍历数组也很方便。

缺点：

*  数组的大小在创建后就确定了，无法扩容；
 *  数组只能存储一种类型的数据；
 *  添加、删除元素的操作很耗时间，因为要移动其他元素

**②、链表**

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用，

这是一种双向链表，当前元素 item 既有 prev 又有 next，不过 first 的 prev 为 null，last 的 next 为 null。如果是单向链表的话，就只有 next，没有 prev。

![16a09f0a72db550eb771ca8918f4ec4a.png][]

优点：

*  不需要初始化容量；
 *  可以添加任意元素；
 *  插入和删除的时候只需要更新引用。

缺点：

*  含有大量的引用，占用的内存空间大；
 *  查找元素需要遍历整个链表，耗时。

**③、栈**

栈按照“后进先出”、“先进后出”的原则来存储数据，先插入的数据被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始依次读出

![f018fc132a456e28cc0837ab18d230f6.png][]

**④、队列**

队列会对两端进行定义，一端叫队头，另外一端就叫队尾。队头只允许删除操作（出队），队尾只允许插入操作（入队）

![63174bc372aa0db502b45c3b43a14453.png][]

**⑤、树**

树是一种典型的非线性结构，它是由 n（n>0）个有限节点组成的一个具有层次关系的集合

![01a30df777349b4e5623032ef1b4c05c.png][]

**⑥、堆**

*  堆中某个节点的值总是不大于或不小于其父节点的值；
 *  堆总是一棵完全二叉树

**⑦、图**

图是一种复杂的非线性结构，由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合

![4f66ae3e1fb51801b894db94f9dec380.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VqaW54aWFu_size_16_color_FFFFFF_t_70]: /images/20221021/45f62f85a3b64d2d893ba5beb8fe40d5.png
[16a09f0a72db550eb771ca8918f4ec4a.png]: /images/20221021/546e60220e0e433da3e5962cf0d04756.png
[f018fc132a456e28cc0837ab18d230f6.png]: /images/20221021/c77e5314007d4aac83125b983c9a89b3.png
[63174bc372aa0db502b45c3b43a14453.png]: /images/20221021/04315794ada24c54b9101bbe7ec561bd.png
[01a30df777349b4e5623032ef1b4c05c.png]: /images/20221021/1741fc48e3854ef9a83d9e53bfb1c31c.png
[4f66ae3e1fb51801b894db94f9dec380.png]: /images/20221021/ecc19fd334954a4cbe7fe000f0b602b6.png