一、概述 數(shù)據(jù)結(jié)構(gòu)的概念最早由C．A．R．Hoare于1966年提出。在他的經(jīng)典論文《數(shù)據(jù)結(jié)構(gòu)筆記》中，首次系統(tǒng)地論述了一組數(shù)據(jù)結(jié)構(gòu)的構(gòu)造、表示和操作等問題。1973年，D. E. Knuth在《計算機程序設(shè)計技巧》第一卷中給出了關(guān)于“信息結(jié)構(gòu)”的系統(tǒng)論述；1976年，N. Wirth用“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這個公式表達了算法與數(shù)據(jù)結(jié)構(gòu)的聯(lián)系及它們在程序設(shè)計中的地位，從此確立了數(shù)據(jù)結(jié)構(gòu)在計算機相關(guān)專業(yè)中的核心基礎(chǔ)課程地位。 “數(shù)據(jù)結(jié)構(gòu)”是一門關(guān)于非數(shù)值數(shù)據(jù)在計算機中表示、變換及處理的課程。這里的數(shù)據(jù)實質(zhì)是指計算機所能表示的各種不同數(shù)據(jù)對象的集合。對于每一具體的數(shù)據(jù)對象，通常其數(shù)據(jù)元素之間的關(guān)系不是孤立的，數(shù)據(jù)元素之間的內(nèi)在聯(lián)系被稱為結(jié)構(gòu)。從數(shù)據(jù)元素之間的關(guān)系特征分析，各種數(shù)據(jù)對象中的數(shù)據(jù)元素之間的關(guān)系僅呈現(xiàn)以下四種結(jié)構(gòu)之一：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。 歷經(jīng)多年的發(fā)展，“數(shù)據(jù)結(jié)構(gòu)”課程的主要討論范疇已基本取得共識。盡管計算機應(yīng)用領(lǐng)域仍在不斷地擴大并產(chǎn)生了許多新的數(shù)據(jù)結(jié)構(gòu)和算法，但“數(shù)據(jù)結(jié)構(gòu)”課程最基本和最核心的內(nèi)容還是討論上述四種結(jié)構(gòu)在計算機中表示、變換和處理的過程。2006年，教育部高等學校計算機科學與技術(shù)教學指導委員會編制了《高等學校計算機科學與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范》，其中算法與數(shù)據(jù)結(jié)構(gòu)涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多個知識單元，知識點包括：基本數(shù)據(jù)結(jié)構(gòu)(包括堆棧、隊列、鏈表、哈希表、串、數(shù)組和廣義表、樹型結(jié)構(gòu)及應(yīng)用、圖型結(jié)構(gòu)及應(yīng)用)、遞歸、常用排序算法、常用查找技術(shù)、算法分析基礎(chǔ)等；2009年，教育部考試中心制訂了全國碩士研究生入學統(tǒng)一考試關(guān)于“數(shù)據(jù)結(jié)構(gòu)”科目的考試大綱。以上內(nèi)容通常構(gòu)成了編寫數(shù)據(jù)結(jié)構(gòu)相關(guān)教材的大綱依據(jù)。 沒有不包含數(shù)據(jù)結(jié)構(gòu)的程序！顯然，數(shù)據(jù)結(jié)構(gòu)還應(yīng)是一門兼具理論性與實踐性的課程。在理解數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，運用數(shù)據(jù)結(jié)構(gòu)加強并提高程序設(shè)計的能力尤為重要。因此，“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計”這門課程應(yīng)運而生。 二、教材的特色 鑒于授課對象的高級語言基礎(chǔ)，教材主要選用C語言作為描述算法或程序設(shè)計的工具。同時，為增強語言的描述功能，對傳統(tǒng)C做了若干擴充。如：在算法或程序的編寫中使用了程序設(shè)計語言C++的引用調(diào)用&，動態(tài)內(nèi)存分配、釋放語句new、delete，輸入輸出流cin、cout等。讀者在學習時請注意甄別。 本教材以傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容為主線，強調(diào)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。每一章節(jié)都設(shè)計了多個案例，且在每一案例的描述過程中，依據(jù)以下步驟循序漸進展開講解： 【需求分析】 對課程設(shè)計題目進行充分的描述，闡明選題的目的及意義。 【概要設(shè)計】 對課程設(shè)計題目中數(shù)據(jù)對象的邏輯屬性予以充分認知，并為之設(shè)計解題的抽象數(shù)據(jù)類型，簡述解題的方法。 【詳細設(shè)計】 選擇合適的存儲結(jié)構(gòu)實現(xiàn)各個基本操作，封裝抽象數(shù)據(jù)類型，描述解題的算法，編寫解題的程序。 【調(diào)試分析】 討論解題的要點、難點，思考并比較解題的不同算法，運用時間、空間的分析手段分析算法的合理性及準確性。 【測試運行結(jié)果及用戶手冊】 說明程序的使用方法，列出測試的輸入輸出數(shù)據(jù)，使面對苛刻的、刁難式的測試數(shù)據(jù)程序也能正確運行。 【附錄】 源程序文件名清單。 本教材將數(shù)據(jù)結(jié)構(gòu)課程設(shè)計與數(shù)據(jù)結(jié)構(gòu)理論課程有機結(jié)合。在描述各個案例的同時，采用三元式(D，S，P)的方式，完成對線性表、棧、隊列、字符串、廣義表、二叉樹、圖、集合等抽象數(shù)據(jù)類型的定義、描述和封裝。借助于這些基本數(shù)據(jù)結(jié)構(gòu)類型，不僅實現(xiàn)了教材中的各個案例，也可將之作為工具或平臺，復用于其它應(yīng)用中。 教材中每一個算法或程序的編寫力求高效、易讀并遵循程序設(shè)計的規(guī)范，從而幫助讀者順利完成學習、模仿、提高、應(yīng)用的過程。 本教材中的所有案例的源程序均可通過掃描二維碼或登錄出版社網(wǎng)站(www.xduph.com)獲取。 三、結(jié)束語 本教材作為與理論課程“數(shù)據(jù)結(jié)構(gòu)”配套的實踐課程“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計”的教材，希望讀者通過學習，既能更好地掌握數(shù)據(jù)結(jié)構(gòu)的理論，又能更好地運用數(shù)據(jù)結(jié)構(gòu)提高程序設(shè)計的能力。值此再版之際，教材做了部分修改，但仍難避免存在缺點，懇請廣大讀者予以批評與指正。 編 者 2021年11月