數據結構是高等學校計算機及其相關專業的核心課程，是計算機程序設計的基礎。本書按照"像外行一樣思考,像專家一樣實踐”的解決問題的思維方法，基于學習者的認知規律，列舉大量實際或工程案例，從具體問題中引出抽象概念，運用類比、圖形化描述等方式，對經典數據結構內容做深入淺出的介紹。在介紹數據結構和算法的基本概念和算法分析方法的基礎上，從軟件開發的角度，通過應用背景或知識背景介紹、數據分析、函數設計、算法設計、測試調試等環節，分別對順序表、鏈表、棧、隊列、串、數組、樹、圖等基本類型的數據結構進行了分析和討論；介紹數據的典型操作方法，如數據排序方法和查找方法；介紹常見的如遞歸、分治法、動態規劃、貪心法等經典算法。

再 版 說 明
數據結構是一門專業核心基礎課程，在程序語言設計課程和其他計算機專業課程中起著承上啟下的重要作用。計算機技術已經發展到“復雜信息系統時代”，對于一般計算問題，計算機的計算性能不再是求解問題的瓶頸，與計算機技術發展相適應的學生培養方式，是進行計算思維的實踐，讓學生真正掌握利用計算機解決計算問題的通用方法。因此，基礎程序設計類課程的具體目標應該是，使學生學會從計算機的角度思考問題，培養學生的邏輯思維能力和程序設計方法。
2016年4月出版的本書第1版正是基于上述目標，通過對每種數據結構的由來或工程應用背景的介紹、發展邏輯的分析、表示方式的描述、實現細節的思維展現，探討數據結構的本質和內涵，將程序設計的思維痕跡完全展現出來，對經典數據結構及應用也進行了代碼級的實現，希望為學習者提供更多的幫助。
這一版本是在第1版的基礎上重新修訂而成的。除了修訂各種錯誤，還對相關度不大的內容進行了刪減；增加了一些有趣的案例；對篇幅較大的內容增加了分節標題，使條理更清晰。
英文版教材
本書對應的英文版教材Data Structures and Algorithms Analysis: New Perspectives入選國內信息領域英文課程“十三五”系列規劃教材，由科學出版社與DE GRUYTER（德國德古意特出版社）聯合出版，分國內版和海外版兩個版本（內容相同）。英文版因篇幅的關系，分為上下兩卷：
Volume 1: Data Structures Based on Linear Relations，ISBN：978-3-11-059558-1
Volume 2: Data Structures Based on Nonlinear Relations and Data Processing Methods，ISBN：978-3-11-067607-5
培訓教材
本書被某軟件開發公司選中作為培訓教材，在多個著名IT網站有對應的視頻課程。
獲獎
本書2017年獲西安電子科技大學第十五屆優秀教材一等獎（第二名）。
致謝
在第1版教材的使用過程中，有不少細心的讀者指出了書中的各種錯誤，特別是鐵滿霞教授和范敬喆同學，在認真通讀全書后，把各種問題一一標出，與作者認真討論。
非常感謝各位老師與讀者的熱心支持。
周幸妮
2020年5月2日

