第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.

Slides:



Advertisements
Similar presentations
面向对象程序设计 、. 第二章 面向对象的分析与设计 学习目标 1 确定系统中的对象 2 确定对象的属性及操作 3 测试对象的有效性 4 区分对象和类 5 了解面向对象的编程和过程化编程之间的区别 6 了解封装的主要好处 7 了解软件开发的主要步骤.
Advertisements

<<會計資訊系統課程講義>> 統一塑模語言(UML)語法精要 -- 物件導向概念、需求分析及系統分析
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
基本概論 Basic concepts.
数据结构 杨鹏宇 QQ: 版权所有,转载或翻印必究
第一章 绪论.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
Introduction 基本概念 授課老師:蕭志明
Ch02物件導向程式設計 物件導向系統分析與設計.
第八章 信息系统开发概述.
数据结构(C语言版) Data Structure
算法设计与分析 Algorithm Design and Analysis
Performance Evaluation
D、結構化技術 主要的結構化技術 結構化程式設計 (Structured Programming)
第一章 面向对象程序设计.
課程名稱:程式設計 授課老師:________
程設一.
第二章 JAVA语言基础.
類別與物件 Class & Object.
第9章 面向对象方法学引论 9.1 面向对象方法学概述 9.2 面向对象的概念 9.3 面向对象建模 9.4 对象模型 9.5 动态模型
新世代計算機概論 第14章 程式語言.
第八章 分析與設計階段 – 物件導向設計(OOD)
第5章 面向对象程序设计 本章要点 5.1 面向对象程序设计概述 5.2 Java语言的面向对象程序设计 5.3 方法的使用和对象数组
第2章 建立Visual Basic應用程式 2-1 如何設計Visual Basic應用程式 2-2 建立主控台應用程式
第2章 建立Visual Basic應用程式.
物件導向程式設計 (Object-Oriented rogramming)
Classes Lecturer: 曾學文.
第 1 章 演算法分析.
第16章 VB.NET物件導向與.NET Framework
本單元介紹何謂變數,及說明變數的宣告方式。
Java软件设计基础 5. 继承与多态.
程式撰寫流程.
C++ 與 物件導向 程式設計概念簡介 魏天君 2018/12/3.
面向对象程序设计 、.
第9章 類別圖與物件圖 9-1 類別圖與物件圖的基礎 9-2 類別圖的符號 9-3 類別關係 9-4 物件圖 9-5 繪製類別圖與物件圖
Java程序设计 第9章 继承和多态.
CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司.
Visual Basic 6.0 ——程序设计.
软件学院 张 慧 清华大学软件学院.
Php class 組員: 賴羿陵 林昱廷 莊正暉 張雅晴
Java程序设计 第2章 基本数据类型及操作.
作业 考核方式 书面作业:每个单元3-5个题,树、图和查找单元5-10个题。 上机作业:从第三周起每周一次 , 大约14次
鄧姚文 資料結構 第一章:基本概念 鄧姚文
Week 2: 程式設計概念與 演算法的效能評估
JAVA 编 程 技 术 主编 贾振华 2010年1月.
資料結構與C++程式設計進階班 課程大綱 講師:洪安.
第1章 绪论 2019/4/16.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
软件设计任务 从工程管理的角度来看,软件设计分两步完成。 概要设计,将软件需求转化为数据结构和软件的系统结构。
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
程序基础 2019/4/25.
程式語言 程式語言發展史 資料型態 程式指令 程序定義和使用.
計算機概論 跨越講義 第4章 基本視窗程式應用 4-1 程式語言簡介 4-2 結構化VS物件導向程式設計
演算法時間複雜度 (The Complexity of Algorithms)
講師:郭育倫 第2章 效能分析 講師:郭育倫
第二章 Java语法基础.
資料結構簡介 綠園.
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
Review 1~3.
第二章 Java基本语法 讲师:复凡.
方法進階及物件導向基礎 Lecturer: 楊昌樺.
第6單元 6-1 類別的繼承 (Class Inheritance) 6-2 抽象類別 (Abstract Class)
JAVA 程式設計與資料結構 第三章 物件的設計.
變數、資料型態、運算子.
第2章 Java语言基础.
對於成員(member)存取權的限制 成員的資料被毫無限制的存取,任誰都可以指定任意值給成員,Java語言為了防止這種現象的產生,規定:有一種成員的資料不能任由類別外部的任何人隨意存取。
面向对象程序设计 C++教程 西安工业大学 于帆.
Data Structure.
Summary
Presentation transcript:

第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java

資料結構簡介 資料與資訊 演算法 演算法的條件

資料與資訊 所謂資料(Data),指的就是一種未經處理的原始文字(Word)、數字(Number)、符號(Symbol)或圖形(Graph)等,它所表達出來的只是一種沒有評估價值的基本元素或項目。 當資料經過處理(Process),例如以特定的方式有系統的整理、歸納甚至進行分析後,就成為「資訊」(Information)。

演算法 日常生活中有許多工作都可以利用演算法來描述,例如員工的工作報告、寵物的飼養過程、學生的功課表等。 資料結構與演算法是程式設計中最基本的內涵。 程式是否能清楚而正確的把問題解決,取決於演算法。 所以可以這麼認為:「資料結構加上演算法等於可執行的程式。」 日常生活中有許多工作都可以利用演算法來描述,例如員工的工作報告、寵物的飼養過程、學生的功課表等。

演算法的條件 當認識了演算法的定義後,我們還要說明演算法所必須符合的五個條件:

演算法的五項條件 演 算 法 特 性 內 容 與 說 明 輸入(Input) 0個或多個輸入資料,這些輸入必須有清楚的描述或定義。 輸出(Output) 至少會有一個輸出結果,不可以沒有輸出結果。 明確性(Definiteness) 每一個指令或步驟必須是簡潔明確而不含糊的。 有限性 (Finiteness) 在有限步驟後一定會結束,不會產生無窮迴路。 有效性(Effectiveness) 步驟清楚且可行,能讓使用者用紙筆計算而求出答案。

常用的演算法 一般文字敘述:中文、英文、數字等。文字敘述法的特色在使用文字或語言敘述來說明演算步驟。例如以下就是一個學生小華早上上學並買早餐的簡單文字演算法:

虛擬語言(Pseudo-Language):接近高階程式語言的寫法,也是一種不能直接放進電腦中執行的語言。一般都需要一種特定的前置處理器(preprocessor),或者用手寫轉換成真正的電腦語言,經常使用的有SPARKS、PASCAL-LIKE等語言。以下是用SPARKS寫成的鏈結串列反轉的演算法: Procedure Invert(x)   Px;QNil;   WHILE P≠NIL do      rq;qp;  pLINK(p);  LINK(q)r;    END   xq; END

表格或圖形:如陣列、樹狀圖、矩陣圖等。

流程圖:流程圖( Flow Diagram) 算是一種通用的表示法,也有的圖型符號。例如請您輸入一個數值,並判別是奇數或偶數。

程序語言:目前演算法也能夠直接以可讀性高的高階語言來表示,例如Visual Basic語言、C語言、C++語言、Java語言。

演算法和程序 演算法和程序是有所區別,因為程式不一定要滿足有限性的要求,如作業系統或機器上的運作程式。 除非當機,否則永遠在等待迴路(waiting loop),這也違反了演算法五大原則之一的「有限性」。 只要是演算法都能夠利用程式流程圖表現,但因為程式流程圖可包含無窮迴路,所以無法利用演算法來表達。

認識程式設計 資料結構與演算法必須透過程式(Program)的轉換,才能真正由電腦系統來執行。 所謂程式,是由合乎程式語言語法規則的指令所組成,而程式設計的目的就是透過程式的撰寫與執行來達到使用者的需求。

程式語言的好壞 可讀性(Readability)高:閱讀與理解都相當容易。 平均成本低:成本考量不侷限於編碼的成本,還包括了執行、編譯、維護、學習、除錯與日後更新等成本。 可靠度高:所撰寫出來的程式碼穩定性高,不容易產生邊際錯誤(Side Effect)。 可撰寫性高:對於針對需求所撰寫的程式相對容易。

