數(shù)據(jù)結構-C語言版課件（全）

1、數(shù)據(jù)結構（C語言版）鄢田云12011級工程方向與應用方向“數(shù)據(jù)結構”課程體系實行A、B班教學A班教學：由鄢田云老師承擔，數(shù)據(jù)結構課程在選課系統(tǒng)中是工程方向。周一1-2節(jié)，在1603教室；周三1-2節(jié)，在1207教室。B班教學：由李莉麗老師承擔，數(shù)據(jù)結構課程在選課系統(tǒng)中是應用方向。周一1-2節(jié)，在1303 教室；周三1-2節(jié)，在1604教室。 僅數(shù)據(jù)結構和本學期后續(xù)的經(jīng)典算法的設計與實現(xiàn)按此原則選課。其余的課程按實際的工程、應用方向選課。區(qū)別：A班更多自由支配時間，完成要求教學內容；B班很多限制支配時間，要額外增加難度。2課時安排數(shù)據(jù)結構總學時： 72（學時） = 56（理論學時）+ 12（上機

2、學時）+4（實驗學時）行課安排時間:第 1 14 周，上機從第4周開始。經(jīng)典算法的設計與實現(xiàn)總學時： 24（學時） = 12（上機學時）+ 12（實驗學時）行課安排時間:第 8 17 周第8、11、12 章的內容為自學內容；目錄中標有 * 的內容不作要求。課程性質：核心必修考試課，4.5+1.5=6學分?？荚嚪绞剑洪]卷考試，平時占30，考試占70。3上機安排時間上機時間安排：應用方向周三下午7-8節(jié)，6308；計工方向周三晚上9-10節(jié)（6:30-8:00）, 6308；時間從第4周開始到期末：包括數(shù)據(jù)結構經(jīng)典算法的設計與實現(xiàn)經(jīng)典算法的設計與實現(xiàn)的實驗部分，需要大家課外花大量時間完成，不全在機

3、房上機。云計算機房6306正在測試中，后面有可能要在云計算機房上機。4成績計算平時成績：30% 考勤+課堂表現(xiàn)+作業(yè)+上機實驗報告+上機考察考試成績：70%要求：上機不能做與該課程無關的內容。5考核資格審查第三條 考核資格審查（成都信息工程學院普通全日制學生學習成績考核辦法，成信院發(fā)2006136號）1.每學期開設的必修、選修、加修課程都必須在期末停課復習前十天或課程教學工作結束前十天，由任課教師逐個審查學生的考核資格。審查結果送學生所屬系，由主管教學的系主任終審，報教務處備案。2.學生的考核資格按下述原則審查： 學生有以下情況之一者，不能參加課程成績考核，該課程的考核成績以零分處理。在確定學

4、籍處理、授予學士學位時，該門課程以考核不及格門次參加統(tǒng)計。（1）全期曠課累計達該課程教學時數(shù)五分之一（含五分之一）以上者；（2）全期缺交該課程任課教師布置作業(yè)三分之一（含三分之一）以上者；或全期所交該課程作業(yè)，雖達到任課教師布置作業(yè)三分之二以上，但所交作業(yè)的準確度、整潔度有二分之一不合格者；（3）全期缺做該課程實習、實驗或缺交實習、實驗報告達三分之一（含三分之一）以上者；或全期參加該課程實習、實驗，所交實習、實驗報告都在三分之二以上，但有二分之一不合格者；（4）未經(jīng)批準或未辦理選課手續(xù)，擅自修讀該門課程者。 3.到課率（出勤）、作業(yè)、實習、實驗等環(huán)節(jié)全部完成并合格，則取得該課程的考核資格。 4

5、.經(jīng)課程承擔系主任終審，未取得某門課程考核資格的學生名單，于考核前一周由系辦公室報教務處并通知學生本人。擅自參加考核者，以違反考場紀律論處。6紀律要求理論課和上機課：兩者無故缺席累積超過5次，平時成績?yōu)? 。無故缺勤或上機時間玩游戲等違紀行為：第1次平時成績扣5分，第2次扣10分，第3次扣15分，第4次扣20分，第5次扣30分，第6次平時成績?yōu)?。7教材與參考書教材：嚴蔚敏，數(shù)據(jù)結構，清華大學出版社參考書：李勤，數(shù)據(jù)結構，中國電力出版社Clifford A. Shaffer，數(shù)據(jù)結構與算法分析，電子工業(yè)出版社 Sartaj Sahni, 數(shù)據(jù)結構、算法與應用, 機械工業(yè)出版社嚴蔚敏，數(shù)據(jù)結構題

