1、 数据结构与算法第一章 绪论1 数据结构的分类：线性结构。其中每个结点最多只有一个前驱和后继的结构。线性表（单链表、循环链表、双向链表） 、栈、队列等都是线性表的结构。 “一对一”树形结构。其中每个结点最多只有一个前驱，但可以有多个后继的结构。二叉树、树、森林都是树形结构。 “一对多”复杂结构。其中结点的前驱和后继点个数都不做限制的结构。有向图、无向图都是复杂结构。 “多对多”2 存储的各种表示：顺序表示、连接表示、散列旗袍、索引表示3 文件的处理，在文件上的操作的种类：检索插入删除修改排序4 算法的性质：有穷性、确定性、可行性练习题：1 计算下列程序片段的时间代价int i=1;while(
2、in-1;q=p;q-)palist-elementq+1=palist-elementq删除 for(q=p;qn-1;n-1;q+)Palist-elementq=palist-elementq+1;2 单链表：插入 int insertPost_link(LinkList llist,PNode p,DataType x)删除 int deleteV_link(LinkList llist,DataType x)3 循环双链表插入 p-llink-rlimk=p-rlink;p-rlink- -llink=p-llink;删除 q=(PDoubleNode)malloc(sizeof(s
3、truct DoubleNode);4 采用顺序存储方式表示矩阵一般有行优先顺序和列优先顺序。按行优先顺序存储，其地址计算公式为：loc(a ij)=loc(a00)+in+j按列优先顺序存储，其地址计算公式为：loc(a ij)=loc(a00)+im+j5 深度：一个广义表的深度，就是指广义表中所含括号的层数。练习题：1 某线性表采用顺序存储结构，每个元素占据 4 个存储单元，首地址为 100，则下标为 11的（第 12 个）元素的存储地址为 100+411=144 2 线性表的链式存储结构主要有 、 、 三种形式。3 线性表的顺序存储时通过 来反映元素之间的逻辑关系，而链式存储结构是通过
4、 反映元素之间的逻辑关系。4 在一个链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行 A s-link=p;p-link=s B s-link=p-link;p-link=sC s-link=p-link;p=s D p-link=s;s-link=p第三章 字符串一个串中包括的字符的个数称为这个串的长度。长度为零的串称为空串。第四章 栈与队列1 栈 栈是一种特殊的线性表，它所有的插入和删除操作都限制在表的同一端进行。表中允许进行插入、删除操作的一端叫做栈顶，另一端则叫做栈底。栈的插入操作通常称为进栈或入栈(push)，栈的删除操作通常称为 退栈或出栈（pull ）
5、 。顺序栈 进栈的代码：void push_seq(PSeqStack pastack,DataType x)出栈的代码：void pop_seq(PSeqStack pastack)链式栈 进栈的代码：void push_link(PLinkStack plstack,DataType x)出栈的代码：void pop_link(PLinkStack plstack)栈空的条件 plstack !=NULLPlstack-top=NULL栈满的条件5 队列队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的一端称为对头，允许进行插入的一
6、端叫做队尾。队列的插入操作通常称为入队，队列的删除操作通常称为出队。顺序队列顺序队列的入队 void enQueue_seq(PSeqQueue paqu,DataType x)顺序队列的出队 void enQueue_seq(PSeqQueue paqu)环形队列判满条件 (paqu-r+1)%MAXNUM=pauqu链式队列 链式队列的入队 void enQueue_link(PSeqQueue plqu,DataType x)链式队列的出队 void enQueue_link(PSeqQueue plqu)练习题：若按从左到右的顺序依次读入已知序列a,b,c,d,e,f,g中的元素，然后
7、结合栈的操作，能得到下列序列中的哪些序列（每个元素进栈一次，哪些序列可能为出栈的次序）？Ad,e,c,f,b,g,a Bf,e,g,d,a,c,bCe,f,d,g,b,c,a Dc,d,b,e,f,a,g第五章 二叉树与树1 结点的层数：规定根的层数为 0，其余结点的层数等于其父结点的层数加 12 结点的度数：结点的非空子树（即后缀）个数叫做结点的度数3 一般二叉树的性质：性质一：在非空二叉树的 i 层上，至多有 2i个结点（i0）性质二：高度为 k 的二叉树中最多有 2k+1-1 个结点（k0）性质五：对于具有 n 个结点的完全二叉树，如果按照从上（根结点）到下（叶结点）和从左到右的顺序对二
8、叉树中的所有结点从 0 开始到 n-1 进行编号，对于任意的下标为 i 的结点，有：如果 i=0，则它是根结点，他没有父结点，如果 i0，则它的父结点的下标为 （i-1）/2如果 2i+1n-1，则下标为 i 的结点的左子结点的下标为 2i+1，否则下标为 i 的结点没有左子结点如果 2i+2n-1，则下标为 i 的结点的右子结点的下标为 2i+2，否则下标为 i 的结点没有右子结点4 二叉树的周游（要求会做题）先根次周游（DLR）：若二叉树不空，则先访问根；然后按先根次序周游左子树；最后按先根次序周游右子树后根次序（LRD）：若二叉树不空，则先按后根次序周游左子树；然后按后根次序周游右子树；
9、最后访问根。对称（中根）次序：若二叉树不空，则先按对称序周游左子树；然后访问根；最后按对称序周游右子树5 二叉树的表示对于完全二叉树，如果按照（根结点）到下（叶结点）和从左到右的顺序，对二叉树中的所有结点从 0 到 n-1 编号，这样存放到一继数组中，只要通过数组元素的下标关系，就可以确定二叉树中结点之间的逻辑关系。 （会做题）看 p132 图 5.10 及该数组的度 p133 图5.116 看 p136 线索二叉树7 哈夫曼树的权值 WPL=w ili假设有一组（无序）实数w 1,w2,w3,wm,现要构造一棵以 wi（i=1,2，,m）为权的 m个外部结点的扩充的二叉树，使得带权的外部路径
10、长度 WPL 最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树（会构建哈夫曼树，会求权值）8 在树中，结点的度数：在树中一个结点的子结点个数叫做这个结点的度数9 树的周游：主要分先根次序和后根次序两种先根次序：首先访问根结点，然后从左到右按先根次序周游根结点的每颗子树后根次序：首先从左到右按后根次序周游根结点的每科子树，最后访问根结点10 p161 长子-兄弟表示法11 树林的周游：树林的周游方法有两种：先根次序和 后根次序先根次序：首先访问树林中第一棵树的根结点，然后先根次序周游第一棵树除去根结点剩下的所有子树构成的树林，最后先根次序周游除去第一棵树之后剩下的树林。后根次序：首先后根
11、次序周游第一棵树的根结点的所有子树构成的树林，然后访问树林中第一棵树的根结点，最后后根次序周游除去第一棵树之后剩下的树林12 p164 树林与二叉树的转换练习题：1 对于给定的一组权值 w=1.4.9,16,25,36,49,64,81,100，构造具有最小带权外部路径长度的扩充二叉树，并求出它的带权外部路径长度2 已知某二叉树的先根周游序列为 A,B,D,E,G,C,F,H,I,J,对称序周游序列为D,B,G,E,A,H,F,I,J,C,试给出该二叉树的后根次序周游序列3 已知一棵度为 m 的树中有 n1个度为 1 的结点，n 2个度为 2 的结点,nm 个度为 m 的结点，问该树中有多少个
12、叶子结点？第七章 高级字典结构1 构造二叉排序树 p209-p2122 二叉排序树的删除检索被删除结点*p；if(*p 无左子女)用*p 的右子女代替*p；else找*p 的左子树中最 右下结点*r；用*r 的右指针指向*p 的右子女；用*p 的左子女代替*p；第九章 图1 有 n(n-1)条边的有向图称为有向完全图有 n(n-1)/2 条边的有向图称为无向完全图2 度：与顶点 v 相关联的边数称为顶点的度，记为 D（v）(会求某一顶点的度)入度：若 G 是一个有向图，则以顶点 v 为终点的边的数目称为 v 的入度，记为 ID（v）出度：以 v 为始点的边的数目称为 v 的出度，记为 OD（v）
