数据结构基础知识

范围第1，2，3，6，7，9，10章。黑体字为老师提到的考点，涉及算法都不考程序第一章绪论㈠四个基本结构：集合、线性结构、树形结构、网状结构（书p5图）㈡四种存储（物理）结构：顺序存储表示、链接存储表示、索引存储表示、散列存储表示㈢程序产生的五个阶段：需求、设计、分析、细化与编码、验证㈣算法的五个特性：有穷性、确定性、可行性、输入、输出（书p13）㈤几种时间复杂度：（考计算）1.O(1):常数时间2.O(log2n)：对数时间3.O(n)：线性时间4.O(nlog2n)：线性对数时间5.O(n2):平方时间6.O(n3):立方时间上述的时间复杂度的优劣次序如下（n=16):7.O(2n):指数时间O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)第二章线性表㈠单链表的基本运算·插入（三种情况，2和3一样）1.在第一个结点前插入2.在链表中间插入3.在链表末尾插入newnode-link=first;newnode-link=p-link;newnode-link=p-link;first=newnode;p-link=newnode；p-link=newnode；·删除在单链表中删除ai结点q=p-link;(此时p指针指向ai-1)p-link=q-link;㈡带表头结点的单链表·插入q-link=p-link;·删除q=p-link;p-link=q;p-link=q-link;deleteq;㈢双向循环链表·插入q-prior=p;·删除q-next=p-next;p-next-prior=p-prior;p-next=q;p-prior-next=p-next;q-next-prior=q;第三章栈和队列㈠表达式求值（转换、求值）（*考在小题里）·表达式标识方法例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+·由原表达式求后缀表达式的方法1.设立暂存运算符的栈;2.设表达式的结束符为“#”,予设运算符栈的栈底为“#”3.若当前字符是操作数，则直接发送给后缀式;(后缀与前缀式操作数的顺序是相同的)4.若当前运算符的优先数高于栈顶运算符，则进栈;5.否则，退出栈顶运算符发送给后缀式;6.“(”对它之前后的运算符起隔离作用，“)”为自左括弧开始的表达式的结束符。·表达式求值的算法（课件，书p52）·算符间优先级（课件，书p53表3.1）例：表达式3*(7-2),求值过程（课件，书p54例3-1）㈡循环队列队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1:front=(front+1)%maxsize;队尾指针进1:rear=(rear+1)%maxsize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxsize==front;㈢递归（※最后一道大题，写一个小程序可能从二叉树里面考）第六章树和二叉树㈠二叉树的性质性质1在二叉树的第i层上至多有2i－1个结点。性质2深度为k的二叉树至多有2k-1个结点(k1)。性质3（证明必会）对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.证明：若度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1性质4具有n(n0)个结点的完全二叉树的深度为log2(n)＋1性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：·若i=0,则i无双亲·若i0,则i的双亲为(i-1)/2·若2*i+1n,则i的左子女为2*i+1，若2*i+2n,则i的右子女为2*i+2·若结点编号i为偶数，且i!=0,则左兄弟结点i-1.·若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.·结点i所在层次为log2(i+1)㈡二叉树的存储结构二叉链表（课件，书p127图）//二叉树的二叉链表存储表示typedefstructBiTNode{TElemTypedata;StructBiTNode*lchild*rchild;//左右孩子指针}BiTNode,&BiTree;㈢树的左子女-右兄弟表示（二叉链表表示，会画(书p137图6.15)）㈣森林与二叉树的转换（孩子放左，兄弟放右，见课件，书p138图6.17）㈤二叉树的遍历（课件，书p128遍历二叉树的递归算法定义，p129式6-3式6-4式6-5分别为图6.9中树的先序、中序、后序遍历结果）㈥二叉树的计数（给出两种遍历次序，把树画出来（见课件，书p154例6-5））㈦树的遍历1.先根次序（对应二叉树前序）2.后根次序（对应二叉树中序）㈧线索二叉树（会画）中序线索二叉树BDAEC（如图）LeftThread=0,LeftChild为左子女指针LeftThread=1,LeftChild为前驱线索RightThread=0,RightChild为右子女指针RightThread=1,RightChild为后继指针㈨霍夫曼树（计算带权路径长度，画出构造过程，计算霍夫曼编码）（课件，书p146）第七章图（凡涉及算法都看）㈠图的存储结构邻接表（画法：把所有顶点列出，再把与每个顶点直接相连的顶点接在后面。课件，书p164图7.10为图7.1的邻接表，书p171图7.14为p159图7.3(a)的邻接表）㈡两种图的遍历方法（要会遍历）:深度优先搜索DFS（类似树的先根遍历）、广度优先搜索BFS（类似树的按层次遍历）（课件，书p168图7.13）㈢最小生成树—普里姆(Prim)算法（两个数组中间过程）（课件，书p174）㈣拓扑排序（给图写结果课件，书p181下面~182上面）㈤关键路径（课件，书p183~184）㈥最短路径—Dijkstra算法（课件，书p188图7.34、7.35）第九章查找㈠折半查找（比较几次）（课件，书p219）·折半查找算法实现1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。2.初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功lChildDatarChilddatafirstChildnextSibling若kr[mid].key，则high=mid-1若kr[mid].key，则low=mid+13.重复上述操作，直至lowhigh时，查找失败。㈡二叉排序树（二叉查找树）（课件，书p227）二叉排序树或者是一棵空树，或者是具有如下特性的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也都分别是二叉排序树。㈢平衡二叉树二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差（平衡因子BF）的绝对值不大于1·构造二叉平衡（查找）树的方法：（课件，书p234~235）（1）单向右旋平衡处理，可以记为左左-右。（2）单向左旋平衡处理，可以记为右右-左。（3）双向旋转（先左后右）平衡处理，可记为左右-左右。（4）双向旋转（先右后左）平衡处理，可记为右左-右左。㈣B-树B-树：一种平衡的多路查找树（课件，书p239图9.14）一棵m阶的B-树或为空树，或为满足下列特性的m叉树：1.树中每个节点至多有m棵子树2.若根结点不是叶子结点，则至少有两棵子树3.除根结点之外的所有非终端结点至少有m/2棵子树4.所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)其中Ki(i=1,…,n)为关键字，且KiKi+1,(i=1,…,n-1)Ai(i=0,…,n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki(i=1,…,n),An所指子树中所有节点的关键字均大于Kn,n(m/2-1)≤n≤m-1)为关键字的个数（或n+1为子树个数）。5.所有的叶子结点都出现在同一层次上，并且不带信息（空指针）。·B-树的插入：（课件，书p241~243）·B-树的删除：（课件，书p244算法9.14下~p245）㈤哈希表（给函数、处理冲突办法，给数往表里填）哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成，addr(ai)=H(ki)其中：ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法·除留余数法：设定哈希函数为:H(key)=keyMODp(p≤m)其中，m为表长，p为不大于m的素数或是不含20以下的质因子冲突：key1key2，但H(key1)=H(key2)的现象处理冲突的方法：开放定址法、再哈希法、链地址法·开放定址法：（课件、书p257）为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm其中：i=1,2,…,sH(key)为哈希函数;m为哈希表长;di为增量序列,有下列三种取法:1)线性探测再散列di=ci最简单的情况c=12)二次探测再散列di=12,-12,22,-22,…,3)随机探测再散列di是一组伪随机数列或者di=i×H2(key)(又称双散列函数探测)第十章内部排序㈠每种类型（了解）（课件，书）类型：1.插入排序：直接插入排序、折半插入排序、希尔排序2.快速排序：起泡排序、快速排序3.选择排序：简单选择排序、树形选择排序、堆排序4.归并排序：2-路归并排序5.基数排序：多关键字排序、链式基数排序㈡希尔排序（缩小增量排序）（课件，书271）基本思想：当待排记录数n很小时，直接插入排序的效率较高。当待排序列按关键字基本有序时直接插入排序的效率也较高。所以从这两点出发可对直接插入排序改进，先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。设待排序对象序列有n个对象,首先取一个整数gapn作为间隔,将全部对象分为gap个子序列,所有距离为gap的对象放在同一个子序列中,在每一个子序列中分别施行直接插入排序。然后缩小间隔gap,例如取gap=gap/2，重复上述的子序列划分和排序工作。直到最后取gap==1,将所有对象放在同一个序列中排序为止。㈢快速排序（课件，书p275）基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：·左侧子序列中所有对象的排序码都小于或等于基准对象的排序码·右侧子序列中所有对象的排序码都大于基准对象的排序码·基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。·然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。·基准对象也称为枢轴（或支点）记录。一趟快速排序的具体做法是：设两个指针low和high，设枢轴记录的关键字为pivotkey，首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。快速排序是一种不稳定的排序方法。㈣堆排序堆(Heap)：设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从1开始连续编号。若满足KiK2i&&KiK2i+1或KiK