数据结构...所以我怎么理解他们？ [英] Data Structures... so how do I understand them?
问题描述
第一次，我没有C ++的经验，课程期望我们在第一周结束时进行编码。我努力学习了几个第一个编程任务（MP）。不用说，我习惯了，在本学期的剩余时间里，语法很少。但随之而来的数据结构更加困难，理论（Big O）成为困难的一部分。所有这一切都是一个很好的经历，但我觉得我的问题是我没有培养良好的学习习惯。我做了议员，并且出席了讲座，但似乎我的心不在我身边。我想再次改变这个，因为回头看课程，我有一个很好的时间，我喜欢的材料。但是，当我需要花时间考虑如何使数据结构有效使用时，我发现自己花费太多时间思考/设置数据结构。
学习理论很困难（主要是因为它不是那么令人兴奋），所以我应该如何应用自己真正了解数据结构涵盖的类？我一直是视觉学习者，互动学习者...我不想花时间在做我的议员。相反，我想用这样的方式度过我的时间，以便我真正学习/理解这些概念，然后直接应用知识。
我正在寻找任何建议...或许可以就过去学习习惯的学习习惯提出建议，采取技术...任何你想分享的东西:)最重要的是，如何准备在学期开始之前。
即使选择了答案，请随时提供反馈。我正在寻找你的建议...这就是为什么我发布:)谢谢！
注意：课程涵盖的数据结构和主题：列表，堆栈，队列，树（不同种类），哈希表，图表，搜索/排序/遍历技术。
更新：这是迄今为止从答案编译的链接和参考文献列表。
- Robert Sedgewick的C ++算法
- Cormen算法简介
- NIST字典的算法和数据结构
- 排序算法
- 树遍历
- 图遍历
- 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
您已经收到了一些有趣的链接和想法。我希望我可以提供一点不同的观点：
我学会了通过教导计算机内存像一个很长的列表来可视化和喜欢数据结构。然后，结构在内存中具有不同的布局。通过可视化内存中的结构，对我而言（和有趣的）它们如何工作变得显而易见。了解内存中的数据布局对于程序员来说是非常重要的，因为当今不断增长的机器通常由内存访问停止。良好的内存布局可以帮助CPU从内存中获取数据，使CPU无需等待数据到达。
数据结构是数据在内存中的布局。将内存视为长列表，就像购物清单，但没有条目。
0 ...
1 ...
2 ...
3 ...
4 ...
5 ...
6 ...
当将结构放入内存时，它们基本上在内存中填充这些插槽。
一个列表很简单，它只是从顶部和底部填充记忆列表：
0元素0
1元素1
2元素2
3元素3
虽然有时你想要将元素2更改为别的东西，也可能是零。这就是列表的工作方式。您可以通过了解其索引（在本例中为0 .. 3）来访问结构中的数据。
堆栈是不同的。您只能通过将元素推到其顶部或从其顶部弹出元素来访问堆栈的顶部。推动意味着添加另一个元素，旧的顶部变得不可见。 Poping意味着删除顶部元素，下面的元素可以看到。
0 [隐藏数据]
。 [隐藏数据]
。 [隐藏数据]
。 [隐藏数据]
n [隐藏数据]
n + 1元素4
链接列表不同。链表包含一个指针（内存列表中的索引）到数据，一个指针指向下一个元素：
0数据：内存索引0x00000100
1下一页：内存索引6
2
3
4
5
6数据：内存索引104
7下一页：内存索引8
...
100从第一个成员指向的数据
101
102
103
104数据指向从第二个成员
队列就像一个更强大的堆栈，您可以访问底部和最佳。您只能将项目推到顶部，您只能从底部弹出项目。
0（底部）元素（准备弹出）
1 [隐藏数据]
2 [隐藏数据]
3 [隐藏数据]
。
。
。
n（上）（空，准备被推/给予数据）
通过可视化每个数据结构的布局，他们在如何需要内存以及如何真正工作（也在内存中）中变得更加明显。我希望我的例子为您提供一些简短的启发性知识，以您将来的研究为基础。作为数据结构的最后一个例子，我将给出一个不平衡的二叉树，它们具有以下元素插入顺序：
3，2，1，10，9，8，6，5，4，7， / p>
树从内存地址100开始，因为内存地址0无效，我将其用作无指针。
100值：3
101左ptr：103
102右ptr ：109
103价值：2
104左ptr：106
105右ptr：0
106值：1
107左ptr：0
108右ptr：0
109值：10
110左ptr：112
111 Right ptr：0
112价值：9
113左ptr：115
114右ptr：0
115值：8
116左ptr：118
117 Right ptr：0
118值：6
119左ptr：121
120右ptr：127
121值：5
122左ptr：124
123右ptr：0
124值：4
125左ptr：0
126右ptr：0
127值：7
128左ptr：0
129右ptr：0
希望有帮助！
So I am a Computer Science student and in about a week or so... I will be retaking a Data Structures course, using C++ for applying the theory. Yes, I did say "retaking". I took the course last Fall and I feel like there is more that I need to learn. Being a student, I feel that I MUST know the basics because it will be much easier to understand new concepts in future classes by already knowing the basic concepts... not having to relearn every time.
The first time around, I had no experience in C++ and the course expected us to be coding by the end of the first week. I struggled getting through several of the first programming assignments (MPs). Needless to say, I got used to it and had little trouble with the syntax the remainder of the semester. But then the harder Data Structures came around and the theory (Big O), became the difficult part.
All in all it was a great experience, but I feel my problem was that I didn't develop good study habits. I did the MPs and showed up to lecture, but it seems like my heart wasn't there with me. I want to change this the second time around because looking back at the class, I did have a good time and I enjoyed the material. But I found myself spending too much time thinking about/setting up the data structure(s) when I needed to be spending the time thinking about how to put the data structure to use effectively.
Learning theory is difficult (mostly because it isn't so exciting) so how should I apply myself to truly understand the Data Structures covered class? I've always been a visual learner, an interactive learner... I don't want to spend time just doing my MPs. Rather, I want to spend my time in such a way that I truly learn/understand the concepts and then directly apply the knowledge.
I'm looking for any suggestions... perhaps advice on study habits that have worked for you in the past learning such concepts... or suggestions on good note-taking techniques... anything that you'd like to share :) ... and most importantly, how to prepare before the semester starts.
Please feel free to provide feedback even if an answer has been selected. I am looking for your advice... this is why I posted :) Thanks!
NOTE: Data Structures and Topics covered in the course: Lists, Stacks, Queues, Trees (different kinds), Hash Tables, Graphs, Searching/Sorting/Traversal techniques.
UPDATE: Here's a list of links and references compiled from the answers so far.
- Algorithms in C++ by Robert Sedgewick
- Introduction to Algorithms by 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
UPDATE 2: Here's a list of some more sources that I found:
- 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
You have received some interesting links and ideas already. I hope I can provide a little different point of view:
I learned to visualize and "like" data structures by being taught that computer memory is like a really long list. The structures then have different layout in the memory. By visualizing the structures in the memory, it became obvious to me (and interesting) how they work. Knowing the data layout in memory is incredibly important for a programmer as today's continuously growing machines are often halted by memory-access. A good memory-layout easen the burden for the CPU to fetch the data from the memory so that the CPU doesn't have to wait for data to arrive.
Data structures is the layout of the data in a memory. Consider memory as a long list, just like a shopping list but without the entries.
0...
1...
2...
3...
4...
5...
6...
When you put structures into the memory, they essentially fill up these slots in memory.
A list is very simple, it just fills the memory-list from the top and down:
0 Element 0
1 Element 1
2 Element 2
3 Element 3
Although sometimes you want to change element 2 to something else, maybe zero. That's the way lists work. You can access the data in the structure by knowing their index (in this case, 0 .. 3).
Stacks are different. You can only access the "top" of a stack by "pushing" an element to the top of it, or "poping" an element from the top of it. Pushing means adding another element and the old top becomes invisible. Poping means removing the top element and the one below it becomes visible.
0 [ Hidden data ]
. [ Hidden data ]
. [ Hidden data ]
. [ Hidden data ]
n [ Hidden data ]
n+1 Element 4
Linked lists are different. A linked list contains a pointer (index in the memory-list) to the data, and one pointer to the next element:
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
Queue's is like a more powerful stack, you have access to both the bottom and the top. You can only push items to the top and you can only pop items from the bottom.
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)
By visualizing the layout of each data-structure, they became a lot more obvious to me in how they require memory and how they really work ( also in the memory). I hope that my examples have given you some brief starting knowledge for you to base your future studies on. As a final example on data structures, I will give you an unbalanced binary tree that have had the following order of element insertion: 3, 2, 1, 10, 9, 8, 6, 5, 4, 7
The tree starts at memory address 100, since memory address 0 is invalid and I'll use that as a "no pointer".
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
Hope that helps!
这篇关于数据结构...所以我怎么理解他们？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
