數(shù)據(jù)結(jié)構(gòu)與算法實驗.ppt

1、數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu)與算法實驗 2012.9-2013.1,紙上得來終覺淺，絕知此事要躬行 讀+寫+討論,學習方法,上課時間:周二1-2節(jié) 周四1-2節(jié) 上機時間:周四3-4節(jié) 答疑時間:周一15:00-16:30 239 周三13:00-15:00 239,所有作業(yè)按時交，注釋不少于30% 書面作業(yè)晚依天9折,放慢速度？ 9/25 時常復習以前講的？ 8個小時？ 全部/部分？ 只會課上講的？ 答疑了嗎？,講但不是全部 部分內(nèi)容需要自己學習 希望預習,北大： 計算概論 周4學時（48） 3學分 程序設計實習 周4學時 3學分 數(shù)據(jù)結(jié)構(gòu)與算法 周4學時 3學分 數(shù)據(jù)結(jié)構(gòu)與算法實習 周2學時

2、2學分,首師大： C語言程序設計 4+2 面向?qū)ο蟪绦蛟O計 3+2 數(shù)據(jù)結(jié)構(gòu)與算法 4+2 算法設計與分析 3,復旦大學 3+2 浙江大學 4 湖南師大 4+1 南京師大 4+2 華東師大 3+2 上海師大 3+2 杭州電子科技大學 4+1,希望： 提前5分鐘到教室，不遲到 不吃東西 手機靜音 隨時問，積極響應 按時交作業(yè),對老師的希望？,數(shù)據(jù)結(jié)構(gòu)學什么 數(shù)據(jù)結(jié)構(gòu)的地位和作用 怎么學好數(shù)據(jù)結(jié)構(gòu),教學內(nèi)容,特點：用數(shù)學方程進行數(shù)值運算,稱這類問題的數(shù)學模型是數(shù)學方程,第一章緒論,例1：數(shù)學方程 （1）用二分法求方程的根 （2）用迭代法求a的平方根,例2:學生成績管理系統(tǒng),建立一個小型的學生成績管

3、理系統(tǒng)，該系統(tǒng)具有輸入、查詢、修改、打印功能。 實驗要求： （1）每位學生數(shù)據(jù)中包含學號、姓名、性別、年齡、五門課的成績。要求學生人數(shù)不少于16人，從文件中輸入數(shù)據(jù) （2）能根據(jù)學號或姓名查詢?nèi)我粚W生某門課程成績或所有課程成績 （3）系統(tǒng)界面自行設計 （4）能修改學生的任何一個數(shù)據(jù)，并設置相應的修改口令 （5）能按總成績從高到低顯示所有學生的數(shù)據(jù)，包括每個學生的平均分，并輸出到文件。,涉及： 數(shù)據(jù)錄入 數(shù)據(jù)查詢 數(shù)據(jù)維護 數(shù)據(jù)排序、輸出,需要： 建一張表 確定表中前后數(shù)據(jù)的關系 實現(xiàn)對表進行操作的方法,例3:撲克牌接龍游戲,洗牌 發(fā)牌、出牌、移牌 比較、判斷 輸贏判斷,（1）表示所有撲克牌 （

4、2）實現(xiàn)各種游戲動作,特點：兩個數(shù)據(jù)之間有一定順序 主要操作有：插入、查找、修改、刪除 稱這類問題的數(shù)學模型為線性表(線性結(jié)構(gòu)),學生成績管理系統(tǒng),撲克牌接龍游戲,.,.,例4 人機對奕,.,.,.,.,.,井字棋、中國象棋、國際象棋 對奕過程中可能出現(xiàn)的棋盤狀態(tài)稱為格局,格局之間的關系由下棋規(guī)則確定 從一個格局中可以派生出若干個新格局 從新格局又可以派生出更新的格局 整個對奕過程可能派生出的所有格局就象一棵倒掛的樹 樹根為對奕開始的格局 樹葉為可能出現(xiàn)的一種結(jié)局 對奕的過程就是從樹根走到樹葉的過程,表示每一種格局 表示格局之間的派生關系 給出對奕的算法：從所有兒子格局中找出 最有利的格局,需

