數(shù)據(jù)結(jié)構與算法第一張清華大學出版社趙玉蘭

劉詠梅cslym@內(nèi)蒙古大學計算機學院315數(shù)據(jù)結(jié)構與算法

DATASTRUCTURE

ANDARITHMETIC數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第1頁!課程介紹課程性質(zhì)計算機專業(yè)的課程分為公共基礎課專業(yè)基礎課專業(yè)方向課專業(yè)選修課屬于專業(yè)基礎課考研的必考科目計算機科學與技術學科聯(lián)考專業(yè)基礎綜合共150分，其中《數(shù)據(jù)結(jié)構》占45分數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第2頁!課程介紹在教學計劃中的地位：核心課程前導課程高等數(shù)學離散數(shù)學程序設計語言后續(xù)課程操作系統(tǒng)編譯數(shù)據(jù)庫數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第3頁!課程介紹教學內(nèi)容第3單元常用數(shù)據(jù)處理技術數(shù)據(jù)結(jié)構的基本概念算法的基本概念第1單元基本概念線性表樹和二叉樹圖特殊線性表廣義線性表第2單元基本數(shù)據(jù)結(jié)構排序技術索引技術查找技術集合數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第4頁!課程介紹成績組成總成績＝平時成績×30％＋期末考試成績×70％平時成績包括作業(yè)成績和上機成績數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第5頁!第1章概述1.1數(shù)據(jù)結(jié)構的發(fā)展1.2數(shù)據(jù)結(jié)構1.3數(shù)據(jù)的邏輯結(jié)構1.4抽象數(shù)據(jù)類型1.5數(shù)據(jù)的存儲結(jié)構1.6算法與算法分析1.7總結(jié)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第6頁!1.1數(shù)據(jù)結(jié)構的發(fā)展程序設計的發(fā)展階段無結(jié)構階段應用領域：科學計算處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)數(shù)據(jù)之間的關系：數(shù)學方程或數(shù)學模型例方程組求解定積分在這一階段，數(shù)據(jù)結(jié)構還未形成一門系統(tǒng)的學科，而是零星地分布在程序設計、圖論、集合、代數(shù)、操作系統(tǒng)和編譯原理等課程中。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第7頁!1.1數(shù)據(jù)結(jié)構的發(fā)展面向?qū)ο箅A段應用領域：更多地應用于非數(shù)值處理處理的數(shù)據(jù)：更多地處理非數(shù)值型數(shù)據(jù)數(shù)據(jù)之間的關系：數(shù)據(jù)結(jié)構發(fā)展到面向?qū)ο箅A段（數(shù)據(jù)結(jié)構＋算法）＝程序類和數(shù)據(jù)結(jié)構之間的對應關系類屬性方法數(shù)據(jù)結(jié)構數(shù)據(jù)之間的關系基本操作對應數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第8頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構的研究對象用計算機求解問題的一般過程具體問題建立模型設計算法編制計算機程序問題分為兩類數(shù)值問題非數(shù)值問題數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第9頁!1.2數(shù)據(jù)結(jié)構非數(shù)值問題例1電話號碼簿黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院49929306845678是誰的電話？太難找了！數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第10頁!1.2數(shù)據(jù)結(jié)構改變結(jié)構：按電話號碼的大小排列黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930黨政機關黨委總機4811122宣傳部4811234組織部4812345大專院校內(nèi)蒙古大學校務辦公室4991234計算機學院4992930110……...匪警119………火警120………急救1234567….…….6845678….Tom………6845678是老朋友Tom的電話，太容易找了！數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第11頁!1.2數(shù)據(jù)結(jié)構例3人機對弈問題——樹結(jié)構…………..……..………...……數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第12頁!1.2數(shù)據(jù)結(jié)構總結(jié)非數(shù)值問題建立的模型是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構，而不是數(shù)學方程非數(shù)值問題求解的核心是數(shù)據(jù)處理，而不是數(shù)值計算數(shù)據(jù)結(jié)構是一門研究非數(shù)值問題中計算機的操作對象以及它們之間的關系和操作的學科。數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第13頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)元素（DataElement）（數(shù)據(jù)成員）：數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。數(shù)據(jù)項（DataItem）：組成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第14頁!1.2數(shù)據(jù)結(jié)構例2學籍管理問題每一行是一個數(shù)據(jù)元素每一列是一個數(shù)據(jù)項學生數(shù)據(jù)元素的集合是一個數(shù)據(jù)對象姓名學號性別年齡民族系專業(yè)入學時間王小林060631男18漢族計算機計算機科學2006.9陳紅060632女20蒙族計算機計算機應用2006.9劉建平060633男19回族計算機電子商務2006.9……..……..…….…….……………….數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第15頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構按照某種邏輯關系組織起來的一批數(shù)據(jù)，按一定的存儲方法把它存儲在計算機中，并在這些數(shù)據(jù)上定義了一個運算的集合。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第16頁!1.3數(shù)據(jù)的邏輯結(jié)構預備知識偶對在數(shù)學中，用來表示兩個事物之間所具有的固定關系的方法，叫偶對分類無序偶對兩個事物之間的關系沒有次序之分表示：(a,b)有序偶對兩個事物之間的關系有次序之分表示：<a,b>abab數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第17頁!1.3數(shù)據(jù)的邏輯結(jié)構二元關系（DualityRelationship）R是集合A上的二元關系：RAA數(shù)據(jù)的邏輯結(jié)構由數(shù)據(jù)元素集及其邏輯關系組成，可形式地描述為：Data_Structure=（D,R）其中：D是數(shù)據(jù)元素的有限集合；R是D上的有限關系集合。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第18頁!1.3數(shù)據(jù)的邏輯結(jié)構線性結(jié)構（LinearStructure）LS=(D,R)

