数据结构……那么我如何理解它们?[关闭]

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

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

数据结构是内存中数据的布局。把内存看作一个长列表,就像一个购物列表,但是没有条目。

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)

通过可视化每个数据结构的布局,它们在如何需要内存以及如何真正工作方面对我来说变得更加明显。( 也在记忆中 )我希望我的例子能给你一些简单的入门知识,让你将来的学习有基础。作为数据结构的最后一个例子,我将给出一个不平衡的二叉树,它具有以下元素插入顺序: 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

希望有帮助!

这是我最大的帮助… 由于你是一个视觉化的人,谷歌一些可视化排序算法,树遍历,散列等,以获得一个大致的想法,什么是发生的。在那之后,尝试用不同的结构制作一个简单的程序,并对它们进行不同排列的实验——例如,你可以先制作一个链表,然后将其变成循环链表,然后将其变成双链表,然后将其变成双循环链表,等等……

您只需对这些结构进行试验,这样,您将开始了解哪些数据结构适合您要开发的应用程序。

这是一些很好的推荐信。 排序算法: http://www.sorting-algorithms.com/ 树遍历: http://nova.umuc.edu/~jarc/idsv/lesson1.html 图形遍历: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

至于效率(大O分析),一旦您了解了数据结构每个操作的算法级别上正在发生的事情,就会或多或少地自然而然地了解到这一点。

我的大学强调的是开发自己的数据结构(这是自下而上的学习),而不必跳入预先建立的C++模板(自顶向下的学习)。通过从头开始,您真正了解了插入、删除、搜索(遍历)和从某个结构访问数据所涉及的开销,这将有助于您将来设计系统时的直觉。

练习,练习,练习。

我对你的第一条建议是尽可能精通C++。

数据结构和编程是两个非常不同的主题。如果您发现自己在编程方面遇到困难,那么您不太可能理解数据结构。

你是如何精通C++的?练习,练习,练习。所有程序。尽你所能去了解它。写几十个小程序。你可以做任何事情来适应C++。

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

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

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

此数据结构表示一个人。你需要确保你理解简单的结构概念,比如这些,然后你可以转向更大的事情。

例如,当您开始讨论数据结构(如堆栈和队列)时,首先尝试从概念上理解数据结构在做什么。例如,对于堆栈,我们使用后进先出原则,即后进先出。对于队列,我们使用FIFO原则(先进先出)。

还有一个会绊倒很多人的链接列表。您需要很好地理解这一个的指针,所以在尝试处理链接列表之前,首先要做一些简单的事情:

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

您应该能够查看该代码并立即知道它在做什么。如果不能,那么您还没有准备好移动到更高级的数据结构,如链表。

我想说的重点是你需要先把基础知识冷却下来,然后再建立在基础之上。同样重要的是要非常努力地跟上课堂,询问你的老师或导师是否有问题,并确保你每周都在正常的轨道上,不要落后。

计算机科学课和数学课很像,每周都是建立在你从前n周学到的所有东西的基础上。所以如果你不理解一个关键的概念,比如指针,那么你在学期的剩余时间里会遇到重大的困难。

我喜欢DCP的回答。

最好的方法是写一些小例子来概括数据结构。即使你从你的书中复制它们,如果你能让它们工作和编译,用你自己的手指输入它们,你也会学到很多东西。

当你读你的书时,在每堂课结束后,写下你能创建和使用的最短的程序(显示、使用等)你刚刚学到的数据结构。

然后,当你必须完成你的实际任务时,你会在你尝试的时候学到更多的东西,并把你的小例子插入到解决任务问题中去。

我认为为单个数据结构编写最短/最小的工作代码是非常有用的。另外,不要害怕复制代码(为了你自己的启发,而不是为了你的成才)。如果您通过键入而不是复制粘贴进行复制,那么您最终会学到很多东西,因为它强制您查看代码中的每个字符。

如果整个数据结构看起来“太多”了,以至于无法完全理解,那么从编写数据结构组件的小示例开始。所以用一个指针来储存书名。然后用指向指针的指针存储许多书的标题。阅读带有方括号符号和指针算术的书名。在简单函数中使用递归,这样可以清楚地知道发生了什么…..例如,递归显示一个数的阶乘比递归显示二叉树(在我看来)更简单…

