|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆： 或 ，并相应地称为小顶堆或大顶堆。
|
|
|
|
|
|
判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
|
|
|
|
|
|
堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。栈进行插入和删除操作的一端称为栈顶，另一端称为栈底。不含数据元素的栈称为空栈。
|
|
|
|
|
|
.置空栈InitStack(S)：创建一个空栈S。
|
|
|
|
.判栈空Empty(S)：当栈S为空栈时返回真值；否则返回假值。
|
|
|
|
.入栈Push(S,x)：将元素x加入栈顶，并更新栈顶指针。
|
|
|
|
.出栈Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将Pop(S)定义为一个函数，它返回栈顶元素的值。
|
|
|
|
.读栈顶元素Top(S)：返回栈顶元素的值，但不修改栈顶指针。
|
|
|
|
|
|
（1）顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说，栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满，若栈满，则元素入栈会发生上溢现象。
|
|
|
|
利用栈底位置不变的特性，可以让两个顺序栈共享一个一维数据空间，以互补余缺，实现方法是：将两个栈的栈底位置分别设在存储空间的两端，让它们的栈顶各自向中间延伸。这样，两个栈的空间就可以相互调节，只有在整个存储空间被占满时才发生上溢，这样一来产生上溢的概率要小得多。
|
|
|
|
（2）链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头节点，链表的头指针就是栈顶指针。
|
|
|
|
|
|
栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现中以及将递归过程转变为非递归过程的处理中，栈有重要的作用。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
当在一个函数（称为调用函数）中需要使用另一个函数（称为被调用函数）实现的功能时，便以名字进行调用，称为函数调用。在使用一个函数时，只要知道如何调用即可，并不需要关心被调用函数的内部实现。因此，程序员需要知道被调函数的名字、返回值和需要向被调函数传递的参数（个数、类型、顺序）等信息。
|
|
|
|
|
|
|
|
在C程序的执行过程中，通过函数调用使得被调用函数得以执行。函数体中若调用自己，则称为递归调用。
|
|
|
|
C语言采用传值方式将实参传递给形参。调用函数和被调用函数之间交换信息的方法主要有两种：一种是由被调用函数把返回值返回给调用函数，另一种是通过参数带回信息。函数调用时，实参与形参间交换信息的主要有传值调用和引用调用两种方法。
|
|
|
|
（1）传值调用（Call by value）。若实现函数调用时实参向形参传递相应类型的值，则称为是传值调用。这种方式下形参不能向实参传递信息。
|
|
|
|
例如，下面给出函数swap定义，其功能是交换两个整型变量值。
|
|
|
|
|
|
|
|
因为是传值调用，swap函数运行后只能交换x和y的值，而实参a和b的值并没有交换。
|
|
|
|
在C语言中，要实现被调用函数对实参的修改，必须用指针作形参，调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参。本质上仍属于传值调用。
|
|
|
|
下面给出函数swap的定义，其功能是交换两个整型变量值。
|
|
|
|
|
|
|
|
由于形参px、py分别得到了实参变量a、b的地址，所以px指向的对象*px即为a，py指向的对象*py就是b，因此在函数中交换*px和*py的值实际上就是交换实参a和b的值，从而实现了调用函数中两个整型变量值的交换。这种方式是通过数据的间接访问来完成运算要求的。
|
|
|
|
（2）引用调用。引用是C++中增加的数据类型，当形参为引用类型时，函数中对形参的访问和修改实际上就是针对相应实参所作的访问和改变。例如：
|
|
|
|
|
|
|
|
引用调用方式下调用swap（a，b）时，x、y就是a、b的别名，因此，函数调用完成后，交换了实参a和b的值。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
除了CPU，内存也是影响系统性能的最常见的瓶颈之一。看系统内存是否够用的一个重要参考就是分页文件的数目，分页文件是硬盘上的真实文件，当操作系统缺少物理内存时，它就会把内存中的数据挪到分页文件中去，如果单位时间内此类文件使用频繁（每秒个数大于5）,那就应该考虑增加内存。具体考察内存的性能的参数包括内存利用率、物理内存和虚拟内存的大小。
|
|
|
|
|
|
|
|
|
|
|
|
|
