本書將數(shù)據(jù)結構課程設計與數(shù)據(jù)結構理論課程有機結合，以傳統(tǒng)數(shù)據(jù)結構的主要內容為主線，精心設計多個案例。在描述各個案例的同時，采用三元式(D，S，P)的方式，完成對線性表、棧、隊列、字符串、廣義表、二叉樹、圖、集合等抽象數(shù)據(jù)類型的定義、描述和封裝。這些基本數(shù)據(jù)結構類型不僅應用于教材中的各個案例，也可作為工具或平臺復用于其它應用中。 本書中每一個算法或程序的編寫力求高效、易讀，并遵循程序設計的規(guī)范，從而幫助讀者順利完成學習、模仿、提高、應用的過程。 本書可作為計算機類專業(yè)數(shù)據(jù)結構課程設計教材，也可作為學習數(shù)據(jù)結構及其算法的C程序設計的參考教材，還可供從事計算機應用工作的相關人員參考。

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

第1章 線性表 1 設計題1.1 集合運算 2 設計題1.2 約瑟夫環(huán) 17 練習題1 27 第2章 棧和隊列 29 設計題2.1 馬踏棋盤 29 設計題2.2 車廂調度 45 練習題2 56 第3章 數(shù)組、串和廣義表 58 設計題3.1 稀疏矩陣的轉置 58 設計題3.2 廣義表的操作 66 練習題3 86 第4章 樹型結構 87 設計題4.1 二叉樹的遍歷和基本操作 87 設計題4.2 算術表達式求值 102 設計題4.3 哈夫曼樹及哈夫曼編碼 114 練習題4 126 第5章 圖型結構 128 設計題5.1 最小代價生成樹 129 設計題5.2 哈密頓圖的判斷 150 設計題5.3 歐拉圖的判斷 170 練習題 5 191 第6章 查找與排序 193 設計題6.1 各種靜態(tài)查找方法的實現(xiàn)和比較 193 設計題6.2 哈希表的查找 207 設計題6.3 各種排序方法的實現(xiàn)和比較 217 練習題6 232 參考文獻 234