6、集，清華大學出版社8算法是計算機科學基礎的重要主題 70年代前，計算機科學基礎的主題沒有被清楚地認識。 70年代，Knuth出版了The Art of Computer Programming(三卷）, 以各種算法研究為主線，確立了算法為計算機科學基礎的重要主題，1974年獲得圖靈獎。 Knuth home page： :/knuth/ 70年代后，算法作為計算機科學的核心推動了計算機科學技術的飛速發(fā)展與牛頓的自然哲學的數(shù)學原理齊名 9計算機科學的體系 解決一個計算問題的過程：可計算否?能行可計算否?算法設計與分析用計算機語言實現(xiàn)算法軟件系統(tǒng)定義 對于一個n元函數(shù)f(x1,.,xn)，如果存在

7、一個機械的實現(xiàn)過程使得對于任意賦值(a1,.,an)，該過程在有限的步驟內產(chǎn)生出f(a1,.,an)，那么就稱f(x1,.,xn)是可計算的（或能行可計算的）。10計算機處理對象的發(fā)展數(shù)值計算問題與非數(shù)值計算問題解決一個具體問題，計算機來實現(xiàn)需要經(jīng)過以下幾個步驟： 具體問題 抽象 數(shù)學模型 設計 算法求解 編寫程序 進行測試、調整至最終解答 程序=數(shù)據(jù)結構+算法11課程重要性簡介是計算機相關專業(yè)考研的重點內容大公司筆試的主要內容 是計算機專業(yè)核心必修課，是其它后續(xù)計算機課程的重要基礎是非計算機專業(yè)的主要選修課12 數(shù)據(jù)結構在學科中的地位 數(shù)據(jù)結構是計算機科學中一門綜合性的專業(yè)基礎課。數(shù)據(jù)結構的

8、研究不僅涉及計算機的硬件的研究范圍，而且和計算機軟件的研究有著更為密切的關系，無論是編譯程序還是操作系統(tǒng)，都涉及數(shù)據(jù)元素在存儲器中的分配問題?？梢哉J為數(shù)據(jù)結構是介于數(shù)學、計算機硬件、計算機軟件三者之間的一門核心課程。數(shù)據(jù)結構 所處的地位 13課程主要內容簡介數(shù)據(jù)的邏輯結構數(shù)據(jù)的存儲結構(順序與鏈式)及其操作(算法)（插入、刪除與遍歷等）線性表、樹和圖查找與排序（屬常用算法總結）算法的時空效率分析法14本課程章節(jié)主要內容 第一章：緒論 第二章：線性表 第三章：棧和隊列 第四章：串 第五章：數(shù)組和廣義表 第六章：樹和二叉樹 第七章：圖 第九章：查找 第十章：內部排序15第一章 緒 論 數(shù)據(jù)結構的引

9、論例1 圖書館的書目檢索系統(tǒng)自動化問題 線形數(shù)據(jù)結構，1：1的關系 在書目自動檢索系統(tǒng)中可以建立一張按登錄順序號排列的書目文件和三張分別按書名、作者名和分類號順序排列的索引表，如下所示： 什么是數(shù)據(jù)結構001002003004高等數(shù)學理論力學高等數(shù)學線形代數(shù)樊映川羅遠祥華羅庚欒汝書S01L01S01S02書目卡片線性表16高等數(shù)學理論力學線形代數(shù)001,003, 002, 004, LS002,001, 003特點：計算機按某個特定的要求進行查詢.處理對象之間存在一種簡單的線形關系,這類模型可以稱為簡單的線形數(shù)據(jù)結構.按書名排列樊映川華羅庚欒汝書001,003,004,按作者排列按索引號排列1

10、7例2 計算機和人的對弈問題“樹”形數(shù)據(jù)結構，1：N的關系 對奕的過程是在一定的規(guī)則下隨機進行的,因此,計算機必須對對弈過程之中可能發(fā)生的情況以及相應的對策都考慮周全.這個關系不是線形的,從一個棋盤可以派生出幾個格局,如下圖: “樹根”是對奕開始之前的棋盤格局,而所有的“葉子”是可能出現(xiàn)的結局,對奕的過程就是從樹根沿樹叉到達某個葉子的過程. *(a) 棋盤格式示例(b)井字棋對弈樹的局部*樹18例3 多叉路口交通燈的管理問題（ “圖”形數(shù)據(jù)結構，M：N的關系 可以把這類交通,道路的問題當作一種給力的“圖”的結構：一個頂點表示一條通道,而通道之間的矛盾的關系以兩個頂點之間的連線表示.如下圖所示:

11、AEDCB(a) 五叉路口ABACADBABCBDDADBDCEAEBECED程序=數(shù)據(jù)結構+算法圖19結論：綜合上面三個例子,描述這類非數(shù)值計算性問題的數(shù)學模型不再是數(shù)學方程,而是諸如表、樹和圖之類的數(shù)據(jù)結構.數(shù)據(jù)結構: 數(shù)據(jù)結構是一門非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科.數(shù)據(jù)結構的發(fā)展簡史（p3） 1968年美國唐歐克努特（ ）教授所著的計算機程序設計技巧第一卷基本算法中較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結構和存儲結構及其操作。不知道此人的程序員是不可原諒的 20 數(shù)據(jù)（Data) 客觀事物的符號表示，能輸入到計算機中并被計算機中程序處理的符號的總稱。如文字、

12、聲音和圖像等。 數(shù)據(jù)元素 (Data element) 數(shù)據(jù)的基本單位，可由數(shù)據(jù)項組成。例如書目信息和棋盤格局。 數(shù)據(jù)項(data item)是數(shù)據(jù)不可分割的最小單位， 也稱域(field)。數(shù)據(jù)對象 (Data Object) 性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。例如整數(shù)。 基本概念21一個數(shù)據(jù)項一個數(shù)據(jù)元素學號姓名語文數(shù)學C語言6201001張三8554926201002李四9284646201003王五8774736201004.整個表的記錄是學生成績數(shù)據(jù)22數(shù)據(jù)類型 是一個值的集合和定義在這個值集上一組操作總稱。例如：int數(shù)據(jù)類型，取值范圍為3276832767，操作運算有加、減

