数据结构…所以我怎么理解他们呢?

所以我是一名计算机科学专业的学生,​​在大约一个星期左右的时间里,我将会重新拿一个数据结构课程,用C ++来应用这个理论。 是的,我确实说过“重新获得”。 去年秋天我参加了这个课程,我觉得还有更多需要学习的东西。 作为一名学生,我觉得我必须了解基础知识,因为通过已经了解基本概念,不需要每次重新学习,就能更容易地理解未来课程中的新概念。

第一次,我没有使用C ++的经验,课程期望我们在第一周结束时进行编码。 我挣扎了几个第一次编程作业(MP)。 不用说,我已经习惯了,学期余下的时间也没有什么问题。 但是,更困难的数据结构出现,理论(大O)成为困难的一部分。

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

学习理论是困难的(主要是因为它不那么令人兴奋),所以我应该如何应用自己来真正理解数据结构覆盖的类? 我一直是一个视觉学习者,一个互动的学习者…我不想花时间做我的议员。 相反,我想花时间去真正地学习/理解概念,然后直接运用知识。

我正在寻找任何build议…也许对过去学习这些概念的学习习惯的build议…或好的笔记技巧的build议…任何你想分享的东西:) …最重要的是,如何准备在学期开始之前。

即使select了答案,也请随时提供反馈意见。 我正在寻找你的build议…这就是为什么我张贴:)谢谢!


:本课程涵盖的数据结构和主题:列表,堆栈,队列,树(不同种类),哈希表,graphics,search/sorting/遍历技术。


更新 :这里是从目前的答案编译的链接和引用的列表。

  • Robert Sedgewick在C ++中的algorithm
  • Cormenalgorithm介绍
  • NISTalgorithm和数据结构字典
  • sortingalgorithm
  • 树遍历
  • 图遍历
  • 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不必等待数据到达。

数据结构是内存中数据的布局。 把记忆当成一个长列表,就像购物清单一样,但没有logging。

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

当你把结构放入内存时,它们基本上填满了内存中的这些槽。

列表非常简单,它只是从上到下填充内存列表:

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

虽然有时候你想要把元素2改成别的东西,也许是零。 这是列表工作的方式。 您可以通过了解其索引来访问结构中的数据(在本例中为0 .. 3)。

堆栈是不同的。 你只能通过“推”一个元素到顶部,或者从顶部“popup”一个元素来访问堆栈的“顶部”。 推动意味着添加另一个元素,旧的顶部变得不可见。 popup意味着删除顶部的元素,下面的元素变得可见。

 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 

队列就像一个更强大的堆栈,你可以访问底部和顶部。 您只能将物品推到顶部,而且只能从底部popup物品。

 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) 

通过可视化每个数据结构的布局,对于我们如何要求内存以及它们是如何工作的( 在内存中 ),它们变得更加明显。 我希望我的例子能够为你提供一些简要的初步知识,使你的未来学习成为可能。 作为数据结构的最后一个例子,我会给你一个不平衡的二叉树,它具有如下顺序的元素插入: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 

希望有所帮助!

以下是对我最有帮助的一点…因为你是一个可视化的人,Google可以通过一些可视化的sortingalgorithm,树遍历,散列法等来了解发生了什么。 之后,尝试使用不同的结构进行简单的程序,并尝试不同的排列方式 – 例如,可以使链表开始,然后将其设置为循环链表,然后使其成为双向链表,然后使其成为一个双向链表,依此类推…

您只需要尝试一下这些结构,然后就可以开始了解哪些数据结构适合您开发的应用程序。

这里有一些很好的参考你..sortingalgorithm: http : //www.sorting-algorithms.com/树遍历: http : //nova.umuc.edu/~jarc/idsv/lesson1.html图遍历: http: //www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html


至于效率(大O分析),一旦你理解了在数据结构的每个操作的algorithm级别发生了什么,它就会自然地来到你的面前。

我的大学强调的一件事就是我们自己开发数据结构(这是自下而上的学习),而没有潜入预先build立的C ++模板(自上而下的学习)。 通过从头开始,您真的了解了插入,删除,search(遍历)以及从某个特定结构访问数据所涉及的开销,这将有助于您在devise未来系统时的直觉。