程式設計步驟 需求認識(requirements):了解程式所要解決的問題是什麼,有那些輸入及輸出等。 設計規劃(design and plan):根據需求,選擇適合的資料結構,並以任何的表示方式寫一個演算法以解決問題。 分析討論(analysis and discussion):思考其他可能適合的演算法及資料結構,最後再選出最適當的標的。 編寫程式(coding):把分析的結論,寫成初步的程式碼。 測試檢驗(verification):最後必需確認程式的輸出是否符合需求,這個步驟得細步的執行程式並進行許多的相關測試。

資料型態簡介 基本資料型態(atomic data type) 結構型資料型態(structure data type) 抽象資料型態(Abstract Data Type, ADT)

基本資料型態(atomic data type) 或稱為實質資料型態(physical data type),也就是一個基本的資料實體,例如一般程式語言中的整數、實數、字元等等。 像C語言的基本資料型態為整數(int)、字元(char)、單精度浮點數(float)與倍精度浮點數(double)。

結構型資料型態 (structure data type) 或稱為虛擬資料型態(virtual data type),比實質資料型態更高一層,是指一個資料實體包含其他的資料型態。 例如字串(string)、集合(set)、陣列(array)。

抽象資料型態 (Abstract Data Type, ADT) 比結構型資料型態更高一層,ADT是指定義一些結構型資料型態所具備的數學運算關係,使用者毋需考慮到ADT的製作細節,只要知道如何使用即可。 通常出現於物件導向程式語言(OOP) 中,例如堆疊(stack)或佇列(queue)就是一種很典型的ADT模式。

結構化程式設計 主要是以「由下而上法」與「由上而下法」為主。 「由下而上法」是指程式設計師將整個程式需求最容易的部份先編寫,再逐步擴大來完成整個程式。 「由上而下法」將整個程式需求從上而下、由大到小逐步分解成較小的單元,或稱為「模組」 (module)。 核心精神,就是「由上而下設計」 與「模組化設計」。 例如在Pascal語言中,這些模組稱為「程序」 (Procedure),C語言中稱為「函式」 (Function)。

結構化程式設計控制流程 流程結構名稱 概念示意圖 [循序結構] 逐步的撰寫敘述。 [選擇結構] 依某些條件做邏輯判斷。 [重複結構] 依某些條件決定是否重複執行某些敘述。

物件導向程式設計 「物件導向程式設計」 (Object-Oriented Programming, OOP) 是近年來相當流行的一種新興程式設計理念。 它主要讓我們在設計程式時,能以一種更生活化、可讀性更高的設計觀念來進行,並且所開發出來的程式也較容易擴充、修改及維護。 常見的物件導向語言包括C++、Java等語言。

抽象化動作說明表 名稱 特 色 與 說 明 屬性 屬性(attribute)是指物件的靜態外觀描述,例如一輛車子的顏色、          特 色 與 說 明 屬性 屬性(attribute)是指物件的靜態外觀描述,例如一輛車子的顏色、 大小等。就如同於JAVA程式中的類別成員資料(member data)。 方法 方法(method)是指物件中的動態回應方式,例如車子可以開動、停 止。就是一種行為模式,是用來代表一個物件的功能,也就是JAVA 中的類別成員方法(member method)。 事件 事件(event)是指物件可以針對外部事件做出各種反應,譬如車子沒油 時,引擎就會停止,當然物件也可以主動地發出事件訊息。例如 JAVA程式中的視窗元件就可以對事件做出反應與處理。

物件導向程式設計 封裝(Encapsulation) 繼承(Inheritance) 多形(Polymorphism)

封裝(Encapsulation) 是利用「類別」來實作「抽象化資料型態」(ADT)。 「抽象化」,就是將代表事物特徵的資料隱藏起來,並定義一些方法來做為操作這些資料的介面,也符合了資訊隱藏的意義,就稱為「抽象化資料型態」。 可將其資料成員定義為私有的(private),而將用來運算或操作資料的函式成員則定義為公有的(public)或受保護的(protected)來實現資訊隱藏的功能,這就是「封裝」(encapsulation)的作用。

繼承(Inheritance) 在繼承關係中,被繼承者稱為「基礎類別」或「父類別」,而繼承者則稱「衍生類別」或「子類別」。 而繼承允許我們去定義一個新的類別來繼承既存的類別,進而使用或修改繼承而來的方法,並可在子類別中加入新的資料成員與函式成員。

