数据结构总结(一)

  • 数组的元素都在一起,链表的元素是分开的,每个元素都存储了下个元素的地址。

  • 数组的读取速度很快,链表的插入和删除速度很快。

  • 二分查找的数组必须是有序的

  • 选择排序就是不断找出最小的数放入新数组,最后新数组就是排序好的结果

  • 递归有两个条件:基线条件和递归条件

  • 栈有两个操作:压入和弹出

  • 函数调用都是入栈,函数返回都是出栈;递归就是不断地入栈然后出栈的过程,递归过程太长的话,栈会很长,这将占用大量内存

  • 分而治之(D&C divide and conquer)是一种递归式问题解决方法,快速排序就是利用分而治之的思想。

  • 散列表的三个必要条件:(1)散列函数总是将同样的输入映射到相同的索引;(2)散列函数将不同的输入映射到不同的索引;(3)散列函数不知道数组有多大,只返回有效的索引。

评论