练习,练习,练习。

我为你提供的第一条build议是尽可能精通C ++。

数据结构和编程是两个非常不同的话题。 如果你发现自己在编程方面苦苦挣扎,那么你就不太可能理解数据结构。

你如何精通C ++? 练习,练习,练习。 编程一切。 了解你所能做的一切。 写几十个小程序。 任何你可以做的,以适应C + +。

如果你精通C ++,那么我向你保证,数据结构将变得更容易。 (注意,我没有说容易,我说更容易:))

学习数据结构的关键是从一些小的东西开始,然后在此基础上进行构build。 我们从一个简单的C结构开始:

 struct Person { char name[100]; int age; }; 

这个数据结构代表一个人。 你需要确保你理解这些简单的结构概念,然后你可以移动到更大的东西。

例如,当你开始讨论像堆栈和队列这样的数据结构时,首先试着从概念上理解数据结构在做什么。 例如,对于堆栈,我们使用LIFO原则,即“后进先出”。 有一个队列,我们​​使用FIFO原理(先进先出)。

然后就是那个让很多人上去的链接列表。 你需要很好地理解这个指针,所以在试图处理链表之前,先从简单的事情开始:

 int* x; int y = 10; x = &y; 

你应该可以看看这个代码,并立即知道它在做什么。 如果你不能,那么你还没有准备好转移到更高级的数据结构,如链接列表。

我试图做的主要观点是你需要把基础知识冷落下来,然后build立在这些基础之上。 同时要勤于跟class,同时要问老师或老师是否有问题,确保你每周都在跟踪,不要落伍。

计算机科学课很像math课,每周通常build立在你从前N周学到的所有东西上。 所以,如果你不了解一个关键的概念,比如说指针,那么在这个学期剩下的时间里,你将会有很大的困难。

我喜欢dcp的答案。

围绕数据结构打包的最好方法是编写小例子。 即使你从你的书中复制它们,如果你能让它们工作和编译,并用你自己的手指input它们,你将学到很多东西。

当你阅读你的书,并在每次讲座后,写出你可以创build和使用(显示,使用等)你刚才了解到的数据结构的最短程序。

然后,当你必须做你的实际任务,你会学习更多,当你试图拿你的小例子,并将其插入解决任务的问题。

我认为写个人数据结构的最短/最小可能的工作代码是非常有用的。 此外,不要害怕复制代码(为了您自己的教化,而不是为了您的转身)。如果您通过键入而不是复制粘贴来复制,您最终会学到很多东西,因为这会迫使您看代码中的每个字符。


如果整个数据结构看起来像“太多”来包装你的头,那么开始写数据结构的组件的小例子。 所以用指针存储一个书名。 然后存储许多指向指针的书名。 用方括号表示法和指针算术读取书名。 在简单的函数中使用recursion,这是清楚发生了什么事情…..例如recursion显示数字的阶乘是更简单的包装头比recursion显示二叉树(在我看来)… ..

你会看到你的问题领域是什么,并尽可能将它们分离为一个小而具体的东西,然后写一个简短的程序,你可以处理这个问题领域…..然后build立。

你的讲座是关于整个数据结构……巨大的Cummulus云理论……所以,它们本质上是自上而下的。 在小问题中隔离一些小问题的语法和用法是自下而上的。 所以你的老师可以帮助你从顶部攻击,你从底部攻击练习,很快就没有什么中间的东西!

有意义地学习数据结构和algorithm的唯一方法是将它们应用于现实世界的问题,并用它们来解决现实世界的问题。 将它们编码为工作应用程序 – 即使他们做了devise – 也会加强理论知识,使您能够更好地保留思想,并将其融入您个人的解决问题的方法中。

我build议在algorithm上写一本好书(Cormen等人的“Introduction to Algorithms”是我的build议)。 通过这本书,你将会开发和使用不同的数据结构,你很可能会意识到每个结构都适合什么。 数据结构只能作为实现不同目标的手段:解决特定的问题。

