学院
《数据结构与算法》之实际应用
二零一三年三月十三日
四、参考文献……………………………………………………………6
小组成员：
         
数据结构与算法在实际中的应用
摘要：
计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理 。何为信息，信息就是大量的数据，需要对大量的数据进行处理。进而我
们需要《数据结构与算法》这门课作为基础，去发展计算机学科。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。通过《数据结构与算法》的学习，我们能够解决很多学科问题、生活实际问题。
一、定义
《数据结构与算法》应该包括两个部分：数据结构、算法。
数据结构在计算机科学界至今没有标准的定义。根据各自的理解的不同而有不同的表述方法，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用时间复杂度和空间复杂度衡量。
二、在各领域中的应用
在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求等等。
（一）、排队叫号系统（尾插法）
数据结构包含数的操作,排序和查等一系列问题。其中，排序的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的排列。数据结构的排序有5种。
1、插入排序：插入排序是逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次排序，直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个序列的排序。
2、选择排序：直接选择排序是每次将后面的最小的出来插入前面的已排好的序中。数据结构与算法论文
3、冒泡排序：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进行n次冒泡排序。
4、归并排序：将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。
5、基数排序。
在现实生活中也有很多情况需要进行排序。举个简单的例子来说明。
排队叫号系统（尾插法）
（1）、取票：顾客取一张号票吗，上面有号码、等候人数、时间、办理的业务类型等
（2）、休息等待：持号票在休息区休息并留意显示屏音箱叫号
（3）、按键叫号：工作人员办完一笔业务后按下叫号器上的下一位按钮
（4）、前去办理：叫号时根据显示屏音箱的信息到指定位置享受一对一的服务。
能够发现，银行排队叫号系统就是《数据结构与算法》中尾插法的实际应用。通过这种方式，巧妙的减轻了银行的压力，同时能够使得等待的人先去处理其他的事或者是休息，极为人性化。
（二）、搜索引擎与数据结构算法
为何在baidu上搜索一个词，只要不到1秒钟的时间就能得到数千结果呢？
搜索引擎工作原理：
爬行和抓取
搜索引擎派出一个能够在网上发现新网页并抓文件的程序，这个程序通常称之为蜘蛛。搜索引擎从已知的数据库出发，就像正常用户的浏览器一样访问这些网页并抓取文件。搜索引擎会跟踪网页中的链接，访问更多的网页，这个过程就叫爬行。这些新的网址会被存入数据库等待抓取。所以跟踪网页链接是搜索引擎蜘蛛发现新网址的最基本的方法，所以反向链接成为搜索引擎优化的最基本因素之一。搜索引擎抓取的页面文件与用户浏览器得到的完全一样，抓取的文件存入数据库。
建立索引
搜索词处理
排序
对搜索词处理后，搜索引擎程序便开始工作，从索引数据库中出所有包含搜索词的网页，并且根据排名算法计算出哪些网页应该排在前面，然后按照一定格式返回到“搜索”页面。
数据结构
搜索引擎的核心数据结构为倒排文件（也称倒排索引），倒排索引是指用记录的非主属性值(也叫副键)来查记录而组织的文件叫倒排文件，即次索引。倒排文件中包括了所有副键值，并列出了与之有关的所有记录主键值，主要用于复杂查询。 与传统的SQL查询不同，在搜索引擎收集完数据的预处理阶段，搜索引擎往往需要一种高效的数据结构来对外提供检索服务。而现行最有效的数据结构就是“倒排文件”。倒排文件简单一点可以定义为“用文档的关键词作为索引，文档作为索引目标的一种结构（类似于普通书籍中，索引是关键词，书的页面是索引目标）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。