算法与数据结构入门.doc

键入文字上海青大实训 第一章 算法与数据结构入门目标 讨论常用算法 理解简单的数据结构栈和队列 用图形描述栈的工作原理 用图形描述队列的工作原理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）远离工作的一种数据结构成为“栈”。当我们适用栈来保存数据时，最先被保存的数据，只能在最后取出，最后保存的数据，将被最先取出。栈的操作类型有两种：入栈和出栈。入栈就是把数据保存到栈中，出栈就是从栈中取出数据，我们假设编号为1、2、3、4、和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栈的应用在实际的计算机应用中.很多地方都会用到栈的结构来保存和处理数据，比如处理回文验证、数制转换、表达式求值、括号匹配检骇、行编辑程序、递归实现等。3.4队列本章介绍队列的定义和对应的操作。3.4.1队列的定义我们把在存储数据时按先进先出(First In First Out,FIFO)远离工作的一种数据机构称为“队列”。当我们使用队列来保存数据时，最先被保存的数据会被先取出，最后保存的数据据则最后取出。队列的操作类型有两种:入队和出队。如对就是把数据保存到队列中，出队就是从队列中取出数据，如图 3.12所示。在我们平常生活中，也能发现很多类似队列结构的情形：以在银行排队为例，当顾客去银行办事时，他们站在队伍末尾排队，在或得所需服务后，队伍前面的人先出来。 1. 入队如对操作将数据加入到对列尾，如图3.13所示。其中，第一个数据从末尾入队，然后第二个数据也入队，并向前移动，知道迪个数据也入队位置。 2. 出队 出队操作从队列头移除数据，如图3.14所示。第一个数据从队列头出队，然后第二个数据。类似地，这个过程一直继续到最后一个数据出队。3.4.2队列的应用 操作系统中就使用了队列这种数据结构，当我们向操作系统发出很多任务或指令后，操作系统并不能把它们立即都完成，但也不是无序地随意执行，而是按一定顺序完成。原因就在于这些指令被保存在一个队列的结构中。先披保存的指令将先被取出、先被执行。队列还被广泛地应用在多关键字排序、解决毛机与外部设备之间速度不匹配问题、解决多用户引起的资源竞争问题、最短路径问越、迷宫问题等各个方面。 总结：1、最人值、最小值和平均值等各种常用的算法。2、两种搜索数据的方法:线性查找和二分法查找。3、两种对数据进行排序的方法:胃泡排序法和插入排序法。4、栈是按后进先出(LIF0)原则工作的一种数据结构。5、队列是按先进先出原则(F1FO)工作的一种数据结构。练习 1.二分法查找要求数据已经按（ ）排列。 A.随机 B.递减 C.排序好的顺序 D.递增 2.为了从无序数组中查找数据，（ ）算法是查找数据比