取决于你花了多less时间或者想花多less时间,你可以尝试从ACM ICPC等不同的编程竞赛中获得问题。 大部分的问题都需要你运用这些知识。 请注意,algorithm和数据结构都是语言不可知的,所以如果你有任何其他语言的良好的知识只是使用它。

在我看来,这些东西比在理论课程中更好,在工作中或通过经验学习。 大多数时候,我在学校的时候,努力工作以保持领先地位是我认为与你所经历的经历相似的重要部分。 虽然你想要彻底地理解它是值得赞赏的,但只要你知道在什么时候需要它find好的参考资料,那么这个过程就已经达到了目的。

大多数课程将build立在过去课程中学到的知识上。 你会在学习中再次碰到这些细节,你的教授应该能够帮助你把你以前学过的东西应用到你当前的课堂上。 作为互动学习者,办公时间,实习机会和导师机会似乎是更好地获取所需信息的方法。

祝你好运!

你总是需要记住的一件事是数据结构不仅仅存在。 它们是为了适应需要而发明的,因此意味着它们由于某些原因是有益的,而不是为了其他原因。
找出这些原因是什么,数据结构是什么,在你告诉他们之前,试着弄清楚操作的大O.
始终比较数据结构。 即使是最简单的 – 一个数组。 以此为出发点,并将每个find的数据结构与数组进行比较。 有时你会发现一些小技巧,可以帮助你避免使用大数据结构。
对我来说,帮助我理解很多数据结构和algorithm的是这里的小程序,我希望它也能帮助你: Applet

如果你能想象现实生活中数据结构的实现,或解决现实生活中的问题,那么你可能会发现它更容易理解。

这里有一些

  1. FIFO链接列表 – 这是通过在麦当劳的驱动器
  2. LIFO链接列表 – 一叠餐盘
    • search和sorting – rolodex(如果你真的老了,你实际上已经看到这些东西之一)

这里是一个很好的文章,让你开始: http : //www.codeproject.com/KB/cpp/linked_list.aspx。开始一个简单的链接列表。 这很容易,你会比其他数据结构更容易理解。 堆栈和队列在概念上可能更容易,但它们是基于简单的链表。 然后你可以移动到双链表和树。 期待看到你的编码问题,祝你好运! 🙂

如果你是一个视觉学习者,然后问你的老师更多的图表。 你可能会问其他学生是否可以和他们一起学习。 也许他们中的一个能够以一种更容易理解的方式向你解释事情

一个好的资源是NIST的algorithm和数据结构字典 。 你不会坐下来记住所有这些信息,你不应该使用它来避免编码你自己的结构,这将完全无效的类的价值,但本网站作为一个很好的参考,因为它链接数据结构中包含了使用它们的algorithm,并且还显示了一些变体,这些变体提供了有关如何修改用于其他用途的结构的信息。

希望有所帮助。 祝你好运。


我可以记得我的第一个数据结构课程。 我记得起初有点不知所措。

我更多的是一个视觉学习者。 为了更好地掌握材料,它确实有助于看图片。 我曾经画出插入,删除和遍历数据结构(如链表或队列)的步骤。 在我完成之前,它已经占用了大量的纸张,但这是非常值得的。

一旦我画出了插入的过程,什么不是,实际编程数据结构的过渡就容易多了。

能够可视化记忆中发生的事情确实有帮助。 和其他人一样,在我之前提到:练习,练习,练习!

这是成功的一大部分。

祝你好运!

不确定这是否有帮助,但可能有些鼓舞。

4年前我参加了数据结构研究的时候,我就坐在同一条船上。 我带着足够的知识经历过class级,至less在课堂上得到B,即使我不了解它。

我不明白模板,链表,“这个”指针,而且一般也不了解指针,这也是很大的阻碍了我的能力。 我奇迹般地完成了作业和testing所需要的东西(尽pipetesting成绩对每个人来说仍然很低,而我的老师却弯腰弯腰),并且完成了B.

之后,我又继续上了几年课。 我发现在这些课程中分别教授不同的概念,帮助我更好地理解它们。 algorithm教授更多关于sorting和大O,大会更多地了解计算机的“底层”内容,帮助我理解指针等等。

