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