数据结构与二叉排序树 .ppt

查找表：是一种以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构。 各种排序方法的综合比较 一、时间性能 ??? 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序； 时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序； 时间复杂度为O(n)的排序方法只有基数排序。 2.当待排记录序列按关键字顺序有序时: 直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。 3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1.所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn? )，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd? )。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它 们在序列中的相对位置，在排序之前和经过排序之后，没 有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用 稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 选择排序，快速排序和堆排序是不稳定的排序方法。 例上例的Vl(j) i=9…1为 已知 V(9)=Ve(9)=18 Vl(8)=Vl(9)-dut(a11)=18-4=14 Vl(7)=Vl(9)-dut(a10)=18-2=16 Vl(6)=Vl(8)-dut(a9)=14-4=10 Vl(5)=Vl(8)-dut(a8)=14-7=7 =Vl(7)-dut(a7)=16-9=7 Vl(4)=Vl(6)-dut(a6)=10-2=8 Vl(3)=Vl(5)-dut(a5)=7-1=6 Vl(2)=Vl(5)-dut(a4)=7-1=6 Vl(1)=Vl(4)-dut(a3)=8-5=3 =Vl(3)-dut(a2)=6-4=2 =Vl(2)-dut(a1)=6-6=0 求Vl(j):事件j的最迟发生时间能够计算之前，对事件j所有的后继事件（即由j邻接到的事件．例如k）的最迟发生时间必须计算出来，这些后继事件的最迟发生时间能够利用类似于求Ve(j)的办法求得，但此时必须把图用逆邻接表表示，表头结点的数据域中存放顶点出度的信息。 在toposort算法中插入的 Vl(j):=min｛Vl(k)-dut(j,k｝ j,k∈s 1≤i≤n-1 即可求得Vl(j) i=9,8,7…1 3). 计算活动i的最早开始时间e(i) 所谓活动i 的最早开始时间e(i) 是事件j发生的最早时 间，即只有事件j发生了，活动i 才能开始。 活动i j k 计算方法： e(i) = Ve(j) 4). 计算活动i 的最迟开始时间l(i) 所谓活动i 的最迟开始时间l(i) 是指不推迟整个工期 的前提下活动i 开始的最晚时间。 计算方法： l(i) = vl(k) -j,k的权 活动i j k 我们的目的是求网的关键路径，但必须要求出e(i)和l(i),而要求e(i)和l(i)就必须要求出Ve(j)和Vl(j);而要求出Ve(j)和Vl(j)则必须要建立邻接表和逆邻接表,这样的话,未免有些浪费存储单元。因此对于此问题一般是取十字链表作为网的存储结构。在十字链表中，每个结点表示一条弧，它由5个域组成： tail head dut hlink tlink tail: 弧的尾顶点j head: 弧的头顶点k dut: 是活动ai的持续时间 hlink: 链接以k为头的另一条弧 tlink: 链接以j为尾的另一条弧 另设一个由n个表头结点组成的向量，每个表头结点表示一个顶点，它也由同上面的结点一样由5个域组成。其中， tail域存放该顶点的出度OD值； head域存放该顶点的入度ID值；