操作堆的插入、删除和建立过程,及堆排序方法。
1. 堆
堆:n个元素序列{k1,k2,...,ki,...,kn},当且仅当满足下列关系时称之为堆:
(ki <= k2i,ki <= k2i+1)
或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4,...,n/2)
若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
一般用数组来表示堆,i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2。如第0个结点的左右子结点下标分别为1和2。
2. 堆的插入
每次插入都是将先将新数据放在数组最后,由于从这个新数据的父结点到根结点必然为一个有序的序列,现在的任务是将这个新数据插入到这个有序序列中——这就类似于直接插入排序中将一个数据并入到有序区间中。
代码:
/* * 堆插入算法。(小顶堆) * 先将num插入堆尾,易知从新数据的父结点到根结点是一个有序的序列, * 将num插入到该有序序列当中,该过程为直接插入排序。 * 未插入前数据长度为n。 */ int HeapInsert(int *heap, int n, int num) { int i, j; heap[n] = num;//num插入堆尾 i = n; j = (n - 1) / 2;//j指向i的父结点 //注意不要漏掉i!=0的条件。因为必须保证i有父结点j。j>=0并不能保证i!=0。 //如果没有此条件,当i=0时,j=0,若heap[0]>num,程序就会陷入死循环。 while (j >= 0 && i != 0) { if (heap[j] <= num) break; heap[i] = heap[j]; i = j; j = (i - 1) / 2; } heap[i] = num; return 0; }
3. 堆的删除
堆中每次都只能删除堆顶元素。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于根结点数据的“下沉”过程。
代码:
/* * 堆删除算法。(删除堆顶元素) * n表示未删除前堆中数据的总数。 */ int HeapDelete(int *heap, int n) { //使用堆尾元素直接覆盖堆顶元素。 heap[0] = heap[n - 1]; //从堆顶到堆尾(此时堆中只有n-1个元素)进行堆调整。 HeapAdjust(heap, 0, n - 1); return 0; } /* * 堆调整算法。(小顶堆) * 已知heap[top]结点的左右子树均为堆,调整堆中元素,使以heap[top]为根结点的树为堆。 * n为堆中元素总数。 */ int HeapAdjust(int *heap, int top, int n) { int j = 2 * top + 1; //左孩子结点 int temp = heap[top]; while (j < n) { if (j + 1 < n&&heap[j + 1] < heap[j]) j++; //使j指向左右孩子中较小的结点。 if (heap[j] >= temp) break; heap[top] = heap[j]; top = j; j = 2 * top + 1; } heap[top] = temp; return 0; }
4. 堆的建立
从无序序列建堆的过程就是一个反复调整的过程。若将此序列看成是一个完全二叉树,则最后一个非终端结点是第(n-2)/2个结点,由此调整过程只需从该结点开始,直到堆顶元素。
代码:
/* * 建堆算法。 * 将无序数组array[]转换为堆。 */ int CreatHeap(int *array, int n) { int i; //最后一个结点的编号为n-1,该结点的父节点(n-2)/2为最后一个非终端结点。 //从结点(n-2)/2到根结点,依次进行堆调整。 for (i = (n - 2) / 2; i >= 0; i--) { HeapAdjust(array, i, n); } return 0; }
5. 堆排序
若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重建一个堆,则得到n个元素中的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序。
输出堆顶元素之后,以堆中最后一个元素替代之,此时根结点的左右子树均为堆,则仅需进行一次从上到下的调整即可重建一个堆。
代码:
/* * 堆排序算法。 * 形参heap为大顶堆时,实现的是由小到大; * 形参heap为小顶堆时,实现的是由大到小; */ int HeapSort(int *heap, int n) { int i; int temp; for (i = n - 1; i > 0; i--) { //将堆顶元素和未排序的最后一个元素交换。 temp = heap[0]; heap[0] = heap[i]; heap[i] = temp; //交换之后进行堆调整 HeapAdjust(heap, 0, i); } return 0; }
6. 测试代码
/* * 堆的建立、插入、删除和堆排序算法 */ #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define TOTAL 20 int HeapInsert(int *heap, int n, int num); int HeapDelete(int *heap, int n); int HeapAdjust(int *heap, int top, int n); int HeapSort(int *heap, int n); int CreatHeap(int *array, int n); int main() { int heap[TOTAL]; int num; int i; //先输入一半的数据,对输入的数组建堆。 printf("输入Total/2个数据:\n"); for (i = 0; i < TOTAL / 2; i++) scanf("%d", &heap[i]); CreatHeap(heap, TOTAL / 2); //检验是否建堆成功。 printf("建堆后:\n"); for (i = 0; i < TOTAL / 2; i++) printf("%-3d", heap[i]); putchar('\n'); //向已建好的堆中插入数据,并重组为堆。 printf("继续输入Total/4个数据:\n"); for (i = TOTAL / 2; i < TOTAL / 2 + TOTAL / 4; i++) { scanf("%d", &num); HeapInsert(heap, i, num); } //检验是否插入成功。 printf("重组为堆之后:\n"); for (i = 0; i < TOTAL / 2 + TOTAL / 4; i++) printf("%-3d", heap[i]); putchar('\n'); //删除堆顶元素Total/4次。 printf("删除Total/4个数据:\n"); for (i = 0; i < TOTAL / 4; i++) HeapDelete(heap, TOTAL / 2 + TOTAL / 4 - i); //检验是否删除成功。 for (i = 0; i < TOTAL / 2; i++) printf("%-3d", heap[i]); putchar('\n'); //向堆中插满数据,进行堆排序。 printf("继续输入Total/2个数据:\n"); for (i = TOTAL / 2; i < TOTAL; i++) { scanf("%d", &num); HeapInsert(heap, i, num); } HeapSort(heap, TOTAL); printf("排序后:\n"); for (i = 0; i < TOTAL; i++) printf("%-3d ", heap[i]); putchar('\n'); return 0; } /* * 堆插入算法。(小顶堆) * 先将num插入堆尾,易知从新数据的父结点到根结点是一个有序的序列, * 将num插入到该有序序列当中,该过程为直接插入排序。 * 未插入前数据长度为n。 */ int HeapInsert(int *heap, int n, int num) { int i, j; heap[n] = num;//num插入堆尾 i = n; j = (n - 1) / 2;//j指向i的父结点 //注意不要漏掉i!=0的条件。因为必须保证i有父结点j。j>=0并不能保证i!=0。 //如果没有此条件,当i=0时,j=0,若heap[0]>num,程序就会陷入死循环。 while (j >= 0 && i != 0) { if (heap[j] <= num) break; heap[i] = heap[j]; i = j; j = (i - 1) / 2; } heap[i] = num; return 0; } /* * 堆删除算法。(删除堆顶元素) * n表示未删除前堆中数据的总数。 */ int HeapDelete(int *heap, int n) { //使用堆尾元素直接覆盖堆顶元素。 heap[0] = heap[n - 1]; //从堆顶到堆尾(此时堆中只有n-1个元素)进行堆调整。 HeapAdjust(heap, 0, n - 1); return 0; } /* * 堆调整算法。(小顶堆) * 已知heap[top]结点的左右子树均为堆,调整堆中元素,使以heap[top]为根结点的树为堆。 * n为堆中元素总数。 */ int HeapAdjust(int *heap, int top, int n) { int j = 2 * top + 1; //左孩子结点 int temp = heap[top]; while (j < n) { if (j + 1 < n&&heap[j + 1] < heap[j]) j++; //使j指向左右孩子中较小的结点。 if (heap[j] >= temp) break; heap[top] = heap[j]; top = j; j = 2 * top + 1; } heap[top] = temp; return 0; } /* * 堆排序算法。 * 形参heap为大顶堆时,实现的是由小到大; * 形参heap为小顶堆时,实现的是由大到小; */ int HeapSort(int *heap, int n) { int i; int temp; for (i = n - 1; i > 0; i--) { //将堆顶元素和未排序的最后一个元素交换。 temp = heap[0]; heap[0] = heap[i]; heap[i] = temp; //交换之后进行堆调整 HeapAdjust(heap, 0, i); } return 0; } /* * 建堆算法。 * 将无序数组array[]转换为堆。 */ int CreatHeap(int *array, int n) { int i; //最后一个结点的编号为n-1,该结点的父节点(n-2)/2为最后一个非终端结点。 //从结点(n-2)/2到根结点,依次进行堆调整。 for (i = (n - 2) / 2; i >= 0; i--) { HeapAdjust(array, i, n); } return 0; }
7. 测试结果
参考:白话经典算法系列之七 堆与堆排序
推荐阅读
-
操作堆的插入、删除和建立过程,及堆排序方法。
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
Grid++Report 锐浪报表开发常见问题解答集锦-报表设计 问:怎样在设计时打印预览报表? 答:为了及时查看报表的设计效果,Grid++Report 报表设计应用程序提供了四种查看视图:普通视图、页面视图、预览视图与查询视图。通过窗口下边的 Tab 按钮可以在四种视图中任意切换。在预览视图中查看报表的打印预览效果,在查询视图中查看报表的查询显示效果。如果在报表的记录集提供了数据源连接串与查询 SQL,在进入预览视图与查询视图时会利用数据源连接串与查询 SQL 从数据源中自动取数,否则 Grid++Report 将自动生成模拟数据进行模拟打印预览与查询显示。注意:在预览视图与查询视图中看到的报表运行结果有可能与在你程序中的最终运行结果有差异,因为在报表的生成过程中我们可以在程序中对报表的生成行为进行一定的控制。 问:怎样用 Grid++Report 设计交叉表? 答:Grid++Report 没有提供专门实现交叉表的功能,其它的报表构件提供的交叉表功能一般也比较死板和功能有限。利用 Grid++Report 的编程接口可以做出灵活多变,功能丰富的交叉表。示例程序 CrossTab 就是一个实现交叉表的例子程序,认真领会此例子程序,你就可以做出自己想要各种交叉表,并能提取一些共用代码,便于重复使用。 问:怎样设置整个报表的缺省字体? 答:设置报表主对象的字体属性,也就是设置了整个报表的缺省字体。如果改变报表主对象的字体属性,则没有专门的设置字体属性的子对象的字体属性也跟随改变。同样每个报表节与明细网格也有字体属性,他们的字体属性也就是其拥有的子对象的缺省字体。 问:怎样在打印时限制一页的输出行数? 答:设定明细网格的内容行的‘每页行数(RowsPerPage)’属性即可。另外要注意‘调节行高(AdjustRowHeight)’属性值:为真时根据页面的输出高度自动调整行的高度,使整个页面的输出区域充满。为假时按设计时的高度输出行。 问:怎样显示中文大写金额? 答:将对象的“格式(Format)”属性设为 “$$” 及可,可以设置格式的对象有:字段(IGRField)、参数(IGRParameter)、系统变量(IGRSystemVarBox)与综合文字框(IGRMemoBox),其中综合文字框是在报表式上设格式。 问:能否实现自定义纸张与票据打印? 答:Grid++Report 完全支持自定义纸张的打印,只要在报表设定时在页面设置中选定自定义纸张,并指定准确的纸张尺寸。当然要在最终输出时得道合适的打印结果,输出打印机必须支持自定义纸张打印。Windows2000/XP/2003 操作系统上可以在打印机上定义自定义纸张,也可以采用这种方式实现自定义纸张打印。 问:怎样实现 0 值不打印? 答:直接设置格式串就可以,在“数字格式”设置对话框中选定“0 不显示”,就会得到合适的格式串。也可以通过直接录入格式串来指定 0 不显示,但格式串必须符合 Grid++Report 的规定格式。另一种实现办法是在报表获取明细记录数据时,在 BeforePostRecord 事件中将值为零的字段设为空,调用字段的 Clear 方法将字段置为空。 问:怎样实现多栏报表? 答:在明细网格上设‘页栏数(PageColumnCount)’属性值大于 1 即可。通过 Grid++Report 的“页栏输出顺序”还可以指定多栏报表的输出顺序是“先从上到下”还是“先从左到右”。 问:如何实现票据套打? 答:Grid++Report 为实现票据套打做了很多专门的安排:报表设计器提供了页面设计模式,按照设定的纸张尺寸显示设计面板,如果将空白票据的扫描图设为设计背景图,在定位报表内容的输出位置会非常方便。报表部件可以设定打印类别,非套打输出的内容在套打打印模式下就不会输出。 问:Grid++Report 有没有横向分页功能? 答:回答是肯定的,在列的总宽度超过打印页面的输出宽度时,Grid++Report 可以另起新页输出剩余的列,如果左边存在锁定列,锁定列可以在后面的新页中重复输出,这样可以保证关键数据列在每一页都有输出。仔细体会 Grid++Report 提供的多种打印适应策略,选用最合适的方式。Grid++Report 的多种打印适应策略为开发动态报表提供了很好的支持。 问:怎样实现报表本页小计功能? 答:定义一个报表分组,将本分组定义为页分组,在本分组的分组头与分组尾上定义统计。页分组就是在每页产生一个分组项,在每页的上端与下端都会分别显示页分组的分组头与分组尾,页分组不用定义分组依据字段。 报表运行 问:怎样与数据库建立连接? 答:如果在设计报表时指定了数据集的数据源连接串与查询 SQL 语句,Grid++Report 采用拉模式直接从数据源取得报表数据,Grid++Report 利用 OLE DB 从数据源取数,OLE DB 提供了广泛的数据源操作能力。如果 Grid++Report 的数据来源采用推模式,即 Grid++Report 不直接与数据库建立连接,各种编程语言/平台都提供了很好的数据库连接方式,并且易于操作,应用程序在报表主对象(IGridppReport)的 FetchRecord 事件中将数据传入,例子程序提供了各种编程语言填入数据的通用方法,对C++Builder 和 Delphi 还进行了专门的包装,直接关联 TDataSet 对象也可以将 TDataSet 对象中的数据传给报表。 问:打印时能否对打印纸张进行自适应?支持表格的折行打印吗? 答:Grid++Report 在打印时采用多种适应策略,通过设置明细网格(IGRDetailGrid)的‘打印策略(PrintAdaptMethod)’属性指定打印策略。(1)丢弃:按设计时列的宽度输出,超出范围的内容不显示。(2)绕行:按设计时列的宽度输出,如果在当前行不能完整输出,则另起新行进行输出。(3)缩放适应:对所有列的输出宽度进行按比例地缩放,使总宽度等于页面的输出宽度。(4)缩小适应:如果列的总宽度小于页面的输出宽度,对所有列的输出宽度进行按比例地缩小,使总宽度等于页面的输出宽度。(5)横向分页:超范围的列在新页中输出。(6)横向分页并重复锁定列。 问:如何改变缺省打印预览窗口的窗口标题? 答:改变报表主对象的‘标题(Title)’属性即可。 问:利用集合对象的编程接口取子对象的接口引用,但不是自己期望的结果。 答:Grid++Report中所有集合对象的下标索引都是从 1 开始,另按对象的名称查找对象的接口引用时,名称字符是不区分大小写的。 问:怎样在运行时控制报表中各个对象的可见性?即怎样在运行时显示或隐藏对象? 答:在报表主对象(GridppReport)的 SectionFormat 事件中设定相应报表子对象的可见(Visible)属性即可。 问:报表主对象重新载入数据,设计器中为什么没有反映新载入的数据? 答:应调用 IGRDesigner 的 Reload 方法。 问:怎样实现不进入打印预览界面,直接将报表打印出来?