13、、乘、除、取模、乘方等。 數(shù)據(jù)類型分類：(按值的不同特性進行分類)原子類型 ：每一個對象僅由單值構成的類型； 值不可以分解；如：整型、字符型結構類型 ：每一個對象可由若干成分按某種 結構構成的類型。 值由若干成分按某種結構組成。 又分為固定聚合類型和可變聚合類型。 如：復數(shù)、數(shù)組數(shù)據(jù)類型 (Data Type)或抽象數(shù)據(jù)類型（ADT）23抽象數(shù)據(jù)類型（ADT）作用：抽象數(shù)據(jù)類型可以使我們更容易描述實際問題。例：用線性表描述學生成績表，用樹或圖描述遺傳關系。定義：一個數(shù)學模型以及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型與數(shù)據(jù)類型實質上是同一個概念。好處：可提高軟件的復用程度。 使用它的人可以只關

14、心它的邏輯特征，不需要了解它的存儲方式。定義它的人同樣不必要關心它如何存儲。24抽象數(shù)據(jù)類型表示法：三元組表示：（D，S，P） 其中D是數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。抽象數(shù)據(jù)類型的定義格式：ADT 抽象數(shù)據(jù)類型名數(shù)據(jù)對象：數(shù)據(jù)關系：基本操作：ADT 抽象數(shù)據(jù)類型名見P9 例1-6 抽象數(shù)據(jù)類型三元組的定義。25抽象數(shù)據(jù)類型的表示與實現(xiàn) 抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。注 1 ：它有些類似C語言中的結構（55）類型，但增加了相關的服務。注 2 ：教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具。好處：不拘泥于C語言細節(jié)，又能很

15、容易轉換成C或C+語言程序。26抽象數(shù)據(jù)類型的語言的描述-P10預定義常量和類型 /函數(shù)結果狀態(tài)代碼 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 # define INFEASIBLE -1 # define OVERFLOW -2 typedef int Status; / Status是函數(shù)的類型，其值是函數(shù)結果狀態(tài)代碼 例如：P23 Status InitList_Sq(SqList &L) return OK;數(shù)據(jù)結構的表示用類型定義（typedef）描述，數(shù)據(jù)元素類型約定為ElemType，可以是C語

16、言中任何數(shù)據(jù)類型。27基本操作的算法用以下形式函數(shù)來描述函數(shù)類型函數(shù)名（函數(shù)參數(shù)表） / 算法說明 語句序列 /函數(shù)名 C語言中操作的描述（見P10-11） P12 例17賦值語句選擇語句循環(huán)語句結束語句輸入和輸出語句注釋基本函數(shù)邏輯運算約定28數(shù)據(jù)結構 (Data Structure) 相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的相互關系稱為結構。有下列四種基本結構： （1）集合 （2）線形結構 （3）樹形結構 （4）圖狀結構(網(wǎng)狀結構） 集合線性樹圖29數(shù)據(jù)結構DS的形式定義： 數(shù)據(jù)結構是一個二元組： DS（D，S） 其中： D是數(shù)據(jù)元素的有限集 S是數(shù)據(jù)元素之間關系的有

17、限集 對于S中任意二元關系（x，yD），稱x為第一元素（或y的前驅），y為第二元素（或x的后繼）。 （ 注：DS Data Structure）30 數(shù)據(jù)元素之間的相互關系數(shù)據(jù)元素之間的相互關系包括三個方面：數(shù)據(jù)的邏輯結構、存儲結構、操作集合。數(shù)據(jù)元素之間的邏輯關系，稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)的邏輯結構分兩大類： 線性結構（線性表、棧、隊列、字符串、數(shù)組、廣義表）； 非線性結構（樹、二叉樹、圖）。 數(shù)據(jù)結構在計算機中的表示，稱為數(shù)據(jù)的物理結構（存儲結構）。位 (bit，計算機中表示信息的最小單位)元素或結點 (一個數(shù)據(jù)元素在計算機中的映象，如單字符數(shù)據(jù)元素由8位二進制數(shù)表示)數(shù)據(jù)域（數(shù)據(jù)項對應的

18、子位串，一個數(shù)據(jù)元素可以有若干數(shù)據(jù)項）31 數(shù)據(jù)元素之間的關系在計算機中的表示：有順序映像和非順序映像兩種方法，由此得到兩種存儲結構：順序存儲結構：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。 鏈式存儲結構：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)的邏輯結構與存儲結構密切相關算法設計 邏輯結構算法實現(xiàn) 存儲結構邏輯結構是面向用戶的、是抽象的；存儲結構是面向計算機的、面向實現(xiàn)的。32元素n元素i元素2元素1L0L0+m L0+(i-1)*m L0+(n-1)*m存儲地址存儲內容Loc(元素i)=L0+(i-1)*m順序存儲33 鏈式存儲 1536元素21400元素

19、11346元素3 元素4h1345h34 數(shù)據(jù)操作描述數(shù)據(jù)的基本操作：插入：在數(shù)據(jù)結構的指定位置添加新的數(shù)據(jù)元素。刪除：去掉數(shù)據(jù)結構中某個指定的數(shù)據(jù)元素。更新：改變數(shù)據(jù)結構中某個數(shù)據(jù)元素的值。查找：在數(shù)據(jù)結構中尋找某個滿足特定要求的數(shù)據(jù)元素。排序：重新安排數(shù)據(jù)元素的邏輯順序關系，使其值按從小到大或從大到小的順序排列。從操作的特性分，所有的操作可以歸結為兩類：加工型操作操作改變了（操作之前的）結構的值。引用型操作不改變值，只是查詢或求得結構的值。 35 算法：是對特定問題求解步驟的一種描述，是指令的有限序列。 什么是算法算法的五個特征：1、輸入：可有0個或多個輸入；2、輸出：至少有1個或多個輸出