多形(Polymorphism) 「多形」也是物件導向設計的重要特性,也稱為「同名異式」。 功能可讓軟體在發展和維謢時,達到充份的延伸性。 最直接的定義就是讓具有繼承關係的不同類別物件,可以呼叫相同名稱的成員函式,並產生不同的反應結果。

演算法效能分析 對一個程式(或演算法)效能的評估,經常是從時間與空間兩種因素來做考量。 時間方面是指程式的執行時間,稱為「時間複雜度」(Time Complexity)。 空間方面則是此程式在電腦記憶體所佔的空間大小,稱為「空間複雜度」(Space Complexity)。

時間複雜度 例如程式設計師可以就某個演算法的執行步驟計數來衡量執行時間的標準,但是同樣是兩行指令: 由於涉及到變數儲存型態與運算式的複雜度,所以真正絕對精確的執行時間一定不相同。 這時可以利用一種「概量」的觀念來做為衡量執行時間,我們就稱為「時間複雜度」(Time Complexity)。 a=a+1與a=a+0.3/0.7*10005

時間複雜度詳細定義 在一個完全理想狀態下的計算機中,我們定義一個T(n)來表示程式執行所要花費的時間,其中n代表資料輸入量。 當然程式的執行時間或最大執行時間(Worse Case Executing Time)作為時間複雜度的衡量標準,一般以Big-oh表示。 由於分析演算法的時間複雜度必須考慮它的成長比率(Rate of Growth)往往是一種函數,而時間複雜度本身也是一種「漸近表示」(Asymptotic Notation)。

Big-oh O(f(n))可視為某演算法在電腦中所需執行時間不會超過某一常數倍的f(n),也就是說當某演算法的執行時間T(n)的時間複雜度(Time Complexity)為O(f(n))(讀成Big-oh of f(n)或Order is f(n))。 意謂存在兩個常數c與n0,則若n≧n0,則T(n)≦cf(n),f(n)又稱之為執行時間的成長率(rate of growth)。

範例 1.3.1 假如執行時間T(n)=3n3+2n2+5n,求時間複雜度為何? 範例 1.3.2 請證明   =O(n2)

範例1.3.3 考慮下列x←x+1的執行次數。 (1) (3) : x←x+1 : for i←1 to n do : (2) for i←1 to n do :  x←x+1 : end (3) for i←1 to n do :     for j←1 to m do     :     x←x+1     :    end : end

範例1.3.4 範例1.4.5 求下列演算法中x←x+1的執行次數及時間複雜度。 請決定以下片斷程式的執行時間: for i←1 to n do   j←i   for k←j+1 to n do x←x+1   end end k=100000 while k<>5 do   k=k DIV 10 end

常見Big-oh Big-oh 特 色 與 說 明 O(1) 稱為常數時間(constant time),表示演算法的執行時間是一個常數倍。         特 色 與 說 明 O(1) 稱為常數時間(constant time),表示演算法的執行時間是一個常數倍。 O(n) 稱為線性時間(linear time),執行的時間會隨資料集合的大小而線性成長。 O(log2n) 稱為次線性時間(sub-linear time),成長速度比線性時間還慢,而比常數時間還快。 O(n2) 稱為平方時間(quadratic time),演算法的執行時間會成二次方的成長。 O(n3) 稱為立方時間(cubic time),演算法的執行時間會成三次方 的成長。 O(2n) 稱為指數時間(exponential time),演算法的執行時間會成 二的n次方成長。 O(nlog2n) 稱為線性乘對數時間,介於線性及二次方成長的中間之行為 模式。

對於n≥16時,時間複雜度的優劣比較關係如下: 範例1.3.6 決定下列的時間複雜度(f(n)表執行次數) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n) a.f(n)=n2logn+logn    b.f(n)=8loglogn c.f(n)=logn2 d.f(n)=4loglogn e.f(n)=n/100+1000/n2 f.f(n)=n!

Ω(omega) Ω是一種時間複雜度的漸近表示法,以下是Ω的定義: 範例1.3.7 對f(n)= Ω(g(n))(讀作”big-omega of g(n)”),意思是存在常數c和n0,對所有的n值而言,n>= n0時,f(n)≧cg(n)均成立。 例如f(n)=5n+6,存在c=5 n0=1,對所有n≧1時,5n+6≧5n,因此f(n)= Ω(n)而言,n就是成長的最大函數。 範例1.3.7 f(n)=6n2+3n+2,請利用Ω來表示f(n)的時間複雜度。