您将看到您的问题区域是什么,并尝试将它们隔离到尽可能小和具体的一件事情上,然后尽可能短地编写一个可以处理该问题区域的程序…..然后再建立起来。

你的讲座是关于整个数据结构的…巨大的卡姆卢斯云理论库……所以,本质上,它们是自上而下的。在小问题中隔离语法和用法的小问题是自下而上的。所以你的老师帮助你从上攻击,你通过练习从下攻击,很快就没有任何东西在中间!

唯一有意义地学习数据结构和算法的方法是将它们应用于实际问题,并使用它们来解决实际问题。将它们编码成可工作的应用程序——即使它们是人为设计的——将加强理论知识,这样您将有更好的机会保留这些想法并将它们集成到您的个人问题解决方法中。

我建议你读一本关于算法的好书(Cormen等人的《算法导论》)。这是我的建议)。通过这本书,你将同时开发和使用不同的数据结构,你很可能会意识到每种结构都有什么好处。数据结构只作为实现不同目标的手段:解决特定问题。

根据你有多少时间或者想花多少时间在上面,你可以尝试从不同的编程竞赛中得到问题,比如ACM ICPC。大多数问题都需要你练习这些知识。请注意,算法和数据结构都是语言不可知论者,所以如果您对任何其他语言都有很好的了解,就使用它。

在我看来,比起理论课,这些东西在工作中或是通过经验来学习会更好。大多数时候,当我在学校的时候,努力保持在曲线的前面是很重要的一部分,我认为这和你经历过的经历类似。虽然你想彻底理解它是值得称赞的,但只要你知道在需要的时候从哪里找到好的参考材料,那么课程就已经达到了它的目标。

大多数课程将建立在你在过去的课程中所获得的知识之上。你会在学习中再次遇到这些细节,你的教授应该能够帮助你将过去学到的知识应用到你现在的课堂作业中。作为一个互动型的学习者,办公时间、实习和指导机会似乎是获得你想要的信息的更好方法。

祝你好运!

您需要记住的一件事是,数据结构不仅仅存在。它们的发明是为了满足需求,这意味着它们出于某些原因是好的,但不适合其他人。
找出这些原因是什么,数据结构有什么好处,在你被告知之前,试着找出操作的大O。
总是比较数据结构。即使是最简单的一个数组。以它为起点,将找到的每个数据结构与数组进行比较。有时你会发现一些小技巧,帮助你避免使用大数据结构。
对我来说,帮助我理解很多数据结构和算法的是这里的小程序,我希望它也能帮助您: Applet

如果您能够在现实生活中可视化数据结构的实现,或者解决现实生活中的问题,那么您可能会发现它更容易理解。

这里有几个

1. FIFO链接列表-这是麦当劳的驱动器
2. 后进先出法链表-一堆餐盘
   • 搜索和排序-一个Rolodex(如果你老了,你实际上已经看到了其中的一个)

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

如果你是一个视觉学习者,那就向你的老师要更多的图表。你可以问其他学生你是否可以和他们一起学习。也许其中一个可以用一种更容易掌握的方式向你解释事情。

一个好的资源是 The NIST Dictionary of Algorithms and Data Structures . 你不会坐下来记住所有这些信息,也不应该用它来避免对你自己的结构进行编码,这会使类的值完全无效,但是这个站点是一个很好的参考,因为它将数据结构与使用它们的算法相链接,并且还显示了一些变体,这提供了洞察力。如何修改结构以供其他用途。

希望有帮助。祝你好运。

我记得我的第一个数据结构课程。我记得刚开始有点不知所措。

我更像是一个视觉学习者。为了更好地掌握材料,它真的有助于看图片。我曾经画出插入、删除和遍历数据结构(如链表或队列)的步骤。在我完成之前,它花了我很多纸,但它是如此值得。

一旦我画下插入的过程和不需要的东西,到实际编程数据结构的转换就容易得多。

能够想象记忆中发生的事情真的很有帮助。正如我前面提到的:练习,练习,练习!

成功的很大一部分。

祝你好运!

不确定这有什么帮助,真的,但这可能有点鼓舞人心。

4年前,当我使用数据结构时,我也在同一条船上。我通过这门课,有足够的知识来通过并获得B,至少,在课堂上,即使我不太明白。