D={d1,d2,…,dn}R={<di,di+1>|i=1,2,3,…,n-1}例4DS=(D,R1)

D={d1,d2,d3,d4,d5,d6}R1={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>,<d5,d6>}d1d2d3d4d5d6僅有一個開始結(jié)點，僅有一個終端結(jié)點其它都是內(nèi)部結(jié)點，且都有且僅有一個直接前驅(qū)、一個直接后繼數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第19頁!1.3數(shù)據(jù)的邏輯結(jié)構樹形結(jié)構例6DS=(D,R3)

D={d1,d2,d3,d4,d5,d6,d7}R3={<d1,d2>,<d1,d3>,<d3,d7>,<d2,d4>,<d2,d5>,<d2,d6>}d4d1d2d3d5d6

d7

有且僅有一個根結(jié)點其它結(jié)點有且僅有一個前驅(qū)結(jié)點對于非根結(jié)點都存在從根到該結(jié)點的一條路徑結(jié)構中的數(shù)據(jù)元素存在一對多的關系數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第20頁!1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTypes，ADT）面向?qū)ο蠹夹g核心概念面向?qū)ο蟪绦蛟O計的基礎（C++，Java，……）抽象層次高，模塊復用度高——使用ADT有極大的優(yōu)勢數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第21頁!1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTypes，ADT）一個數(shù)學模型以及定義在該模型上的一組操作的總稱抽象數(shù)據(jù)類型與數(shù)據(jù)類型的區(qū)別數(shù)據(jù)類型僅局限于計算機（高級程序設計語言）中定義并實現(xiàn)了的數(shù)據(jù)類型抽象數(shù)據(jù)類型還包括用戶在設計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型關鍵使用它的人可以只關心它的邏輯特征，不需要了解它的存儲方式定義它的人同樣不必要關心它如何存儲數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第22頁!1.4抽象數(shù)據(jù)類型例8自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumber

