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