数据结构的重点知识点.doc

教材：数据结构教程（第4版） 李春葆主编、清华大学出版社要求：不是死记下面的文字，要根据书本用脑理解好！充分利用开发工具VisualC+6.0 或visual studio 帮助理解第一章（6大知识点）P5逻辑结构：1、线性结构：结点一对一关系2、树形结构：结点一对多关系3、图形结构：结点多对多关系P6存储结构：4、顺序存储：元素在内存里相邻（物理位置上相邻）5、链式存储：元素通过指针的指向相邻P13（倒数第四段）6、算法的时间复杂度第二章（4大知识点）线性表的顺序存储：P30 1、顺序表的结构体typedef struct ElemType dataMaxsize; Int length;SqList;P31-34 2、顺序表对元素操作的算法代码（要求理解好原理）特别重点：插入一个元素、删除一个元素线性表的链式存储：P38 3、单链表结点结构体typedef struct LNode ElemType data; Struct LNode *next;LinkList;P42-45 4、链表对元素操作的算法代码特别重点：插入一个元素、删除一个元素第三章（8大知识点）栈的顺序存储：P66 1、顺序栈的结构体P66-67 2、顺序栈对元素操作的算法代码特别重点：进栈、出栈栈的链式存储：P68（倒数第三段代码） 3、链栈结点结构体P68-70 4、链栈对元素操作的算法代码特别重点：进栈、出栈队列的顺序存储：P81 5、顺序队列的结构体P83-84 6、循环顺序队列对元素操作的算法代码特别重点：进队、出队队列的链式存储：P85（倒数两段） 7、链队列结点结构体P 86-87 8、链队列对元素操作的算法代码特别重点：进队、出队第六章（3大知识点）P121（第二段） 1、什么叫递归P123 2、递归模型包括递归出口和递归体P125-126 3、递归过程中怎么样利用栈保存中断地址和参数值第七章（14大知识点）P154 1、树的定义是递归的定义P156 2、树的基本术语：（1）结点的度、树的度（2）分支结点、叶子结点（3）孩子结点、双亲结点、兄弟结点（4）树的高度、森林P162-163 3、什么叫满二叉树、什么叫完全二叉树P163 7.2.2 第三行 4、总结点数n0+n1+n2第四行 总的分支数n1+2n2第六行 总的分支数=总结点数-1二叉树的链式存储P168 5、链二叉树的结点结构体typedef struct node ElemType data;struct node *lchild;struct node *rchild; BTNode;P171 6、二叉树查找结点算法代码P172 7、二叉树求高度算法代码P173-174 8、二叉树三种递归遍历算法（超重要！）P185 9、已知先序+中序序列-唯一确定一棵二叉树P187 10、已知后序+中序序列-唯一确定一棵二叉树P189第一段中文11、由n个结点组成的二叉树一共有2n个指针域，但只有n-1个有效指针，浪费了剩下的n+1个指针我们把这n+1个指针充分利用为线索P189第二、三段12、线索：某一个结点没有左孩子或没有右孩子且没有左孩子的使它指向它的前驱，没有右孩子的使它指向它的后继P19013、一棵二叉树中的绝对有空指针域（因为叶子结点没孩子），但已经给线索化的二叉树一定没有空指针域（因为上面空的指针值就是线索）P19414、构造哈夫曼树的关键：每一次选取最小的两个值组成二叉树，并且把刚算出来的值跟原来题目提供的值再一起比较选取最小的两个值第八章（8大知识点）P205-206 1、基本术语（1）端点、邻接点（2）顶点的度、顶点的入度、顶点的出度（3）n个顶点组成的无向完全图有 条边 n个顶点组成的有向完全图有 条边（4）简单回路或简单环（5）连通图、连通分量（6）权、网图的存储结构P208的代码2、邻接矩阵无向图时，是对称矩阵有边时为1或权值无边时为0P209的代码3、邻接表先写头结点，也叫顶点结点再写所有与头结点相邻接的邻接点P211 4、深度遍历：是递归的算法访问当前顶点的任意一个没有被访问的邻接点P2135、广度遍历：访问当前顶点的所有没有被访问的邻接点P223 6、最小生成树(只能是无向图)：以最少的边连接连通图中所以顶点有且仅有n-1条边包有所有n个顶点现实应用：在n个村庄里怎么样选择边架构通信网络，使成本最低P225 普里姆算法：U代表已找到的顶点，V代表剩下的顶点目的：每次由V里加一个顶点到U，使n个顶点全部加入到U里条件：每加一个顶点时，满足是代价最小的边P227克鲁斯卡尔算法：目的：每一次添加一条边，直到n-1条边全部添加进来条件：添加边时，满足是权值最小且不形成回路P2317、最短路径：(既可以有向图，也可无向图)经过的边数最少现实应用：由一个城市去另一个城市，怎么走法最短P232狄克斯特拉算法：用来求一个顶点到其余各顶点的最短路径P2408、拓扑排序：(只能有向图)现实应用：工程规划(例如学了C+，才可以学数据结构)P241第2-4行写拓扑序列的技巧：写出一个入度为0的顶点从有向图中，删除写的顶点且删除该顶点发出的边第九章（8大知识点）P2501、顺序查找：算法代码P2512、二分查找（重点）熟练掌握算法代码，只针对有序表二分查找的时间复杂度：lognP2543、索引查找分块有序块内无序P2564、二叉排序树的定义：任一结点比左孩子大，且比右孩子小任一棵子树本身也是一棵二叉排序树对二叉排序树使用中序遍历得到的序列一定要递增有序P258最后一行5、二叉排序树的插入：每插入一个都要从根结点开始往下比较每插入一个都要作为叶子结点P262最后一段6、二叉排序树的删除：分三种情况删除的结点为叶子结点删除结点只有单分支删除结点有双分支一、前驱替换法：找删除结点的左孩子的最右端（即为最大结点）二、后继替换法：找删除结点的右孩子的最左端（即为最小结点）P277第一行7、哈希函数：自变量x通过函数yf(x)求出的y为地址f为哈希函数，y