{

Data：一個整數(shù)的有序子集合，它開始于0，結(jié)束于機器能表示的最大整數(shù)（MaxInt）。

Operations：對于所有的x,yNaturalNumber；False,TrueBoolean，+、-、<、==、=等都是可用的服務。

Zero()：NaturalNumber

返回自然數(shù)0

IsZero(x):Boolean

if(x==0)返回Trueelse返回False數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第23頁!1.5數(shù)據(jù)的存儲結(jié)構數(shù)據(jù)的存儲結(jié)構（StoreStructure）數(shù)據(jù)及其邏輯結(jié)構在計算機中的表示面向計算機，面向具體實現(xiàn)分類順序存儲結(jié)構（SequentialStoreStructure）鏈式存儲結(jié)構（LinkedStoreStructure）數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第24頁!1.5數(shù)據(jù)的存儲結(jié)構鏈式存儲結(jié)構存儲空間不連續(xù)保持了邏輯關系數(shù)據(jù)元素的存儲位置e0b1040a1026d1024c1034102410261028103010321034103610381040abcde不考慮具體地址，抽象為數(shù)據(jù)元素指針結(jié)點（node）：存儲一個數(shù)據(jù)元素及附加信息的存儲空間指針（pointer）：存儲地址

數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第25頁!1.5數(shù)據(jù)的存儲結(jié)構數(shù)據(jù)的邏輯結(jié)構和存儲結(jié)構是密切相關的兩個方面數(shù)據(jù)的邏輯結(jié)構是數(shù)據(jù)的機外表示，數(shù)據(jù)的存儲結(jié)構是數(shù)據(jù)的機內(nèi)表示一種數(shù)據(jù)的邏輯結(jié)構可以用多種存儲結(jié)構來存儲數(shù)據(jù)結(jié)構的基本操作是定義于邏輯結(jié)構，實現(xiàn)于存儲結(jié)構采用不同的存儲結(jié)構，其數(shù)據(jù)處理的效率往往是不同的數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第26頁!1.6算法與算法分析可行性（有效性）算法中的所有操作都可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。輸入算法運行過程中從外界給定的數(shù)據(jù)；一個算法有0個或多個輸入數(shù)據(jù)。輸出對輸入數(shù)據(jù)加工后的結(jié)果的輸出；一個算法至少有1個輸出數(shù)據(jù)。（必須有輸出）數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第27頁!1.6算法與算法分析評價算法“好壞”的幾個標準算法的正確性算法的效率占用空間量簡單性和清晰性最優(yōu)性數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第28頁!1.6算法與算法分析簡單性（Simplicity）簡單的算法的優(yōu)點易于驗證正確性易于實現(xiàn)（編寫程序）易于調(diào)試、修改設計算法時，也需要權衡簡單性和時間、空間復雜度之間的關系通常方法越直接、越簡單，算法的效率越低數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第29頁!1.6算法與算法分析算法性能分析和度量問題的提出計算機的所有應用問題，包括計算機自身的發(fā)展，都是圍繞著“時間——速度”這一中心進行的。算法的效率（算法的工作量）指算法的執(zhí)行時間效率越高，工作量越小，執(zhí)行時間越短對給定的問題設計出多種算法時，如何選擇其中效率高的算法？數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第30頁!1.6算法與算法分析度量算法效率的方法之一——事后測算用源程序分別實現(xiàn)這些算法，然后輸入適當?shù)臄?shù)據(jù)運行，測算不同算法花費的時間。缺點編寫多個程序并進行測算，需要花費很多的時間和精力；測試數(shù)據(jù)的選擇可能對其中的某個算法有利；實驗結(jié)果受運行環(huán)境、編譯器、可用存儲空間大小等的影響，有時容易掩蓋算法本身的優(yōu)劣；即使其中較好的那種算法也超出了你預算的開銷。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第31頁!1.6算法與算法分析時間復雜度（TimeComplexity）例11for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)

x++;count=x; 常規(guī)思維：用日常生活中的時間來度量算法的執(zhí)行時間＝∑每條語句執(zhí)行時間每條語句執(zhí)行時間＝執(zhí)行次數(shù)×執(zhí)行一次的時間每條語句執(zhí)行一次的時間取決于指令系統(tǒng)、編譯產(chǎn)生的代碼質(zhì)量等軟硬件因素