20、；3、確定性：算法中每一步驟必須有確切含義，無二義性；4、有窮性：能夠在有限步驟內結束，不能形成無限循環(huán)；5、可行性：算法可以在紙上作業(yè)方式跟蹤其結果。算法設計的兩個目標易讀、易編碼和調試（軟件工程）充分利用計算機資源（算法和數(shù)據(jù)結構）36算法設計的要求：1、正確性：當輸入數(shù)據(jù)合法時，能夠得到滿足要求的結果； 程序不含語法錯誤； 程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； 程序對于精心選擇的典型、苛刻的輸入數(shù)據(jù)能夠得出滿足要求的結果； 程序對于一切合法的輸入數(shù)據(jù)都能夠得出滿足要求的結果。2、可讀性：算法簡單明了，便于別人對算法的理解和對程序的維護；3、健壯性：當輸入非法時也能作出反應；4、效

21、率與低存儲量要求 低存儲規(guī)模：存儲規(guī)模是指算法在執(zhí)行過程中所需的最大存儲空間，也稱為算法的空間復雜性； 高效率：執(zhí)行時間短的算法其效率就高，算法的執(zhí)行時間也稱為算法的時間復雜性。37算法與程序的區(qū)別： 計算機科學家 N.沃思 給出一個著名公式： 數(shù)據(jù)結構算法程序1、程序是在特定計算機上執(zhí)行的算法，是具體的；而算法與具體計算機無關，是抽象的；2、程序可以不滿足有限性要求；而算法必須滿足有限性。 如：操作系統(tǒng)程序，除非關機，否則一直在等待循環(huán)中等待下一個工作進入系統(tǒng)，所以只要系統(tǒng)是在運作下，則操作系統(tǒng)程序就不會終止。解決一個具體問題，計算機來實現(xiàn)需要經(jīng)過以下幾個步驟：具體問題 抽象數(shù)學模型 設計算

22、法求解 編寫程序，并進行測試、調整至最終解答38 算法效率需通過該算法編制的程序在計算機上運行所消耗的時間多少以及所需輔助空間的大小來度量。 算法效率的度量算法效率的衡量指標：時間復雜度和空間復雜度。時間復雜度：從算法中選取一個對于所研究的問題來說是基本操作的原操作（指固有數(shù)據(jù)類型的操作），以該基本操作重復執(zhí)行的次數(shù)作為算法的時間量度。 計作：T（n）= O（f（n）。它表示隨著n的增大，算法執(zhí)行時間的增長率和 f ( n ) 的增長率相同。39空間復雜度： 一個上機執(zhí)行的程序除了需要存儲空間來積存本身所用指令，常數(shù)，變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些實現(xiàn)計算所需信

23、息的輔助空間。該輔助空間的大小及反映了該算法的空間復雜性。計作：S（n）= O（f（n）。頻度：某語句重復執(zhí)行的次數(shù)。40程序段一： +x; s=0； 該程序中“+x”是基本操作語句，其頻度為1，其時間復雜度為O(1)，為常量階。例：求下面程序的時間復雜度。41程序段二： for(i=1;i=n;+i) +x; s+=x; 該程序中“+x”是基本操作語句，其頻度為n，其時間復雜度為O(n)，為線性階。42程序段三： for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x; 該程序中“+x”是基本操作語句，其頻度為n2，其時間復雜度為O(n2)，為平方階。43程序段四：

24、 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x; 語句“+x”的執(zhí)行次數(shù)關于n的增長率為n2,它是語句頻度表達式(n-1)(n-2)/2中增長最快的項,時間復雜度為O(n2) 。i=2，執(zhí)行0次；i=3，執(zhí)行1次；i=4，執(zhí)行2次；i=n，執(zhí)行n-2次；總共執(zhí)行次數(shù)123(n-2)=(n-2)(n-2+1)/2=(n-2)(n-1)/2=(n2 -3n+2)/244常見的幾種時間復雜度數(shù)量級一般情況下，隨著n的增大，T(n)增長較慢的算法為最優(yōu)的算法。應該選擇對數(shù)階或多項式階的算法，避免使用指數(shù)階的算法。45衡量兩個算法的好壞，應當是在n足夠大的情形下

25、，對算法的工作量進行比較，即對算法進行漸近性態(tài)分析。n較小時難辨優(yōu)劣46運行時間估計例：假設CPU每秒處理106 個指令，對于輸入規(guī)模 n=108 的問題，時間代價為T(n)=2n2的算法要運行多長時間？操作次數(shù)為： T(n)=T(108)=2(108)2=21016運行時間為： 21016/106 = 21010秒每天有86,400秒，因此需要231,480 天(634年)47例：假設CPU每秒處理106 個指令，對于輸入規(guī)模為n=108的問題，時間代價為T(n)=nlogn的算法要運行多長時間？操作次數(shù)為： T(n)=T(108)= 108 log108=2.66109運行時間為： 2.6

