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

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

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

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

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 文件系統,/ (root),bin,lib,user,etc,math,ds,clg,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,這類問題的數學模型稱為樹（樹型結構、層次結構） 樹的特點： 除根外每個結點有唯一一個雙親(上級，祖先) 除葉子結點外，每個結點可以有多于一個兒子 樹的操作：各種遍歷搜索,例6 多叉路口交通燈管制 多叉路口需要設幾種顏色的燈才能使車輛互不相撞且車流量最大,需要：表示圓

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

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

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

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

10、從三個方面進行： （1）邏輯結構 （2）存儲結構 （3）操作（運算） 對數據進行的處理， 定義在數據的邏輯結構上 具體實現于數據的存儲結構,引用,引用（reference）作用是為變量起一個別名 例如：int a; int 說明：（1）b是一個引用變量，它的作用與a相同 （2）b與a占用相同的內存空間,假設變量a的地址為1000，值為123,定義了int int ,（5）定義引用變量的作用是使得函數調用時， 實參與形參之間不僅有傳值方式，還有傳地址方式 引用變量做參數，相當于傳地址,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 ,抽象數據類型 (ADT: Abstract Data Types),數據類型 int char float struct,描述數據邏輯結構的工具,(1)ADT是指一個數學模型及其在該模型上的一組操作 (2)ADT只考慮數學模型上數據元素之間的邏輯關系， 而忽略其物理結構,(3)ADT是一個邏輯數據類型以及定義在該類型上的一組操作，每個操作由它的輸入/出定義，而隱藏其實現細節，如定義一個整數類

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

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

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

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

16、mn, 則交換m和n 3m除以n，余數為r 4若r=0，則n為最大公因子，輸出n，否則執行5 5nm，rn，轉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.問題的輸入規模 3.編譯產生的代碼質量 4.機器指令執行的速度,1.策略 2.問題的輸入規模,1效率：時間、空間,2時間復雜度 算法中最基本、主要的運算執行的次數作為算

17、法執行時間長短的度量稱為算法的時間復雜度，它是問題規模的函數，記作T(n) 一般以量級的形式來討論時間復雜度 一個函數f(n)是g(n) 級的，當且僅當存在一個常數c和一個整數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 個指令，對于輸入規模為108的問題，時間代價T(n) = 2n2的算法要運行多長時間？,操作次數為T(n) = T(108) = 2(108)2 = 21016 運行時間為21016/106 = 21010秒 每天有86,400秒，因此需要231,481 天(634年）,例：假設CPU每秒處理106個指令，對于輸入規模為108的問題，時間代價為nlog n 的算法要運行多長時間？,操作次數為 T(n) = T(108) = 108 log 108 = 2.66109 運行時間為2.66109/106 = 2.66103秒= 44.33分鐘,例：設CPU每秒處理106個指令，則每小時能夠解決的最大問題規模 T(n) / 106 3600 對T(n) = 2n2， 即2n2 3600 106 n 42 , 426 對T(n) = n