——不公平、計算繁瑣數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第32頁!1.6算法與算法分析算法的執(zhí)行時間＝基本語句的執(zhí)行次數(shù)對不同的問題，其求解算法的基本語句是不同的基本語句的執(zhí)行次數(shù)與輸入尺寸有關輸入尺寸：指輸入量的多少，可從問題描述中得到問題基本語句輸入尺寸在數(shù)組中查找元素x元素比較元素個數(shù)兩實數(shù)矩陣相乘加、乘階數(shù)排序 元素比較、移動元素個數(shù)求多項式P(x)的值加、乘階數(shù)循環(huán) 循環(huán)體數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第33頁!1.6算法與算法分析大O表示法定義：若存在兩個正常數(shù)c和n0，對于任意n>n0，有|T(n)|c|f(n)|，則稱T(n)在集合O(f(n))中。大O表示法用于描述某一算法的上限，即當輸入尺寸為n時，一種算法所消耗的某種資源（通常是時間）的最大值。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，則A(n)=O(nm)。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第34頁!1.6算法與算法分析應用規(guī)則加法規(guī)則－－針對并列程序段T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))乘法規(guī)則－－針對嵌套程序段T(n,m)=T1(n)T2(m)=O(f(n)g(m))數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第35頁!1.6算法與算法分析測試題voidexample(floatx[][],intm,intn,intk){floatsum[];for(inti=0;i<m;i++){//x[][]中各行數(shù)據(jù)累加

sum[i]=0.0;for(intj=0;j<n;j++)sum[i]+=x[i][j];

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和cout<<“Line”<<i<<“:”<<sum[i]<<endl; }時間復雜度為O(max(mn,m))=O(mn)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第36頁!1.6算法與算法分析舊機器：1小時可完成10000個基本操作新機器：執(zhí)行速度是舊機器的10倍T(n)：算法的時間復雜度n：舊機器一小時能完成的輸入尺寸n’：新機器一小時能完成的輸入尺寸增長率高的算法從機器升級中得益較少！數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第37頁!1.6算法與算法分析基本語句：元素比較執(zhí)行次數(shù)：取決于被查元素在數(shù)組中的位置最好情況：數(shù)組中個元素就是k，算法只需比較1次。最壞情況:數(shù)組中最后一個元素是k，算法需要比較n次。平均情況：查找到數(shù)組一半時找到k，比較次數(shù)n/2次。intFind(intA[],intn,intk){for(inti=0;i<n;i++)if(A[i]==k)break;returni;}數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第38頁!1.6算法與算法分析最壞情況下的時間復雜度（Worst-caseComplexity）定義為

其中：Dn是問題的所有尺寸為n的輸入集；

I是Dn的元素；

t(I)是算法對輸入I所做的工作量。平均情況下的時間復雜度（AverageComplexity）定義為

其中：Pr(I)是輸入元素I出現(xiàn)的概率。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第39頁!1.6算法與算法分析時間/空間權衡原則（time/spacetradeoff）犧牲空間或其它資源都可以減少時間代價，反之亦然例如：程序?qū)π畔⒌膲嚎s或加密后，可以節(jié)省存儲空間，然而解壓縮和解密的過程又需要額外的時間代價。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第40頁!1.6算法與算法分析用自然語言描述算法①輸入m和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。優(yōu)點：容易理解缺點：冗長、二義性使用方法：粗線條描述算法思想注意事項：避免寫成自然段數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第41頁!1.6算法與算法分析用程序設計語言描述算法#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第42頁!1.6算法與算法分析用偽代碼描述算法偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結(jié)合自然語言來設計。本書采用類C++語言描述算法1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;優(yōu)點：表達能力強，抽象性強，容易理解

intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第43頁!1.6算法與算法分析不使用友元，邏輯上相關的類認為都是友元，可直接訪問任一對象的數(shù)據(jù)函數(shù)參數(shù)表：對類型十分明確的參數(shù)，在參數(shù)表中可不做類型說明為了與C++兼容，本書算法中的數(shù)組下標均從0開始數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第44頁!1.7總結(jié)ADT的三個不同的視圖ADT

邏輯結(jié)構操作集合1n數(shù)據(jù)結(jié)構

存儲結(jié)構算法設計1n類

成員變量成員函數(shù)定義視圖設計視圖實現(xiàn)視圖數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第45頁!1.7總結(jié)好的程序設計選擇好的數(shù)據(jù)邏輯結(jié)構設計選擇好的數(shù)據(jù)存儲結(jié)構設計選擇好的算法支持好的解決問題的方案開發(fā)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第46頁!書面作業(yè)P191-1題，1-2題，1-5題補充題按增長率從小到大的順序排列下列各函數(shù)：數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第47頁!課程介紹教材及參考書《數(shù)據(jù)結(jié)構與算法》趙玉蘭等著，清華大學出版社《數(shù)據(jù)結(jié)構—用面向?qū)ο蠓椒ㄅcC++描述》殷人昆著，清華大學出版社《數(shù)據(jù)結(jié)構》嚴蔚敏、吳偉民著，清華大學出版社《數(shù)據(jù)結(jié)構與算法分析》張銘、劉曉丹譯，電子工業(yè)出版社《ComputerAlgorithms–IntroductiontoDesignandAnalysis》Sarabase，高等教育出版社影印《DataStructuresandAlgorithms》AlfredV.Aho網(wǎng)上閱讀材料數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第48頁!課程介紹學習目標知識方面掌握基本的數(shù)據(jù)結(jié)構掌握數(shù)據(jù)結(jié)構的實現(xiàn)方法以及經(jīng)典算法掌握初步的算法分析技術能力方面培養(yǎng)算法設計能力、程序設計能力培養(yǎng)計算機思維能力數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第49頁!課程介紹學習要求重視課后習題重視上機實驗最有害的行為抄襲他人作業(yè)拷貝他人程序數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第50頁!1.1數(shù)據(jù)結(jié)構的發(fā)展數(shù)據(jù)結(jié)構起源于程序設計，并隨著程序設計的發(fā)展而發(fā)展程序設計的實質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理數(shù)據(jù)表示：如何將數(shù)據(jù)從機外表示轉(zhuǎn)化為機內(nèi)表示，存儲在計算機（內(nèi)存）中數(shù)據(jù)處理：如何處理機內(nèi)表示的數(shù)據(jù)，實現(xiàn)問題求解或完成處理要求《數(shù)據(jù)結(jié)構與算法》課程主要討論數(shù)據(jù)表示和數(shù)據(jù)處理過程中的基本問題。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第51頁!1.1數(shù)據(jù)結(jié)構的發(fā)展結(jié)構化階段應用領域：科學計算與非數(shù)值性數(shù)據(jù)處理處理的數(shù)據(jù)：數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)70’s80’s90’s70’s—80’s非數(shù)值問題猛增