前 言
從新視角來看待舊問題，則需要創造性的思維。
—愛因斯坦
數據結構的教與學經歷
六七年前上數據結構課時，駕輕就熟地依然按照一貫的講法上課。上了幾次課后，收到班上一位同學的E-mail，其中說：“我自己是特別熱愛寫程序的。一方面我很熟悉電腦，軟硬件都有涉獵，所以學起來就不缺相關的基礎知識（像內存、寄存器、電子電路等這些都很熟悉）；另一方面我好像很能適應，也很喜歡這種思維方式……但班上不少同學好像對數據結構的學習理解和接受起來還是比較困難的……”
教授數據結構的課程也有十余年了，一直以來，學生們總認為數據結構不是一門容易學的課程，“在眾多的專業課中，數據結構被很多學生認為是一門很難學習的課程。”雖然我在學校讀書時沒有學習過數據結構的課程，只是因為后來要教書，才自學了數據結構。在自學的過程中，也并沒有覺著內容怎么難，這是怎么回事呢？
仔細回想一下自己學習與工作的經歷過程，或許就是來信的這位同學所說的，是因為在學習數據結構書本知識之前，已經有了較強的編程技能、一些數據結構實際應用的先驗知識吧。比如，在研究所工作時首次參加的軟件開發項目中，就有多進程、鏈表、隊列、散列等實際應用，雖然在學校并沒有學過這些概念，而是先接觸到實際項目中要處理的問題，再看到其他程序員的具體算法處理和程序實現方法，從實際的問題切入，就比較容易理解相應的數據組織形式和對應的算法，后來再接觸到書本的理論知識，就有一種一通百通、豁然開朗的感覺。還有一個原因是在軟件開發過程中逐漸熟悉并掌握了程序調試方法，對例程通過跟蹤的方法，很容易弄清執行的路徑和結果，對算法的設計和實現的理解也起到了事半功倍的效果。
回頭來看學生們學習的教科書，概念的介紹是傳統意義上的敘述方式，抽象度很高，但從實際到抽象、從抽象到實際的過程介紹不足，感性認識不足，抽象就難以理解接受。“現在有一個不好的傾向，就是教材或課堂過于重視抽象化的知識，忽視應用背景。數據結構的教材是這一傾向的代表。這對入門階段的學生來講是不適宜的，因為學生難以走進所涉及的抽象世界，最終表現為不知道在講什么。”
我的學生既沒有實際軟件開發的經驗也沒有熟練的編程調試基礎，對數據結構沒有感性認識，先接觸的是那些抽象的概念，感到理解和接受困難也就可以理解了。鄒恒明在《數據結構：炫動的0、1之弦》一書中指出，對于很多人來說，數據結構的概念并不難，真正的難點是：
? 如何實現從數據結構概念到程序實現的跨越（即如何實現一個數據結構）。
? 如何實現從實際應用到數據結構抽象的跨越（即如何利用數據結構解決實際問題）。
對于我來說，僅僅在學校學了一點點程序設計語言（記得所有上機時間加起來不超過20小時），沒有任何數據結構的知識，剛出校門就參與了歷時三年多后來獲得國家科技進步獎的大型軟件開發工作，以及后續多個電信用戶單位的實際軟件安裝、應用調試和維護工作，親歷和實現了上述兩個“跨越”的最實際生動的案例。項目的開發過程非常艱苦，在用戶單位調試現場連續大半年的天天加班到深夜，第二天依然要正點到機房的超負荷工作，有通宵的跟蹤調試，有24小時在線系統內存泄漏的巨大壓力，有上線后雙機備份系統同時崩潰爭分奪秒找bug的驚心動魄，等等。應該說自己是很幸運的，雖然在學校僅僅學習了一點點編程的概念，但在工作中根據需要自學和向同事學習了很多新知識、經驗和技巧，這樣的實踐和磨練，對后來的程序設計類課程的理解和教授是非常有益的。
學習數據結構困難的癥結
回想與總結起來，上述兩個要“跨越”的鴻溝是由學校的傳統教科書教法和實際的應用要求脫節造成的。
弗里德里希?威廉?尼采曾寫道：“人們無法理解他沒有經歷過的事情。”換句話說，我們只接受與過去早已理解的事物相關的信息。這是一種比較學習的過程，在這個過程中，大腦要尋找每條信息之間的聯系，借助以往經驗來理解新事物。
“歐拉認為，如果不能把解決數學問題背后的思維過程教給學生，數學教學就是沒有意義的。現代計算機實質上的發明者萊布尼茲也說過：在我看來，沒有什么能比探索發明的源頭還要重要，它遠比發明本身更重要。從小到大，我們看過的數學書幾乎無一不是歐幾里得式的：從定義到定理，再到推論。這樣的書完全而徹底地扭曲了數學發現的真實過程。目前幾乎所有的算法書的講解方式也都是歐幾里得式的，每一個推導步驟都是精準制導、直接面向數據結構目標的，實際上，這完全把人類大腦創造發明的步驟給反過來了。對讀者來說，這就等于直接告訴你答案和做法，然后讓你去驗證這個答案和做法是可行或成立的，而答案和做法到底是怎么來的，從問題到答案之間經歷了怎樣的思維過程，卻鮮有書能夠很好地闡釋。對于這類知識講述方式（歐幾里得式）的批判，西方（尤其是在數學領域）早就有了。”
傳統數據結構教科書的一般模式都是給出問題，然后直接給出算法，而實際上要用計算機解決問題，必須考慮的處理步驟有：如何分析問題中的已知信息，如何提煉數據及數據間的聯系（數據的邏輯結構），如何選用合適的存儲方式（數據的存儲結構）將邏輯結構存到計算機中，然后在存儲結構之上按照自頂向下逐步細化的方法給出算法，這才是真正解決實際問題的思維方法和步驟，也是軟件開發中實際采用的方法。傳統教科書的問題在于沒有對思維過程的引導與分析，致使概念論述、實現細節有余，設計實現過程描述不足，讓學生看到的只是一個個問題具體的詳解，而把握不住算法設計的總方法和原則。
本書嘗試從學以致用的角度給出問題或算法的知識背景或應用背景，增加了一些在實際軟件開發中的算法應用背景或實例；強調算法的分析方法、設計思路，給出重要算法的測試及調試分析，彌補了傳統教科書中的不足。教學生用“軟件開發的方法”處理問題，使學生容易理解并掌握它，在實際的軟件開發過程中能靈活選擇適當的邏輯結構、存儲結構及相應算法，設計性能優、效率高、可讀性強、易維護的程序，達到數據結構課程預期的目標。
程序設計與數據結構的關系
在學習數據結構知識之前要有程序設計的基礎，那么我們先來看看與編程相關的問題。
什么是編程？編程不僅僅是對語法的掌握，還涉及諸多方面：
（1）程序的解題思路—算法是由基本運算及規定的運算順序構成的完整解題步驟，是程序的靈魂，算法的優劣直接影響程序的效率。本書的算法描述方法見稍后的說明。
（2）程序運行的速度—程序運行的速度受很多因素的影響。用戶對程序的運行速度往往是有要求的，如實時響應系統。
（3）程序的運行空間—代碼運行需要相應的內存空間及相關運行環境。一些應用場合對程序占用的空間有限制，如嵌入式系統。
（4）代碼規范—代碼要按照一定的規范格式書寫，以保證代碼的一致性，便于交流和維護。
（5）程序的結構—一個功能復雜的程序由多個功能相對獨立的模塊組成。模塊內高內聚，模塊間低耦合，是判斷程序結構是否合理的標準。
（6）模塊接口—模塊間的信息交流通過接口完成，模塊間信息傳遞參數的設置應合理有效。
（7）程序的測試與調試—由精心設計的測試用例來測試程序是否正確。調試是高效率完成軟件產品的有效方法，一位編程高手也應該是調試專家，調試的經驗方法大多是在實踐中得到的。
我們在學習數據結構知識之前要有程序設計的基礎，那么數據結構與程序設計間的關系是怎樣的呢？應該說，數據結構是編寫規模龐大、邏輯復雜的更高級程序所需的基礎。表0.1給出了程序設計與高級編程的特點。
表0.1 程序設計與高級編程

