算法与数据结构.doc

数据结构与算法第一章 绪论1 数据结构的分类：线性结构。其中每个结点最多只有一个前驱和后继的结构。线性表（单链表、循环链表、双向链表）、栈、队列等都是线性表的结构。“一对一”树形结构。其中每个结点最多只有一个前驱，但可以有多个后继的结构。二叉树、树、森林都是树形结构。“一对多”复杂结构。其中结点的前驱和后继点个数都不做限制的结构。有向图、无向图都是复杂结构。“多对多”2 存储的各种表示：顺序表示、连接表示、散列旗袍、索引表示3 文件的处理，在文件上的操作的种类：检索插入删除修改排序4 算法的性质：有穷性、确定性、可行性练习题：1 计算下列程序片段的时间代价int i=1;while(i=n) printf(“i=%dn”.i); i=i+1;2 计算下列程序片段的时间代价int i=1;while(i=n) int j=1; while(j=n) int k=1; while(kn-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(struct DoubleNode);4 采用顺序存储方式表示矩阵一般有行优先顺序和列优先顺序。按行优先顺序存储，其地址计算公式为：loc(aij)=loc(a00)+in+j按列优先顺序存储，其地址计算公式为：loc(aij)=loc(a00)+im+j5 深度：一个广义表的深度，就是指广义表中所含括号的层数。练习题：1 某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为 100+411=144 2 线性表的链式存储结构主要有 、 、 三种形式。3 线性表的顺序存储时通过 来反映元素之间的逻辑关系，而链式存储结构是通过 反映元素之间的逻辑关系。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）。顺序栈 进栈的代码：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 !=NULL Plstack-top=NULL 栈满的条件5 队列队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的一端称为对头，允许进行插入的一端叫做队尾。 队列的插入操作通常称为入队，队列的删除操作通常称为出队。 顺序队列顺序队列的入队 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中的元素，然后结合栈的操作，能得到下列序列中的哪些序列（每个元素进栈一次，哪些序列可能为出栈的次序）？ 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个结点的完全二叉树，如果按照从上（根结点）到下（叶结点）和从左到右的顺序对二叉树中的所有结点从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）：若二叉树不空，则先按后根次序周游左子树；然后按后根次序周游右子树；最后访问根。 对称（中根）次序：若二叉树不空，则先按对称序周游左子树；然后访问根；最后按对称序周游右子树5 二叉树的表示 对于完全二叉树，如果按照（根结点）到下（叶结点）和从左到右的顺序，对二叉树中的所有结点从0到n-1编号，这样存放到一继数组中，只要通过数组元素的下标关系，就可以确定二叉树中结点之间的逻辑关系。（会做题）看p132图5.10及该数组的度 p133图5.116 看p136 线索二叉树7 哈夫曼树的权值 WPL=wili 假设有一组（无序）实数w1,w2,w3,wm,现要构造一棵以wi（i=1,2，,m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树（会构建哈夫曼树，会求权值）8 在树中，结点的度数：在树中一个结点的子结点个数叫做这个结点的度数9 树的周游：主要分先根次序和后根次序两种 先根次序：首先访问根结点，然后从左到右按先根次序周游根结点的每颗子树 后根次序：首先从左到右按后根次序周游根结点的每科子树，最后访问根结点10 p161长子-兄弟表示法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的结点，n2个度为2的结点,nm个度为m的结点，问该树中有多少个叶子结点？第七章 高级字典结构1 构造二叉排序树 p209-p2122 二叉排序树的删除检索被删除结点*p；if(*p无左子女) 用*p的右子女代替*p；else 找*p的左子树中最 右下结点*r； 用*