1.1 數據結構的基本概念

1.1.1 為什么要學習數據結構

軟件設計是計算機學科的核心內容之一。進行軟件設計時要考慮的首要問題是數據的表示、組織和處理方法，這直接關系到軟件的工程化程度和軟件的運行效率。

隨著計算機技術的飛速發展，計算機應用從早期的科學計算擴大到過程控制、管理和數據處理等領域。計算機處理的對象也從簡單的數值數據，發展到各種多媒體數據。軟件系統處理的數據量越來越大，數據的結構也越來越復雜。因此，針對實際問題，如何合理地組織數據，如何建立合適的數據結構，如何設計好的算法，是軟件設計的重要問題，而這些正是“數據結構”課程討論的主要內容。

在計算機中，現實世界中的對象用數據來描述?！皵祿Y構”課程的任務是，討論數據的各種邏輯結構、在計算機中的存儲結構以及各種操作的算法設計。數據結構課程的主要目的是，培養學生掌握處理數據和編寫高效率軟件的基本方法，為學習后續專業課程以及進行軟件開發打下堅實基礎。

數據結構是軟件設計的重要理論和實踐基礎，數據結構設計和算法設計是軟件系統設計的基礎和核心?！皵祿Y構”課程討論的知識內容是軟件設計的理論基礎，“數據結構”課程介紹的技術方法是軟件設計中使用的基本方法?！皵祿Y構”是一門理論與實踐并重的課程，學生既要掌握數據結構的基礎理論知識，又要掌握運行和調試程序的基本技能。因此，“數據結構”課程在計算機學科本科培養過程中的地位十分重要，是計算機專業本科的核心課程，是培養程序設計能力的必不可少的重要環節。

在計算機界流傳著一句經典名言“數據結構+算法=程序設計”（瑞士Niklaus Wirth教授），這句話簡潔、明了地說明了程序（或軟件）與數據結構和算法的關系，以及“數據結構”課程的重要性。

1.1.2 什么是數據結構

數據（data）是描述客觀事物的數字、字符以及所有能輸入到計算機中并能被計算機接受的各種符號集合的統稱。數據是信息的符號表示，是計算機程序的處理對象。除了數值數據，計算機能夠處理的數據還可以是各種非數值數據，如字符串、圖形、圖像、音頻、視頻等多媒體數據。

表示一個事物的一組數據稱為一個數據元素（data element），數據元素是數據的基本單位。一個數據元素可以是一個不可分割的原子項，也可以由多個數據項組成。數據項（data item）是數據元素中有獨立含義的、不可分割的最小標識單位。例如，一個整數、一個字符都是原子項，一個學生數據元素由學號、姓名、性別和出生日期等多個數據項組成。關鍵字（key）是數據元素中用于識別該元素的一個或多個數據項，能夠唯一識別數據元素的關鍵字稱為主關鍵字（primary key）。

在由數據元素組成的數據集合中，數據元素之間通常具有某些內在聯系。研究數據元素之間存在的關系并建立數學模型，是設計有效地組織數據和處理數據方案的前提。

數據的結構是指數據元素之間存在的關系。一個數據結構（data structure）是由n（n≥0）個數據元素組成的有限集合，數據元素之間具有某種特定的關系。

數據結構概念包含三方面：數據的邏輯結構、數據的存儲結構和數據的操作。

1.數據的邏輯結構

數據的邏輯結構是指數據元素之間的邏輯關系，用一個數據元素的集合和定義在此集合上的若干關系來表示，常被簡稱為數據結構。

根據數據元素之間邏輯關系的不同數學特性，數據結構可分為三種：線性結構、樹結構和圖結構（如圖1.1所示），其中樹和圖又稱為非線性結構。

圖1.1以圖示法表示了數據的邏輯結構，一個圓表示一個數據元素，圓中的字符表示數據元素的標記或取值，連線表示數據元素之間的關系。

（1）線性結構

線性結構是最簡單的數據結構，數據元素之間具有線性關系，即除第一個和最后一個元素外，每個元素有且僅有一個直接前驅元素和一個直接后繼元素，第一個元素沒有前驅元素，最后一個元素沒有后繼元素。在圖1.1（a）中，元素B的前驅是A，后繼是C，元素A沒有前驅，元素C沒有后繼。線性表、串、棧和隊列等都是線性結構。

數據元素可以是數字﹑字符、字符串或其他復雜形式的數據，如整數序列{1, 2, 3, 4, 5, 6}，字母序列{'A', 'B', 'C',…, 'Z'}，表1-1所示的學生序列也是線性表，數據元素之間具有順序關系。學生數據元素由“學號”、“姓名”、“年齡”等多個數據項組成，“姓名”可以作為標識一個學生的關鍵字，但不是主關鍵字；“學號”是能夠唯一標識一個學生的主關鍵字。