我不理解模板、链接列表、“这”指针,也不太了解一般的指针,这极大地阻碍了我的能力。我奇迹般地完成了家庭作业和考试所要求的(尽管每个人的考试成绩仍然很低,我的老师最终还是把它们弯成曲线),并得了B。

在那之后,我又上了几年其他的课。我发现在这些课程中,不同的概念是分开教授的,这有助于我更好地理解它们。算法教会了更多关于排序和大O的知识,汇编教会了更多关于计算机“引擎盖下”发生的事情,这有助于我理解指针等等。

我意识到我第五年的第二至最后一个学期,我几乎对数据结构的所有概念都了如指掌,而且我甚至没有花费任何额外的努力去学习这些概念,至少不是从回顾和尝试具体理解数据结构的角度来看,如果这有任何意义的话。

没有任何实际的努力,我最终编写了一个模板化的链接列表堆栈和队列,以便在操作系统中完成一些家庭作业,我理解它们。它把我吹走了。我肯定这对你也是一样的。给它一点时间,把注意力集中在其他课程上,所有的课程都会点击。似乎要花很长时间才能全部点击到我身上,但确实如此。

希望有帮助。

老实说,我最初是一个自学的C++程序员(我的主要参考是半衰期2的源游戏引擎的公共领域代码),我通过绘制图表和阅读评论和代码,学到了很多让我通过数据结构的东西。

也许我只是一个奇才或者其他什么东西,因为它对我来说总是相对容易的,但是我在花费大量的时间来阅读、思考和分析每种结构的特殊用途,以及为什么每种结构最初都是与其他数据结构分离的。

在高中严格限制的Ti-83 Plus计算器上(P.S.使用Ti Basic,P.S.)编写了一些严肃的代码项目(即连接四个和侧滚式空间射手,以及三维等轴测绘图仪和二维绘图程序)。 不 汇编),我意识到什么样的操作更有效,我意识到内置列表系统(一个基本向量)在某些情况下对于数据存储的限制。当我尝试用不同大小的输入列表为程序的运行时计时时,我还发现big-o是如何工作的。

练习,思考你正在做的事情,并试着找出它们是如何工作的和为什么工作的,不要害怕被测试搞得一团糟。毕竟,没有实验的科学是什么?

当我教编程的时候,我总是把那些神秘的书交给我的学生。

我建议你阅读:
- Data Structures Demystified
-OOP去神秘化

这两本书在分解数据结构和OOP原则方面做得很好,用简单易读的术语,用简单易懂的例子。这是一个很好的概述,但它不涉及STL提供的数据结构。

Donald Knuth's "The art of computer programming", vol 1 .

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

例如,您应该能够探索一下为什么下面的链接列表在一分钟内不能工作。

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

有些人喜欢画画。其他人喜欢看麻省理工学院开放式课程——我建议至少尝试一下。

class node
{

  int data;
  node* next;

  node* addnode()
  {
    node newnode;
    this->next = &newnode;

    return &newnode;
  }
};

这近似于我10年前学习数据结构时写的一个链接列表的(窃听)实现。

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

如果您对O符号有问题,那么Cormen等人的“算法简介”。以易于理解的方式介绍这些理论概念。这本书基本上是关于基本数据结构的圣经。运行时/空间边界的证明总是以非常有指导意义的方式呈现。

像往常一样,如果你学习这本书,不仅要读它,而且要努力做大多数练习。通常,这样做对学习这些东西非常有效。

另一个一般技巧是:试着加入一个由2-3名其他学生组成的本地学习小组——通常,与其他人(面对面)讨论这些材料,同时试着向同龄人解释自学的材料,这会给你很多提示,你需要更多的东西。

为了掌握C++的习题,Stroustrup的《C++程序设计语言》对各种语言概念有很好的介绍和借鉴。由于C++是这样一种多范型语言,初学者经常会混淆在实际中用来解决某些问题的概念。帮助Scott Myers完成“有效C++”是一个很好的开始。

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

对我来说,迄今为止我所找到的理解数据结构的最好的书是史蒂文·斯基纳的。 The Algorithm Design Manual .
除了第一部分包括算法分析、算法和数据结构外,第二部分在寻找(或至少缩小)解决问题的正确数据结构/算法方面绝对是无价的。