本章知识结构如图1-1所示。
图1-1 第1章知识结构图。
1．算法基本概念。
算法是解决某个特定问题求解的一种描述，它是指令的有限序列。算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。
2．算法的基本特征。
1）有穷性：一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。
2）确定性：算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。
3）可行性：要求算法中有待实现的运算都是基本的、能够实现的。
4）输入：一个算法有0个或多个输入。
5）输出：作为算法运算的结果，一个算法产生一个或多个输出。
3．算法设计的基本方法。
1）列举法；
2）归纳法；
3）递推；4）递归；
5）减半递推技术；
6）回溯法。
4．算法复杂度。
算法复杂度主要包括算法时间复杂度和算法空间复杂度。
1）算法时间复杂度：是指执行算法所需要的计算工作量。
例1.1 交换i和j的内容。
temp=i；
i=j；j=temp；
时间复杂度 t（n）=o（1）。
例1.2 变量计数之一。
x=0；y=0；
for（k=1;k<=n;k++）
x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
y++;时间复杂度t（n）=o（n2）。
2）算法空间复杂度：是指执行这个算法所需要的内存空间。
1．数据结构基本概念。
数据结构是指相互有关联的数据元素的集合。
研究的三个方面：数据集合中和数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。
2．数据的逻辑结构。
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。包含两方面：表示数据元素的信息；表示各数据元素之间的前后件关系。
3．数据的存储结构。
数据的存储结构是指数据结构在计算机存储空间中的存放形式。
常见的存储结构有两种：顺序存储结构，特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构，特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。
4．数据结构分类。
数据结构可分类为线性结构和非线性结构。
1）线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。
2）非线性结构：不满足线性结构条件的数据结构。
1．线性表概念。
线性表是由n（n 0）个数据元素al，a2，a3，…组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a1，a2，…，ai，…，an）。
线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
2．非空线性表的结构特征。
有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。
3．线性表的顺序存储结构。
顺序存储具有基本特点：线性表中所有元素所占的存储空间是连续的、按逻辑顺序依次存放的；线性表中存储密度小、数据元素可以随机查找。
顺序表的运算包括查找、插入、删除。
4．线性表的链式存储结构。
链式存储的特点是：
线性表中元素所占的空间可以不连续；
线性表插入、删除操作方便；
可以不必事先估计线性表长度。
链式存储可分为单链表、双链表、单循环链表、双循环链表。
数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
结点由两部分组成：一是用于存储数据元素值，称为数据域；二是用于存放指针，称为指针域，用于指向前一个或后一个结点。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。
线性链表中，head称为头指针，head=null（或0）称为空表，如果是两指针：左指针（llink）指向前件结点，右指针（rlink）指向后件结点。线性链表的基本运算包括查找、插入、删除。
1．栈。栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
栈的存储：顺序存储，栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。
栈的基本运算：插入元素称为入栈运算；删除元素称为退栈运算；读栈顶元素是将栈顶元素给一个指定的变量，此时指针无变化。
2．队列。队列的概念：是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。
队列的存储：队列是“先进先出”（fifo）或“后进后出”（lilo）的线性表。
队列的运算：入队运算。从队尾插入一个元素，退队运算，从队头删除一个元素。
1．树和二叉树的概念。
树是一种简单的非线性结构，所有元素之间具有明显的层次特性，如图1-2所示。
二叉树：在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次数称为树的深度。
2．术语。根结点：在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。
叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
度：在树结构中，一个结点所拥有的后件个数称为该结点的度。
孩子、双亲、兄弟：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。树中某个结点的子树之根称为该结点的孩子，相应的，该结点称为孩子的双亲或父亲。
3．二叉树的基本性质。
性质1：在二叉树的第k层上，最多有2k–1个结点。
性质2：深度为k的二叉树最多有2k–1个结点。
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，即n0=n2+1。
性质4：具有n个结点的二叉树，其深度至少为log2n+1。
二叉树如图1-3所示。
图1-3 二叉树。
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k–1个结点，且深度为k的满二叉树有2k–1个结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点，如图1-4所示。
性质5：具有n个结点的完全二叉树的深度为log2n+l。
性质6：设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号（k=1，2，…，n），有以下结论：
若k=1，则结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为int（k/2）；
若2k③ 若2k+1图1-4 完全二叉树。
根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
4．二叉树的存储。
1）二叉树的顺序存储：这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容，如图1-5所示。
图1-5 二叉树顺序存储。
2）二叉树的链式存储：在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域，存储结构如图1-6和图1-7所示。
图1-6 二叉树的存储结构。
二叉树二叉树链式存储。
图1-7 二叉树及链式存储。
5．二叉树的遍历。
1）前序遍历（dlr），首先访问根结点，然后遍历左子树，最后遍历右子树。
2）中序遍历（ldr），首先遍历左子树，然后访问根结点，最后遍历右子树。
3）后序遍历（lrd），首先遍历左子树，然后遍历右子树，最后访问根结点。
1．顺序查找。
顺序查找又称顺序搜索，顺序查找一般是指**性表中查找指定的元素。
以下两种情况只能采用顺序查找：
1）如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
2．二分法查找。
二分法查找只适用于顺序存储的有序表，在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。二分法查找的效率要比顺序查找高得多。
对于长度为n的有序线性表，在最坏情况下，二分法查找只需要比较log2n次，而顺序查找需要比较n次。
1．排序概念。
所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。
2．排序方法。
1）交换类排序法：冒泡排序法和快速排序法，最后情况需要比较的次数均为n(n–1)/2。
2）插入类排序法：简单插入排序法，最坏情况需要n（n–1）/2次比较；希尔排序法，最坏情况需要o（n）次比较。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...