南大软院 数据结构.ppt

* * 例子 ababaafffaacdcdcdefefefefff a:6 b:2 c:3 d:3 e:4 f:9 5 a b c f d e 6 2 4 3 3 9 7 11 16 27 0 0 0 0 0 1 1 1 1 1 Exercise 给出dataanddataanddata的霍夫曼编码结果 * * * * * * * * * * * * * * * * * * * * * 数据结构 算法的时间复杂性 估算一个程序或者函数的时间复杂性就是首先选择一种或多种操作（如加、乘和比较等等），然后确定这种操作分别执行了多少次。 取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。 渐近符号（O） f(n)表示一个时间或者空间复杂性，是实例特征n的函数。显然，f(n)=0，同时n=0。渐近符号允许我们对于足够大的n值，给出f的上限值或下限值。 渐近符号O给出了函数f的一个上限。 f(n)=O(g(n))当且仅当存在正的常数c和n0,使得对所有的n= n0,有f(n)=cg(n) f(n)=3n+2, f(n)=O(n); f(n)=10n2，f(n)=O(n2) f(n) = 10n2+ 3n+2, f(n)=O(?) 直接插入排序算法 一个元素的数组是一个有序的数组 从第一个元素开始，通过把第二个元素插入到这个单元数组中，就可以得到一个大小为2的有序数组。 依次类推，插入第三个元素可以得到一个大小为3的有序数组,…… 该算法称为直接插入排序。 算法实现（JAVA） void InsertionSort (int a[], int n) { for (int i =1;in; i++) { int temp = a[i]; int j =0; for (j=i-1;j=0tempa[j]; j--) { a[j+1]=a[j]; } a[j+1] = temp; } } 该算法复杂度 比较次数，f(n)=n-1，f(n)=(n-1)n/2 所以f(n) = O(n*n)或则O(n2) 快速排序 任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。 exercise 给出上述快速排序理论上的最佳划分序列 抽象数据类型 表ADT 栈ADT 队列ADT 链表 数据对象实例的每个元素都放在单元或节点中进行描述。每个节点中都包含了与该节点相关的其他节点的位置信息。这种关于其他节点的位置信息称为链(link)。 L=(E1,E2,E3,……，En)是一个线性表。（单链表） E2 E1 E3 En 0 …… First 类定义 节点类 节点位置类 链表类 双向链表 在单向链表的基础上，再增加一个指向前一个元素的指针，即为双向链表。 0 1 2 3 0 n LeftEnd RightEnd …… Exercise (30 mins) 参考单链表，实现双向链表中的如下方法 find insert remove 抽象数据类型 - 栈 定义 栈是一个线性表，其插入和删除操作都在表的同一端进行，其中一端被称为栈顶，另外一端被称为栈底。 特点 Last In First Out 抽象数据类型 – 队列 队列也是表，其插入和删除操作在表的两端进行，插入元素在其中一端进行，称为队尾，删除元素在另外一端，称为队头。 特点 First In First Out Exercise 将一栈和队列串联构成一系统，1，2，3，…10，这十个数据以如下方式依次通过该系统，第一次过1个数据，第二次过2个数据，第三次过3个数据，第四次过4个数据，列出这些数据最后的顺序。 二叉树 二叉树 (binary tree) t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。 + b / d c * a 二叉树 遍历算法 前序（前根）遍历 中序（中根）遍历 后序（后根）遍历 二叉树的节点类实现 BinaryNode BinaryTree 二叉树遍历算法 Exercise(30 mins) 给出前述二叉树前序、中序和后序遍历结果 假设一棵二叉树的后序遍历序列为 D G J H E B I F C A，中序遍历序列为 D B G E H J A C I F，则其前序遍历序列为 。 高度为h的二叉树中，节点最大个数为 。 计算二叉树的高度。 计算二叉树中左子树比右子树高1的节点个数。 计算二