所谓算法，是指对问题解决方案的准确、完整的描述。对于一个问题，如果你能通过一个计算机程序在有限的存储空间内运行有限的时间来得到正确的结果，这个问题是算法可以解决的。作为一种算法，它通常应具有以下特征：

• 可行性：算法中的每一步都必须能够实现，算法执行的结果必须能够达到预期的目的；
• 确定性：算法中的每一步都必须明确定义；
• 穷性：算法必须在执行有限步骤后终止；
• 有足够的信息：算法是否有效取决于算法提供的信息（输入数据）。

工程中常用的几种计算机算法设计方法如下：

• 列举法：列举所有可能的情况，并根据问题中给定的条件进行检查；
• 归纳法:通过列出少量特殊情况进行分析。最后找出一般关系；
• 递推：从已知的初始条件出发，逐步推出所需的中间结果和最终结果；
• 递归:为了减少问题的复杂程序，逐层分解问题，最后归结为一些最简单的问题，然后沿着原始分解的逆过程逐步进行综合。

所谓时间复杂性，是指执行算法所需的计算工作量，可以利用执行过程中所需的基本操作的执行次数来衡量算法的工作量。
算法执行所需的基本操作次数可能与特定输入有关。

• 平均态度：所谓平均态性，指用各种特定输入下基本操作次数的加权平均值来衡量算法的工作量。
• 最坏情况的复杂性：所谓复杂性：分析最坏情况，是指算法执行的最大基本操作次数。

算法的空间复杂性一般是指执行算法所需的内存空间，包括算法程序所占的空间、输入初始数据所占的存储空间和执行所需的空间额外空间。

研究和讨论以下三个方面：

• 数据集中数据元素之间固有的逻辑关系，即数据逻辑结构；
• 在处理数据时，计算机中每个数据元素的存储关系，即数据存储结构；
• 运算各种数据结构。

所谓数据结构，是指以各种方式计算数据集中的各种元素，包括插入、删除、搜索、更改和分析数据元素，即数据结构是指相关数据元素的集合。
一般来说，在具有相同特征的数据元素集合中，每个数据元素之间都有一定的关系，反映了集合中数据元素的固有结构，称为前后关系（直接前驱和直接后继）。

所谓数据的逻辑结构是指反映数据素之间逻辑关系的数据结构，其可以表示成

    数据的逻辑结构在计算机中存储空间中的存放形式称为数据的存储结构，为了描述各元素间的逻辑关系，数据结构的存储结构中不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息，常用的存储结构有顺序、链接、索引等。

    在数据结构的图形表示中，对于数据集合D中每一个数据元素用中间标有元素值的方框表示，称为数据节点；对于R中的每一个二元组，用一条有向线段从前件节点指向后件节点。
    在数据结构中，没有前件的节点称为根节点，没有后件的节点称为终端节点（叶子节点）。

    如果一个非空的数据结构满足：

• 有且只有一个根节点；
• 每一个节点最多有一个前件，也最多有一个后件。

    则称该数据结构为线性结构或线性表，一个线性结构输入或删除任何一个节点后还应是数据结构。
    如果一个数据结构不是线性结构，则称之为非线性结构。

    线性表是由n（n≥0）个数据元素a₁，a₂，···，a_n组成的有限序列，非空线性表具有以下结构特征：

• 有且只有一个根节点a₁，它无前件；
• 有且只有一个终端节点a_n，它无后件；
• 除根节点外，其他所有节点有且只有一个前件，也有且只有一个后件，节点个数n
• 即线性表长度n。

    线性表的顺序存储结构具有以下两个基本特点：

• 线性表中所有元素所占的存储空间是连续的；
• 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

    在程序设计语言中，通常定义一个一位数组来表示线性表的顺序存储空间，在开辟线性表的存储空间时要考虑到线性表在动态变化过程中可能达到的最大长度。线性表的主要运算有以下几种：

