計科系《數據結構與算法》應用舉例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]