（2）樹結構

樹結構是數據元素之間具有層次關系的一種非線性結構，樹中的數據元素通常稱為結點。樹結構的層次關系是指，根結點（最頂層）沒有前驅結點（稱為父母結點），除根之外的其他結點有且僅有一個父母結點，所有結點可有零到多個直接后繼結點（稱為孩子結點）。在圖1.1（b）中，A是樹的根結點，B結點有一個父母結點A，且有3個孩子結點D、E和F。家譜、Windows文件系統的組織方式、淘汰賽的比賽規則等都是樹結構。具有樹結構的淘汰賽比賽規則如圖1.2所示，其中的數據是2006年世界杯足球賽淘汰賽的比賽結果。

（3）圖結構

圖也是非線性結構，每個數據元素可有多個直接前驅元素和多個直接后繼元素。例如，交通道路圖、飛機航班路線圖等都具有圖結構。圖1.3是從南京飛往昆明的航班路線圖，有直飛航班，也有經停重慶或長沙的航班，連線邊上數值表示兩地間的千米數。

2.數據的存儲結構

數據元素及其關系在計算機中的存儲表示或實現稱為數據的存儲結構，也稱為物理結構。軟件系統不僅要存儲所有數據，還要正確地表示出數據元素之間的邏輯關系。

數據的邏輯結構是從邏輯關系角度觀察數據，與數據的存儲無關，是獨立于計算機的。而數據的存儲結構是邏輯結構在計算機物理存儲中的實現，是依賴于計算機的。

數據存儲結構的基本形式有兩種：順序存儲結構和鏈式存儲結構。

（1）順序存儲結構

順序存儲結構使用一組連續的內存單元依次存放數據元素，元素在內存的物理存儲次序與它們的邏輯次序相同，即每個元素與其前驅及后繼元素的存儲位置相鄰。這樣，元素的物理存儲次序體現數據元素間的邏輯關系，通常使用程序設計語言中的數組實現。

（2）鏈式存儲結構

鏈式存儲結構使用若干地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據元素在物理位置上不一定相鄰，數據元素間的關系需要采用附加信息特別指定。通常，采用指針變量記載前驅或后繼元素的存儲地址，由數據域和指針域組成的一個結點表示一個數據元素，通過指針域把相互直接關聯的結點鏈接起來，結點間的鏈接關系體現數據元素間的邏輯關系。

線性表可采用上述兩種存儲結構。如線性表（A, B, C, D）的兩種存儲結構如圖1.4所示。

在線性表的順序存儲結構中，數據域占用所有存儲空間，數據元素連續存儲，邏輯上相鄰的數據元素在存儲位置上也相鄰，因此數據的存儲結構體現數據的邏輯結構。

在鏈式存儲結構中，數據元素分散存儲，每個結點至少由兩部分組成：數據域和指針域，分別保存數據元素及前驅和（或）后繼結點的地址。結點間的鏈接關系體現數據的邏輯結構。

如果一個數據元素由多個數據項組成，則數據域有多個。例如，學生信息表的順序存儲結構和鏈式存儲結構如圖1.5所示。

順序存儲結構和鏈式存儲結構是兩種最基本、最常用的存儲結構。除此之外，將順序存儲結構和鏈式存儲結構進行組合，還可以構造出更復雜的存儲結構。

3.數據操作

數據操作是指對一種數據結構中的數據元素進行各種運算或處理。每種數據結構都有一組數據操作，其中包含以下基本操作。

? 初始化。

? 判斷是否空狀態。

? 求長度：統計元素個數。

? 包含：判斷是否包含指定元素。

? 遍歷：按某種次序訪問所有元素，每個元素只被訪問一次。

? 取值：獲取指定元素的值。

? 置值：設置指定元素的值。

? 插入：增加指定元素。

? 刪除：移去指定元素。

數據操作定義在數據的邏輯結構上，對數據操作的實現依賴于數據的存儲結構。例如，線性表包含上述一組數據操作，采用順序存儲結構或鏈式存儲結構，都可實現這些操作。

1.1.3 數據類型與抽象數據類型

1.數據類型

類型（type）是具有相同邏輯意義的一組值的集合。數據類型（data type）是指一個類型和定義在這個類型上的操作集合。數據類型定義了數據的性質、取值范圍以及對數據所能進行的各種操作。例如，C++語言的整數類型int，除了數值集合[-231, …, -2, -1, 0, 1, 2, …, 231-1]之外，還包括在這個值集上的操作集合[+, -, *, /, %, =]。

