数据结构与算法实际应用

计科系《数据结构与算法》应用举例PAGEPAGE1学院《数据结构与算法》之实际应用二零一目录数据结构与算法在实际中的应用 2摘要： 2一、 定义： 错误!未定义书签。二、 在各领域中的实际应用 错误!未定义书签。（一）、排队叫号系统（尾插法） 2（二）、搜索引擎与数据结构算法 4（三）、图论应用 5（四）、最小生成树在城市高速公路问题中的应用 5三、小结 6四、参考文献……………6小组成员：（二）、搜索引擎与数据结构算法为何在baidu上搜索一个词，只要不到1秒钟的时间就能得到数千结果呢？搜索引擎工作原理：爬行和抓取搜索引擎派出一个能够在网上发现新网页并抓文件的程序，这个程序通常称之为蜘蛛。搜索引擎从已知的数据库出发，就像正常用户的浏览器一样访问这些网页并抓取文件。搜索引擎会跟踪网页中的链接，访问更多的网页，这个过程就叫爬行。这些新的网址会被存入数据库等待抓取。所以跟踪网页链接是搜索引擎蜘蛛发现新网址的最基本的方法，所以反向链接成为搜索引擎优化的最基本因素之一。搜索引擎抓取的页面文件与用户浏览器得到的完全一样，抓取的文件存入数据库。建立索引搜索词处理排序对搜索词处理后，搜索引擎程序便开始工作，从索引数据库中找出所有包含搜索词的网页，并且根据排名算法计算出哪些网页应该排在前面，然后按照一定格式返回到“搜索”页面。数据结构搜索引擎的核心数据结构为倒排文件（也称倒排索引），倒排索引是指用记录的非主属性值(也叫副键)来查找记录而组织的文件叫倒排文件，即次索引。倒排文件中包括了所有副键值，并列出了与之有关的所有记录主键值，主要用于复杂查询。与传统的SQL查询不同，在搜索引擎收集完数据的预处理阶段，搜索引擎往往需要一种高效的数据结构来对外提供检索服务。而现行最有效的数据结构就是“倒排文件”。倒排文件简单一点可以定义为“用文档的关键词作为索引，文档作为索引目标的一种结构（类似于普通书籍中，索引是关键词，书的页面是索引目标）。（三）、图论应用图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。（四）、最小生成树在城市高速公路问题中的应用高速公路问题：假设有N个城市，第i个城市的位置笛卡尔坐标为(xi，yi)，每条公路可以连接两个城市。目前原有的公路有m条，但是不能实现所有城市之间的连通，因此需要继续修建公路，在费用最低的原则下，实现N个城市的连通，还需要修建哪些条公路。由于修路的费用与公路的长短是成正比的，所以这个问题就可以转化成求修建哪几条公路能够实现所有城市的连通，同时满足所修公路总长最短。思想：通过逐个从连通网中删除边来构造最小生成树。具体做法：（1）将连通网中各边按照权值从大到小排序；（2）按照排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删除下一条边)。直至子图中任何一条边都不能删除（即删除任意一条边都会造成该子图不连通）为止。三、小结其实数据结构在现实中的应用还有很多。数据结构不但对多种软件设计方法和程序设计语言非常重要，对我们的现实生活也有很多借鉴意义。我们要根据自己解决实际问题的实际需要，进行有效的数据存储和数据处理。相信只要我们不断的将所学的理论知识在实际应用中摸索和实践，就一定能够熟能生巧，把这门知识运用的炉火纯青。四、参考文献1．严蔚敏吴伟民．数据结构（C语言版）．清华大学出版社，19972．吕凤翥．C＋＋语言程序设计教程．人民邮电出版社20083．徐孝凯，贺桂英.数据结构（C语言描述）[M]