前言

“數據結構”是計算機科學與技術專業、軟件工程及相關專業的核心課程之一，是計算機科學與技術、軟件工程等專業研究生考試必考科目之一，也是IT公司面試或筆試考核的主要內容。數據結構主要分析計算機中數據組織的方式和相關操作算法，涉及數據結構和算法的基本概念與技術，線性表、棧、隊列、串、數組與廣義表、樹、二叉樹、圖等常用數據結構及相關算法，以及排序、查找等重要技術。本課程既是對前導的程序設計類課程、離散數學等課程的深入和拓展，也為繼續深入學習數據庫、操作系統、編譯原理、計算機網絡等后續專業課程打下了重要基礎。

“數據結構”是一門直接面向實際應用、解決實際問題的課程，它的教學目標是，讓學習者學會從問題入手，分析研究計算機加工的數據結構的特性，以便為應用所涉及的數據選擇適當的邏輯結構、存儲結構及其相應的操作算法，并初步掌握時間和空間分析技術。

筆者從事“數據結構”課程的教學已有二十多年，深切了解學習者對于學習“數據結構”課程的普遍體會是，概念難理解、算法難設計、編程難實現、知識難應用。如何幫助學習者實現兩個跨越：從實際應用問題到數據結構抽象的跨越和從數據結構概念到程序實現的跨越，是我們一直努力的目標。近年來，我們以“問題導學”模式進行了該課程教學的探索和實踐，本書是這些工作的成果。

“問題導學”模式是以問題解決為主線，以學生學習為主體，使學生在解決問題的過程中掌握知識，形成自主學習能力的一種教學模式。該模式的具體過程是：引導學生分析問題中的已知信息，提煉數據及數據之間的關系（數據的邏輯結構），選擇合適的存儲方式（數據的存儲結構）將待處理的數據保存到計算機中，然后在存儲結構之上按照自頂向下逐步細化的方法設計算法，給出程序實現，并進行測試和調試分析。

本書的每一章以若干典型的導學問題為主線貫穿組織，由“知識學習”“知識應用”和“知識拓展”等部分組成。圍繞導學問題，引導學習者思考問題、對實際問題進行抽象建模、實現模型和應用模型。與高級程序設計語言課相比，數據結構在培養學生的數據抽象能力方面有著更高的要求，通過本書不同層次的導學問題示例培養學生逐步掌握數據抽象的能力，學會數據結構和數據類型的使用方法，為今后的學習和提高編程水平打下扎實的基礎。

本書以學生學習為主體，在內容的組織和選材上指導學生通過思考、比較、建構，逐步形成學生自己的知識框架，并發展相應的能力。為此，本書在每一章開頭設置了學習導圖，指導學生體驗思考問題、初步解決問題、進一步解決復雜問題這一學習過程。每章學習過程中設置了一些書寫填空題，讓學生不僅耳動起來、嘴動起來，還要手動起來，真正成為課堂的主人，積極主動地進行學習和思考。每章課后安排的思考與練習、應用實戰讓學生能夠進行達標檢測、鞏固知識、查漏補缺。

本書以學生學習為主體，還體現在重視對學生進行復雜程序設計的訓練，指導學生書寫符合軟件工程規范的文件，編寫結構清晰、正確易讀的程序，上機調試并排除錯誤代碼等。全書采用C語言作為數據結構和算法的基本描述工具，同時采用了C++對C的非面向對象的增強功能。例如，輸入/輸出采用了cin、cout運算符，函數參數傳遞采用了引用、動態分配和釋放，存儲結構采用了new和delete運算符等。這些措施使得數據類型的定義和數據結構相關操作算法的描述更加簡明清晰，可讀性好，易于學習掌握。學習者也可把類型定義和操作算法稍加處理，這樣就很容易將其封裝成類，并進一步轉化成面向對象的程序。全書算法和導學問題的源程序使用Visual C++ 6.0集成環境完成并提供下載。

本書在內容組織和設計上進行了創新，一方面可以幫助學習者把學習的新知識形成網、織成塊、用起來；另一方面，也對教師有效地組織課堂教學提供了便利。教師可以根據教材資源，對學習者進行問題引導、疑難精講、質疑點撥、檢測評估。

本書由于泠和陳波執筆完成。全書共9章，第1章簡要介紹數據結構和算法的基本概念；第2～4章介紹了線性結構及其算法，包括線性表、棧和隊列、串；第5～7章介紹了非線性結構及其算法，包括矩陣和廣義表、樹和二叉樹、圖；第8章介紹了常用的查找算法；第9章介紹了常用的排序算法。本書可作為計算機專業、軟件工程專業及其他相關專業“數據結構”課程的教材以及研究生入學考試輔導書，也可供計算機軟件開發人員或編程愛好者參考和使用。

本書作為江蘇省高等教育教學改革重點課題：面向社會化學習的移動虛擬學習社區建設和應用研究（2015 JSJG034）、南京師范大學教改重點項目：以計算思維為導向的信息與計算科學專業實踐教學研究與探索、南京師范大學重點教材建設項目：數據結構導學教程（C/C++版），已經建成了包含本課程教學課件、實驗指導、習題解答、算法源程序、參考資料等資源。讀者可登錄http://www.cmpedu.com下載本書配套資源。讀者可以使用移動設備的相關軟件（如“QQ”）中的“掃一掃”功能掃描書中提供的二維碼，在線查看問題提示或解答。如果“掃一掃”后在微信端無法打開文檔，請選擇用手機瀏覽器直接打開。移動設備的相關軟件，請從Android市場或蘋果App Store等進行下載安裝。

在編寫本書的過程中，查閱和參考了大量的文獻和資料，限于篇幅，未能在書后的參考文獻中全部列出，在此一并致謝。

由于編者水平有限，書中難免有疏漏之處，懇請廣大讀者批評指正。讀者在閱讀本書的過程中若有疑問，也歡迎與作者聯系，電子郵箱是：SecLab@163.com。

編者