程序設計的首要問題是模塊劃分的相關問題，另一個重要問題是把要解決問題的信息轉換成計算機能認識并接收的數據，這一轉換過程就是數據的抽象過程。要處理規模龐大的復雜問題，必須掌握數據的抽象思維方法，還要熟練掌握算法的規范聲明、算法的性能分析、算法的性能評價等諸多技能。
數據結構與其他課程的關系
作為一門重要的專業核心必修課程，“數據結構與算法”課程既是以往課程的深入和擴展，也為深入學習其他專業課程打下基礎。課程中排序問題算法以及基本的樹、圖等數據結構，是計算機科學的基本功。B+樹、散列（Hash）等高級數據結構，也是數據庫、操作系統、編譯原理、計算機網絡等重要專業課程的基礎。本課程在計算機學科中與其他課程的關系如圖0.1所示。

圖0.1 “數據結構與算法”課程在計算機學科中的重要地位
數據結構的重要性
商用程序員肖舸在他的博客中寫道：“這么多年，我做過游戲、通信、工業控制、教育、VoIP、服務器集群等各個方向的項目。不可謂不寬。
但是我知道的是，其實我都是在用一種方法寫程序，那就是從底層的數據結構和算法開始做起，用最基本的C、C++語言開發。用來用去，還是那么幾個數據結構、隊列、堆棧，等等。
這好比武俠小說里面的內功，內力修好了，學招式非常容易。但如果沒有內力，練再好的招式，見到高手就軟了。‘一力破十慧’，就是這個道理。在絕對的實力面前，任何花招都是沒有用的。”
對清華大學計算機系歷屆本科畢業生和部分研究生的追蹤調查顯示，幾乎所有的學生都認為“數據結構”是學校里學過的最有用的課程之一；“數據結構”是國內外許多軟件開發機構要求考核的基本課程之一；公司面試或筆試考核的絕大部分內容是數據結構或算法；數據結構也是計算機科學與技術、軟件工程等專業研究生考試必考科目。
數據結構會過時嗎
電子計算機自20世紀40年代誕生以來在硬件上不斷更新換代，軟件也是同步發展的，作為軟件的一個分支，程序設計語言也從機器語言發展到了第四代。但無論軟件如何發展，無論開發工具如何進步，只要我們的計算機還是基于馮?諾依曼體系的，數據結構和算法仍然是程序的核心，永遠不會被淘汰。
學習數據結構和算法并不僅僅要求我們學會如何使用和實現某種數據結構，更重要的是學會分析解決問題的思想和方法。
本書關于算法與程序實現增加的內容
在線性表、棧與隊列等相關章節中，特別增加了下列內容。
1．增加測試用例的設計
從程序健壯性的角度出發，測試用例的設計是開始程序設計時就應該考慮的重要內容。一般的程序設計與數據結構教科書很少考慮測試用例問題，本書在最初的算法設計中給出了基礎程序的測試用例設計，也是讓學習者以專業的方法學習程序設計，養成良好的設計習慣。
2．增加函數結構的設計
對初學者而言，在學習數據結構時，程序設計語言基礎并不扎實，特別是函數結構的設計不熟練。根據給定的功能、輸入/輸出信息，在調用與被調用的函數關系中，信息是怎樣傳遞的，往往存在多種可能的選擇，對于如何確定合適的形參類型、函數類型，初學者經常無所適從，從而造成編程困難。根據這種情況，本書特別給出了典型數據結構運算的多種方案實現，在對同一問題不同函數結構設計的比較中，讓讀者體會各種信息傳遞的方式和特點，鞏固和熟練編程知識與技巧，達到理論與實踐的統一。
3．增加重要程序的調試
程序設計的過程也是測試與調試的過程，程序的“編”與“調”密不可分。對于初學者而言，若調試不熟練，容易喪失繼續學習的信心。根據多年的教學經驗，若有程序調試演示，則相關程序比較容易掌握，特別是在學習鏈表等內容時，只是解釋數據結構、結點聯系，學生總覺得抽象難懂，若通過演示調試，觀察各結點間的聯系如何動態建立、消除等，則生動直觀，一目了然。由于調試過程步驟較多，學生看過了、明白了，但要再回想并模擬跟蹤過程則不是容易的事情，所以本書把一些重點例子的程序跟蹤過程記錄下來，以方便學生學習。本書所有的源碼均以C語言編制并在VS IDE環境下通過調試和測試。
4．算法描述方法
算法描述方法按照下面的順序給出（主要用于編程最基礎的線性表部分）。
（1）函數接口及測試用例設計：確定問題的輸入、輸出。
（2）算法偽代碼描述：描述問題的功能。
（3）數據結構描述：給出問題存儲結構的C類型描述。
（4）函數結構設計：確定函數類型、形參、返回值等。
函數結構樣例分別見表0.2和表0.3。
表0.2 函數結構樣例1

