一、概述

數據結構的概念早由C．A．R．Hoare於1966年提出。在他的經典論文《數據結構筆記》中，首次繫統地論述了一組數據結構的構造、表示和操作等問題。1973年，D.E.Knuth在《計算機程序設計技巧》卷中給出了關於“信息結構”的繫統論述。1976年，N.Wirth用“算法 數據結構=程序”這個公式表達了算法與數據結構的聯繫及它們在程序設計中的地位，從此確立了數據結構在計算機相關專業中的核心基礎課程地位。

“數據結構”是一門關於非數值數據在計算機中表示、變換及處理的課程。這裡的數據實質是指計算機所能表示的各種不同數據對像的集合。對於每一具體的數據對像，通常素之間的關繫不是孤立的素之間的內在聯繫被稱為結構。素之間的關繫特征分析，各種數據對像中素之間的關繫僅呈現以下四種結構之一：集合結構、線性結構、樹形結構、圖形結構。

歷經40多年的發展，“數據結構”課程的主要討論範疇已基本取得共識。盡管計算機應用領域仍在不斷地擴大並產生了許多新的數據結構和算法，但“數據結構”課程基本和核心的內容還是討論上述四種結構在計算機中表示、變換和處理的過程。2006年，*高等學校計算機科學與技術教學指導委員會編制了《高等學校計算機科學與技術專業發展戰略研究報告暨專業規範》。其中，算法與數據結構涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多個，知識點包括：基本數據結構(包括：堆棧、隊列、鏈表、哈希表、串、數組和廣義表、樹型結構及應用、圖型結構及應用)、遞歸、常用排序算法、常用查找技術、算法分析基礎等。2009年，*考試中心制訂了全國碩士研究生入學統一考試關於“數據結構”科目的考試大綱。以上內容通常構成了編寫數據結構相關教材的大綱依據。

沒有不包含數據結構的程序！顯然，數據結構還應是一門兼具理論性與實踐性的課程。在理解數據結構的基礎上，運用數據結構加強並提高程序設計的能力顯得尤為重要。因此，“數據結構課程設計”這門課程應運而生。

二、教材的特色

鋻於授課對像的高級語言基礎，教材主要選用C語言作為描述算法或程序設計的工具。同時，為增強語言的描述功能，對傳統C做了若干擴充。如：在算法或程序的編寫中使用了程序設計語言C 的引用調用&，動態內存分配、釋放語句new、delete，輸入輸出流cin、cout等。讀者在學習時請注意甄別。

本教材以傳統數據結構的主要內容為主線，強調數據結構的應用。在每一章節中設計多個案例，且在每一案例的描述過程中，依據以下步驟循序漸進展開講解。

【需求分析】

對課程設計題目進行充分的描述，闡明選題的目的及意義。

【概要設計】

對課程設計題目中數據對像的邏輯屬性予以充分的認知，並為之設計解題的抽像數據類型，簡述解題的方法。

【詳細設計】

選擇合適的存儲結構實現各個基本操作，封裝抽像數據類型；描述解題的算法，編寫解題的程序。

【調試分析】

討論解題的要點、難點，思考並比較解題的不同算法，運用時間、空間的分析手段分析算法的合理性及準確性。

【測試運行結果及用戶手冊】

說明程序的使用方法，列出測試的輸入輸出數據，使面對苛刻的、刁難式的測試數據程序也能正確運行。

【附錄】

源程序文件名清單。

本書將數據結構課程設計與數據結構理論課程有機結合。在描述各個案例的同時，式(D，S，P)的方式，完成對線性表、棧、隊列、字符串、廣義表、二叉樹、圖、集合等抽像數據類型的定義、描述和封裝。借助於這些基本數據結構類型，不僅實現了教材中的各個案例，也可將之作為工具或平臺，復用於其它應用中。

書中每一個算法或程序的編寫力求高效、易讀並遵循程序設計的規範，從而能夠幫助讀者順利完成學習、模仿、提高、應用的過程。

本教材中的所有案例的源程序均可通過掃描二維碼或登錄出版社網站(www.xduph.com)獲取。

三、結束語

本書作為與理論課程“數據結構”配套的實踐課程“數據結構課程設計”的教材，希望讀者通過學習，既能更好地認知數據結構的理論，又能更好地運用數據結構提高程序設計的能力。但限於能力和經驗，書稿雖經多次修改，仍難免存在缺陷，懇請讀者予以批評指正。

編者

2017年6月