• 插入：在线性表的指定位置加入一个新的元素；
• 删除：在线性表中删除制定的元素；
• 查找：在线性表中查找某个（某些）特定的元素；
• 排序：对线性表中的元素进行；
• 分解：按要求将一个线性表分解成多个线性表；
• 合并：按要求将多个线性表合并成一个线性表；
• 复制：复制一个线性表；
• 逆转：逆转一个线性表。

    一般来说，设长度为n的线性表为

    现要在线性表的第i个原宿a_i之前插入一个新元素b，插入后得到长度为n+1的线性表为

    则插入前后的两线性表中的元素满足：

    一般来说，设长度为n的线性表为

    现要删除第i个元素，删除后得到长度为n-1的线性表为

    则插入前后的两线性表中的元素满足：

    栈是一种限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端成为栈底。栈是按照先进后出（FILO）或后进先出（LIFO）的原则组织数据的。

    通常用指针top表示栈顶的位置，用指针bottom指向栈底，示意图如下：

    在程序设计语言中，用一位数组S(1:m)作为栈的顺序存储空间，通常栈底指针S(bottom)指向栈空间的低地址一端（即起始地址一端），S(top)为栈顶指针，top=0表示栈空，top=m表示栈满.
    栈的基本运算有三种:

• 入栈：在栈顶位置插入一个新元素；
• 退栈：取出栈顶元素并赋给一个指定的变量；
• 读栈顶元素：将栈顶元素赋给一个指定的变量。

    队列是允许在一段进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，允许删除的一端称为队头，通常一个用一个排头指针(front)指向排头元素的前一个位置。
    队列是先进先出(FIFP)或后进后出(LILO)的线性表，往队列的队尾插入一个元素称为入队运算，其只涉及队尾指针rear的变化，往队列的排头删除一个元素称为退队操作，其只涉及排头指针front的变化。

    所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，循环队列包含两种操作：

• 入队运算：首先判断循环队列是否满（标志s=1且rear=front），之后将队尾指针rear置为rear+1，最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。
• 退队运算：首先判断循环队列是否为空（标志s=0），然后将排头指针front置为front+1，将排头指针指向的元素赋给指定的元素，最后判断如退出后front=rear循环队列置空标志。

    假设数据结构中的每一个数据节点对应于一个存储单元，这种存储单元称为存储结点，简称结点。在链式存储中，每个节点由两部分组成：

• 一部分用于存放存放数据元素值，称为数据域；
• 另一部分用于存放指针，指向节点的前/后一个结点，称为指针域。
      在链式存储结构中，存储结构数据的存储空间可以不连续，数据元素之间的逻辑关系由指针域确定，链式存储结构可用于表示线性结构与非线性结构。

    线性表的链式存储结构称为线性链表，在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点，称为头指针，HEAD=NULL时表为空表。一般来说，线性链表中各结点在存储空间中的位置关系与逻辑关系是不一致的。

    一般的线性单链表每个结点只有一个指针域，有这个指针只能找到后件结点。而在双向链表中，每个结点设置两个指针，一个称为左指针(Llink)，一个称为右指针(Rlink)。

    栈也是线性表，也可使用链式存储结构，带链的栈可以收集计算机存储空间中的所有空闲的存储结点，称为可利用栈。

    队列也是线性表，也可以采用链式存储结构。

    线性链表的运算主要有以下几个：

• 线性链表的查找
• 线性链表的插入：要将结点p插入到结点q之后，需先将结点p指向包含元素x的结点（结点q的后件结点），然后将结点q的指针域内容改为指向结点p。
• 线性链表的删除：要删除结点q后包含元素x的结点p，应让结点q的指针指向结点p的指针指向的结点。
• 合并线性链表
• 分解线型链表
• 逆转线性链表
• 线性链表的排序
• 线性链表的查找

    循环链表具有两个特点：

• 增加了表头结点，以数据域为任意或根据需要设置，指针域指向线性表第一个元素的结点，循环链表头指针指向表头结点；
• 最后一个结点的指针域不是空，而是指向表头结点。

    循环链表与线性单链表相比，具有以下优点：

• 只要指出任何一个结点位置，就可以从它出发访问到表中其他所有结点；
• 循环链表中设置了表头结点，任何情况下循环列表中至少有一个结点。

    树是一种简单的非线性结构，其中所有数据元素之间的关系具有明显的层次特性。在树中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为根结点，在树中，每个结点可以有多个后件，称为子结点，没有后件的结点称为叶子结点。
    在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。
    树具有明显的层次关系，根节点在第一层，同一层上所有结点的子节点都在下一层，树的最大层次称为树的深度。

    二叉树是一种很有用的非线性结构，其具有以下两个特点：