26、6109/106 = 2.66103秒，即分鐘48規(guī)定時間內能解決的問題規(guī)模假設CPU每秒處理106個指令，則每小時能夠解決問題的最大規(guī)模為多少？T(n)/1063600對T(n) = 2n2 而言，有： 即 2n2 3600 106 n 42 , 426對T(n) = nlogn而言，有： 即 nlogn 3600 106 n 133 , 000 , 00049算法的階設非負函數(shù)f(n)和g(n)，nN，如果存在正常數(shù)c和正整數(shù)n0 ，使得當nn0 時，有f(n)cg(n)，則稱f(n)的階小于或等于g(n)的階；記為 f(n)O(g(n)，讀作f(n)是 g(n)的大O。一般采用求極限的方

27、法，來比較兩個算法時間復雜性函數(shù)的階： 當n時，lim f(n)/g(n)=c (1)當c0，f(n)比g(n)低階，記為f(n) O(g(n)； (2)當c0，f(n)和g(n)同階，記為f(n)(g(n)； (3)當c，f(n)比g(n)高階，記為f(n)(g(n)；50算法的階51算法的階例如：2n-5 O(n2)，因為當n時，lim (2n -5)/n2 = 2/n - 5/n2 0-0=0；低階例如：5n2 -3n=(n2)，因為當n時，lim (5n2 -3n)/n2 = 5 - 3/n5-0=5；同階例如： n2 +5n=(n)，因為當n時，lim (n2 +5n)/n= n +

28、5 ；高階注意：在求時間復雜度時，不需要嚴格區(qū)分同階的情況下，把低階或同階的f和g統(tǒng)一寫成 f O(g)52本章重點1.數(shù)據(jù)結構的有關基本概念2.數(shù)據(jù)結構的類型（邏輯結構）和存儲方式（物理結構）3.算法及算法分析（算法評價）53作業(yè)1課件密碼：y1t2y3 54第二章 線性表線性表的定義線性表的順序表示線性表的鏈式表示一元多項式的運算55 線性表的基本概念線性表：是由一組數(shù)據(jù)元素組成，線性表或者是一個空表，或者 可以寫成a1,a2, ai, , an，其中ai是取自某個集合S 的元素。 當1in時，數(shù)據(jù)元素ai-1稱為數(shù)據(jù)元素ai的直 接前趨，而稱ai+1為ai的直接后繼。 若一個數(shù)據(jù)元素由若

29、干個數(shù)據(jù)項組成，則該數(shù)據(jù)元素又稱為記錄，含有大量記錄的線性表又稱為文件。 例子參見： P18 圖學生健康情況登記表 線性表的定義56基本術語直接前驅： a i - 1 ，針對 a i 直接后繼： a i + 1 ，針對 a i 線性表的長度：是指線性表中數(shù)據(jù)元素的個數(shù)，n = 0 時為空表。位序：下標i是數(shù)據(jù)元素ai 在線性表中的位序。57 線性結構的特點1、數(shù)據(jù)元素的數(shù)據(jù)類型一致。2、數(shù)據(jù)元素之間的相對位置呈線性關系。3、存在唯一的一個被稱做“第一個”和“最后一個”的數(shù)據(jù)元素。4、除第一個和最后一個外，集合中每個數(shù)據(jù)元素均只有一個前驅和一個后繼。58線性表抽象數(shù)據(jù)類型的定義(邏輯結構)ADT

30、 List 數(shù)據(jù)對象:D=ai | ai ElemSet , i = 1,2,.,n, n 0 數(shù)據(jù)關系:R1= |ai-1, ai D, i = 2,3,.,n 基本操作：/& 符號說明函數(shù)參數(shù)是引用型 InitList(&L) ListLength(L) DestroyList(&L) GetElem(L , i , &e) ClearList(&L) LocateElem(L , e ) ListEmpty(L) PriorElem(L , cur_e , &pre_e) ListInsert(&L , i , e) ListDelete(&L , i , &e) ADT List 59

31、利用ADT中的基本運算，可進行一些更復雜的操作，如線性表的合并、拆分等。例2-1 用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)求新集合A = AB。算法如下：void union(List &La，List Lb) /在La中加入在Lb但不在La的元素 La_len = ListLength(La); Lb_len = ListLength(Lb); for(i = 1; i = Lb_len; i+) /掃描Lb中所有元素 GetElem(Lb，i，&e); /取Lb中第i個元素置于e if(!LocateElem(La，e，equal) /若在La中找不到e, ListInsert(L

32、a，+La_len，e); /則將e添加到La /end for /union60例2-2 巳知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。算法如下：void MergeList(List La，List Lb，List &Lc) /保序歸并：歸并非遞減序列La和Lb為非遞減序列Lc InitList(Lc); i = j = k = 1; /i,j,k為La,Lb,Lc的元素指針 La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_l

33、en) & (j = Lb_len) /只要i,j均指向表內便繼續(xù) GetElem(La，i，&ai); /取La中第i個元素置于ai GetElem(Lb，j，&bj); /取Lb中第j個元素置于bj if (ai = bj) /若ai小， ListInsert(Lc，k+，ai); /ai置于Lc第k位,k后移 i+; /i指針后移(j指針不動) else /否則(bj小), ListInsert(Lc，k+，bj); /bj置于Lc第k位,k后移 j+; /j指針后移(i指針不動) /end if /end while61 /上個循環(huán)結束后，La和Lb一定有一個表的元素被 /用完，而另一

34、個表的元素若未用完，處理之： while(i = La_len) /若La未用完，則將剩余元素依次加入Lc GetElem(La，i+，&ai); /取La中第i個元素置于ai,i后移 ListInsert(Lc，k+，ai); /ai置于Lc第k位,k后移 /end while while(j = Lb_len) /若Lb未用完，則將剩余元素依次加入Lc GetElem(Lb，j+，&bj); /取Lb中第j個元素置于bj,j后移 ListInsert(Lc，k+，bj); /bj置于Lc第k位,k后移 /end while/MergeList62線性表的存儲結構順序存儲的線性表，叫順序表鏈

35、式存儲的線性表，叫鏈表 63線性表的順序表示和實現(xiàn)順序表的概念用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。順序表的特點：邏輯關系上相鄰的兩個元素在物理位置上也相鄰。順序表是隨機存取的存儲結構： 可以隨機存?。ㄋ钑r間相同）表中任一元素，因為它的存儲位置可用一個簡單、直觀的公式（位序的線性函數(shù)）來表示。 順序分配的存儲結構采用向量結構：設線性表的長度為N，建立一向量V，用Vi表示第i個分量，第i個分量是線性表第i個元素ai在計算機存儲中的映像，即Vi = ai 。64存儲地址內存狀態(tài)元素序號空閑aaaa12in: :bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in

36、線性表的順序存儲結構示意圖 若線性表中的第一個存儲元素的地址為LOC(a1)，每個元素占用L個存儲單元，則表的第i個元素的存儲地址（內存地址）為： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai)=LOC(ai-1)+L若每個元素僅占用1個存儲單元，則表的第i個元素的存儲地址為：LOC(ai)=LOC(a1)+(i-1)存儲密度d：d=數(shù)據(jù)元素的值所需的存儲量/該數(shù)據(jù)元素所需的存儲總量在順序分配的存儲結構中，所有的存儲單元空間全部被數(shù)據(jù)元素有效占用，因此，順序分配結構的存儲密度d=1。6566注意： 1）數(shù)據(jù)元素ai 的存儲位置（內存地址）不同于位序 i ； 2）Loc(ai)是

37、ai在內存中的第一個字節(jié)的地址。 例如： 整型線性表存儲在內存中的地址是C000，則表中的第7個元素的存儲地址是多少？答：C000+2*6=C00C67順序存儲結構/定義順序表類型SqList typedef int ElemType ; typedef Elemtype ET;typedef struct ElemType *elem ; /存儲空間基址(順序表的起址) int length ; /實際元素個數(shù) int listsize ; /當前存儲容量 /當前分配的存儲容量(以sizeof(ElemType)為單位)SqList ; / SqList 是順序表的類型名。68順序表的基本操

38、作算法 /構造一個空的線性表 L#define List_Init_Size 100#define ListIncrement 10Status InitList_Sq( SqList &L) = (ET *) malloc(List_Init_Size*sizeof(ET); =NULL) exit(OVERFLOW); /*存儲分配失敗*/ =0; /* 空表的長度 */ =List_Init_Size; /* 初始存儲容量 */ return OK; / InitList_Sq69順序表的插入操作舉例：例：設有長為n的線性表a1,a2, , an, 在第i位置插入新數(shù)據(jù)元素e。 順序存儲

39、結構的插入操作ea1a2a3ai-1aian:123i-1ini+1:a1a2a3ai-1an-1:123i-1ini+1n+1:aiean順序表的插入操作算法： 1、如果1=i=n+1，則插入數(shù)據(jù)元素e。反之，則退出。 2、從第n到第i個存儲單元的數(shù)據(jù)元素，依次后移，騰出空位i：第n個元素送給第n+1個存儲單元，將第n-1個元素送到第n個存儲單元，直到將第i個元素送給第i+1個存儲單元。 3、在空位i處插入元素e，線性表長度加1。 4、返回。70順序表的插入操作：在順序表L中第i個位置上插入一個新的元素e。形式參數(shù)為：&L ,i , e ；算法步驟如下：對輸入?yún)?shù)的安全性檢查:插入位置i應落