數(shù)據(jù)之間的關系：產(chǎn)生了數(shù)據(jù)結(jié)構，提出了程序結(jié)構模塊化，開始注意數(shù)據(jù)表示和操作的結(jié)構化數(shù)據(jù)結(jié)構＋算法＝程序1968年，D.E.Knuth所著的《計算機程序設計技巧》卷《基本算法》，首次較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構和存儲結(jié)構以及定義在數(shù)據(jù)上的操作，開創(chuàng)了數(shù)據(jù)結(jié)構的課程體系。同年，《數(shù)據(jù)結(jié)構》作為一門獨立的課程在計算機科學的學科課程中開始出現(xiàn)。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第52頁!1.1數(shù)據(jù)結(jié)構的發(fā)展數(shù)據(jù)結(jié)構的創(chuàng)始人——D.E.Knuth1938年出生，25歲畢業(yè)于加州理工學院數(shù)學系，博士畢業(yè)后留校任教，28歲任副教授。30歲時，加盟斯坦福大學計算機系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他計劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計算機科學界的最高榮譽圖靈獎。此時，他年僅36歲。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第53頁!1.2數(shù)據(jù)結(jié)構數(shù)值問題建立的模型是數(shù)學方程問題求解的核心是數(shù)值計算例彈道計算<v0,α,…>矩陣運算M1×M2×M3×…×Mn方程組求解定積分數(shù)學方程數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第54頁!1.2數(shù)據(jù)結(jié)構電話號碼簿的結(jié)構：按照單位排列電話號碼內(nèi)蒙古黨委內(nèi)蒙古政府黨政機關理工學院計算機系網(wǎng)絡中心計算中心計算機學院內(nèi)蒙古大學內(nèi)蒙古工業(yè)大學大專院校醫(yī)療衛(wèi)生交通運輸呼和浩特市電話號碼簿數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第55頁!1.2數(shù)據(jù)結(jié)構例2學籍管理問題——表結(jié)構姓名學號性別年齡民族系專業(yè)入學時間王小林060631男18漢族計算機計算機科學2006.9陳紅060632女20蒙族計算機計算機應用2006.9劉建平060633男19回族計算機電子商務2006.9……..……..…….…….……………….數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第56頁!1.2數(shù)據(jù)結(jié)構例4教學計劃編排問題——圖結(jié)構C4,C5,C6數(shù)據(jù)庫原理C7C2,