程序中的每個數據都屬于一種數據類型，決定了數據的類型也就決定了數據的性質以及對數據進行的運算和操作，同時數據也受到類型的保護，確保對數據不能進行非法操作。

高級程序設計語言通常預定義一些基本數據類型和構造數據類型。基本數據類型的值是單個的、不可分解的，它可直接參與該類型所允許的運算。構造數據類型是使用已有的基本數據類型和已定義的構造數據類型按照一定的語法規則組織起來的較復雜的數據類型。構造數據類型的值由若干元素組合而成，這些元素按某種結構組織在一起。

C++語言的基本數據類型有整數類型、浮點數類型、字符類型等，構造數據類型有數組、結構體和文件等。例如，學生數據元素可聲明為如下結構體類型，也可聲明為類（class）。

            struct Student
            {
                char number[10];                       //學號
                char name[20];                         //姓名
                int age;                               //年齡
            };

由若干學生組成的數據序列可聲明存儲在一個數組（array）中。例如：

            Student group[50];

數據類型與數據結構這兩個概念的側重點不同。數據類型研究的是每種數據所具有的特性，以及對這種特性的數據能夠進行哪些操作；數據結構研究的是數據元素之間具有的相互關系，與數據元素的數據類型無關，也不隨數據元素值的變化而改變。

2.抽象數據類型

抽象數據類型（Abstract Data Type，ADT）是指一個數學模型以及定義在該模型上的一組操作。例如，復數是數學中常用的一種類型，但多數程序設計語言沒有提供復數類型。一個復數a+bi由實部a和虛部b兩部分組成，i是虛部標記。復數抽象數據類型描述如下：

            ADT CompIex                                   //復數抽象數據類型
            {
                doubIe reaI,im;                           //復數的實部和虛部
                CompIex（reaI,im）;                       //指定實部和虛部構造一個復數
                CompIex add（CompIex c）;                 //加法，返回當前復數與c相加之后的復數
                CompIex sub（CompIex c）;                 //減法，返回當前復數與c相減之后的復數
            };

抽象數據類型和數據類型本質上是一個概念，“抽象”的含義是“定義與實現相分離”，即將一個類型上的數據及操作的邏輯含義與具體實現分離。程序設計語言提供的數據類型是抽象的，僅描述數據的特性和對數據操作的語法規則，并沒有說明這些數據類型是如何實現的。程序員按照語言規則使用數據類型，只考慮對數據執行什么操作（做什么），而不必考慮怎樣實現這些操作（怎樣做）。程序設計語言實現了它預定義數據類型的各種操作。例如，賦值語句的語法定義如下：

            變量=表達式

它表示先求得指定表達式的值，再將該值賦給指定變量。程序員需要關注所用數據類型的值能夠參加哪些運算、表達式是否合法、表達式類型與變量類型是否賦值相容等；至于如何存儲一個整數、變量的存儲地址是什么、如何求得表達式值等實現細節則不必關注，這些操作由語言的實現系統完成。

ADT的規范描述包括ADT名稱、數據描述和操作描述，操作描述包括操作名、初始條件和操作結果。例如，集合ADT描述如下：

            ADT Set
            {
              數據：集合中有n（n≥0）個數據元素，元素類型為T
              操作：
                booI isEmpty（　）;                      //判斷集合是否為空
                int Iength（　）;                        //返回集合的元素個數
                booI contain（T x）;                   //判斷集合是否包含指定元素x
                booI add（T x）;                       //增加指定元素x
                booI remove（T x）;                    //移去首次出現的指定元素x
                void cIear（　）;                        //清空集合元素
                void print（　）;                        //輸出集合中所有元素
                booI equaIs（Set s）;                  //比較當前集合與集合s是否相等
                booI containAII（Set s）;              //判斷當前集合是否包含集合s中的所有元素
                booI addAII（Set s）;                  //增加集合s中的所有元素，集合并
                booI removeAII（Set s）;               //移去那些也包含在集合s中的元素，集合差
                booI retainAII（Set s）;               //僅保留那些也包含在集合s中的元素
            }

類似地，可將線性表、棧、隊列、串、樹、二叉樹、圖等數據結構分別定義為抽象數據類型，描述相應數據結構的邏輯特性和操作，與該數據結構在計算機內的存儲及實現無關。

抽象是研究復雜對象的基本方法，也是一種信息隱蔽技術，從復雜對象中抽象出本質特征，忽略次要細節，使實現細節相對于使用者不可見。抽象層次越高，其軟件復用程度也越高。抽象數據類型是實現軟件模塊化設計思想的重要手段。一個抽象數據類型是描述一種特定功能的基本模塊，由各種基本模塊可組織和構造起來一個大型軟件系統。