c++ - 数据结构......那么我如何理解它们？

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




所以我是一名计算机科学专业的学生，​​大约一周左右......我将重新学习数据结构类(class)，使用 C++ 来应用理论。是的，我确实说过“重考”。我去年秋天参加了这门类(class)，我觉得我需要学习的还有更多。作为学生，我觉得我必须了解基础知识，因为通过已经了解基本概念，在以后的类(class)中理解新概念会容易得多……不必每次都重新学习。

第一次，我没有 C++ 方面的经验，类(class)要求我们在第一周结束时进行编码。我努力完成了几项最初的编程任务 (MP)。不用说，我已经习惯了，在本学期剩下的时间里，语法几乎没有问题。但随后出现了更难的数据结构，理论(Big O)成为困难的部分。

总而言之，这是一次很棒的经历，但我觉得我的问题是我没有养成良好的学习习惯。我做了国 session 员并出席了演讲，但似乎我的心不在我身边。我想第二次改变这一点，因为回顾类，我确实玩得很开心，而且我很喜欢这些 Material 。但是当我需要花时间思考如何有效地使用数据结构时，我发现自己花了太多时间思考/设置数据结构。

学习理论很困难(主要是因为它不是那么令人兴奋)所以我应该如何运用自己来真正理解涵盖的数据结构类(class)？我一直是一个视觉学习者，一个互动学习者......我不想花时间只是做我的议员。相反，我想以一种真正学习/理解概念然后直接应用知识的方式来度过我的时间。

我正在寻找任何建议......也许是关于过去学习这些概念对你有用的学习习惯的建议......或者关于良好笔记技巧的建议......任何你想分享的东西:) ...最重要的是，如何在学期开始前做好准备。

即使选择了答案，也请随时提供反馈。我正在寻找您的建议...这就是我发布的原因:) 谢谢!

注意 :类(class)中涵盖的数据结构和主题:列表、堆栈、队列、树(不同种类)、哈希表、图、搜索/排序/遍历技术。

更新 :这是迄今为止根据答案汇编的链接和引用列表。

C++ 中的算法作者:Robert Sedgewick

Cormen 算法导论

The NIST Dictionary of Algorithms and Data Structures

Sorting algorithms

Tree traversals

Graph traversals

http://www.codeproject.com/KB/cpp/linked_list.aspx

http://www.codeproject.com/KB/architecture/treedata_class.aspx

更新 2 :这是我发现的更多来源的列表:

http://people.ksp.sk/~kuko/bak/big/

http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html

http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

http://www.cs.duke.edu/csed/jawaa2/examples/BFS.html

Answer 1

您已经收到了一些有趣的链接和想法。我希望我能提供一些不同的观点:

通过被教导计算机内存就像一个非常长的列表，我学会了可视化和“喜欢”数据结构。然后这些结构在内存中具有不同的布局。通过可视化内存中的结构，我很清楚(而且很有趣)它们是如何工作的。了解内存中的数据布局对于程序员来说非常重要，因为当今不断增长的机器经常因内存访问而停止。良好的内存布局减轻了 CPU 从内存中获取数据的负担，因此 CPU 不必等待数据到达。

数据结构是数据在内存中的布局。将内存视为一个长列表，就像购物 list 一样，但没有条目。

0...
1...
2...
3...
4...
5...
6...

当您将结构放入内存时，它们基本上会填满内存中的这些插槽。

一个列表很简单，它只是从上到下填充内存列表:

0 Element 0
1 Element 1
2 Element 2
3 Element 3

尽管有时您想将元素 2 更改为其他内容，可能是零。这就是列表的工作方式。您可以通过了解它们的索引(在本例中为 0 .. 3)来访问结构中的数据。

栈不一样。您只能通过将一个元素“推”到它的顶部或从它的顶部“弹出”一个元素来访问堆栈的“顶部”。插入意味着添加另一个元素，旧的顶部变得不可见。弹出意味着删除顶部元素，而它下面的元素变得可见。

0   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
n   [ Hidden data ]
n+1 Element 4

链表是不同的。链表包含一个指向数据的指针(内存列表中的索引)和一个指向下一个元素的指针:

0 Data: Memory index 0x00000100
1 Next: Memory index 6
2 
3 
4 
5 
6 Data: Memory index 104
7 Next: Memory index 8
...
100 Data pointed to from first member
101
102
103
104 Data pointed to from second member

队列就像一个更强大的堆栈，您可以访问底部和顶部。您只能将项目推到顶部，并且只能从底部弹出项目。

0 (bottom) Element (ready to be popped)
1 [ Hidden data ]
2 [ Hidden data ]
3 [ Hidden data ]
.
.
.
n (top) (empty, ready to be pushed / be given data)

通过可视化每个数据结构的布局，它们在如何需要内存以及它们如何真正工作(也在内存中)方面对我来说变得更加明显。我希望我的例子已经为您提供了一些简要的入门知识，以供您在 future 的学习基础上使用。作为数据结构的最后一个例子，我会给你一个不平衡的二叉树，它的元素插入顺序如下:
3, 2, 1, 10, 9, 8, 6, 5, 4, 7

该树从内存地址 100 开始，因为内存地址 0 无效，我将其用作“无指针”。

100 Value: "3"
101 Left ptr: 103
102 Right ptr: 109

103 Value: "2"
104 Left ptr: 106
105 Right ptr: 0

106 Value: "1"
107 Left ptr: 0
108 Right ptr: 0

109 Value: "10"
110 Left ptr: 112
111 Right ptr: 0

112 Value: "9"
113 Left ptr: 115
114 Right ptr: 0

115 Value: "8"
116 Left ptr: 118
117 Right ptr: 0

118 Value: "6"
119 Left ptr: 121
120 Right ptr: 127

121 Value: "5"
122 Left ptr: 124
123 Right ptr: 0

124 Value: "4"
125 Left ptr: 0
126 Right ptr: 0

127 Value: "7"
128 Left ptr: 0
129 Right ptr: 0

希望有帮助!