40、在（表長1）范圍內，即：1i L.length+1存儲空間的處理：若原表的存儲空間已滿，應追加存儲空間的分配；數(shù)據(jù)塊的搬移：表中從i到位置上的所有元素往后移動一個位置；(移動 個元素)在第i個位置上存儲新的元素e,表長增;注意：邏輯位置（序號）i 對應的存儲下標是i-1。n-i+171重新分配動態(tài)存儲空間的函數(shù)realloc(原動態(tài)區(qū)首址，字節(jié)數(shù))原型： extern void *realloc(void *mem_address, unsigned int newsize); 功能：改變mem_address所指內存區(qū)域的大小為newsize長度。 申請新的動態(tài)存儲空間(成功或失敗);將原動

41、態(tài)區(qū)的數(shù)據(jù)拷貝到新動態(tài)區(qū);釋放原動態(tài)存儲區(qū);返回新存儲區(qū)首地址（無類型）。用途：當原動態(tài)區(qū)不夠用時，追加動態(tài)存儲區(qū)；說明： 如果重新分配成功則返回指向被分配內存的指針，否則返回空指針NULL。當內存不再使用時，應使用free()函數(shù)將內存塊釋放。 注：若用C語言的數(shù)組實現(xiàn)順序表，由于數(shù)組下標從“0”開始，因此屬于SqList類型的表L的第i個元素是L.elemi-1而不是L.elemi。72 順序表插入操作算法描述之一Status ListInsert_Sq (SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /若位置i非法 i

42、f (L.length = ) /若表容量不夠則擴展 p=(ET*), (L.listsize+ListIncrement)*sizeof(ET); if (p= =NULL) exit(OVERFLOW); /若未分配成功，則終止程序 =p; /分配成功，新的表起址 += ListIncrement; /新容量 /追加順序表的存儲空間 for ( j=L.length ; j=i ; -j ) /用數(shù)組實現(xiàn) L.elemj=L.elemj-1; /向后搬移數(shù)據(jù)塊 L.elemi-1=e ; /插入元素e +L.length ; /表長增 return OK; / ListInsert_Sq7

43、3順序表插入操作算法描述之二Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; if (L.length = ) p=(ET*), (L.listsize+ListIncrement)*sizeof(ET); if (p= =NULL) exit(OVERFLOW); =p; +=ListIncrement; q=&(L.elemi-1); / q=L.elem+(i-1) 插入位置 for (p=&(L.elemL.length-1); p=q; -p) /用指針實現(xiàn) *(p+1)=*p

44、; /向后搬移數(shù)據(jù)塊 *q=e ; +L.length ; return OK; /ListInsert_Sq74插入操作的算法性能分析空間復雜度：O( 1 )時間復雜度：O(n) , 其中基本操作是數(shù)據(jù)移動:最壞的情況下(在第一個位置上插入元素)，需要移動n個元素;最好的情況是不移動元素;平均情況下（等概率），需移動表中多少個元素？ 75平均情況下（等概率），需移動表中多少個元素？插入操作算法的時間復雜性： 1、假設在每個位置插入數(shù)據(jù)元素的概率相等，即概率為1/(n+1)。 2、基本操作為移動數(shù)據(jù)元素。 3、平均移動次數(shù)為 4、所以，插入操作算法的時間復雜性為O(n)。76刪除操作：例：設有

45、長為n的線性表a1,a2, , an, 刪除ai，并把它送入某單元e。 eaia1a2a3ai-1aian:123i-1in-1i+1n:a1a2a3ai-1an:123i-1in-1i+1n:ai+1順序存儲結構的刪除操作順序存儲結構的刪除操作算法： 1、如果1=i=n，則將第i個元素送給e。反之，則退出。 2、從第i個存儲單元開始，依次將第i+1個元素送給第i個存儲單元，將第i+2個元素送到第i+1個存儲單元，直到將第n個元素送給第n-1個存儲單元。 3、線性表長度減1。 4、返回。77順序表的刪除操作：在線性表L中刪除ai，并把它送入某單元e形式參數(shù)為：&L , i , &e ；算法步驟

46、如下：對輸入?yún)?shù)的安全性檢查: 刪除位置 i 應落在表長范圍內，即：1 i L.length取出元素值賦給e：數(shù)據(jù)塊的搬移：將表中從i+1到L.length位置上的所有元素往前移動一個位置；表長減：-L.length;78刪除算法 /在線性表L中刪除ai，并把它送入某單元eStatus ListDelete_Sq (SqList &L , int i , ET &e) if(iL.length) return ERROR; e=L.elemi-1; /被刪除元素送給e for( j=i; j; j+) L.elemj-1=L.elemj; -; return OK; / ListDelete_

