数据结构与算法实际应用

学院《数据结构与算法》之实际应用二零一三年三月十三日目录计科系《数据结构与算法》应用举例1数据结构与算法在实际中的应用.............................2摘要：...................................................2一、定义：.............................错误!未定义书签。二、在各领域中的实际应用...............错误!未定义书签。（一）、排队叫号系统（尾插法）.........................2（二）、搜索引擎与数据结构算法.........................4（三）、图论应用.......................................5（四）、最小生成树在城市高速公路问题中的应用...........5三、小结.................................................6四、参考文献……………………………………………………………6小组成员：计科系《数据结构与算法》应用举例2数据结构与算法在实际中的应用摘要：计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。何为信息，信息就是大量的数据，需要对大量的数据进行处理。进而我们需要《数据结构与算法》这门课作为基础，去发展计算机学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。通过《数据结构与算法》的学习，我们能够解决很多学科问题、生活实际问题。一、定义《数据结构与算法》应该包括两个部分：数据结构、算法。数据结构在计算机科学界至今没有标准的定义。根据各自的理解的不同而有不同的表述方法，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用时间复杂度和空间复杂度衡量。二、在各领域中的应用在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求等等。（一）、排队叫号系统（尾插法）数据结构包含数的操作,排序和查找等一系列问题。其中，排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的排列。数据结构的排序有5种。计科系《数据结构与算法》应用举例31、插入排序：插入排序是逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次排序，直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个序列的排序。2、选择排序：直接选择排序是每次将后面的最小的找出来插入前面的已排好的序中。3、冒泡排序：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进行n次冒泡排序。4、归并排序：将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。5、基数排序。在现实生活中也有很多情况需要进行排序。举个简单的例子来说明。排队叫号系统（尾插法）（1）、取票：顾客取一张号票吗，上面有号码、等候人数、时间、办理的业务类型等（2）、休息等待：持号票在休息区休息并留意显示屏音箱叫号（3）、按键叫号：工作人员办完一笔业务后按下叫号器上的下一位按钮（4）、前去办理：叫号时根据显示屏音箱的信息到指定位置享受一对一的服务。能够发现，银行排队叫号系统就是《数据结构与算法》中尾插法的实际应用。通过这种方式，巧妙的减轻了银行的压力，同时能够使得等待的人先去处理其他的事或者是休息，极为人性化。计科系《数据结构与算法》应用举例4（二）、搜索引擎与数据结构算法为何在baidu上搜索一个词，只要不到1秒钟的时间就能得到数千结果呢？搜索引擎工作原理：爬行和抓取搜索引擎派出一个能够在网上发现新网页并抓文件的程序，这个程序通常称之为蜘蛛。搜索引擎从已知的数据库出发，就像正常用户的浏览器一样访问这些网页并抓取文件。搜索引擎会跟踪网页中的链接，访问更多的网页，这个过程就叫爬行。这些新的网址会被存入数据库等待抓取。所以跟踪网页链接是搜索引擎蜘蛛发现新网址的最基本的方法，所以反向链接成为搜索引擎优化的最基本因素之一。搜索引擎抓取的页面文件与用户浏览器得到的完全一样，抓取的文件存入数据库。计科系《数据结构与算法》应用举例5建立索引搜索词处理排序对搜索词处理后，搜索引擎程序便开始工作，从索引数据库中找出所有包含搜索词的网页，并且根据排名算法计算出哪些网页应该排在前面，然后按照一定格式返回到“搜索”页面。数据结构搜索引擎的核心数据结构为倒排文件（也称倒排索引），倒排索引是指用记录的非主属性值(也叫副键)来查找记录而组织的文件叫倒排文件，即次索引。倒排文件中包括了所有副键值，并列出了与之有关的所有记录主键值，主要用于复杂查询。与传统的SQL查询不同，在搜索引擎收集完数据的预处理阶段，搜索引擎往往需要一种高效的数据结构来对外提供检索服务。而现行最有效的数据结构就是“倒排文件”。倒排文件简单一点可以定义为“用文档的关键词作为索引，文档作为索引目标的一种结构（类似于普通书籍中，索引是关键词，书的页面是索引目标）。（三）、图论应用图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。（四）、最小生成树在城市高速公路问题中的应用高速公路问题：假设有N个城市，第i个城市的位置笛卡尔坐标为(xi，yi)，每条公路可以连接两个城市。目前原有的公路有m条，但是不能实现所有城市之间的连通，因此需要继续修建公路，在费用最低的原则下，实现N个城市的连通，还需要修建哪些条公路。由于修路的费用与公路的长短是成正比的，所以这个问题就可以转化成求修建哪几条公路能够实现所有城市的连通，同时满足所修公路总长最短。计科系《数据结构与算法》应用举例6思想：通过逐个从连通网中删除边来构造最小生成树。具体做法：（1）将连通网中各边按照权值从大到小排序；（2）按照排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删除下一条边)。直至子图中任何一条边都不能删除（即删除任意一条边都会造成该子图不连通）为止。三、小结其实数据结构在现实中的应用还有很多。数据结构不但对多种软件设计方法和程序设计语言非常重要，对我们的现实生活也有很多借鉴意义。我们要根据自己解决实际问题的实际需要，进行有效的数据存储和数据处理。相信只要我们不断的将所学的理论知识在实际应用中摸索和实践，就一定能够熟能生巧，把这门知识运用的炉火纯青。四、参考文献1．严蔚敏吴伟民．数据结构（C语言版）．清华大学出版社，19972．吕凤翥．C＋＋语言程序设计教程．人民邮电出版社20083．徐孝凯，贺桂英.数据结构（C语言描述）[M].北京：清华大学出版社，2004，10.注：1、该论文内容部分来源于网上2、我小组成员认为带下划线部分与该课程联系较多，与本课程联系较少部分的直接一笔带过。