Question

数据结构课程重点

Answer 1

我们马上也要考试了，这是我自己总结的重点，希望对你有所帮助：
-------------------------------------------------------------------------------
逻辑结构就是对数据元素间逻辑关系的描述；物理结构就是某种逻辑数据结构在计算机中的存储办法。
-------------------------------------------------------------------------------
时间复杂度就是算法执行中所有语句执行时间的总和。O（1）优于O（logN）优于O（N）优于O（N2）。
冒泡排序、选择排序、插入排序的时间复杂度都是O（N2），一般来说，插入排序优于选择排序优于冒泡排序。归并排序和快速排序都是O（N*logN）归并排序适用于两个有序线性表的合并，快速排序则是应用最多的排序方法。
-------------------------------------------------------------------------------
存储结构 丨 优点 丨 缺点

无序顺序存储 丨 插入快 丨 查找、删除慢
有序顺序存储 丨 查找快 丨 插入、删除慢
链式存储 丨 插入、删除快 丨 查找慢

若存储的数据需要频繁的插入删除，就用链式存储；若需要经常查找，可以用顺序存储。
-------------------------------------------------------------------------------
冒泡排序
先比较前两个数据元素，把这两个元素中较大的那个放在较小的那个元素后面；
再比较第二个和第三个元素大小，将这两个元素中较大的那个放在较小的那个元素后面；
以此类推直至比较完最后两个元素，这时整个表中最大的元素就被排在了最后面。
再进行第二遍比较，从第一个元素开始，至倒数第二个元素结束；
以此类推当有一遍比较结果一次也没有交换时，排序结束。
-------------------------------------------------------------------------------
折半查找仅适用于有序线性表。
取出表中处于中间位置的元素和待查找元素比较大小，判断待查找元素处于中间位置元素的左边还是右边；再取出左边部分（或者右边部分，具体是哪部分要看待查找元素处于中间位置元素的左边还是右边）处于中间位置的元素和待查找元素进行比较；一次类推，直到找到待查找元素。
-------------------------------------------------------------------------------
矩阵转置：一个m×n矩阵M的转置矩阵是一个n×m的矩阵MT ，即：MT（i,j）=M（j,i）
-------------------------------------------------------------------------------
在一棵深度为k（k>=1）的二叉树中，如果前k-1层都是满的，并且第k层或者是满的，或者是在右边缺少连续若干个节点，叫做完全二叉树。
-------------------------------------------------------------------------------
将树转换成二叉树：
树中所有相邻兄弟节点之间连线；
树种每个节点只保留它与第一个孩子的连线
以树根为轴心，顺时针转动一定角度，转换成二叉树。
-------------------------------------------------------------------------------
将二叉树转换成树：
若某节点是其双亲节点的左孩子，则把该节点的右孩子、右孩子的右孩子……都与该节点的双亲节点连起来；
删除原二叉树中所有双亲节点与其右孩子的连线；
整理得到的树，使每个节点的所有孩子节点位于相同层次高度。
-------------------------------------------------------------------------------
需要理解阅读的有：
哈夫曼编码
哈希表
二叉树的遍历
广义表（
-------------------------------------------------------------------------------需要看的代码有：
冒泡排序
链表
栈
队列