計(jì)科系《數(shù)據(jù)結(jié)構(gòu)與算法》應(yīng)用舉例PAGEPAGE1學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》之實(shí)際應(yīng)用二零一目錄數(shù)據(jù)結(jié)構(gòu)與算法在實(shí)際中的應(yīng)用 2摘要： 2一、 定義： 錯(cuò)誤!未定義書(shū)簽。二、 在各領(lǐng)域中的實(shí)際應(yīng)用 錯(cuò)誤!未定義書(shū)簽。（一）、排隊(duì)叫號(hào)系統(tǒng)（尾插法） 2（二）、搜索引擎與數(shù)據(jù)結(jié)構(gòu)算法 4（三）、圖論應(yīng)用 5（四）、最小生成樹(shù)在城市高速公路問(wèn)題中的應(yīng)用 5三、小結(jié) 6四、參考文獻(xiàn)……………6小組成員：（二）、搜索引擎與數(shù)據(jù)結(jié)構(gòu)算法為何在baidu上搜索一個(gè)詞，只要不到1秒鐘的時(shí)間就能得到數(shù)千結(jié)果呢？搜索引擎工作原理：爬行和抓取搜索引擎派出一個(gè)能夠在網(wǎng)上發(fā)現(xiàn)新網(wǎng)頁(yè)并抓文件的程序，這個(gè)程序通常稱(chēng)之為蜘蛛。搜索引擎從已知的數(shù)據(jù)庫(kù)出發(fā)，就像正常用戶的瀏覽器一樣訪問(wèn)這些網(wǎng)頁(yè)并抓取文件。搜索引擎會(huì)跟蹤網(wǎng)頁(yè)中的鏈接，訪問(wèn)更多的網(wǎng)頁(yè)，這個(gè)過(guò)程就叫爬行。這些新的網(wǎng)址會(huì)被存入數(shù)據(jù)庫(kù)等待抓取。所以跟蹤網(wǎng)頁(yè)鏈接是搜索引擎蜘蛛發(fā)現(xiàn)新網(wǎng)址的最基本的方法，所以反向鏈接成為搜索引擎優(yōu)化的最基本因素之一。搜索引擎抓取的頁(yè)面文件與用戶瀏覽器得到的完全一樣，抓取的文件存入數(shù)據(jù)庫(kù)。建立索引搜索詞處理排序?qū)λ阉髟~處理后，搜索引擎程序便開(kāi)始工作，從索引數(shù)據(jù)庫(kù)中找出所有包含搜索詞的網(wǎng)頁(yè)，并且根據(jù)排名算法計(jì)算出哪些網(wǎng)頁(yè)應(yīng)該排在前面，然后按照一定格式返回到“搜索”頁(yè)面。數(shù)據(jù)結(jié)構(gòu)搜索引擎的核心數(shù)據(jù)結(jié)構(gòu)為倒排文件（也稱(chēng)倒排索引），倒排索引是指用記錄的非主屬性值(也叫副鍵)來(lái)查找記錄而組織的文件叫倒排文件，即次索引。倒排文件中包括了所有副鍵值，并列出了與之有關(guān)的所有記錄主鍵值，主要用于復(fù)雜查詢。與傳統(tǒng)的SQL查詢不同，在搜索引擎收集完數(shù)據(jù)的預(yù)處理階段，搜索引擎往往需要一種高效的數(shù)據(jù)結(jié)構(gòu)來(lái)對(duì)外提供檢索服務(wù)。而現(xiàn)行最有效的數(shù)據(jù)結(jié)構(gòu)就是“倒排文件”。倒排文件簡(jiǎn)單一點(diǎn)可以定義為“用文檔的關(guān)鍵詞作為索引，文檔作為索引目標(biāo)的一種結(jié)構(gòu)（類(lèi)似于普通書(shū)籍中，索引是關(guān)鍵詞，書(shū)的頁(yè)面是索引目標(biāo)）。（三）、圖論應(yīng)用圖論算法在計(jì)算機(jī)科學(xué)中扮演著很重要的角色，它提供了對(duì)很多問(wèn)題都有效的一種簡(jiǎn)單而系統(tǒng)的建模方式。很多問(wèn)題都可以轉(zhuǎn)化為圖論問(wèn)題，然后用圖論的基本算法加以解決。遺傳算法是解優(yōu)化問(wèn)題的有效算法，而并行遺傳算法是遺傳算法研究中的一個(gè)重要方向，受到了研究人員的高度重視。（四）、最小生成樹(shù)在城市高速公路問(wèn)題中的應(yīng)用高速公路問(wèn)題：假設(shè)有N個(gè)城市，第i個(gè)城市的位置笛卡爾坐標(biāo)為(xi，yi)，每條公路可以連接兩個(gè)城市。目前原有的公路有m條，但是不能實(shí)現(xiàn)所有城市之間的連通，因此需要繼續(xù)修建公路，在費(fèi)用最低的原則下，實(shí)現(xiàn)N個(gè)城市的連通，還需要修建哪些條公路。由于修路的費(fèi)用與公路的長(zhǎng)短是成正比的，所以這個(gè)問(wèn)題就可以轉(zhuǎn)化成求修建哪幾條公路能夠?qū)崿F(xiàn)所有城市的連通，同時(shí)滿足所修公路總長(zhǎng)最短。思想：通過(guò)逐個(gè)從連通網(wǎng)中刪除邊來(lái)構(gòu)造最小生成樹(shù)。具體做法：（1）將連通網(wǎng)中各邊按照權(quán)值從大到小排序；（2）按照排好的順序從連通網(wǎng)中刪除權(quán)值最大的邊，條件是使刪除該邊后的子圖仍然保持連通(若刪除后子圖不連通則改邊保留，繼續(xù)刪除下一條邊)。直至子圖中任何一條邊都不能刪除（即刪除任意一條邊都會(huì)造成該子圖不連通）為止。三、小結(jié)其實(shí)數(shù)據(jù)結(jié)構(gòu)在現(xiàn)實(shí)中的應(yīng)用還有很多。數(shù)據(jù)結(jié)構(gòu)不但對(duì)多種軟件設(shè)計(jì)方法和程序設(shè)計(jì)語(yǔ)言非常重要，對(duì)我們的現(xiàn)實(shí)生活也有很多借鑒意義。我們要根據(jù)自己解決實(shí)際問(wèn)題的實(shí)際需要，進(jìn)行有效的數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)處理。相信只要我們不斷的將所學(xué)的理論知識(shí)在實(shí)際應(yīng)用中摸索和實(shí)踐，就一定能夠熟能生巧，把這門(mén)知識(shí)運(yùn)用的爐火純青。四、參考文獻(xiàn)1．嚴(yán)蔚敏吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）．清華大學(xué)出版社，19972．呂鳳翥．C＋＋語(yǔ)言程序設(shè)計(jì)教程．人民郵電出版社20083．徐孝凱，賀桂英.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）[M]