我意识到我第五年的第二个学期,我几乎都知道数据结构的所有概念,而且我甚至没有花费额外的努力来学习它们,至less不是从回头看,而是专门去理解数据结构,如果这是有道理的。

在没有任何实际的努力的情况下,我最终编写了一个模板化的链接列表堆栈,并在操作系统中为几个作业分配排队,我理解他们。 它把我吹走了。 我很积极,这对你也是一样。 给它时间和专注于其他类,它会全部点击。 这似乎花了所有的一切点击我,但它确实。

希望有所帮助。

老实说,我最初是一名自学成才的C ++程序员(我的主要参考是来自Half-Life 2的Source游戏引擎的公共领域代码),并且通过绘制图表和阅读评论和代码。

也许我只是一个神童或什么东西,因为它似乎总是对我来说比较容易,但是我花了很多时间阅读,思考和分析每个结构的特定用途,以及为什么每个结构作为独立于其他数据结构的东西而存在。

在高中时,严格限制的TI-83 Plus计算器上编写了一些严肃的代码项目(例如Connect Four和一个横向卷轴空间射击游戏,以及3D等距绘图仪和2D绘图程序)(ps使用TI-Basic, 而不是 Assembly),我意识到什么样的操作更有效率,并且我意识到在某些情况下,内置列表系统(基本Vector)是如何限制数据存储的。 当我尝试使用不同大小的input列表来计算程序的运行时间时,我也想到了Big-O如何工作。

练习,思考一些事情,并尝试弄清楚自己是如何工作的,而且不要害怕被testing弄得肮脏。 毕竟,没有实验的科学是什么?

当我教授编程时,我总是把这些揭秘的书籍提交给我的学生。

我build议你阅读:
– 数据结构揭秘
– OOP揭秘

这两本书在打破简单易读的术语的数据结构和OOP原则方面做得很好,并且容易遵循例子。 这是一个很好的概述,但不涉及STL提供的数据结构。

Donald Knuth的“计算机编程艺术”,第1卷 。

实际上,我发现数据结构需要对指针和内存的理解。

例如,你应该能够饶恕为什么下面的链表不到一分钟不工作。

但是,为了理解为什么它不起作用,您必须了解如何在C和C ++中设置内存,并直观地理解指针的概念。

有些人喜欢画画和画画。 其他人喜欢看麻省理工开放式课程 – 我build议至less试一试。

 class node { int data; node* next; node* addnode() { node newnode; this->next = &newnode; return &newnode; } }; 

这是我大约十年前在学习数据结构时所写的一个链表的实现。

作为最后一点,实践和理论是优秀程序员/开发人员/计算机科学家的阴阳。 没有两个,你不可能真正精通。

如果您在O-notation方面有问题,那么Cormen et.al提供的“algorithm介绍”。 以简单易懂的风格介绍这些理论概念。 那么这本书基本上就是基本数据结构的圣经。 运行时/空间界限的certificate总是以非常有教育意义的方式呈现。

像往常一样,如果你学习这样的书,不要只读它,而是尝试大部分练习。 通常,这样做对学习这些东西非常有效。

另一种通用技巧:尝试join2-3个其他学生的本地学习小组 – 通常与其他人讨论(面对面)材料,同时试图向同学解释自学材料给你许多提示,这些提示你需要覆盖更多的东西。

为了掌握C ++的练习,Stroustrup的“C ++编程语言”为各种语言概念提供了一个很好的介绍和参考。 由于C ++是一种多范式的语言,因此初学者经常困惑实际上用于解决某些问题的实际概念。 为了帮助Scott Myers的“Effective C ++”是一个好的开始。

如果你的课程大量使用STL,那么还有“Effective STL”。 斯科特·迈尔斯的写作风格通常被认为对初学者非常“合适”。

对我来说,迄今为止,我发现的最好的书籍是用于理解数据结构的Steven Skiena的algorithmdevise手册 。
除了第一部分包括algorithm分析,algorithm和数据结构之外,第二部分在寻找(或至less缩小)正确的数据结构/algorithm来解决问题方面是非常宝贵的。