第一章算法与数据结构入门。
目标。讨论常用算法。
理解简单的数据结构——栈和队列。
用图形描述栈的工作原理。
用图形描述队列的工作原理。
3.1常用算法。
算法是逐步解决指定问题的步骤和方法。其实做任何事情都有一个方法问题，有些方法好，有些方法可能就不太好。让计算机完成任务，给计算机下达指令，也同样需要有一个非常好步骤和方法，所以在计算机应用中，特别是写程序的过程中也需要用到各种算法。
我们对于算法的要求是：算法应该简单明确，不得模棱两可，应以有限的步骤解决相应的问题，并且能够处理r些意外情形。下面是为一个想购买钢笔的学生编写的算法：
1)拿到钱。
2)从家里出来。
3)找到一家商店。
4)走进商店。
5)提出要买一支钢笔。
6)从店主展示的钢笔中挑选一支。
7)付钱。8)拿走钢笔。
9)离开商店。
这就是生活中一个问题的算法。
在本章中将学习一些计算机中常用的算法。
3.1.1最大值、最小值和平均值。
1.求最大值的算法。
假如现在我们需要查找某科目考试中的最高分。jack. linda.
steven. jackson,janice和jennifer该科目所获得的分数分别是68. 50.
96. 85. 79和90.
要计算最高分，就必须在各个值之间进行比较，山一开始时并不知道最高分，所以该列中的第一个位68被当作临时最高分，并存储于临时位置`i”中，现在，移到下一分数处，将此分数与具有临时最大值的“i”进行比较，即比较68和50这两个分数中的最高分是68因此，68仍然楚临时最高分。现在移到列表中的96分处，将’i”与96进行比较，由于这两个数中最高分数是96，`i”的值将变为96。以类似方式遍历列表中的每个分数，并将“i”的值与这些分数进行比较，如图3.
1所示。若列表中的分数较高，则用此新值代替“i”的值。若该分数较低，直接移到下一位置进行比较，找出最高分。
此过程一直执打到列表末尾。当到达列表末尾时，“i”存储的就是列表中的最大值了。由于96是列表中的最高分，“i”就取该值，因此，本例中steven获得了最高分。
2.求最小值的算法。
考虑用于查找最大值的同一个例子。
不过这次要找的是最低分，同样必须将列表中的分数进行比较。由于开始时并不知道最低分，所以列表中的第一个值68被认为是临时最低分，并存储于临时位置“i”移到列表中下一个分数50，将其与具有临时最低值的“i”进行比较。此处，50是最低分，它将代替“i”的值。
然后移到列表中的下一个分数，将“i”的值与96进行比较。以类似方式遍历列表中的每个分数，并将“i”的值与这些分数进行比较，如图3.2所示。
若列表中的分数低于此过程一直执行到列表末尾，“i”中所保存的就是要找的最低分。由于50是列表中的最低分，“i"就取该值。因此，本例中linda获得了最低分。
3.求平均值的算法。
如果要计算一个学生的平均分，首先必须将其所有科目分数加在一起，再除以科目的数量。例如，john的科学课程得了75分，数学69分，英语60分。
他的平均得分可按以下方式计算：
1)将所有分数加在一起：75+69+60=204。
2)所得的结果除以科目的数量：204/3=68.这就是平均值。
3) john的平均得分是68，如图3.3所示。
3.1.2查找。
查找是从较大的数据集中找出或定位某些数据(比如字母、同语、文件和**等)的过程。它是许多程序中都会便用到的一项重要操作，为了更有效地进行搜索。可使用各种查找算法。
最常用的查找算法是线性查找和二分法查找。
1.线性查找。
线性查找是从一列给定的值中按顺序进行搜索的过程。它从一端开始(通常从头开始)逐检有好个元素，直到找到所需元索。线性查找义称为顺序查找。
线性查找可用于有序列表。也可用于无序列表。例如，从一列数中查找一个数，假设要在列表中查找数字8。
查找列表中的第一个数，用8与该数进行比较。如果二者不相同。则移到下一个数进行比较。
以类似方式遍历每个数。直到找到8为止，如图3.4所示。
这是一个线性在找的例子此例从列表的开头开始逐个查找。直到找到该查找项。
2.二分法查找。
二分法查找法是在一个有序的元索列表中查找特定位的一种方法。该顺序可能是升序或降序。本例中的顺序为升序。
首先，将有序列表的中间元素与被查找的值进行比较。如果该元素与被查找的位相同，则查找完毕。如果中间元素小于被查找的值，则知道该值一定在中间元素后面的某处。
因l此，排除该有序列表的前一半，然后对其剩余部分执行相同的过程。如果中间元素大于被搜索的值，则知道该值一定在中间元素的某处。
以图3.5中给出的数字列表为例，假没要从给定的这个列衣中搜索35。将该列表从中问一分为二，然后查找需要的数。
假设可能将列表从数字17处分开，比较35大于17还是小于17，如图3.6所示。如果35大一些，则忽略该列表的前半部分。
现在将剩余的表再一分为二，这将可能从22处分开。35大于22还是小于22?如果35大一些，则忽略前半部分，如果35小一些，则忽略后半部分。
在此35更大一些，所以忽略该列表的前半部分继续该过程，直到找到需要查找的数，如阁3.6所示。
3.1.3排序方法。
排序是把一组无序的数据按照递增或递减的次序重新排列的过程。
如果将信息以预先定义的顺序存储，则对信息进行检索就变得容易多了。因此，排序是一项非常重要的活动。例如，将朋友的姓名按字母顺序记在**薄中，则要找出某位朋友的**号码就非常容易。
这很清楚地说明对大量信息进行排序的好处。如果某人翻开**簿，发现其中的姓名末按照字母顺序出现，查找某人的电活号码就会花费很多时间。
对数据进行排序的方法有很多种。下面我们将对其中的冒泡排序和插入排序进行详细**。
1.首泡排序。
冒泡排序是·种简单的排序算法。该排序过程的名称就说明了其工作方式，我们把较小的数类比成气泡，气泡会不断向上省，越小的数就冒得越高，最终达到排序的效果。此方法要先从最底层元素开始。
用它比较和它紧挨着的上一个元索，将两个元素进行比较，如果下面元素小于上面元素，则交换它们，否则保持原样。然后转移到址底层的上一个位置，重复以上过程，最后，最小的元素将从其原始位置，冒到顶部。这时我们再从最底层元素开始比较，重复前面把最小值放在最顶端的步骤，就可以将第二小的值放在第二个位置了。
如此不断重复，直到这组数据中的所有元素都被排序。下面给出了一个排序的过程，该过程将5个数进行了升序(从小到大)排序。
(1)将第五个元素的值与第四个元素的值进行比较。
(2)如果第五个元素的值小十第四个元素的值，则交换这两个元素的值。
(3)接下来，将第四个元素的值与第三个元素的值进行比较。如上面元素的值大于下面元素的值，则交换它们的值。
(4)将第三个元素的值与第二个元素的值进行比较，这样继续比较和交换的过程。
(5)到此过程结束时，最小值到达第一个元素。以形象化的术语可描述为：具有最小值的气泡冒起来了。
(6)在下一交换过程中，再次从最底层的元素开始比较，一直向上进行到第二个元素。由于第一个元素已经包含最小值，不需要与它比较。这样，第二小的元素就被冒到了第二个位置。
(7)再次进行交换，分别将第三和第四小的数冒到合适位置。
(8)排序完成。
通过此方式，在排序过程结束时，较小的值冒起，而较大的值下沉，如图 3.7所示，描述了冒泡排序法。
2.插入排序。
在插入排序法中，一组数字中的每个元素在经过检查之后，放入己排序元素列表中的适当位置。当最后一个数字放入合适位置时，该组数据排序完毕。假设一组数据有5个元素，用以下方法对它们进行排序：
(1)假定第一个元素的值己排序。
(2)将第二个元素的值与该数组的已排序部分(当前只含第一个元素)进行比较。
(3)如果第二个元素的值更小，就将它插在第一个元素之前。此时，前两个元素组成己排序列表，其余元素组成未排序列表。
(4)将未排序列表中的第一个元素(即第三个元素)与已排序列表比较。
〔5)如果第三个元素的值小于第一个元素，则第三个元素的谊就插到第一个元素之前。否则第三个元素的值就插到第二个元素之前。此时，该数组的已排序部分包含3个元索，而未排序部分包括两个元素。
(6)将未排序部分的元素与已排序部分的元索进行比较的过程继续进行，直到数组中的最后一个元素完成比较为止。
在排序过程结束时，每一个元素都插入到适当的位置中。如图3.8描述了插入排序的工作原理。
3.2数据结构简介。
数据结构是对计算机中所保存数据的一种组织和存放方式，每一种不同的数据结构都会将数据按某种特定的方式来保存，并按特定的方式进行操作，相对于零散地保存数据。使用经过精心设计的各种数据结构，有助于更有效地使用数据和各种算法，能用最少的资源、最短的执行时间、缓小的存储空问完成各种关键操作和任务。
数据结构的各种类型如下：栈。队列。
链表。哈希表。树。堆。
图。3.3栈。
在本节中将学习栈的定义及其对应的操作。
3.3.1定义。
我们把在存储数据时按后进先出（last in first out，lifo）远离工作的一种数据结构成为“栈”。当我们适用栈来保存数据时，最先被保存的数据，只能在最后取出，最后保存的数据，将被最先取出。栈的操作类型有两种：
入栈和出栈。入栈就是把数据保存到栈中，出栈就是从栈中取出数据，我们假设编号为、和5的小圆盘为栈中保存的一个数据，其中小圆盘1首先装入，小圆盘5最后妆容天，而在取数据时就必选先取出小圆盘5，才能取下面的，最后才能取出小圆盘1，如图3.9所示。
3.3.2入栈。
入栈又称为"压栈“，该操作是将一个数据添加到栈中，或称为压入栈项，这时找的大小就加1。在如图3.10所示的例子中，每次将一个小圆盘装到另一个上面。
本例中首先装入小圆盘1，然后装入小圆盘2、小圆盘3和小圆盘4，最后装入小圆盘5。
3.3.3出栈。
在此操作中，每个数据逐个弹出，直到栈变为空，如图3.11所示。位于栈顶的小圆盘5首先从栈中弹出，栈的大小减1。该过程一直继续，栈的大小递减为3，然后递减为2，直到栈为空。
3.3.4栈的应用。
在实际的计算机应用中。很多地方都会用到栈的结构来保存和处理数据，比如处理回文验证、数制转换、表达式求值、括号匹配检骇、行编辑程序、递归实现等。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...