數(shù)據(jù)結(jié)構(gòu)第一章概論.ppt

數(shù)據(jù)結(jié)構(gòu) 第一章 概論,重慶一中 葛靜,本章的主要內(nèi)容,問題一：數(shù)據(jù)結(jié)構(gòu)討論的范疇 問題二：基本概念 問題三：算法及其度量,問題一：數(shù)據(jù)結(jié)構(gòu)討論的范疇,尼克勞斯沃斯(Niklaus Wirth)：生于瑞士，求學(xué) 美洲，立業(yè)瑞士。蘇黎世聯(lián)邦理工學(xué)院教授，Pascal系 列語言之父，世界聞名的計(jì)算機(jī)科學(xué)家。 Algorithm+Data Structures=Programs 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 程序：為計(jì)算機(jī)處理問題編制的一組指令集。 算法：處理問題的策略。 數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型。,數(shù)值計(jì)算的程序設(shè)計(jì)問題,全球天氣預(yù)報(bào) 環(huán)流模式方程（數(shù)學(xué)模型） 進(jìn)行大量的數(shù)值運(yùn)算，這是計(jì)算數(shù)學(xué)要討 論的問題。,非數(shù)值計(jì)算的程序問題,例1：求n個數(shù)中的最大值 算法？： 兩兩比較 數(shù)據(jù)結(jié)構(gòu)？： n 的范圍？如果n達(dá)到1012，如何表示這個整數(shù)？,非數(shù)值計(jì)算的程序問題,例2：人機(jī)對弈 算法？： 對弈的規(guī)則和策略 數(shù)據(jù)結(jié)構(gòu)？： 棋盤、棋子怎么表示？,非數(shù)值計(jì)算的程序問題,例3：足協(xié)數(shù)據(jù)庫管理 算法？： 需要管理哪些項(xiàng)目？用戶的界面？條例、規(guī)則等等。 數(shù)據(jù)結(jié)構(gòu)？： 各種各樣的表格和數(shù)據(jù)庫。,綜合各種程序設(shè)計(jì)的問題，抽出其具體的物理含義，就可得到幾類數(shù)學(xué)模型：,1、和數(shù)值計(jì)算相關(guān)的數(shù)學(xué)模型，如線性代數(shù)方程、非線性代數(shù)方程和常微分方程等，他們的數(shù)值解問題就是計(jì)算數(shù)學(xué)要解決的問題。 2、非數(shù)值計(jì)算問題，其數(shù)學(xué)模型的表示和求解就是數(shù)據(jù)結(jié)構(gòu)要研究的內(nèi)容。,概括的說：,數(shù)據(jù)結(jié)構(gòu)要研究的就是： 非數(shù)值型計(jì)算的程序設(shè)計(jì)問題中描述現(xiàn)實(shí)世 界實(shí)體的數(shù)學(xué)模型 和 在計(jì)算機(jī)中表示的方法 以及 這些數(shù)學(xué)模型進(jìn)行的操作如何在計(jì)算機(jī)中 實(shí)現(xiàn)。,問題二：基本概念,數(shù)據(jù)：是計(jì)算機(jī)要處理的信息集合，是信息的某 種特定的符號表示形式。其含義隨著計(jì)算機(jī)的發(fā) 展不斷擴(kuò)大。 數(shù)據(jù)元素：是數(shù)據(jù)中的一個“個體”，是數(shù)據(jù)結(jié)構(gòu) 中討論的基本單位。但不是最小單位。 如：學(xué)生（數(shù)據(jù)元素） 姓名、性別、出生日期（年月日）、入學(xué)日期、 班級 數(shù)據(jù)項(xiàng)才是數(shù)據(jù)結(jié)構(gòu)中要討論的最小單位。,數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。,結(jié)構(gòu)：就是數(shù)據(jù)元素之間存在的約束關(guān)系。 例1：一個含有12位數(shù)的十進(jìn)制整數(shù)可以用三個4位的十進(jìn)制整數(shù)表示。 1548，4913，7875a1(1548),a2(4913),a3(7875) 在a1,a2,a3之間存在次序關(guān)系 , 4973,7875,1548 1548,4913,7875 a2 a3 a1 a1 a2 a3,數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。,例2：2行3列的二維數(shù)組a1,a2,a3,a4,a5,a6 行的次序關(guān)系：row=, 列的次序關(guān)系：col=, a1 a3 a4 a1 a2 a3 a2 a6 a5 a4 a5 a6,數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。,例3：一位數(shù)組a1,a2,a3,a4,a5,a6，這6個數(shù)據(jù)元 素還可以存在單純的次序關(guān)系i=1,2,3,4,5 所以：相同的數(shù)據(jù)元素，不同的約束關(guān)系，構(gòu)成 了不同的數(shù)據(jù)結(jié)構(gòu)。,例3 人機(jī)對奕問題,多叉路口交通燈管理問題,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)在邏輯上的聯(lián)系，叫做數(shù)據(jù)的邏輯結(jié)構(gòu)。,數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系 數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn),數(shù)據(jù)邏輯結(jié)構(gòu)的定義,定義為一個二元組： Data_structures=(D,S) 其中： D是數(shù)據(jù)元素的有限集， S是D上關(guān)系的有限集。 如：線性結(jié)構(gòu)： 數(shù)據(jù)對象：A=ai1=0,aielemtype 其中n為線性表的表長，n=0時線性表為空表。 數(shù)據(jù)關(guān)系：R=r R=1=i=n-1,數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）,數(shù)據(jù)的在計(jì)算機(jī)上的存儲表示稱作數(shù)據(jù)的物 理結(jié)構(gòu)或存儲結(jié)構(gòu)。 數(shù)據(jù)元素的映像方法： 用二進(jìn)制位（bit）的位串表示數(shù)據(jù)元素。 （321）10=（101000001）2 A=(001000001)2,數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）,關(guān)系集合的映像方法： 所有關(guān)系都可用一個有序?qū)Φ募蟻肀硎尽?, 有序?qū)闯墒顷P(guān)系的一個基本單位，討論關(guān)系 的映像，只要討論這個有序?qū)Φ挠诚穹椒纯伞?映像方法：,順序映像：以存儲位置的相鄰表示后繼關(guān)系。 鏈?zhǔn)接∠螅捍鎯ξ恢脽o固定關(guān)系，用附加信息 （指針）來表示后繼關(guān)系。,數(shù)據(jù)類型,數(shù)據(jù)類型是一個值的集合和定義在這個集合上的一組操作的總稱。 如pascal中的integer類型，數(shù)據(jù)范圍 -32768,32767 操作：+ - * div mod 數(shù)據(jù)類型分為：簡單型和結(jié)構(gòu)類型（構(gòu)造類型）,結(jié)構(gòu)類型,比如：數(shù)組，數(shù)組的值可以分割，它是某個結(jié)構(gòu) 的值，因此這個值集是一個數(shù)據(jù)結(jié)構(gòu)。所以數(shù)據(jù) 類型也可以看成是一個數(shù)據(jù)結(jié)構(gòu)和定義在這個數(shù) 據(jù)結(jié)構(gòu)上的一組操作的總稱。 從這個概念出發(fā)抽象數(shù)據(jù)類型（ADT Abstract Data Type）是指一個數(shù)學(xué)模型以及定義在這個數(shù)學(xué)模型上的一組操作。,例如：抽象數(shù)據(jù)類型復(fù)數(shù)的定義,ADT complex 數(shù)據(jù)對象：D=e1,e2e1,e2real 數(shù)據(jù)關(guān)系：R= e1是復(fù)數(shù)的實(shí)部，e2 是復(fù)數(shù)的虛部 基本操作： Initcomplex(z,v1,v2) 操作結(jié)果：構(gòu)造復(fù)數(shù)z，其實(shí)部和虛部分別賦以 參數(shù)v1,v2的值。,Destroycomplex(z) 操作結(jié)果：復(fù)數(shù)z被銷毀 Getreal(z,x) 初始條件：復(fù)數(shù)已存在 操作結(jié)果：用x返回復(fù)數(shù)z的實(shí)部值 Getimag(z,y) 初始條件：復(fù)數(shù)已存在 操作結(jié)果：用y返回z的虛部值 Add(z1,z2,sum) 初始條件：z1,z2是復(fù)數(shù) 操作結(jié)果：用sum返回兩個復(fù)數(shù)的和值。,抽象數(shù)據(jù)類型的描述方法,(D,S,P)三元組表示： D是數(shù)據(jù)對象 S是D上的關(guān)系集 P是對D的基本操作,抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)：,通過固有數(shù)據(jù)類型，即高級編程語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，來實(shí)現(xiàn)。,問題三：算法及算法的衡量,算法：是為了解決某類問題而規(guī)定的一個有限長 的操作序列。 算法的五個重要特性： 1、有窮性 2、確定性 3、可行性 4、有輸入 5、有輸出,算法的特性,1、有窮性：對任意一組合法輸入值，在執(zhí)行有窮步驟之后，一定能結(jié)束，即能在有限時間內(nèi)完成。 其含義有二： 其一：描述算法的指令條數(shù)有限。 其二：每一步的執(zhí)行時間是有限的，非數(shù)學(xué)意義 上的有限，而應(yīng)理解為合理。,算法的特性,確定性：每種情況下執(zhí)行的操作，在算法中都 有確切的規(guī)定，使算法的執(zhí)行者或者閱讀者能夠 明確其含義及如何執(zhí)行，并且在任何條件下，算 法都只有與之對應(yīng)的一條路徑。 可行性：算法中的所有操作都必須足夠基本， 都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次來實(shí) 現(xiàn)之。 如：將a,b的最大公約數(shù)賦值給c（） 增加x的值（ ） 交換a,b 兩個變量的值（）,算法的特性,有輸入：輸入的形式多樣，有的輸入嵌在算法 中，有的可通過終端輸入。必須保證算法有可以 加工的對象。 如：求100以內(nèi)的素?cái)?shù) For i:=2 to 100 do 有輸出：信息加工的結(jié)果。,算法設(shè)計(jì)（評價(jià)）的原則,1、正確性： 程序不含語法錯誤 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。 對于精心選擇的、典型的、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)都能得出滿足要求的結(jié)果。 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。（相當(dāng)難）,算法設(shè)計(jì)（評價(jià)）的原則,2、可讀性 算法主要是為了人的閱讀與交流，其次才是為了計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難懂的程序易于隱藏較多的錯誤而難以調(diào)試。 例如：多人合作設(shè)計(jì)大型軟件 系統(tǒng)設(shè)計(jì) 程序設(shè)計(jì) 編程,算法設(shè)計(jì)（評價(jià)）的原則,3、健壯性（對應(yīng)著正確性） 當(dāng)輸入數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从?或進(jìn)行相應(yīng)的處理，而不是產(chǎn)生莫名其妙的輸出 結(jié)果，并且，不應(yīng)該中斷程序的執(zhí)行，而應(yīng)是返 回一個表示錯誤或錯誤性質(zhì)的值。 4、高效率與低存儲量的需求。 效率：算法執(zhí)行的時間 存儲量：算法執(zhí)行過程中最大的存儲空間。 二者均與問題的規(guī)模有關(guān)。,算法效率的衡量方法和準(zhǔn)則,1、事后統(tǒng)計(jì)法： 算法程序運(yùn)行時間 缺點(diǎn)： （1）必須執(zhí)行程序 （2）其他因素掩蓋算法本質(zhì) 2、事前分析估算法,和算法執(zhí)行時間相關(guān)的因素：,算法選用的策略。 問題的規(guī)模。 編寫程序的語言。 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量。 計(jì)算機(jī)執(zhí)行指令的速度。 第3、4、5條均與硬件及軟件有關(guān)，一般不考慮。 一個特定算法的“運(yùn)行工作量”的大小，只依 賴于問題的規(guī)模n，或者說，它是問題規(guī)模n的函 數(shù)。,我們要關(guān)系的是： 隨著n的增長，算法執(zhí)行時間的增長與n的關(guān)系。 T(n)=O(f(n) T(n)就是算法的漸近時間復(fù)雜度，T(n)增大的趨 勢與f(n)相同。,如何估算？,算法=控制結(jié)構(gòu)*原操作（固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時間 =（原操作執(zhí)行的次數(shù)原操作執(zhí)行的時間） 從算法中選取起決定作用的基本操作叫原 操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)為 算法運(yùn)行時間的衡量準(zhǔn)則。,例1：for i:=1 to n do for j:=1 to n do begin ci,j:=0; for k:=1 to n do ci,j:=ci,j+ai,k*bk,j; end; 控制結(jié)構(gòu)：3重循環(huán) 基本操作：乘法 時間復(fù)雜度：O(n3),例2：for i:=1 to n-1 do begin j:=i; for k:=i+1 to n do if aki then swap(aj,ai); end; 基本操作：比較。 比較次數(shù)： (n-1)+(n-2)+1=n(n-1)/2=(n2-n)/2與 n2成正比。故時間復(fù)雜度O(n2)。,例3：t:=true; i:=n-1; while (i=1)and(t) do begin t:=false; for j:=1 to i do if ajaj+1 then begin swap(aj,aj+1);t:=true;end; dec(i); end; 該算法與輸入有關(guān)，最好情況O(n-1)，最壞O(n2),算法的存儲空間需求,算法的空間復(fù)雜度 S(n)=O(g(n) 表示隨著n的增大，算法運(yùn)行所需存儲量的增 長率與g(n)的增長率相同。 算法的存儲量包括： 程序本身所占空間。（細(xì)微差別，可不考慮） 輸入數(shù)據(jù)所占得空間。 輔助變量所占空間。 一般情況下，所需存儲量依賴于特定的輸 入，通常按最壞情況考慮。,如何學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),了解常見的抽象數(shù)據(jù)類型 對每種ADT，了解常見的邏輯結(jié)構(gòu) 設(shè)計(jì)邏輯結(jié)構(gòu)是最難的！ 對給定的邏輯結(jié)構(gòu)，自己設(shè)計(jì)物理結(jié)構(gòu) 物理結(jié)構(gòu)一般只是數(shù)組和鏈結(jié)構(gòu) 數(shù)組可以隨機(jī)訪問（設(shè)計(jì)下標(biāo)計(jì)算公式） 經(jīng)典例子：哈希表，二叉堆，并查集，線段樹 鏈結(jié)構(gòu)應(yīng)該根據(jù)元素間關(guān)系（鏈接）進(jìn)行“移動” 經(jīng)典例子：伸展樹，二項(xiàng)堆，跳躍表 *特殊算法需要自己歸納出ADT并設(shè)計(jì)邏輯結(jié)構(gòu) PQ樹，后綴樹,1. 算法的計(jì)算量的大小稱為計(jì)算的( B ) A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度 2. 算法的時間復(fù)雜度取決于（ C） A.問題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C. A和B 3.計(jì)算機(jī)算法指的是（C），它必須具備（B）這三個特性。 (1) A.計(jì)算方法 B.排序方法 C.解決問題的步驟序列 D. 調(diào)度方法 (2) A可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性 C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性,4一個算法應(yīng)該是（ B ）。 A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C. 5. 下面關(guān)于算法說法正確的是（ D ） A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) B. 為解決某問題的算法同為該問題編寫的程序含義是相同的 C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的,6. 下面說法錯誤的是（C ） (1)算法原地工作的含義是指不需要任何額外的輔助空間 (2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法 (3)所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 (4)同一個算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3),7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( C)兩大類。 A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C. 線性結(jié)構(gòu)、非線性結(jié)構(gòu) D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) 8在下面的程序段中，對x的賦值語句的頻度為(C ) FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A O(2n) BO(n) CO(n2) DO(log2n),1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( F ) 2. 記錄是數(shù)據(jù)處理的最小單位。 ( F ) 3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；( F ) 4算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。( F ) 5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