数据结构_2013new.

数据结构DataStructure《数据结构与算法分析-Java语言描述》，MarkAllenWeiss著冯舜玺译，机械工业出版社大纲算法复杂度查找与排序抽象数据类型–表、堆栈、队列二叉树二叉查找树哈夫曼编码程序=数据结构+算法瑞士科学家，图灵奖得主NicklausWirth教授的名言算法的时间复杂性估算一个程序或者函数的时间复杂性就是首先选择一种或多种操作（如加、乘和比较等等），然后确定这种操作分别执行了多少次。取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。渐近符号（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的有序数组,……该算法称为直接插入排序。（3）例子例如，已知待排序的一组记录的初始排列如下所示：),94(),27(),13(),76(),97(),65(),38(),49(RRRRRRRR按算法10.1进行直接插入排序的过程如图10.1所示。监视哨L.r[0]图直接插入排序示例[初始关键字]:(49)38659776132749i=2:(38)(3849)659776132749i=3:(65)(384965)9776132749i=4:(97)(38496597)76132749i=5:(76)(3849657697)132749i=6:(13)(133849657697)2749i=7:(27)(13273849657697)49i=8:(49)(1327384949657697)（4）算法效率从空间来看，只需要一个记录的辅助空间。从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。数达最大值(n+2)(n－1)/2（即），记录移动的次数也达最大值(n+4)(n－1)/2（即）。nii2)1(②当待排序列中记录按关键字非递增有序排序（“逆序”）时，总的比较次nii2③若待排序记录是随机的，即待排序列中的记录可能出现的各种排列概率相同，则取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数，约为n2/4。综上所述，直接插入排序的时间复杂度为O(n2)。①当待排序列中记录按关键字非递减有序排序（“正序”）时，所需进行关键字间比较的次数达最小值n－1（即），记录不需移动。ni21算法实现（JAVA）voidInsertionSort(inta[],intn){for(inti=1;in;i++){inttemp=a[i];intj=0;for(j=i-1;j=0&&tempa[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)快速排序(QuikSort)任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。[4655134294051770]ij[4655134294051770]ij[1755134294054670]ij[1746134294055570]ij[1705134294465570]ij[1705134294465570]ij[1705134294465570]ij[17051342]46[945570]ij图7-4快速排序的一次划分交换交换交换大纲算法复杂度查找与排序抽象数据类型–表、堆栈、队列二叉树二叉查找树哈夫曼编码抽象数据类型表ADT栈ADT队列ADT链表数据对象实例的每个元素都放在单元或节点中进行描述。每个节点中都包含了与该节点相关的其他节点的位置信息。这种关于其他节点的位置信息称为链(link)。L=(E1,E2,E3,……，En)是一个线性表。（单链表）E2E1E3En0……First类定义节点类节点位置类链表类双向链表在单向链表的基础上，再增加一个指向前一个元素的指针，即为双向链表。01230nLeftEndRightEnd……Exercise(30mins)参考单链表，实现双向链表中的如下方法–find–insert–remove2.双向链表typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;priorelementnext最后一个结点的指针域的指针又指回第一个结点的链表a1a2…...an3.循环链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。双向循环链表空表非空表a1a2…...an双向链表的操作特点：“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。ai-1aies-next=p-next;p-next=s;s-next-prior=s;s-prior=p;psai-1ai插入(注意：先后域再前域)ai-1删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1抽象数据类型-栈定义–栈是一个线性表，其插入和删除操作都在表的同一端进行，其中一端被称为栈顶，另外一端被称为栈底。特点–LastInFirstOut有一个空栈，元素序列a1,a2,a3,…,a10依次通过栈先后顺序排列是a5,a6,a4,a3,a8,a7,a9,a10,a2,a1,那么该堆栈至少应该是____个元素抽象数据类型–队列队列也是表，其插入和删除操作在表的两端进行，插入元素在其中一端进行，称为队尾，删除元素在另外一端，称为队头。特点–FirstInFirstOut大纲算法复杂度查找与排序抽象数据类型–表、堆栈、队列二叉树二叉查找树哈夫曼编码Exercise将一栈和队列串联构成一系统，1，2，3，…10，这十个数据以如下方式依次通过该系统，第一次过1个数据，第二次过2个数据，第三次过3个数据，第四次过4个数据，列出这些数据最后的顺序。二叉树二叉树(binarytree)t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。+b/dc*a二叉树遍历算法前序（前根）遍历中序（中根）遍历后序（后根）遍历二叉树的遍历（递归实现）二叉树遍历的定义–二叉树的遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。–二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。–通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化二叉树的遍历（递归实现）二叉树遍历的分类–二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。–若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。–如果限定先左后右，则只有前三种方式DLR（称为先序遍历）LDR（称为中序遍历）LRD（称为后序遍历）。下面的内容如果没有特别说明都采用二叉链表作为二叉树的存储结构二叉树的遍历（递归实现）先序遍历（DLR）–先序遍历的递归过程为：–若二叉树为空，遍历结束。否则：1：访问根结点；2：先序遍历根结点的左子树；3：先序遍历根结点的右子树。–先序遍历二叉树的递归算法如下：voidPreOrder（BiTreebt）{/*先序遍历二叉树bt*/if(bt==NULL)return;/*递归调用的结束条件*/Visite（bt-data）;/*访问结点的数据域*/PreOrder（bt-lchild）;/*先序递归遍历bt的左子树*/PreOrder（bt-rchild）;/*先序递归遍历bt的右子树*/}ADBCDLRADLRDLRBDCDLR先序遍历序列：ABDC先序遍历:二叉树的遍历（递归实现）中序遍历（LDR）–中序遍历的递归过程为：–若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。–中序遍历二叉树的递归算法如下：voidInOrder（BiTreebt）{/*中序遍历二叉树bt*/if(bt==NULL)return;/*递归调用的结束条件*/InOrder（bt-lchild）;/*中序递归遍历bt的左子树*/Visite（bt-data）;/*访问结点的数据域*/InOrder（bt-rchild）;/*中序递归遍历bt的右子树*/}ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC中序遍历:二叉树的遍历（递归实现）后序遍历（LRD）–后序遍历的递归过程为–若二叉树为空，遍历结束。否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树。（3）访问根结点；–后序遍历二叉树的递归算法如下：voidPostOrder（BiTreebt）{/*后序遍历二叉树bt*/if(bt==NULL)return;/*递归调用的结束条件*/PostOrder（bt-lchild）;/*后序递归遍历bt的左子树*/PostOrder（bt-rchild）;/*后序递归遍历bt的右子树*/Visite（bt-data）;/*访问结点的数据域*/}ADBCLRDLRDLRDADCLRD后序遍历序列：DBCA后序遍历:B二叉树的遍历（递归实现）举例–先序遍历结果序列：ABDGCEF–中序遍历结果序列：DGBAECF–后序遍历结果序列：GDBEFCA二叉树的遍历（递归实现）练习–先序遍历序号：A,B,D,E,C,F–中序遍历序号：D,B,E,A,C,F–后序遍历序号：D,E,B,F,C,A二叉树的节点类实现BinaryNodeBinaryTreeBinaryNode.javaBinaryTree.java二叉树遍历的应用应用：表达式求值的表达式语法分析树–表达式的语法用二叉树表示非常直观–把表达式语法树用3种遍历方式写出来会得到什么呢？先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后续遍历：abcd-*+ef/---/+*abcdef二叉树遍历算法BinaryTree.javaExercise(30mins)给出前述二叉树前序、中序和后序遍历结果假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为。高度为h的二叉树中，节点最大个数为2h-1。计算二叉树的高度。计算二叉树中左子树比右子树高1的节点个数。计算二叉树中树叶的个