C4計算機原理C6C3,C4數(shù)據(jù)結(jié)構C5C1,C2程序設計C4C1離散數(shù)學C3無計算機導論C2無高等數(shù)學C1先修課課程名稱編號C1C2C3C4C6C5C7數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第57頁!1.2數(shù)據(jù)結(jié)構基本概念數(shù)據(jù)（Data）：是信息的載體，在計算機科學中指所有能輸入到計算機中，并能被計算機程序識別和處理的符號集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第58頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)對象（DataObject）：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對象，包括{0,1,2,…}字母數(shù)據(jù)對象，包括{‘A’,’B’,…,’Z’,’a’,’b’,…,’z’}學生數(shù)據(jù)對象數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第59頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)類型（DataType）：指定一種數(shù)據(jù)對象的類型。定義為一個值的集合以及定義在該值集合上的一組操作的總稱。C++語言的數(shù)據(jù)類型基本類型結(jié)構類型整型實型字符型枚舉型指針型數(shù)組型結(jié)構型共用體類數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第60頁!1.2數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構研究的對象包括三個方面數(shù)據(jù)的邏輯結(jié)構指數(shù)據(jù)元素之間的邏輯關系，即指數(shù)據(jù)元素之間的關聯(lián)方式或鄰接關系數(shù)據(jù)的存儲結(jié)構指數(shù)據(jù)元素在計算機中的存儲結(jié)構，如某個電話號碼在號碼本上的位置運算的集合定義在該結(jié)構上的一組操作，如輸入/讀取、檢索/查找、插入、刪除、更新等數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第61頁!1.3數(shù)據(jù)的邏輯結(jié)構（直接）前驅(qū)（Previous）與（直接）后繼（Next）如果有<a,b>，稱a是b的（直接）前驅(qū)，b是a的（直接）后繼笛卡兒積（DescartesSet）給定兩個集合A和B，如果有序偶對的個分量是A的一個元素，第二個分量是B的一個元素，則所有這種有序偶對的集合稱為集合A和B的笛卡兒積記為：A×B＝{<x,y>|xA∧yB}數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第62頁!1.3數(shù)據(jù)的邏輯結(jié)構說明從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關可以看作是從具體問題抽象出來的數(shù)據(jù)模型面向問題，面向用戶分類（根據(jù)數(shù)據(jù)元素間的不同特性）非線性結(jié)構線性結(jié)構集合樹形結(jié)構圖或網(wǎng)狀結(jié)構數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第63頁!1.3數(shù)據(jù)的邏輯結(jié)構集合例5DS=(D,R2)

D={d1,d2,d3,d4,d5,d6}R2={d1D,d2D,d3D,d4D,d5D,d6D}結(jié)構中的數(shù)據(jù)元素只具有“同屬于一個集合”的關系d2d6d1d3d5d4數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第64頁!1.3數(shù)據(jù)的邏輯結(jié)構圖形或網(wǎng)狀結(jié)構例7DS=(D,R4)D={d1,d2,d3,d4,d5}R4={<d1,d2>,<d3,d1>,<d1,d4>,<d5,d1>,<d2,d3>,<d5,d4>,<d3,d5>}結(jié)構中的數(shù)據(jù)元素存在多對多的關系d1d2d3d4d5數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第65頁!1.4抽象數(shù)據(jù)類型數(shù)據(jù)類型一個值的集合以及定義在該值集合上的一組操作的總稱規(guī)定了該數(shù)據(jù)類型的取值范圍和對這些數(shù)據(jù)所能采取的操作例，C++中的整型變量抽象抽出問題本質(zhì)的特征而忽略非本質(zhì)的細節(jié)，是對具體事物的一個概括隱藏了繁雜的細節(jié)，只保留實現(xiàn)目標所必需的信息例，地圖、駕駛汽車數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第66頁!1.4抽象數(shù)據(jù)類型ADT的描述ADTADT-name{

Data數(shù)學模型或數(shù)據(jù)的邏輯結(jié)構

Operations //操作集

Constrictor //構造操作，初始化 Initialvalues：用于初始化的值。Process：初始化。

Operation1 Input：輸入數(shù)據(jù)（參數(shù)）。Preconditions：執(zhí)行本操作前系統(tǒng)必須處于的狀態(tài)。Process：操作。Output：輸出。Postconditions：執(zhí)行本操作后系統(tǒng)所處狀態(tài)。

Operation2 …… Operationk}//ADT-name數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第67頁!1.4抽象數(shù)據(jù)類型

Add(x,y):NaturalNumber

if(x+y<=MaxInt)返回x+yelse返回MaxInt

Subtract(x,y):NaturalNumber

if(x<y)返回0else返回x-y

Equal(x,y):Boolean

if(x==y)返回Trueelse返回False

Successor(x):NaturalNumber

if(x==MaxInt)返回xelse返回x+1

……}//

NaturalNumber

數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第68頁!1.5數(shù)據(jù)的存儲結(jié)構順序存儲結(jié)構例9LS={D,R}D={a,b,c,d,e}R={<a,b>,<b,c>,<c,d>,<d,e>}abcde10241026102810301032存儲空間連續(xù)保持了邏輯關系數(shù)據(jù)元素的存儲位置abcd