θ(theta) 是一種比Big-O與Ω更精確時間複雜度的漸近表示法。定義如下: f(n)= θ(g(n))(讀作”big-theta of g(n)”),意是存在常數c1、c2、n0,對所有的n≧n0時,c1g(n)≦f(n)≦c2g(n)均成立。換句話說,當f(n)=θ(g(n))時,就表示g(n)可代表f(n)的上限與下限。 例如以f(n)=n2+2n為例,當n≧0時,n2+2n≦3n2,可得f(n)=O(n2)。同理,n≧0時,n2+2n≧n2,可得f(n)=Ω(n2)。所以f(n)=n2+2n=θ(n2)

物件導向程式設計與Java JAVA是一種純物件導向程式設計(Object-Oriented Programming, OOP)語言。 程式中所有相關的程式運算或執行動作,都是利用由類別所產生的物件來控制。

類別與物件 通常物件並不會無憑空產生,它必須有一個可以依據的原型(Prototype),而這個原型就是一般在物件導向程式設計中所稱的「類別」(Class)。 在JAVA中,物件的實作宣告方式如下: new:依照類別建構子所代表的參考型別,配置記憶體空間,以建立該類別的實體物件。 建構子(constructor):用來建立該類別的物件,並在建立的同時設定初始值。 類別名稱 物件(變數)名稱 = new 建構子();

範例程式:ch01_01.java

物件導向特性 名稱 特 色 與 說 明 封裝 使用類別來製作抽象化的資料型態(abstract data type,         特 色 與 說 明 封裝 使用類別來製作抽象化的資料型態(abstract data type, ADT),也就是利用類別將資料和用來處理資料的方法 包裝起來。 繼承 繼承是使所謂的衍生類別能完全地使用基礎類別的成員 資料與成員方法。 多形 多形或稱為「同名異式」(Polymorphism),就是讓具 有繼承關係的不同類別物件,可以呼叫相同名稱的成員 方法,並產生不同的反應結果。

資料封裝 關鍵字名稱 特 色 與 說 明 private 以private(私有的)所宣告的資料或方法,僅能被同一類別中的成員所使用。       特 色 與 說 明   private 以private(私有的)所宣告的資料或方法,僅能被同一類別中的成員所使用。  protected 以protected所宣告的資料或方法,只可以在同一個類別,或是衍生類別或同一套件中,作有限度地存取動作。  public 以public所宣告的各種資料或方法,可以被所有外部程式、類別或物件使用。

程式宣告片段 private int usePassword //宣告整數型態變數userPassword 為私有的資料成員 protected getPassword() //宣告類別方法getPassword為受 保護的成員方法 public class checkPassword //宣告類別checkPassword為公開 的類別

類別繼承 繼承就類似遺傳的觀念,當物件導向技術以這種生活實例去定義其功能時,則稱為繼承(inheritance)。 這種繼承模式在JAVA平台下的宣告語法如下: 存取修飾子 class 衍生類別名稱 extends 基礎類別名稱

存取修飾子 它代表的意義為:相同「套件」(package)中的所有類別都能存取此類別。 存取修飾子的關鍵字如下表: 關鍵字 特 色 說 明 特 色 說 明 public (公開的) 代表所有類別皆可存取此類別。 abstract(抽象的) 代表此類別不能被實體化(建立物件)。 final(最終的) 代表此類別無法再被重新定義(繼承)。

範例程式:ch01_02.java

物件多形 是利用類別繼承架構的基礎,先建立一個內容為「null」的基本類別物件,讓使用者可以將它轉變成為各種衍生類別物件,進而加以控制所有衍生類別的「同名異式」方法。

範例程式:ch01_03.java

抽象類別 宣告語法如下: abstract class 類別名稱 { … abstract 傳回值的資料型態 成員方法(引數列); }

範例程式:ch01_04.java

介面 宣告語法表列如下: interface 介面名稱 { … 傳回值的資料型態 成員方法(); }

範例程式:ch01_05.java