數(shù)據(jù)結(jié)構(gòu)與算法實際應(yīng)用

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