数据结构详解：从数组到树，再到哈希表
本文深入探讨几种常见的数据结构，包括数组、链表、二叉搜索树（BST）和哈希表，并阐述其在内存中的组织方式及优缺点。
信息结构与抽象数据结构
信息结构指的是内存中组织信息的方式，而抽象数据结构则是我们概念上对这些结构的理解。 理解抽象数据结构有助于我们更好地在实践中实现各种数据结构。
堆栈和队列
队列是一种遵循FIFO（先进先出）原则的抽象数据结构，类似于排队等候。其主要操作包括入队（添加元素到队列尾部）和出队（移除队列头部元素）。
堆栈则遵循LIFO（后进先出）原则，如同叠盘子。其操作包括压入（添加元素到堆栈顶部）和弹出（移除堆栈顶部元素）。
数组
数组是一种在内存中连续存储数据的结构。 如下图所示，数组在内存中占据连续的存储空间。
内存中可能存在其他程序、函数和变量，以及之前使用过的冗余数据。 如果需要向数组添加新元素，则需要重新分配内存并复制整个数组，这会造成效率低下。
预先分配过多的内存虽然可以减少复制操作，但却会浪费系统资源。因此，根据实际需求分配内存至关重要。
链表
链表是一种强大的数据结构，它允许将位于不同内存区域的值连接成一个列表，并支持动态扩展或缩小。
每个节点包含两个值：数据值和指向下一个节点的指针。最后一个节点的指针值为NULL，表示链表的结尾。
C语言中，节点可以定义如下：
typedef struct node { int number; struct node *next;} node;
以下示例展示了链表的创建过程：
链表的缺点包括：需要额外内存存储指针，以及无法通过索引直接访问元素。
二叉搜索树 (BST)
二叉搜索树是一种高效存储、搜索和检索数据的树形结构。
BST 的优点在于动态性和搜索效率（O(log n)），缺点在于树不平衡时搜索效率会下降到 O(n)，并且需要额外的内存存储指针。
哈希表
哈希表类似于字典，包含键值对。 它利用哈希函数将键映射到数组索引，从而实现 O(1) 的平均查找时间。
哈希冲突（多个键映射到同一个索引）可以通过链表或其他方法解决。 哈希函数的设计对哈希表的性能至关重要。 一个简单的哈希函数示例如下：
#include unsigned int hash(const char *word) { return toupper(word[0]) - 'A';}
本文基于cs50x 2024源码整理。
以上就是CS-第 5 周的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1461260.html
微信扫一扫 
支付宝扫一扫 
