961-软件工程学科

【实例简介】
第一部分 软件工程 第二部分 计算机系统基础 第三部分 数据结构与算法
数据结构总结: 线性表 口是n个数据元秦的有限序列 口常见线性表包括数组、链表、栈、队列等 线性表的两种实现方式 口顺序 口链式 口对比:插入(有序、无序)、删除、查找、读取 环形链表、单向链表、双向链表、带啃兵节点的链表 口又称循环列表,是另一种形式的链式存储结构。它的特点是表中最后一个元 素的指针域指向头结点 单向链表存储结构的节点中只有一个指向后继节点的指针; 双向链表的节点中有两个指针,其中一个后继节点的指针,另一个指向前一 个节点的指针。 /单向链表使用的节点 typedef struct tag_A int nData struct tag_A"next: ∥/双向链接使用的节点 typedef struct tag_B int n data: struct tag_B*prec, struct tag _B *next: 口没有啃兵节点时,添加一个节点要先判断是否是第一个节点,并单独保留第 个节点的指针;以便于返回整个链表的头指针。有啃兵节点时,链表头是 固定的,不可能为空,后续的节点都是链接在前一个节点的,不需要单独判 断是否为头节点 栈 口栈是限定仅在表尾进行插入和删除操作的线性表 口后进先出特性(LIFO) 口栈顶、栈庶、出栈、入栈 设计递归问题的非递炟算法一般需要用到栈机制 ■三个数a、b、c进栈,不可能出现c、a、b顺序出栈 数制转换 口十进制数字与d进制数字的转换 口N=(Ndvd)×d+ n mod d 其中di为整除,mod为求余。 表达式求值 口中缀表达式转后缀表达式 规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成 为后绥表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括 号或优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并 捋当前符号进栈,一到最终输出后缀表达式为止。 思路 数字位序不变,运算符位置改变 后缀表达式无括号,运算顺序同中缀表达式 口后缀表达式求值 从左到右扫描后缀表达式,遇到运算符就把表达式中该运算符前面两个操作 数取出并运算,然后把结果带回后缀表达式;继续扫描直到后綴表达式最后一个表 达式。 ■三种表达式 前缀表达式 +a b 口中缀表达式 a+ b 口后缀表达式 b 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递函数 口优点:结构清晰、程序易读、正确性容易得到证明 口缺点:效率相对较低 ■队列 口队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表 口先进先出特性(FIFO) 口队尾、队头、入队、出队 ■双向队列 口亦称双端队列( Deque) 口是限定插入和删除操作在表的两端进行的线性表 口可以用于包装产生栈和队列 树 口是n(n≥0)个结点的有限集 口在任意一棵非空树中 有且仅有一个特定的称为根的结点 当n>1时,其余结点可以分为m(m>0)个互不相交的有限集,其 中每个集合本身又是一棵树,并且称为根的子树 口树属于层次结构数据结构 节 节点不仅包含数据元素,而且包含指向子树的分支 标签(忽略) 父节点、子节点、兄弟节点、祖先节点、子孙节点 路径(忽略)、树枝(忽略) 上层的节点、下层节点子树的根、同一父节点下的同层节点、从根到该节点所经分 支的所有节点、从该节点下层子树中的任一节点 根、叶子 根节点、终端节点 次数(就是“度") 节点的度∶节点拥有的子树个数或者分支的个数。 树的度:树中各节点度的最大值。 内部节点、外部节点 除根结点外的分枝结点统称为内部结点、外部节点一般是叶子 树的次数、K次树 树的次数就是树的度∶树中各节点度的最大值、K次数的树 节点层次、树的高度和深度 节点所在的层次,根节点是第一层、树的总层次 子树 设T是有根树,a是T中的一个顶点,由a以及a的所有后裔(后代)导出的子图 称为有向树T的子树,a是子树的根。 有序树、无序树 树中任薏节点的子结点之间有顺序关系,这种树称为有序树 如果捋树中结点的各子树看作从左到右有序的则该树为有序树 ordered tre,否则 为无序树。 树中任意节点的子结点之间没有顺序关系,这种树称为无序树也称为自由树 ■森林、果园 森林( (fores是m棵互不相交的树的集合,m(m0)棵树的集合。从定义可知,一棵树 有根结点和m个子树构成,若把树的根结点删除,则树变成了包含m棵树的森林。 当然,根据定义,一棵树也可以称为森林。 如果原来的树是有序的则砍去根后的森林也是有序的此时称该森林为有序森林或 果园。 ■二叉树( Binary Tree) 口另一种树形结构,特点是每个结点至多只有二棵子树,且子树有左右之分, 其次序不能任意颠倒 二叉树可能的五种基本形态 ■在二叉树的第i层上至多有2-个结点(i≥1) 棵二叉树第五层上至多有多少个结点?至少多少?答案:16,1 ■深度为k的二叉树至多有2-1个结点(k21) 一棵深度为5的二叉树至多有多少个结点?至少多少?答案:31,5 高度为h(h>0)的二叉树最少有个结点?答案:h 对于任何二叉树如果叶子节点数为n,度为2的节点数为n2则n=n2+1 满二叉树 一棵深度为k且有2-1个结点的二叉树 可以对满二叉树的结点进行连续编号,约定编号从根开始,自上而下,自左而右c 完全二叉树 深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉 树中编号从1到n的结点一一对应时,称为完全二叉树。 ■完全二叉树特点 叶子结点只可能出现在层次最大的两层上 对任一结点,若其右分支下子孙的最大层次为|,其左下分支的子孙的最大层次必为 或者|+1 深度为k的完全二叉树第k层最少1个结点,最多2-1-1个结点;整棵树最少2k1 个结点,最多21个结点 个具有767个结点的完全二叉树,其叶子结点个数为。 答案:384 分析:可以根据公式进行推导,假设n是度为0的结点总数(即叶子结点数),n是度为1的结点总数,n是度为2 的结点总数,由二又树的性质可知:n=n2+1,则n=n+n1+n2(其中n为完全二又树的结点总数),由上述公式把 n消去得n=2n+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n=(n+1)/2或no =n/?,合并成一个公式:nb=[(n十1)/2],就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得:384 具有n个结点的完全二又树的深度为ogn]+1 如果含有n31个节点的二叉树的高度为[ogn]+1,捋其所有结点按层次序编号则对 于任一节点j(1划￡n),有 如果j=1则节点j是树的根无双如果j1则其父节点 parent是节点/2 如果2n则节点j无左子节点;否则其左子节点为2 如果2+1>n则节点j无右子节点;否则其右子节点为2j+1 完全树的数组形式存储算法 将其编号为i的结点元秦存储在一维数组下标为-1的分量中 树的逼历 按某种搜索路径巡访树中每个结点:使每个结点均被访问一次仅且一次 二叉树的遍历可分为前序、中序、后序、层次序等 普通树的遍历可以分为先根、后根、层次序等 ■二叉树的逼历 前序、中序、后序定义 前序先根结点,遍历左子树,逼历右子树 递归算法: void preorder traverse( BiTreet) (T{ >aata PreOrder Traverse(T->lchild) PreOrder Traverse (T->rchild)i 中序:中序逼历左子树,访问根节点,遍历石子树 递归算法: void inorder traverse( Bitreet) If (Di InOrder Traverse(T->lchild). Printf(%C,T->data); InOrder Traverse(T->rchild); 后序:后序逼历左子树,逼历右子树,访问根结点 递归算法: void PostOrder Traverse(BiTreeT)( If (Di PostOrder Traverse(T->lchild) PostOrderTraverse(T->rchild) Printf(°c;T->data); 层次序:从上而下,从左至右 常见问题 巳知树写遍历结果 已知逼历结果画树 依据∴:二叉树的前序和中序逼历可以唯一确定一棵二叉树 思路:前序定根,中序定左右 递归和非递算法实现 ■对于任意k次树到相应二叉树的转换算法 对于具有子节点nn2.n的节点n捋n作为其左子节点且k作为k(1￡ ￡k-1)的右子节点 思路“不同层在左,同层在右 简单方法:1在同胞兄弟之间加连线 2保留结点与第一个孩子之间的连线,去掉其余连线 3颠顺时针旋转45度,以根节点为轴左孩子不再旋转。 对于任意森林到相应二叉树的转换算法为 设T=(TT2…T)为m(m30)棵树的序列而BT(T,T…)为相应的二叉树, 则 如果m=0则BT为空树 如果m>0则T的根节点就是BT的根节点而BT的左子树是T的子 树Tn,T12T1k转换成的BT(T1T2.T1)其右子树为BT(T2…Tm) 简单方法:1将森林中的每棵树转换成二叉树 2将已转换的二叉树的根相连 3顺时针旋转45度 Huffman树: 又称最优树,是一类带权路径长度最短的树 基本概念 树的路径长度:从根到每一结点的路径长度之和。 结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度:中所有叶子结点的带权路径长度之和,通常记做WPL WPL=∑1W+li Huffman算法基本概念: 假设有n个权值W,试构造一棵有n个叶子结点的二叉树,每个叶子的结 点带权为W,则其中wPL最小的二叉树称为最优二叉树或赫夫曼树 ■ Huffman树算法 (1)由给定的n个权值,W,…W,构造具有m棵二叉树的集合F={ 万,万,灬,不m},其中每一棵二叉树不只有一个带有权值w的根结点,其左、右子树 均为空。 (2)在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新 的二叉树。置新的二叉树的根结点的权值为其左、右子村上根结点的权值之和 (3)在F中删去这两棵二叉树,加入新得的树。 (4)重复(2(3),疸到F只含一棵树为止。这棵树就是赫夫曼树 fuman编码 编码:等长编码/不等长编码 前缀编码:若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字 符编码的前缀,这种编码叫做前缀编码 Huffman编码∶以n种字符出现的频率做权,设计一棵赫夫曼树,由此得到的前缀 编码称为 Huffman编码 例题⌒ 查找描述 查找的基本概念;对线性关系结构的査找,顺序査找,二分査找; Hash查找法常见的Hash函数(疸接定址法随机数法hash冲突的概念,解 决冲突的方法(开散列方法/拉链法闭散列方法/开址定址法)二次聚集现象; BST树定义性质ADT及其实现BST树查找插入,删除算法; 平衡树(AVL)的定义性质ADT及其实现平衡树查找插入算法平衡因子的 概念 优先队列与堆堆的定义堆的生成调整算法;范围查询; 查找表 search table 具有同一类型数据元素(经常称为记录)的集合 ■查找表的基本操作有: 查找某个“特定“记录是否在表中 查找到后取出某个“特定"记录的各个数据项 向表中插入记录 从表中删除记录 ■静态查找表( static search table) 仅用于查询的查找表。 ■动态查找表( dynamic search table) 若在查找过程中需同时插入表中不存在的记录;或者需要删除记录,则称之为 动态查找表。 ■关键字/键值(key): 记录某个数据项的值用其可以标示该记录 当记录只有一个数据项时其关键字即为该记录的值 如果一个key可以唯一标示一个就则称之为主关键字( primary key)否则称 之为次关键字( secondary key) ■查找( search): 在一个查找表中找出具有“特定"键值的那些记录 所谓查找戍功是指在查找表中找到了满足案件的记录,此时一般会返回找到 的记录或者返回记录的位置信息或者仅仅返回找到(true 否则称为查找失败,此时一般返回空指针或特殊值或者仅仅返回没有找到 fase),有时也会就此插入这个元素 ■二叉排序树( Binary Sorted Tree)BsT树 又称二叉搜索树或二叉查找树 或者是一棵空树; 或者是具有下列性质的二叉树 如果左子树非空则左子树中所有节点的键值均小于它的根结点的值; 如果右子树非空则右子树中所有节点的键值均大于它的根结点的值 它的左右子树也都是二叉排序树。 二叉排序树性质 如果对二叉排序树进行中序谝历,则得到一个从小到大排好序的列表所以可 以得到一种简单的排序方法叫做“树排序“( treesor) 我们也可以根据这个性质定义二叉排序树为如果一棵树按中序逼历为排好 序的,则这棵树是二叉排序 BST树查找,插入,删除算法 面图 算法 平衡二叉树 平衡因子(ba| anced factor) 二叉树上任一节点的左子树高度减去右子树高度的差 AVL Tree,根据其三位发明者( Adelson elskii and landis)的名字命名 棵BST树中每个节点平衡因子的绝对值不超过1 基本思想 在插入或删除节点后对新树进行判断如果新树已经变得不平衡,则通过旋转 〔 rotationη)的方法对树进行重组/(改组( re-arrange)使得重组后的树在保持查 找树特性的同时保持平衡 所谓旋转 通过改变支撑点来维持平衡 顺时针旋转为右旋逆时针旋转为左旋 可以进行连续的多次旋转 算法代码及基本的时间复杂度分析: 查找方法 平均时间 顺序查找 o(n) 二分查找 o(ogn) BST查找 o(ogn AVL查找 o(ogn) ■Hash查找法,常见的Hash函数: 哈希(Hash)函数 在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关 键字和结构中一个唯一的存储位置相对应。这个对应关系f为哈帮巫数按 这个思想建立的表为新表 哈希囪数的设定可以很灵活,只要使得任何关键字的哈希函数值都落在表长 允许范围之内即可。 直接定址法 直接取key或者key的某个线性函数值 h(key)=akey+b,ab为常数 除留余数法 选择一个适当的正整数P,用P去除关键字,取所得得余数作为散列地址, 即:H(key)=key%P 方法的关键是选取适当的P。选择P最好不要是偶数,也不要是基数的幂。 般地选P为小于或等于散列表长度m的某个最大素数比较好。 缺点 整数相除速度较慢 冲奕与解决冲奕 对不同的关键字可能得到同一哈希地址,这种现象称冲奕。具有相同凼数值的关键 字对该哈希函数来说称作同义词。 在一般情况下,沖奕只能尽可能的少,而不能完全避免。 解决冲奕的共同思想:将具有相同函数值的记录存作一个链 闭散列方法/开址定址法 冲奕记录存储在表内 开散列方法链地址法 冲奕记录存储在表外 解决冲奕的基本思想 当冲突发生时,使用某种方法在散列表中形成一个探查序列(也称之 为“链"),按此序列逐个单元的查找,直到找到一个指定的关键字或 碰到一个开放的地址(单元为空)为止。 H=(H(key )+d)mOd m ￡jm-1m为hash表长度 d为增量数列各种方法的不同就区别在取不同的增量数列 上 常用的增量数列 线性探测法 二次探测法 伪随机法 再哈希法/二次哈希法 桶式散列法 线性探测法 【实例截图】
【核心代码】