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