表0.3 函數結構樣例2

（5）程序實現：給出代碼實現。
（6）算法效率分析：分析問題的時間復雜度。
注：#define TRUE 1
#define FALSE 0
“數據結構”課程簡介
用計算機解決實際問題，首先要做的事情就是把問題涉及的相關信息存儲到計算機中，也就是需要把問題的信息表示為計算機可接收的數據形式，然后根據問題處理功能的要求，對存儲到計算機中的數據進行處理。歸結為一句話，就是用計算機解題首先要用合理的結構表示數據，然后才能根據相應的算法處理數據。
“數據結構”主要介紹如何合理組織數據、有效存儲和處理數據、正確設計算法以及對算法進行分析和評價。
1．課程性質與教學目的
“數據結構”是計算機科學中一門綜合性的專業基礎課。通過本課程的學習，學生能深入透徹地理解數據結構的邏輯結構和物理結構的基本概念以及有關算法，學會分析數據對象特征，掌握數據組織方法和計算機的表示方法，以便在實際的軟件開發過程中靈活選擇適當的邏輯結構、存儲結構及算法，設計性能優、效率高、可讀性強、易維護的程序，解決實際問題。同時，為學習“操作系統”“編譯原理”“數據庫”等課程奠定基礎。
“數據結構”是一門實踐性很強的課程，注重學生實踐活動。大量的上機實驗能讓學生加深對課程理論知識的理解，增強學習的興趣，提高計算機算法思維邏輯能力，為以后的研究和工作打下堅實的基礎。
2．基本要求
（1）了解數據結構及其分類、數據結構與算法的關系。
（2）熟悉各種基本數據結構及其操作，學會根據實際問題要求選擇數據結構。
（3）掌握設計算法的步驟和算法分析方法。
（4）掌握數據結構在排序和查找等常用算法中的應用。
（5）初步掌握文件組織方法和索引技術。
本書的組織結構
本書共9章。第1章介紹數據結構和算法的基本概念與算法分析方法；第2章至第6章從軟件開發的角度，通過應用背景或知識背景介紹、數據分析、函數設計、算法設計、調試等環節，對順序表、鏈表、棧、隊列、串、數組、樹、圖等基本類型的數據結構進行分析和討論；第7章介紹常見的數據排序方法，第8章介紹數據的索引與查找方法，這兩章的內容是對數據典型操作方法的介紹；第9章介紹常見的如遞歸、分治法、動態規劃、貪心算法等經典算法。
前言、第1～6章由周幸妮老師完成；第7、9章由任智源老師完成；第8章由馬彥卓老師完成；樊凱老師提供了通信等方面的部分專業應用案例；周幸妮對全書進行統稿。
書中設有“思考與討論”“知識ABC”等欄目。在“思考與討論”欄目中提出問題，引起讀者思考，并對提出的問題進行探討，幫助讀者加深對相關概念的理解，以期活躍思路、擴展思維。“知識ABC”欄目主要介紹概念的背景、算法的發明背景或故事等，以擴大讀者的知識面、了解數據結構的應用背景等。有些知識可能專業性比較強，對此可以“不求甚解”，大致了解即可，需要時再去查閱相關資料。
致謝
本書的寫作動力依然源自我的學生，起因是09級教改班同學的提議，他們說老師的授課方式、思路都不錯，寫出來會別具一格，讓大家學習這門課程時能更易于理解一些，這部分內容在我的《C語言程序設計新視角》一書中有所提及。
我的動力亦源于父親的鼓勵、家人的支持。感謝鐵滿霞教授、陳慧嬋教授的指點。感謝屈宇澄同學自始至終的支持和幫助。感謝孫蒙、丁煜、孫舒、孫亞萍、張柯、楊恒杰、吳偉基、黃超、張平等同學的熱心幫助。感謝西電通信工程學院13級教改班、14級卓越班，空間科學與技術學院13級實驗班同學們，對本書初稿講義提出的有益意見和建議。
和同學們、同事們的討論都讓我受益匪淺，這些討論或開闊了視野，或引起了深入思考，一切都是一種成長與完善的歷程。
感謝曾經給予我很多幫助、一起辛苦工作的同事們；感謝我有趣的人生經歷；感謝我可愛的學生們；感謝所有關心和幫助我的人們。
感謝Bandari的《April》，每天伊始，美妙的樂曲讓我在純凈、安定、溫暖的情緒中開始一天的寫作。
感恩一切。
周幸妮
2015年春于長安