47、Sq問：基本操作是什么？時間復雜度是多少？79算法分析：基本操作是什么？ 時間復雜度是多少？刪除操作算法的時間復雜性： 1、假設刪除每個數(shù)據(jù)元素的概率相等，即概率為1/n。 2、基本操作為移動數(shù)據(jù)元素。 3、平均移動次數(shù)為 4、所以，刪除操作算法的時間復雜性為O(n)。80提問順序表中求表長的時間復雜度為（ ）順序表中取第i元素的時間復雜度為（ ）順序表中刪除數(shù)據(jù)元素的時間復雜度為（ ）順序表中插入數(shù)據(jù)元素的時間復雜度為（ ） A) O(n) B) O(1) C) O(logn) D) O(n2)81算法 /* 定位：在順序表L中查找首個與給定值e滿足比較關系compare()的元素并返回其位

48、序，若未找到則返回0 算法步驟： 1: 依次查訪第1至n個元素 2: 返回結果 */int LocateElem_Sq (SqList *L, ElemType e, int (*compare)(ElemType, ElemType) ElemType *p; int i; p = ; /p指向首元素 for (i = 1; i = ; i+) if (compare(*p+, e) /成功找到e元素，退出for循環(huán) break; /end for if (i = ) /成功找到e元素，返回i return i; else /沒找到e元素，返回0 return 0;/LocateElem_S

49、q82/* 算法 順序表保序歸并 */ void MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc) /保序歸并：歸并非遞減順序表La和Lb為非遞減順序表Lc ElemType *pa, *pb, *pc, *pa_last, *pb_last; pa = ; /a表當前指針初始為指向首元素 pb = ; /b表當前指針初始為指向首元素 pa_last = + - 1; /a表尾指針 pb_last = + - 1; /b表尾指針 = = + ; /c表容量和表長 = (ElemType *)*sizeof(ElemType); pc = ; /c

50、表當前指針初始為指向首元素 if (pc= =NULL) exit(OVERFLOW); /存儲分配失敗83/歸并：while(pa = pa_last) & (pb = pb_last) /只要pa, pb均指向表內便繼續(xù) if (*pa = *pb) /若a表當前元素小， *pc = *pa; /則置其于c表當前位置， pc+; pa+; /a和c指針后移(b指針不動)； else /否則(b表當前元素小), *pc = *pb; /則置b表當前元素于c表當前位置， pc+; pb+; /b和c指針后移(a指針不動)； /end if /end while 84 /上個循環(huán)結束后，La和L

51、b一定有一個表的元素被用完，而另一個表的元素可能未用完，處理之： while (pa = pa_last) /若La未用完，則將剩余元素依次加入Lc *pc = *pa; pc+; pa+; /end while while (pb next; while (p) printf(%c - , p-data); p = p-next; printf(NULLn);頭abcd Lppppp93創(chuàng)建一個有N個節(jié)點的單鏈表void CreatList( LinkList *L, int n) int i; LinkList p, q; ET c; p=(LinkList)malloc(sizeof(L

52、Node); p-next=NULL; /生成頭結點 *L = q = p; printf(Please input the data : ); for (i=n; i0; i-) /添加結點 p=(LinkList)malloc(sizeof(LNode); c = getche(); printf(nn); p-data = c; p-next =NULL; q-next = p; q=p; 頭dcba Lpq頭Lqp頭d Lpqqd p94初始化一個單鏈表void Init(LinkList *L) int n; printf(Please input the number of the

53、 node : ); scanf(%d, &n); CreatList(L, n);95單鏈表的插入操作在單鏈表L中的第 i 個結點之前的插入操作步驟如下：( i 0 )尋找第 i-1個結點； /O(n)測試已知量的合法性； /O(1)申請一個結點存儲空間，并給其數(shù)據(jù)域賦值； / O(1)新結點插入鏈表中。 /O(1)該算法的時間復雜度是：O(n)96單鏈表的插入操作算法Status ListInsert(LinkList *L, int i, ET e) int j=0; LinkList p, s; p=L; while ( p & jnext; +j; if ( !p | ji-1 )

54、return ERROR; s=(LinkList) malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK;97接收插入數(shù)據(jù)，調用插入操作Status Insert(LinkList L) int i, flag; ET data; printf(Please input the position : ); scanf(%d, &i); printf(Please input the data : ); data = getche(); flag = ListInsert(L, i, data); return f

55、lag;98單鏈表的刪除操作：刪除第i個結點步驟若頭指針為空，則退出；否則執(zhí)行下面的操作。找到要刪除結點的直接前驅，將該結點的指針域指向它的直接后繼。若不能找到，則返回。釋放該結點所占用的內存空間。 BATCATHATWATLq第i個結點p BATHATWATLp99單鏈表的刪除操作算法Status ListDelete (LinkList *L, int i, ET *e) /刪除第i個結點 LinkList p, q; int j=0; p=L; while (p & jnext; +j; if ( !(p-next) | (ji-1) ) return ERROR; /刪除位置不對 q=

56、p-next; /刪除q結點，即刪除p的下一個結點i p-next=q-next; *e=q-data; free(q); /釋放刪除的結點q return OK; 100從單鏈表L中，讀取第i個元素的值賦給參數(shù)eStatus GetElem (LinkList L, int i, ET *e) int j=1; LinkList p; p=L-next; while (p & jnext; +j; if( !p | ji) return ERROR; *e=p-data; return OK; 時間復雜度為：O(n) 問題：在順序表中，GetElem_Sq時間復雜度是什么？O(1)101將兩

57、個有序單鏈表合并為一個void MergeList(LinkList L1, LinkList L2, LinkList L3) LinkList pa, pb, pc; pa = L1-next; /L1和L2含頭結點(第0個結點)， pb = L2-next; /pa和pb分別指向頭結點的下一個結點(第1個結點) pc = L3; while (pa & pb) if (pa-data data) /pc-next = pa; 意味著pc也含頭結點 pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = p

58、b-next; pc-next = pa? pa: pb; /插入剩余部分 L1-next=NULL; L2-next=NULL; /L1和L2只保留頭結點102功能控制函數(shù)void MenuSelect (LinkList La, LinkList Lb) int select, done=1; LinkList Lc; while (done) MenuList( ); printf(input the operating code : ); scanf(%d, &select); switch(select) case 1: Insert(La);break; case 2: Inser

59、t(Lb);break; case 3: Delete(La);break; case 4: Delete(Lb);break; case 5: Union(La, Lb);break; case 6: CreatList(&Lc, 0);MergeList(La, Lb, Lc); printf(LC: );printlk(Lc); break; case 7: printf(LA: );printlk(La); printf(LB: ); printlk(Lb); break; case 8: done=0;break; default: printf( ERRORn); 103主函數(shù)ma

60、in( ) LinkList La, Lb; printf(LA ); Init(&La) ; printlk(La); printf(LB ); Init(&Lb) ; printlk(Lb); MenuSelect(La, Lb);104構造一個空的單鏈表, 算法描述：Status InitList_L (LinkList *L) / L是雙指針 *L=( LinkList ) malloc ( sizeof ( Lnode ) ); if ( *L=NULL) exit (OVERFLOW); (*L) next=NULL; (*L) data=0; return OK ; 0NULLL