5、要,8,7,1,4,3,2,9,13,6,5,14,10,15,11,12,1,2,3,5,6,7,9,10,11,4,8,12,13,14,15,15謎問題,例5 文件系統(tǒng),/ (root),bin,lib,user,etc,math,ds,clg,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,這類問題的數(shù)學模型稱為樹（樹型結(jié)構(gòu)、層次結(jié)構(gòu)） 樹的特點： 除根外每個結(jié)點有唯一一個雙親(上級，祖先) 除葉子結(jié)點外，每個結(jié)點可以有多于一個兒子 樹的操作：各種遍歷搜索,例6 多叉路口交通燈管制 多叉路口需要設幾種顏色的燈才能使車輛互不相撞且車流量最大,需要：表示圓

6、圈（道路） 表示邊（是否沖突） 給出染色方法,著色問題,例7 最短路徑問題 油田鋪設管道，把原油送到加工廠，要求所鋪設的管道最短,特點：任何兩個數(shù)據(jù)之間都可以有關系(單向、雙向) 操作：遍歷、染色、最短路徑 這種數(shù)學模型稱為圖,用計算機解決一個實際問題的步驟：,問題分析 建立模型 確定算法 設計程序 上機調(diào)試 結(jié) 果,數(shù)據(jù)結(jié)構(gòu) 是一門研究計算機的操作對象 以及操作對象之間的關系 和對操作對象實施的典型操作 的學科,1.1 什么是數(shù)據(jù)結(jié)構(gòu),操作對象 關系 典型操作,1.2 基本概念和術語,數(shù)據(jù)：Data 數(shù)據(jù)是計算機化的信息（對現(xiàn)實世界的事物采用計算機能夠識別、存儲和處理的形式所進行的描述） 數(shù)

7、值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù),數(shù)據(jù)元素：Data Element 數(shù)據(jù)的基本單位，如格局、結(jié)點 通常作為一個整體進行考慮和處理 數(shù)據(jù)元素的組成成員稱為數(shù)據(jù)項,數(shù)據(jù)項：Data Item 數(shù)據(jù)的最小單位 一個數(shù)據(jù)元素由多個數(shù)據(jù)項組成,數(shù)據(jù)對象：Data Object 具有相同性質(zhì)的數(shù)據(jù)元素的集合 如所有書目、所有撲克牌、所有格局、所有道路,數(shù)據(jù)類型：Data Type,數(shù)據(jù)結(jié)構(gòu)：Data Structure,（1）相互間存在一種或多種特定關系的數(shù)據(jù)元素的集合 一種或多種關系稱為結(jié)構(gòu) 有4種基本結(jié)構(gòu)：,struct student /數(shù)據(jù)類型 int num; char name12; char sex

8、; int age; int score5; int scoresum; s50; /數(shù)據(jù)對象,數(shù)據(jù)項,s0、s1、s2、. 數(shù)據(jù)元素 數(shù)組-數(shù)據(jù)關系的表示,struct stu /數(shù)據(jù)類型 int num; int score; struct stu *next; *head,*p1;,數(shù)據(jù)項,*p1、*head、. 數(shù)據(jù)元素 鏈表-數(shù)據(jù)關系的表示 head為首的數(shù)據(jù)元素構(gòu)成數(shù)據(jù)對象,（2）數(shù)據(jù)元素+關系 數(shù)據(jù)結(jié)構(gòu)是一個二元組： Data_structure=(D, S) D:數(shù)據(jù)元素的有窮集合 S:數(shù)據(jù)之間有窮關系的集合,例：DS1=（D，S） D=V1,V2,V3, V4 S=, , ,