e數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第69頁!1.5數(shù)據(jù)的存儲結(jié)構順序存儲結(jié)構的基本思想用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素數(shù)據(jù)元素之間的邏輯關系是由元素的存儲位置來（隱式）表示的鏈式存儲結(jié)構的基本思想用一組任意的存儲單元存儲數(shù)據(jù)元素數(shù)據(jù)元素之間的邏輯關系是用指針來（顯式）表示的數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第70頁!1.6算法與算法分析算法（Algorithms）定義對具體問題的求解步驟，是指令的有限序列。特性有窮性一個算法必須在執(zhí)行有限步驟后終止，且每一步都在有限時間完成。確定性算法中的每條指令必須有確切的含義，無二義性。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第71頁!1.6算法與算法分析算法≠程序程序是對一個算法使用某種程序設計語言的具體實現(xiàn)，是對算法的精確描述，可在計算機上執(zhí)行算法一定要滿足有窮性而程序并不一定滿足程序設計的核心是算法設計數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第72頁!1.6算法與算法分析算法的正確性對任一合法的輸入，算法結(jié)束后得到正確結(jié)果。體現(xiàn)在兩個方面求解問題的方法（算法）是正確的；對算法實現(xiàn)（程序）是正確的。算法的正確性由問題領域的理論和定理保證和證明。如高斯迭代法，其正確性是由線性代數(shù)的理論證明。程序的正確性通過軟件測試來判定，但測試無法保證程序是絕對正確的。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第73頁!1.6算法與算法分析最優(yōu)性（Optimality）問題的下界（LowerBounds）問題固有的復雜度，解決該問題至少要做的工作量算法的上界（UpperBounds）算法工作量的上界最優(yōu)算法算法的上界＝問題的下界2m問題的下界算法的上界數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第74頁!1.6算法與算法分析例10在三個整數(shù)中求最大者max(inta,intb,intc){

if(a>b){

if(a>c)returna;

elsereturnc;

}

else{

if(b>c)returnb;

elsereturnc;

}}/*無需額外存儲空間，只需兩次比較*/max(inta[3]){intc,inti;c=a[0];for(i=1;i<3;i++)if(a[i]>c)c=a[i];returnc;}/*需要兩個額外的存儲空間，兩次比較，至少一次賦值*/數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第75頁!1.6算法與算法分析度量算法效率的方法之二——算法分析算法分析：對一個算法執(zhí)行時所消耗的兩種計算機資源（時間和空間）進行事前估算。如何度量時間復雜度空間復雜度數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第76頁!1.6算法與算法分析步簡化假設每條簡單語句執(zhí)行一次的時間都是單位時間1算法的執(zhí)行時間＝∑每條語句執(zhí)行次數(shù)

——精確計算出每條語句執(zhí)行次數(shù)之和很困難第二步簡化用算法中基本語句的執(zhí)行次數(shù)來度量基本語句（基本操作）：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句算法的執(zhí)行時間＝基本語句的執(zhí)行次數(shù)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第77頁!1.6算法與算法分析由以上分析，算法的執(zhí)行時間T是輸入尺寸n的函數(shù)，記作T(n)＝f(n)。為了客觀反映一個算法的執(zhí)行時間，可以用算法中基本語句的執(zhí)行次數(shù)的數(shù)量級來度量算法的工作量，稱為算法的漸進時間復雜度，簡稱時間復雜度，通常用大O記號表示。數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第78頁!1.6算法與算法分析時間復雜度分析舉例x++;for(inti=1;i<=n;i++)x++;for(inti=1;i<=n;i++)for(intj=1;j<=i-1;j++)x++;基本語句：x++執(zhí)行次數(shù)：1時間復雜度T(n)=1=O(1)基本語句：x++執(zhí)行次數(shù)：n時間復雜度T(n)=n=O(n)基本語句：x++執(zhí)行次數(shù)：時間復雜度T(n)==O(n2)數(shù)據(jù)結(jié)構與算法張清華大學出版社趙玉蘭共92頁，您現(xiàn)在瀏覽的是第79頁!1.6算法與算法分析例12①sum=0;②for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++;③for(k=1;k<=n;k++)a[k]=k-1;①的基本語句：sum=0執(zhí)行次數(shù)：1時間復雜度：O(1)②的基本語句：sum++執(zhí)行次數(shù)：n2