数据结构笔记.doc

数据结构笔记.DOC2004数据结构笔记数据之间的内在联系。要了解3种数据结构的概念:逻辑结构;物理结构;基本操作。例如:栈和队的逻辑结构都是线性的,但她们的基本操作不同,就是不同的数据结构。常见的数据结构的分类:线性关系;集合关系;一对多;多对多(图人什么事物理结构(应该有印象)。算法设计吋要用类PASCAL,类C,不要用C++.算法分析的常用方法:事前分析;事后统计。时间/空间复杂度的概念。空间是算法运行时资源占用情况。时间复杂度:最坏,最好,平均。例如:归并排序都是0(n*logn),最好,最怀,平均都是一样的插入排序:最好为O(n),最坏为O(n2)线性表:逻辑关系,各种基本操作,两个有序表的归并。线性表的顺序存储:线性表的操作在顺序表中的实现。例如:lo插入与删除和插入的位置与表长有关。,要有插入位置的概率分布表达式,即给岀此表达式,算平均复杂度。线性表的链式存储:链表的基本操作:2个有序表的归并。例如:lo把链表就地逆置:一个指针P指向当前逆置好的一系列节点的最后一个节点,取P的NEXT插入队头。:节点红黄蓝在链表上无序排列,把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针P,头指针S,,S后接红节点。若P为红,插入S后。若P为黄,插入Q后。若P为兰,不动。然后P向后移,求下个。注:要了解单链表的插入,删除在什么位置操作。静态链表(数组表示人不能象单链表那样不受限增加节点。循环链表:如果表示队列,用它最好。P指向队尾。好处:用于优先队列中。双向链表:单链表中只有P指向当前节点,不能删除P。因为无法找到P的前驱。而双向链表可以。注意指针变化情况。栈:后进先出。基本操作:出入栈,取栈顶。在顺序表和链表上的实现;出栈序列是否合理?例如:入栈序列是1,2,,,n,则出栈序列有几种?(即n个节点的二叉树的个数。因为树的先序是1,2,,,n)o栈与递归:见我给你寄过去的手写体。队列:先进现出。链队列,循环队列。例如:lo把从队头开始的第i个元素删除:队列只有出队入队,不能育•接删除。要先将前“个岀队,入队尾;i出队;i+1以后的出队入队尾。(队头与队尾交互):岀队入栈;后岀栈入队。注意:这些结构的基本操作有什么,不能混。循环队列:队头指针和队尾指针。记住队空和满的标志。见手写版。串:loKMP算法,求NEXT函数值等。时间:O(n+m)o其中,模式匹配为0(n);预处理为0(m),要会证明她们。简略证明见手写版。,时间为0(n)是不行的,至少要052)。具体证明估计不会考。17・数组:存储位置与下标对应。特殊数组(对称,上三角等)。三元组,稀疏矩阵(求逆)。计数技术,在设计算法中的应用。十字链表不考。广义表:基本概念,存储结构(二叉链表)。应用不考。广义表递归算法了解。二叉树的性质(熟)。存储结构:二叉链表,三叉链表。遍历:屮,先,后。按层遍历:用辅助队列。例如求K层有多少节点。线索二叉树:中序(先后序不考)。线索中的插入删除不考。树与森林的遍历:树的先根与后根(分别对应相应二义树的先序,中序)。森林的先序和后序(分别对应相应二叉树的先序,中序)。树与二叉树 对应。由先序屮序可以唯一确定二叉树。而由先序后序不能。例子见手写版。二叉树可以为空,树不能