9、 , ,其中： 關系的描述是數(shù)據(jù)元素之間的邏輯關系， 稱為數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素及其邏輯關系在機內(nèi)的表示 稱為數(shù)據(jù)的物理結(jié)構(gòu)，或數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu),a1,a2,a3,a4,a5,邏輯結(jié)構(gòu),物理結(jié)構(gòu)（一）,物理結(jié)構(gòu)（二）,a1,a2,a3,a4,a5,a3,a4,a2,a5,a1,0,關系的表示方法,數(shù)據(jù)的存儲結(jié)構(gòu)借助于高級語言中的數(shù)據(jù)類型來描述,順序映象 非順序映象,鏈式存儲結(jié)構(gòu),（3）數(shù)據(jù)之間的結(jié)構(gòu)關系 它包括數(shù)據(jù)的邏輯結(jié)構(gòu)和 數(shù)據(jù)的物理結(jié)構(gòu) （4）是一類普通數(shù)據(jù)的表示及其相關操作 （5）根據(jù)各種不同的數(shù)據(jù)集合和數(shù)據(jù)之間的關系研究如何表示、存儲、操作這些數(shù)據(jù)的技術,研究數(shù)據(jù)結(jié)構(gòu)

10、從三個方面進行： （1）邏輯結(jié)構(gòu) （2）存儲結(jié)構(gòu) （3）操作（運算） 對數(shù)據(jù)進行的處理， 定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上 具體實現(xiàn)于數(shù)據(jù)的存儲結(jié)構(gòu),引用,引用（reference）作用是為變量起一個別名 例如：int a; int 說明：（1）b是一個引用變量，它的作用與a相同 （2）b與a占用相同的內(nèi)存空間,假設變量a的地址為1000，值為123,定義了int int ,（5）定義引用變量的作用是使得函數(shù)調(diào)用時， 實參與形參之間不僅有傳值方式，還有傳地址方式 引用變量做參數(shù)，相當于傳地址,void swap(int ,輸出： a=4,b=3,比較： void swap1(int x, int y)

11、int t; t=x; x=y; y=t; void swap2(int *x, int *y) int t; t=*x; *x=*y; *y=t; ,void f (int x, int y, int ,抽象數(shù)據(jù)類型 (ADT: Abstract Data Types),數(shù)據(jù)類型 int char float struct,描述數(shù)據(jù)邏輯結(jié)構(gòu)的工具,(1)ADT是指一個數(shù)學模型及其在該模型上的一組操作 (2)ADT只考慮數(shù)學模型上數(shù)據(jù)元素之間的邏輯關系， 而忽略其物理結(jié)構(gòu),(3)ADT是一個邏輯數(shù)據(jù)類型以及定義在該類型上的一組操作，每個操作由它的輸入/出定義，而隱藏其實現(xiàn)細節(jié)，如定義一個整數(shù)類

12、型及在整數(shù)類型上的操作,(4)ADT由三元組構(gòu)成：（D，S，P） D 數(shù)據(jù)對象 S 關系 P 操作集,(5)約定格式為： ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關系： 基本操作： ADT 抽象數(shù)據(jù)類型名,基本操作的格式： 基本操作名（參數(shù)表） 初始條件： 操作結(jié)果：,形式參數(shù)： 賦值參數(shù)-傳值 引用參數(shù)-傳地址,ADT List 數(shù)據(jù)對象:D=aiaiElemSet,i=1,2,3，,n,n0 數(shù)據(jù)關系:R=ai-1 ,aiD,i=2,3， ,n 基本操作: ReadFile( 初始條件:表L已經(jīng)存在. 操作結(jié)果:在表L中刪除元素a,PrintList(L); 初始條件:表L已經(jīng)存在. 操作

13、結(jié)果:依次輸出表L的所有元素 ,1. 學生成績管理系統(tǒng) 2電話簿管理系統(tǒng) 3學校圖書管理系統(tǒng) 4職工工資管理系統(tǒng),功能:輸入、查詢、修改、打印,/定義表示學生結(jié)構(gòu)體 struct stu int num; char name10; char class10; int score5; ;,/定義表示聯(lián)系方式的結(jié)構(gòu)體 struct call char name10; char class10; int telephone; char mobile12; char addr20; ;,/定義表示圖書結(jié)構(gòu)體 struct book int num; char name10; char author10

14、; char publish20; struct date day; ;,/定義表示職工結(jié)構(gòu)體 struct employe int num; char name10; float jiben; float jiangjin; float butie; ;,1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn),1原則： 通過已有的類型定義或組合成新的類型 用類C語言描述,2C+引用參數(shù),3各種預定義和約定,數(shù)據(jù)元素的類型為ElemType 數(shù)據(jù)存儲結(jié)構(gòu)用typedef定義,typedef struct int num; char name10; char sex; int age; . ElemType;,用,基

15、本操作的描述 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） / 算法說明 語句序列 /函數(shù)名,int f1(int n, int ,Status f1(int n, int ,1.4 算法和算法分析,一、算法的概念 算法是解決某一個/一類問題的一個有序的有窮序列，該序列確定了解決問題的方法和步驟。,例：用輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公因子 1輸入m和n 2若mn, 則交換m和n 3m除以n，余數(shù)為r 4若r=0，則n為最大公因子，輸出n，否則執(zhí)行5 5nm，rn，轉(zhuǎn)3,三、算法設計的要求： 正確性 可讀性 健壯性/容錯性 有效性,二、算法的特征%,例：用輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公因子 1輸入m和n 2若

16、mn, 則交換m和n 3m除以n，余數(shù)為r 4若r=0，則n為最大公因子，輸出n，否則執(zhí)行5 5nm，rn，轉(zhuǎn)3,四、算法的效率,sum=0; for(i=1; i=n; i+) term=1; for(j=1; j=i;j+) term=term*j; sum=sum+term; ,sum=0;term=1; for(i=1; i=n; i+) term=term*i; sum=sum+term; ,決定因素: 1.策略 2.問題的輸入規(guī)模 3.編譯產(chǎn)生的代碼質(zhì)量 4.機器指令執(zhí)行的速度,1.策略 2.問題的輸入規(guī)模,1效率：時間、空間,2時間復雜度 算法中最基本、主要的運算執(zhí)行的次數(shù)作為算

17、法執(zhí)行時間長短的度量稱為算法的時間復雜度，它是問題規(guī)模的函數(shù)，記作T(n) 一般以量級的形式來討論時間復雜度 一個函數(shù)f(n)是g(n) 級的，當且僅當存在一個常數(shù)c和一個整數(shù)n0 (c0, n00)，對于一切nn0，有 f(n) c g(n) 成立 記作：O(g(n),事先估計 事后估計,事先估計,#define N 10 main( ) int i, j, t, aN; printf(“input 10 number:”); for(i=0; iaj+1) t=aj; aj=aj+1; aj+1=t; printf(“the sorted number:n”); for(i=0; iN;

18、i+) printf(“%3d”,ai); printf(“n”); ,3空間復雜度 S（n）,4效率對算法的影響,O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn),例：假設CPU每秒處理10 6 個指令，對于輸入規(guī)模為108的問題，時間代價T(n) = 2n2的算法要運行多長時間？,操作次數(shù)為T(n) = T(108) = 2(108)2 = 21016 運行時間為21016/106 = 21010秒 每天有86,400秒，因此需要231,481 天(634年）,例：假設CPU每秒處理106個指令，對于輸入規(guī)模為108的問題，時間代價為nlog n 的算法要運行多長時間？,操作次數(shù)為 T(n) = T(108) = 108 log 108 = 2.66109 運行時間為2.66109/106 = 2.66103秒= 44.33分鐘,例：設CPU每秒處理106個指令，則每小時能夠解決的最大問題規(guī)模 T(n) / 106 3600 對T(n) = 2n2， 即2n2 3600 106 n 42 , 426 對T(n) = n