<sup id="gs2s0"></sup>
<sup id="gs2s0"></sup>
<acronym id="gs2s0"><center id="gs2s0"></center></acronym>
<rt id="gs2s0"><center id="gs2s0"></center></rt>

數據結構(C語言版)第二版

所需積分/C幣:42 2018-12-16 18:22:19 38.58MB PDF
收藏 收藏
舉報

數據結構 C語言版 第二版 電子書,非常適合新手使用。 早期的計算機主要用于數值計算,現在,計算機主要用于非數值計算,包括處理字符、表格和圖像等具有一定結構的數據。這些數據內容存在著某種聯系,只有分清楚數據的內在聯系,合理地組織數據,才能對它們進行有效的處理,設計出高效的算法。
第】章 緒論 早期的計算機主要用于數值計算,現在,計算機主要用于非數值計算,包括處理字符、表格 和圖像等具有一定結構的數據。這些數據內容存在著某種聯系,只有分清楚數據的內在聯系,合 理地組織數據,才能對它們進行有效的處理,設計出高效的算法。如何合理地組織數據、高效地 處理數據,這就是“數據結構”主要研究的問題。本章簡要介紹有關數據結構的基本概念和算法 分析方法。 11數據結構的研究內容 計算機主要用于數值計算時,一般要經過如下幾個步驟:首先從具體問題抽象出數學模型 然后設計一個解此數學模型的算法,最后編寫程序,進行測試、調試,直到解決問題。在此過程 中尋求數學模型的實質是分析問題,從中提取操作的對象,并找出這些操作對象之間的關系,然 后用數學語言加以描述,即建立相應的數學方程。例如,用計算機進行全球天氣預報時,就需要 求解一組球面坐標系下的二階橢圓偏微分方程;預測人口增長情況的數學模型為常微分方程。求 解這些數學方程的算法是計算數學研究的范疇,如高斯消元法、差分法、有限元法等算法。數據 結構主要研究非數值計算問題,非數值計算問題無法用數學方程建立數學模型,下面通過三個實 例加以說明 【例1.1】學生學籍管理系統。 高等院校教務處使用計算機對全校的學生情況作統一管理。學生的基本信息,包括學生的學 號、姓名、性別、籍貫、專業等,如表1.1所示。每個學生的基本情況按照不同的順序號,依次 存放在“學生基本信息表”中,根據需要對這張表進行查找。每個學生的基本信息記錄按順序號 排列,形成了學生基本信息記錄的線性序列,呈一種線性關系。 表1.1 學生基本信息表 學號 姓名 性別 籍貫 專業 060214201 楊陽 男 安徽 計算機科學與技術 060214202 薛林 男 福建 計算機科學與技術 060214215 王詩萌 女 吉林 計算機科學與技術 060214216 馮子晗 女 山東 計算機科學與技術 諸如此類的線性表結構還有圖書館的書目管理系統、庫存管理系統等。在這類問題中,計算 數據結構(C語言版)(第2版) 機處理的對象是各種表,元素之間存在簡單一對一的線性關系,因此這類問題的數學模型就是各 種線性表,施加于對象上的操作有查找、插入和刪除等。這類數學模型稱為“線性”的數據結構。 【例12】人機對弈問題。 計算機之所以能和人對弈是因為已經將對弈的策略在計算機中存儲好。由于對弈的過程是在 定規則下隨機進行的,所以,為使計算機能靈活對弈,就必須把對弈過程中所有可能發生的情 況及相應的對策都加以考慮。以最簡單的井字棋為例,初始狀態是一個空的棋盤格局。對弈開始 后,每下一步棋,則構成一個新的棋盤格局,且相對于上一個棋盤格局的可能選擇可以有多種形 式,因而整個對弈過程就如同圖1.1所示的“一棵倒長的樹”。在這棵“樹”中,從初始狀態(根) 到某一最終格局(葉子)的一條路徑,就是一次具體的對弈過程。 人機對弈問題的數學模型就是如何用樹結構表示棋盤和棋子等,算法是博弈的規則和策略。 諸如此類的樹結構還有計算機的文件系統、一個單位的組織機構等。在這類問題中,計算機處理 的對象是樹結構,元素之間是一對多的層次關系,施加于對象上的操作有查找、插入和刪除等。 這類數學模型稱為“樹”的數據結構。 【例1.3】最短路徑問題。 從城市A到城市B有多條線路,但每條線路的交通費不同,那么,如何選擇一條線路,使得 從城市A到城市B的交通費用最少呢?解決的方法是,可以把這類問題抽象為圖的最短路徑問 題。如圖1.2所示,圖中的頂點代表城市,有向邊代表兩個城市之間的通路,邊上的權值代表兩 個城市之間的交通費。求解A到B的最少交通費用,就是要在有向圖中A點(源點)到達B點 (終點)的多條路徑中,尋找一條各邊權值之和最小的路徑,即最短路徑。 區 60 30 20 幽 圖1.1井字棋的對弈樹 圖1.2最短路徑問題 彐第1章緒論 最短路徑問題的數學模型就是圖結構,算法是求解兩點之間的最短路徑。諸如此類的圖結構 還有網絡工程圖和網絡通信圖等,在這類問題中,元素之間是多對多的網狀關系,施加于對象上 的操作依然有查找、插入和刪除等。這類數學模型稱為“圖”的數據結構。 從上面三個實例可以看出,非數值計算問題的數學模型不再是數學方程,而是諸如線性表 樹和圖的數據結構。因此,簡單地說,數據結構是一門研究非數值計算程序設計中的操作對象, 以及這些對象之間的關系和操作的學科。 20世紀60年代初期,“數據結構”有關的內容散見于操作系統、編譯原理等課程中。1968 年,“數據結構”作為一門獨立的課程被列人美國一些大學計算機科學系的教學計劃,同年,著名 計算機科學家D. E. Knuth教授發表了《計算機程序設計藝術》第一卷《基本算法》。這是第一本較 系統地闡述“數據結構”基本內容的著作。之后,隨著大型程序和大規模文件系統的出現,結構化 程序設計成為程序設計方法學的主要研究方向,人們普遍認為程序設計的實質就是對所處理的問題選 擇一種好的數據結構,并在此結構基礎上施加一種好的算法,著名科學家 Wirth教授的《算法+數據 結構=程序》正是這種觀點的集中體現。 目前,數據結構在計算機科學中是一門綜合性的專業基礎課。數據結構的研究不僅涉及計算 機硬件(特別是編碼理論、存儲裝置和存取方法等)的硏究范圍,而且和計算機軟件的硏究有著 密切的關系,無論是編譯程序還是操作系統都涉及數據元素在存儲器中的分配問題。在研究信息 檢索時也必須考慮如何組織數據,以使查找和存取數據元素更為方便。因此,可以認為數據結構 是介于數學、計算機硬件和軟件三者之間的一門核心課程。 有關“數據結構”的研究仍不斷發展,一方面,面向各專門領域中特殊問題的數據結構正在 研究和發展;另一方面,從抽象數據類型的觀點來討論數據結構,已成為一種新的趨勢,越來越 被人們所重視。 1.2基本概念和術語 下列概念和術語將在以后各章節中多次出現,本節先對這些概念和術語賦予確定的含義。 121數據、數據元素、數據項和數據對象 數據(Data)是客觀事物的符號表示,是所有能輸入到計算機中并被計算機程序處理的符號 的總稱。如數學計算中用到的整數和實數,文本編輯中用到的字符串,多媒體程序處理的圖形、 圖像、聲音及動畫等通過特殊編碼定義后的數據。 數據元素( Data element)是數據的基本單位,在計算機中通常作為一個整體進行考慮和處理。 在有些情況下,數據元素也稱為元素、記錄等。數據元素用于完整地描述一個對象,如前一節示 例中的一名學生記錄,樹中棋盤的一個格局(狀態),以及圖中的一個頂點等。 數據項( Data Item)是組成數據元素的、有獨立含義的、不可分割的最小單位。例如,學生 基本信息表中的學號、姓名、性別等都是數據項。 數據對象( Data Object)是性質相同的數據元素的集合,是數據的一個子集。例如:整數數 據對象是集合N={0,±1,±2,…},字母字符數據對象是集合C={A’,B',…,Z',a',“b’,…, z”},學生基本信息表也可以是一個數據對象。由此可以看出,不論數據元素集合是無限集(如 整數集),或是有限集(如字母字符集),還是由多個數據項組成的復合數據元素(如學生表)的 二數據結構(C語言版)(第2版)三 集合,只要集合內元素的性質均相同,都可稱之為一個數據對象。 12.2數據結構 數據結構( Data structure)是相互之間存在一種或多種特定關系的數據元素的集合。換句話 說,數據結構是帶“結構”的數據元素的集合,“結構”就是指數據元素之間存在的關系。 數據結構包括邏輯結構和存儲結構兩個層次。 1.邏輯結構 數據的邏輯結構是從邏輯關系上描述數據,它與數據的存儲無關,是獨立于計算機的。因此, 數據的邏輯結構可以看作是從具體問題抽象出來的數學模型。 數據的邏輯結構有兩個要素:一是數據元素;二是關系。數據元素的含義如前所述,關系是 指數據元素間的邏輯關系。根據數據元素之間關系的不同特性,通常有四類基本結構,如圖1.3 所示。它們的復雜程度依次遞進 集合結構 線性結構 o 樹結構 圖結構 圖1.3四類基本邏輯結構關系圖 下面四種結構中所舉的示例是以某班級學生作為數據對象(數據元素是學生的學籍檔案記 錄),來分別考察數據元素之間的關系。 (1)集合結構 數據元素之間除了“屬于同一集合”的關系外,別無其他關系。例如,確定一名學生是否為 班級成員,只需將班級看做一個集合結構。 (2)線性結構 數據元素之間存在一對一的關系。例如,將學生信息數據按照其入學報到的時間先后順序進 行排列,將組成一個線性結構。 (3)樹結構 數據元素之間存在一對多的關系。例如,在班級的管理體系中,班長管理多個組長,每位組 長管理多名組員,從而構成樹形結構。 (4)圖結構或網狀結構 數據元素之間存在多對多的關系。例如,多位同學之間的朋友關系,任何兩位同學都可以是 朋友,從而構成圖狀結構或網狀結構。 其中集合結構、樹結構和圖結構都屬于非線性結構。 線性結構包括線性表(典型的線性結構,如例1.1中的學生基本信息表)、棧和隊列(具有特 第1章緒論 殊限制的線性表,數據操作只能在表的一端或兩端進行)、字符串(也是特殊的線性表,其特殊性 表現在它的數據元素僅由一個字符組成)、數組(是線性表的推廣,它的數據元素是一個線性表) 廣義表(也是線性表的推廣,它的數據元素是一個線性表,但不同構,即或者是單元素,或者是 線性表)非線性結構包括樹(具有多個分支的層次結構)和二叉樹(具有兩個分支的層次結構) 有向圖(一種圖結構,邊是頂點的有序對)和無向圖(另一種圖結構,邊是頂點的無序對)。這幾 種邏輯結構可以用一個層次圖描述,如圖1.4所示。 數據的邏輯結構 線性結構 非線性結構 線性表 樹結構 圖結構 一般線性表特殊線性表線性表的推廣 樹二叉樹有向圖無向圖 線性表棧與隊列字符串數組廣義表 圖14幾種邏輯結構層次圖 2.存儲結構 數據對象在計算機中的存儲表示稱為數據的存儲結構,也稱為物理結構。把數據對象存儲到 計算機時,通常要求既要存儲各數據元素的數據,又要存儲數據元素之間的邏輯關系,數據元素 在計算機內用一個結點來表示。數據元素在計算機中有兩種基本的存儲結構,分別是順序存儲結 構和鏈式存儲結構。 (1)順序存儲結構 順序存儲結構是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系,通常借助 程序設計語言的數組類型來描述。 對于前面的“學生基本信息表”,假定每個結點(學生記錄)占用50個存儲單元,數據從0 號單元開始由低地址向高地址方向存儲,對應的順序存儲結構如表12所示。 表12 順序存儲結構 地址 學號 姓名 性別 籍貫 專業 060214201 楊陽 安徽 計算機科學與技術 50 060214202 薛林 100 060214215 王詩萌 男男女女 福建 計算機科學與技術 吉林 計算機科學與技術 150 060214216 馮子晗 山東 計算機科學與技術 (2)鏈式存儲結構 順序存儲結構要求所有的元素依次存放在一片連續的存儲空間中,而鏈式存儲結構,無需占 用一整塊存儲空間。但為了表示結點之間的關系,需要給每個結點附加指針字段,用于存放后繼 元素的存儲地址。所以鏈式存儲結構通常借助于程序設計語言的指針類型來描述。 假定給前面的“學生基本信息表”中的每個結點附加一個“下一個結點地址”,即后繼指針字 數據結構(C語言版)(第2版 段,用于存放后繼結點的首地址,則可得到如表1.3所示的鏈式存儲結構。從表中可以看出,每 個結點占用兩個連續的存儲單元,一個存放結點的信息,另一個存放后繼結點的首地址。 表1.3 鏈式存儲結構 地址 學號 姓名 性別 籍貫 專業 后繼結點的首地址 0 060214201 楊陽 安徽計算機科學與技術 100 50 060214216 馮子晗 山東計算機科學與技術 100 060214202 薛林 男女男女 福建 計算機科學與技術 150 150 060214215 王詩萌 吉林計算機科學與技術 50 為了更清楚地反映鏈式存儲結構,可采用更直觀的圖示來表示,如“學生基本信息表”的鏈 式存儲結構可用如圖1.5所示的方式表示。 060214201 060214202 060214215 060214216 楊陽 薛林 王詩萌 馮子晗 男 男 女 女 安徽 福建 吉林 山東 計算機科學與技術 計算機科學與技術 計算機科學與技術 計算機科學與技術 圖1.5鏈式存儲結構示意圖 12.3數據類型和抽象數據類型 1.數據類型 數據類型( Data Type)是高級程序設計語言中的一個基本概念,前面提到過順序存儲結構可 以借助程序設計語言的數組類型描述,鏈式存儲結構可以借助指針類型描述,所以數據類型和數 據結構的概念密切相關。 一方面,在程序設計語言中,每一個數據都屬于某種數據類型。類型明顯或隱含地規定了數 據的取值范圍、存儲方式以及允許進行的運算,數據類型是一個值的集合和定義在這個值集上的 組操作的總稱。例如,C語言中的整型變量,其值集為某個區間上的整數(區間大小依賴于不 同的機器),定義在其上的操作為加、減、乘、除和取模等算術運算;而實型變量也有自己的取值 范圍和相應運算,比如取模運算是不能用于實型變量的。程序設計語言允許用戶直接使用的數據 類型由具體語言決定,數據類型反映了程序設計語言的數據描述和處理能力。C語言除了提供整 型、實型、字符型等基本類型數據外,還允許用戶自定義各種類型數據,例如數組、結構體和指 針等。 2.抽象數據類型 抽象就是抽取出實際問題的本質。在計算機中使用二進制數來表示數據,在匯編語言中則可 給出各種數據的十進制表示,它們是二進制數據的抽象,使用者在編程時可以直接使用,不必考 慮實現細節。在高級語言中,則給出更高一級的數據抽象,出現了數據類型,如整型、實型、字 符型等,可以進一步利用這些類型構造出線性表、棧、隊列、樹、圖等復雜的抽象數據類型。 抽象數據類型( Abstract Data Type,ADT)一般指由用戶定義的、表示應用問題的數學模型 6 第1章緒論 以及定義在這個模型上的一組操作的總稱,具體包括三部分:數據對象、數據對象上關系的集合 以及對數據對象的基本操作的集合。 抽象數據類型的定義格式如下: ADT抽象數據類型名{ 數據對象:〈數據對象的定義〉 數據關系:〈數據關系的定義〉 基本操作:〈基本操作的定義 }ADT抽象數據類型名 其中,數據對象和數據關系的定義采用數學符號和自然語言描述,基本操作的定義格式為 基本操作名(參數表) 初始條件:〈初始條件描述〉 操作結果:〈操作結果描述〉 基本操作有兩種參數:賦值參數只為操作提供輸人值;引用參數以“&”打頭,除可提供輸 人值外,還將返回操作結果?!俺跏紬l件”描述了操作執行之前數據結構和參數應滿足的條件,若 初始條件為空,則省略?!安僮鹘Y果”說明了操作正常完成之后,數據結構的變化狀況和應返回的 結果。 13抽象數據類型的表示與實現 運用抽象數據類型描述數據結構,有助于在設計一個軟件系統時,不必首先考慮其中包含的 數據對象,以及操作在不同處理器中的表示和實現細節,而是在構成軟件系統的每個相對獨立的 模塊上定義一組數據和相應的操作,把這些數據的表示和操作細節留在模塊內部解決,在更高的 層次上進行軟件的分析和設計,從而提高軟件的整體性能和利用率。 抽象數據類型的概念與面向對象方法的思想是一致的。抽象數據類型獨立于具體實現,將數 據和操作封裝在一起,使得用戶程序只能通過抽象數據類型定義的某些操作來訪問其中的數據 從而實現了信息隱藏。在C++中,我們可以用類的聲明表示抽象數據類型,用類的實現來實現 抽象數據類型。因此,C++中實現的類相當于數據的存儲結構及其在存儲結構上實現的對數據 的操作。 抽象數據類型和類的概念實際上反映了程序或軟件設計的兩層抽象:抽象數據類型相當于在 概念層(或稱為抽象層)上描述問題,而類相當于在實現層上描述問題。此外,C++中的類只是 個由用戶定義的普通類型,可用它來定義變量(稱為對象或類的實例)。因此,在C++中,最 終是通過操作對象來解決實際問題的,所以我們可將該層次看做是應用層。例如,main程序就可 看做是用戶的應用程序。 由此可以看出,最終表示和實現抽象數據類型,最好用面向對象的方法,比如用C++語言的 類描述比較方便、有效,但本課程大都在大學低年級開設,用C語言的描述方法更符合學生的實 際情況。另外,由于實際問題千變萬化,數據模型和算法也形形色色,因此抽象數據類型的設計 和實現,就不可能像基本數據類型那樣規范和一勞永逸。本書所討論的數據結構及其算法主要是 面向讀者的,故采用介于偽碼和C語言之間的類C語言作為描述工具。這使得數據結構與算法的 數據結構(C語言版)(第2版 描述與討論簡明清晰,不拘泥于C語言的細節,又容易轉換成C或C++程序。 夲書采用的類C語言精選了C語言的一個核心子集,同時做了若干擴充修改,增強了語言的 描述功能,以下對其做簡要說明 (1)預定義常量及類型: //函數結果狀態代碼 #define oK 1 #define error 0 #define OVERFLOW -2 / Status是函數返回值類型,其值是函數結果狀態代碼。 typedef int status; (2)數據結構的表示(存儲結構)用類型定義( typedef)描述;數據元素類型約定為 ElemType, 由用戶在使用該數據類型時自行定義。 (3)基本操作的算法都用如下格式的函數來描述 函數類型函數名(函數參數表 //算法說明 語句序列 }//函數名 當函數返回值為函數結果狀態代碼時,函數定義為 Status類型。為了便于描述算法,除了值 調用方式外,增加了C++語言引用調用的參數傳遞方式。在形參表中,以“&”打頭的參數即為 引用參數。傳遞引用給函數與傳遞指針的效果是一樣的,形參變化實參也發生變化,但引用使用 起來比指針更加方便、高效。 4)內存的動態分配與釋放。 使用new和 delete動態分配和釋放內存空間 分配空間指針變量=new數據類型; 釋放空間 delete指針變量; (5)賦值語句 簡單賦值變量名=表達式; 串聯賦值變量名1=變量名2==變量名n=表達式; 成組賦值(變量名1,,,變量名n)=(表達式1,,表達式n) 結構賦值結構名1=結構名2; 結構名=(值1,值2,.,值n); 條件賦值變量名=條件表達式?表達式T:表達式F; 交換賦值變量名1<-->變量名2; (6)選擇語句: 條件語句1if(表達式)語句 條件語句2if(表達式)語句; else語句 開關語句 switch(表達式) case值1:語句序列1; break; case值2:語句序列2; break; 8

...展開詳情
試讀 127P 數據結構(C語言版)第二版
立即下載 低至0.43元/次 身份認證VIP會員低至7折
一個資源只可評論一次,評論內容不能少于5個字
世上我最好123 這個資源不錯,挺好的!
2020-12-22
回復
ldx19670128 嚴版數據結構, 大家注意,按需求下載。內容不錯的,就是網上其它地方有免費的
2020-02-12
回復
  • GitHub

    綁定GitHub第三方賬戶獲取
關注 私信 TA的資源
上傳資源賺積分,得勛章
最新推薦
數據結構(C語言版)第二版 42積分/C幣 立即下載
1/127
數據結構(C語言版)第二版第1頁
數據結構(C語言版)第二版第2頁
數據結構(C語言版)第二版第3頁
數據結構(C語言版)第二版第4頁
數據結構(C語言版)第二版第5頁
數據結構(C語言版)第二版第6頁
數據結構(C語言版)第二版第7頁
數據結構(C語言版)第二版第8頁
數據結構(C語言版)第二版第9頁
數據結構(C語言版)第二版第10頁
數據結構(C語言版)第二版第11頁
數據結構(C語言版)第二版第12頁
數據結構(C語言版)第二版第13頁
數據結構(C語言版)第二版第14頁
數據結構(C語言版)第二版第15頁
數據結構(C語言版)第二版第16頁
數據結構(C語言版)第二版第17頁
數據結構(C語言版)第二版第18頁
數據結構(C語言版)第二版第19頁
數據結構(C語言版)第二版第20頁

試讀結束, 可繼續閱讀

42積分/C幣 立即下載 >

炫乐彩票