• 非空二叉树只有一个根结点；
• 每一个结点最多有两颗子树，且分别称为该结点的左子树和右子树。

    二叉树具有以下几个性质：

• 在二叉树的第k层上，最多有2^k-1(k≥1)个结点；
• 深度为m的二叉树最多有2^m-1个结点；
• 在任意一颗二叉树中，度为0的结点总是比度为2的结点多一个。

• 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点；
• 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层只缺少右边的若干结点。

    二叉树通常采用链式存储结构，其各元素的存储结点由数据域V(i)和指针域两部分构成。其结点的指针域有两个：一个用于指向左子结点的存储地址，称为左指针域L(I)；另一个用于指向右子结点的存储地址，称为右指针域R(i)。
    二叉树的链式存储结构也成为二叉链表，其中头指针BT指向二叉树根结点。

    二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历过程中，一般先遍历左子树，再遍历右子树。根据先左后右的原则，按照访问根结点的次数，二叉树可分为前序遍历、中序遍历和后序遍历。

• 访问根结点；
• 前序遍历左子树；
• 前序遍历右子树。

• 中序遍历左子树；
• 访问根结点；
• 中序遍历右子树。

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根结点。

    所谓查找，是指在一个给定的数据结构中查找某个指定的元素。

    顺序查找一般是指在顺序表中查找指定的元素，其基本方法如下：从线性表第一个元素开始，依次将元素与被查元素作比较，若相等则查找成功，若所有元素均与被查元素进行比较且不相等，则查找失败。

    二分法查找只适用于顺序存储的有序表，设有序线性表的长度为n，被查元素为x，则查找方法如下：将x与线性表中间项进行比较，若中间项的值等于x，则查找成功，若x小于中间项的值，则在线性表前半部分以相同方法进行查找，若x大于中间项的值，则在线性表后半部分以相同方法进行查找。

    所谓排序，是指将一个无序序列整理成按值非递减顺序排列的有序序列。

    所谓交换类排序法，是指借助数据元素之间的互相交换进行排序的一种方法。

    冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序，其基本方法如下：
    首先从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若前面元素大于后面元素，则将其互换，称为消去了一个逆序。这样在扫描过程中，不断将两相邻元素的大者往后移动，最后就将线性表中的最大者换到了表的最后。
    然后从后到前扫描剩下的线性表，扫描过程中逐次比较相邻元素大小，若相邻元素中后面元素小于前面元素，则将其进行互换，又消去一个逆序。在扫描过程中不断将两相邻元素的的小者往前移动，剩下线性表中的最小者换到了表的最前面。
    对剩下的线性表重复上述来回扫描操作，直至剩下的线性表变空为止，此时的线性表已经变为有序。

    快速排序法也是一种互换类的排序方法，它能够通过一次交换消除多个逆序，其基本思想如下：
    从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，将线性表分成了两部分，T插入到其分界线的位置处，这样的过程称为线性表的分割。
    通过一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。
    对分割后的各子表再按上述原则不断进行分割，直至所有子表为空，此时的线性表就变成了有序表。

    所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

    一般来说，假如线性表中前j-1个元素已经有序，现要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：
    首先将第j个元素放到一个变量T中，然后从有序子表中的最后一个元素开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T插入到刚移出的空位置上，有序子表的长度就变为了。

    希尔排序法的基本思想是将整个无序序列分割成若干小的子序列进行插入排序。子序列的分割方法：
    将相隔某个增量h的元素构成一个子序列，在排序过程中逐次减小增量，最后当h减小到1时完成一次插入排序，排序就完成。
    增量序列一般取h_r=n/2^k，其中n为待排序列长度。

    选择排序法的基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直至子表空为止。

    对于长度为n的序列，进行n-1次扫描，每次扫描均从剩下的子表中选出最小的元素，然后将该最小元素与子表中第一个元素进行交换。

    对于n个元素的序列（h₁，h₂，···，和h_n），当且仅当满足

    时称之为堆。
    堆排序的方法如下：

1. 首先将一个无序序列建成堆；
2. 然后将堆顶元素（序列中最大项）与堆中最后一个元素交换（最大项应该在序列的最后），将子序列调整为堆，重复操作直至剩下的子序列为空。