【正文】 高職高專計(jì)算機(jī)專業(yè)系列教材 數(shù)據(jù)結(jié)構(gòu) 胡慧 前 言 二十一世紀(jì)是科學(xué)技術(shù)高速發(fā)展的信息時(shí)代 ， 而計(jì)算機(jī)是處理信息的主要工具 ， 計(jì)算機(jī)知識(shí)已成為人類當(dāng)代文化的一個(gè)重要組成部分 。 計(jì)算機(jī)的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域 。 在非數(shù)值計(jì)算領(lǐng)域里 ， 數(shù)據(jù)處理的對(duì)象已從簡單的數(shù)值發(fā)展到一般的符號(hào) ， 進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù) 。 在這里 ， 面臨的主要問題是：針對(duì)每一種新的應(yīng)用領(lǐng)域的處理對(duì)象 ， 如何選擇合適的數(shù)據(jù)表示 （ 結(jié)構(gòu) ） ， 如何有效地組織計(jì)算機(jī)存貯 ， 并在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對(duì)象之間的 “ 運(yùn)算 ” 關(guān)系 。 數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論 。 開設(shè)本課程的背景 《 數(shù)據(jù)結(jié)構(gòu) 》 是計(jì)算機(jī)相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課。它主要研究計(jì)算機(jī)加工對(duì)象的邏輯結(jié)構(gòu)、在計(jì)算機(jī)中的表示形式以及實(shí)現(xiàn)各種基本操作的算法。它是學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等計(jì)算機(jī)專業(yè)核心課程的基礎(chǔ)，掌握好這門課程的內(nèi)容，是學(xué)習(xí)計(jì)算機(jī)其他相關(guān)課程的重要條件。 數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的中級(jí)課程，主要培養(yǎng)學(xué)生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴學(xué)生如何編寫效率高、結(jié)構(gòu)好的程序。 本課程將分別講述數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、串和數(shù)組、樹形結(jié)構(gòu)、圖結(jié)構(gòu)、查找、排序和文件等內(nèi)容。 本課程的主要內(nèi)容 學(xué)習(xí)要求 學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。同時(shí)本課程的學(xué)習(xí)也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，易于編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。 新 授 第一章 緒論 本章介紹了數(shù)據(jù)結(jié)構(gòu)這門學(xué)科誕生的背景、發(fā)展歷史以及在計(jì)算機(jī)科學(xué)中所處的地位，重點(diǎn)介紹了數(shù)據(jù)結(jié)構(gòu)有關(guān)的概念和術(shù)語，學(xué)習(xí)本章后應(yīng)能掌握數(shù)據(jù)、數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)等基本概念，并了解如何評(píng)價(jià)一個(gè)算法的好壞。 1 引 言 2 發(fā)展簡史及地位 3 什么是數(shù)據(jù)結(jié)構(gòu) 4 基本概念和術(shù)語 5 算法和算法的描述 引言 計(jì)算機(jī)的應(yīng)用主要是在什么方面？ 數(shù)值計(jì)算 —— 通過數(shù)學(xué)模型方程解出。 非數(shù)值計(jì)算 —— 數(shù)據(jù)處理、信息管理、實(shí)時(shí)控制。（更多） 二十世紀(jì)四十年代 ， 電子數(shù)字計(jì)算機(jī)問世的直接原因是解決彈道學(xué)的計(jì)算問題 。 早期 ， 電子計(jì)算機(jī)的應(yīng)用范圍 ， 幾乎只局限于科學(xué)和工程的計(jì)算 ， 其處理的對(duì)象是純數(shù)值性的信息 ， 通常 ， 人們把這類問題稱為數(shù)值計(jì)算 。 近三十年來 ， 電子計(jì)算機(jī)的發(fā)展異常迅猛 ， 這不僅表現(xiàn)在計(jì)算機(jī)本身運(yùn)算速度不斷提高 、 信息存儲(chǔ)量日益擴(kuò)大 、 價(jià)格逐步下降 ， 更重要的是計(jì)算機(jī)廣泛地應(yīng)用于情報(bào)檢索 、 企業(yè)管理 、 系統(tǒng)工程等方面 ， 已遠(yuǎn)遠(yuǎn)超出了科技計(jì)算的范圍 ， 而滲透到人類社會(huì)活動(dòng)的一切領(lǐng)域 。 與此相應(yīng) ，計(jì)算機(jī)的處理對(duì)象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息 。 現(xiàn)代計(jì)算機(jī)科學(xué)的觀點(diǎn) ， 是把計(jì)算機(jī)程序處理的一切數(shù)值的 、 非數(shù) 值 的信 息 ， 乃 至 程 序統(tǒng) 稱 為 數(shù)據(jù)（ Data） ， 而電子計(jì)算機(jī)則是加工處理數(shù)據(jù) （ 信息 ）的工具 。 由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對(duì)象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計(jì)人員的經(jīng)驗(yàn)和技巧已難以設(shè)計(jì)出效率高、可靠性強(qiáng)的程序。于是，就要求人們對(duì)計(jì)算機(jī)程序加工的對(duì)象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系 ——數(shù)據(jù)結(jié)構(gòu)（ Date Structure）。 數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)算機(jī)科學(xué)中所處的地位 發(fā)展史： “ 數(shù)據(jù)結(jié)構(gòu) ” 作為一門獨(dú)立的課程在國外是從 1968年才開始設(shè)立的。 1968年美國唐 歐 克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的 《 計(jì)算機(jī)程序設(shè)計(jì)技巧 》 第一卷 《 基本算法 》 是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。 地位： 1. “ 數(shù)據(jù)結(jié)構(gòu) ” 在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。 2. 數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。 3. 數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（ 特別是非數(shù)值性程序設(shè)計(jì) ） 的基礎(chǔ) ， 而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序 、 操作系統(tǒng) 、 數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ) 。 什么是數(shù)據(jù)結(jié)構(gòu) 計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（ Algorithm），最后編出程序、進(jìn)行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。 計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān) ， 算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu) ， 數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率 。 運(yùn)算是由計(jì)算機(jī)來完成 ， 這就要設(shè)計(jì)相應(yīng)的插入 、 刪除和修改的算法 。 也就是說 ， 數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法 。 直觀定義： 數(shù)據(jù)結(jié)構(gòu) 是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象