“數據結構與算法”是軟件開發技術的一門重要的專業基礎課程。課程主要討論現實世界中數據之間的各種邏輯結構、在計算機中的存儲結構以及各種算法的設計問題。本書討論的內容包括：線性表、堆棧、隊列、串、數組、樹、圖、查找、排序。其中，線性表、堆棧、隊列、串、數組屬于線性結構，樹和圖是非線性結構，查找和排序是兩個應用廣泛的算法設計問題。
第1章緒論
本章介紹“數據結構與算法”這門課程的相關知識,包括數據結構的概念、課程的主要內容、三種基本邏輯結構、算法的概念和算法評價的度量。通過本章的學習,應能使學生對“數據結構與算法”這門課程有一個基本的了解。
【技能目標】
會用數據結構的概念解釋日常生活的問題。
掌握邏輯結構、存儲結構的概念。
能找到現實生活中線性、樹和圖三種結構的實例。
掌握算法的五個特性準則。
會用算法效率的評價指標評價算法的執行效率。
1.1學習數據結構的意義
早期人們都感覺計算機是用來計算的,用來處理數值計算非常方便快捷。隨著計算機處理能力越來越強,計算機不再只是簡單的數值計算工具,而是被賦予越來越多的功能。現實世界有很多非數值計算的問題,需要一些更科學更有效手段的幫助才能更好地處理這些問題。所以數據結構是一門研究非數值計算的程序設計中計算機的操作對象以及它們之間的關系和操作等相關問題的學科。
針對實際問題,要編寫出高效率的處理程序,就需要解決如何合理地組織數據,建立合適的數據結構,設計較好的算法,來提高程序執行效率這樣的問題。數據結構和算法就是在此背景下形成和發展起來的。
簡而言之,軟件開發要多動腦筋,想到好的解決辦法才能更快更好地編寫出效率更高的程序。“數據結構和算法”這門課程的目的正是使學生更快地編寫出更高效的程序。
1.1.1引言
計算機完成的任何操作都是在程序的控制下進行的,而程序的根本任務就是進行數據處理。隨著計算機在各行各業應用的日益深入,計算機所處理的數據對象也由純粹的數值型發展到字符、表格、圖形、圖像和聲音等多種形式,計算機要處理這些數據,首先要將這些數據存儲在計算機內存中。如何將程序中要處理的數據進行合理地存儲,以及采用何種方法能夠高效地進行數據處理,是程序設計的關鍵,也是數據結構要解決的重要問題。
即使是在廣泛采用可視化程序設計的今天,借助于集成開發環境可以很快地生成程序,但要想成為一個專業的程序開發人員,至少需要具備以下三個條件。
(1)能夠熟練地選擇和設計各種業務邏輯的數據結構和算法。
(2)至少能夠熟練地掌握一門程序設計語言。
(3)熟知所涉及的相關應用領域知識。
其中,后兩個條件比較容易實現,而第一個條件則需要花很多時間和精力才能夠達到,而它恰恰是區分程序設計人員水平高低的一個重要標志。數據結構貫穿程序設計的始終,缺乏數據結構和算法的功底,很難設計出高水平的具有專業水準的應用程序。著名的瑞士計算機科學家尼古拉斯·沃斯(NiklausWirth)提出了“算法+數據結構=程序”的觀點,正說明了數據結構的重要性。
例如,計算機要處理一批雜亂無章的數據,需對其進行有序化處理,計算機解決問題的步驟是什么呢?
要解決這個問題,首先要考慮應如何將這批數據進行合理地存儲;然后考慮應采用什么有效的方法對這些數據進行有序化;最后選擇一種編程語言實現以上方法。其實用計算機解決任何數據處理的問題,都需要經過以上過程才能實現。
數據結構主要研究和討論以下三個方面的問題。
(1)數據集合中各數據元素之間的關系。
(2)在對數據進行處理時,各數據元素在計算機的存儲關系,即數據的存儲結構。
(3)針對數據的存儲結構進行的運算。
解決好以上問題,可以大大提高數據處理的效率。
1.1.2數據結構研究什么
數據結構可定義為一個二元組:Data_Structure=(D,R),其中D表示數據元素的有限集,R表示D之間的關系。數據結構與算法具體應包括以下方面:邏輯結構、邏輯結構的延伸及基本算法、物理結構和運算集合。
1.邏輯結構
數據的邏輯結構是指數據元素之間邏輯關系的描述。根據數據元素之間關系的特性,數據結構有三種基本的邏輯結構,如圖1.1所示。
圖1.1三種基本邏輯結構
(1)線性結構。結構中的數據元素之間存在一對一的線性關系。線性結構將在第2章詳細講解。
(2)樹結構。結構中的數據元素之間存在一對多的層次關系。樹結構將在第6章詳細講解。
(3)圖結構。結構中的數據元素之間存在多對多的任意關系。圖結構將在第7章詳細講解。
2.邏輯結構的延伸及基本算法
(1)串。串是字符串的簡稱,它的每個數據元素都由一個字符組成。串是一種特殊的線性結構。串結構將在第4章詳細講解。
(2)數組。數組是一種數據類型,它是一種順序存儲結構。將在第5章中詳細講解數組中各個元素的相對存放位置,以及用數組存放特殊矩陣,并實現矩陣的運算。
(3)查找。數據結構要跟算法結合起來才有意義,查找算法是數據結構在各種算法中的基本應用,在現實生活中也經常用到這種算法。查找算法將在第8章詳細講解。
(4)排序。排序算法將在第9章中詳細講解。
3.物理結構
物理結構(又稱存儲結構)是邏輯結構在計算機中的存儲映像,是邏輯結構在計算機中的實現(或存儲表示),它包括數據元素的表示和關系的表示。有數據結構Data_Structure=(D,R),對于D中的每一數據元素都對應著存儲空間中的一個單元,D中全部元素對應的存儲空間必須明顯或隱含地體現關系R。邏輯結構與存儲結構的關系為:存儲結構是邏輯結構的映像與元素本身的映像。邏輯結構是抽象,存儲結構是實現,兩者綜合起來建立了數據元素之間的結構關系。存儲結構一般有順序存儲和鏈表存儲兩種方式。
4.運算集合
討論數據結構的目的是為了在計算機中實現所需的操作,施加于數據元素之上的一組操作構成了數據的運算集合,因此運算集合是數據結構很重要的組成部分。
1.2數據結構的基本概念
數據結構有以下這些基本概念。
1.數據
數據是描述客觀事物的數值、字符以及所有其他能輸入計算機中,且能被計算機處理的各種符號的集合。簡言之,數據就是存儲在計算機中的信息。
數據不僅僅包括整型、實型等數值類型,還包括字符、聲音、圖像、視頻等非數值類型。比如,現在常用的搜索引擎一般會有網頁、圖片、音樂、視頻等分類。音樂就是聲音數據;圖片是圖像數據;網頁就是全部數據的集合,包括數字、字符和圖像等數據。
2.數據元素
數據元素是組成數據的基本單位,是數據集合的個體,在計算機中通常作為一個整體進行考慮和處理。
比如,在學生這個群體中,每一個學生就是數據元素。
3.數據項
數據項是有獨立含義的不可再分割的最小單位。一個數據元素可由一個或多個數據項組成,如每一個學生的信息是一個數據元素,它包含學號、姓名等多個數據項。
4.數據對象
數據對象是性質相同的數據元素的集合,是數據的一個子集。例如:整數數據對象是集合N={0,±1,±2,…},字母字符數據對象是集合C={'A','B',…,'Z'},無論數據元素集合是無限集(如整數集)、有限集(如字符集),還是由多個數據項組成的復合數據元素,只要性質相同,都是同一個數據對象。
5.數據類型
數據類型是一組性質相同的值集合以及定義在這個值集合上的一組操作的總稱。值集合確定了該類型的取值范圍,操作集合確定了該類型中允許使用的一組運算。例如高級語言中的數據類型就是已經實現的數據結構。
6.抽象數據類型
抽象數據類型是指基于一類邏輯關系的數據類型。抽象數據類型的定義取決于客觀存在的一組邏輯特性,而與其在計算機內如何表示和實現無關。
7.數據結構
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。
在計算機中,數據元素之間是具有內在聯系的數據集合。數據元素之間存在的關系,就是數據的組織形式。為編寫出一個高效的程序,必須分析處理對象的特性及各對象之間的關系,這就是數據結構要研究的內容。
1.3算法及其描述
算法是解決問題的方法,是程序設計的精髓,程序設計的實質就是構造解決問題的算法。算法的設計取決于數據的邏輯結構,算法的實現取決于數據的物理存儲結構。
1.3.1算法的概念和特性
算法是對特定問題求解步驟的一種描述,它是指令的有限序列。做任何事情都必須事先想好操作的步驟,然后按部就班地進行,才不會發生錯誤。計算機解決問題也是如此。對于一些常用的算法應該熟記,比如求階乘、求素數、計算是否閏年等算法,在解決實際問題時,可參考已有的類似算法,按照業務邏輯設計出符合自己的算法。
一個算法應該具有以下五個重要特性。
(1)有窮性
一個算法應包含有限的操作步驟。即一個算法在執行若干個步驟之后應該能夠結束,而且每一步都在有限時間內完成。
(2)確定性
算法中的每一步都必須有確切的含義,不能產生二義性。
(3)可行性
算法中的每一個步驟都應該能有效地執行,并得到確定的結果。
(4)輸入
所謂輸入,是指在算法執行時,從外界取得必要的數據。計算機運行程序的目的是進行數據處理,在大多數情況下,這些數據需要通過輸入得到。有些情況下,數據已經包含在算法中,算法執行時不需要任何數據,所以一個算法可以有零個或多個輸入。
(5)輸出
一個算法有一個或多個輸出,這是算法進行數據處理后的結果。沒有輸出的算法是毫無意義的。
算法的這些特性可以約束程序設計人員正確地書寫算法,并使之能夠正確無誤地執行,達到求解問題的預期效果。
本書所討論的算法,可用不同的方式進行描述,常用的有類Pascal、類C、類C++、類Java程序設計語言,本書同時以C和Java兩種程序設計語言作為描述工具,以方便廣大同學學習。
1.3.2算法設計的要求
算法設計的好壞關乎程序的執行效率,算法的設計必須滿足下列四個要求。
(1)正確性
正確性的含義是算法對于一切合法的輸入數據都能夠得到滿足要求的結果,事實上要驗證算法的正確性是極其困難的,因為通常情況下合法的輸入數據量太大,用窮舉法逐一驗證是不現實的。所謂的算法正確性是指算法達到了測試要求。
(2)可讀性
算法的可讀性是指人們對算法閱讀理解的難易程度,可讀性高的算法便于閱讀,有利于算法的理解和交流。通常在書寫算法程序時，添加程序注釋、采用按縮進格式書寫、分模塊書寫等方法可增加算法的可讀性。
(3)健壯性
新書資訊