資料結構 Fundamentals of Data Structures in C++

資料結構 Fundamentals of Data Structures in C++
p.1 資料結構 Fundamentals of Data Structures in C++ 透過 C++ 了解資料結構的基本概念學習 Abstract Data Type 練習與資料結構相關的基本演算法

資料結構教材介紹課本：Fundamentals of Data Structures in C++
p.2 資料結構教材介紹課本：Fundamentals of Data Structures in C++ 作者：Ellis Horowitz, Sartaj Sahni, Dinesh Mehta 中譯本：基礎資料結構使用C++ 戴顯權譯中譯本：資料結構－使用C++/余建政,謝志明

題庫介紹這學期開始我會盡量我以前出過的題目與答案放到這個題庫裡面來，歡迎同學使用。
p.3 題庫介紹這學期開始我會盡量我以前出過的題目與答案放到這個題庫裡面來，歡迎同學使用。上課時若需要更多的範例，我會從這裡拿一些相關的題目出來當例子。考試時可能也會從這裡的題目拿出來、修改些數據之後使用。這個題庫的答案都只提供 odp 檔。我不會提供其他格式的檔案，因為推廣 open document 檔案格式也是它的重要目的之一。目前資料結構的題目有八十幾題，希望以後會增加得更多。若有什麼重要的題目想知道答案的話，也可以提供給我，我若有時間、做得出答案時也會放進去。

尊重智慧財產權(學校要我們宣導的) 自本學期起課程綱要內容，教科書旁新增〝請遵守智慧財產權之規定及勿非法影印教材〞。
p.4 尊重智慧財產權(學校要我們宣導的) 自本學期起課程綱要內容，教科書旁新增〝請遵守智慧財產權之規定及勿非法影印教材〞。請任課教師在教學過程中適當引導學生使用教科書，提高學生購置合法教科書之意願。請任課教師在開學初，於授課中明確告知學生勿使用非法影印教科書。

資料結構 Fundamentals of Data Structures in C++
p.5 資料結構 Fundamentals of Data Structures in C++ 評分標準：平常分數 50%(作業、測驗、出席) 期中考 20% 期末考 30%

上課方式：單槍投影機+OpenOffice簡報 +麥克風講義：只提供 odp 與 pdf 講義
上課基本介紹上課方式：單槍投影機+OpenOffice簡報 +麥克風講義：只提供 odp 與 pdf 講義作業：寫 C++ 程式、自己出習題並寫出解答。隨堂測驗：不定期舉行上課秩序要求：上課時請不要聊天與吵鬧

為何使用 OpenOffice 讓同學不需購買或使用盜版的 MS Office 軟體就可以看講義。鼓勵使用正版軟體
鼓勵使用開放式標準 opendocument 鼓勵使用自由軟體如果您一定只要使用 powerpoint 來看講義時怎麼辦？可使用 Sun 出的一個 ODF plugin for MS Office 的程式，就可以用MS Office 看講義。請其他同學用 openoffice 幫您將 odp 檔轉成 ppt 檔找我舊的講義

p.8 教師自我介紹姓名：洪春男電話：轉 2410, 辦公室：H311 Homepage: 已婚、一個女兒(七歲八個月) 信仰：基督徒，芳苑教會，基甸會員

課程大綱 Basic concepts Arrays Stacks and Queues Linked Lists Trees Graphs
Sorting Hashing Heap Structures Search Structures

Chapter 1 Basic Concepts
1.1 Overview(總論): System Life Cycle 1.2 Object-Oriented Design(物件導向設計) 1.3 Data Abstraction and Encapsulation(資料抽象化和封裝化) 1.4 Basics of C++(C++基礎) 1.5 Algorithm Specification(演算法規格) 1.6 Performance Analysis(執行效率分析和測量)

Overview: System Life Cycle
p.11 Overview: System Life Cycle How to create a program ? Requirements? Analysis: bottom-up vs. to-down Design: abstract data type & algorithm specification language independent Refinement and coding Verification Correctness proofs Testing Error Removal

1.2 Object-Oriented Design
p.12 1.2 Object-Oriented Design 1.2.1 Algorithmic Decomposition Versus Object-Oriented Decomposition Algorithmic or functional decomposition views software as a process. Object-oriented decomposition views software as a set of well-defined objects that model entities in the application domain. The principal advantage of object-oriented decomposition is that is encourages the reuse of software.

p.13 1.2 Object-Oriented Design 1.2.2 Fundamental Definitions and Concepts of Object-Oriented Programming Definition: An object is an entity that performs computations and has a local state. It may therefore be viewed as a combination of data and procedural elements. Definition: Object-oriented programming is a method of implementation in which Objects are the fundamental building blocks. Each object is an instance of some type(or class). Classes are related to each other by inheritance relationships.

p.14 1.2 Object-Oriented Design Definition: A language is said to be an object-oriented language if It supports objects. It requires objects to belong to a class. It supports inheritance.

p.15 1.2 Object-Oriented Design 1.2.3 Evolution of programming languages and history of C++ First Generation Languages: FORTRAN Second Generation Languages: Pascal, C Third Generation Languages: Modula Fourth Generation Languages: object-oriented C 語言被廣泛使用的原因：efficient, flexible, availabe.

1.3 Data Abstraction and Encapsulation
Definition: Data Encapsulation or Information Hiding is the concealing of the implementation details of a data object from the outside world. Definition: Data Abstraction is the separation between the specification of a data object and its implementation. 基本資料結構：int, char, float, double，加上short, long, signed, unsigned 等限定字 Arrays 與 structs、classes 的差別

Definition: A data type is a collection of objects and a set of operations that act on those objects. Definition: A abstract data type(ADT) is a data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations.

ADT 1.1: Abstract data type NaturalNumber
ADT NaturalNumber is objects: an ordered subrange of the integers starting at zero and ending at themaximum integer(MAXINT) on the computer. Functions: for all x, y Î NaturalNumber; true, false Î Boolean and where +, -, <, ==, and = are the usual integer operations Zero(): NaturalNumber ::= 0 IsZero(x): Boolean ::= if(x == 0) IsZero = true else IsZero = false Add(x, y): NaturalNumber ::= if (x + y < MAXINT) Add = x+ y else Add = MAXINT Equal(x, y): Boolean ::= if (x == y) Equal = true else Equal = false Successor(x): NaturalNumber ::= if (x==MAXINT) Successor = x else Successor = x + 1 Subtract(x, y): NaturalNumber ::= if (x < y) Subtract = 0 else Subtract = x - y end NaturalNumber

對軟體發展的幫助 Simplification of software development Testing and Debugging Reusability Modifications to the representation of a data type

1.4 BASICS OF C++ C++ 可稱作 a better C，因為
p.20 1.4 BASICS OF C++ C++ 可稱作 a better C，因為 C and C++ have a lot of features in common. C++ has a number of features not associated with either data abstraction or inheritance that improve on C. 1.4.1 Program Organization in C++ header files source files multiple source files:

1.4 BASICS OF C++ 1.4.2 Scope in C++
C++ 的 scope(變數的使用範圍): file scope(全域變數)、function scope(label)、local scope(區域變數)、class scope 在 block 中如何使用 global 變數？在 file1 中宣告的全域變數如何在 file2 中使用？(file2 中宣告 extern) 在 file1 與 file2 使用相同名稱的兩個不同的全域變數，要如何宣告？(兩個檔案都用 static 宣告)

1.4 BASICS OF C++ 1.4.3 C++ Statements and Operators
C++ 比 C 語言多了 new 與 delete 兩個運算子來作動態記憶體管理，輸入與輸出可用 >> 與 <<，也可作運算子重載。

1.4 BASICS OF C++ 1.4.4 Data Declarations in C++
p.23 1.4 BASICS OF C++ 1.4.4 Data Declarations in C++ A data declaration associates a data type with a name. C++ 可使用的資料型態有：constant value 、variables、constant variables、enumeration types、pointers、reference types。

1.4 BASICS OF C++ 1.4.5 Comments in C++
p.24 1.4 BASICS OF C++ 1.4.5 Comments in C++ Multiline comments: /* 與 */ 之間的部份都是註解。 Single line comments: // 之後的部份。 1.4.6 Input/Output in C++ #include <iostream.h> main() { int n = 50; float f=20.3; cout << "n: " << n << endl; cout << "f: " << f << endl; }// Program 1.1 Output in C++

1.4 BASICS OF C++ 1.4.6 Input/Output in C++
#include <iostream.h> #include <fstream.h> main() { ofstream outFile("my.out", ios::out); if(!outFile) { cerr << "cannot open my.out" << endl; return; } int n = 50; float f=20.3; outFile << "n: " << n << endl; outFile << "f: " << f << endl; } //Program 1.3 File I/O in C++

1.4 BASICS OF C++ 1.4.7 Functions in C++
p.26 1.4 BASICS OF C++ 1.4.7 Functions in C++ C++ 的函式分為兩類：regular functions 與 member functions(類別裡面的函式) A function consists of a function name, a list of arguments or signature(input), a return type(output), and the body(code that implements a function). 所有C++的函式都有傳回值的資料型態，不傳回值的函式之傳回值資料型態是 void。

1.4 BASICS OF C++ 1.4.8 Parameter Passing in C++
C++ 中一般的引數傳遞方式是 pass by value，也就是將引數複製到函式的區域變數中。 C++ 也有 pass by reference 的方式，就是只將引數的記憶體位置傳到函式中。陣列的預設傳遞方式。 Pass by constant references 是不錯的作法：速度快又安全。

1.4 BASICS OF C++ 1.4.9 Function Name Overloading in C++
p.28 1.4 BASICS OF C++ 1.4.9 Function Name Overloading in C++ Function overloading means that there can be more than one function with the same name as long as they have different signatures. 例如以下的函式都代表不同的函式 int max(int, int); int max(int, int, int); int max(int*, int); int max(float, int); int max(int, float);

1.4 BASICS OF C++ 1.4.10 Inline Functions
p.29 1.4 BASICS OF C++ Inline Functions inline int sum(int a, int b) { return a + b; } The inline keyword tells the compiler that any calls to sum must be replaced by the body of sum. The objective of the inline and const keywords is to eliminate the use of preprocessor directives such as #define, which have traditionally been used to perform macro substitution.

1.4 BASICS OF C++ 1.4.11 Dynamic Memory Allocation in C++
p.30 1.4 BASICS OF C++ Dynamic Memory Allocation in C++ The new operator creates an object of the desired type and returns a pointer to the data type that follows it. int *ip = new int; if(ip == 0) cerr << "Memory not allocated" << endl; ... delete ip; int *jp = new int[10]; if(jp == 0) cerr << "Memory not allocated" << endl; delete [ ]jp;

1.5 ALGORITHM SPECIFICATION
1.5.1 Introduction Definition: An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria: Input. (零或多個) Output (至少一個) Definiteness(每個指令要清楚不模糊) Finiteness(每種情況都必須在有限步驟完成) Effectiveness(每個指令是基本、可執行的)

程式(program)與演算法(algorithm)的差異：程式不需要符合前面第四項的標準，例如作業系統就是 infinite。要如何表示演算法？用什麼語言或圖形表示演算法？flowcharts(流程圖)、pseudocode(虛擬碼)，此書中大部份的演算法都用 C++ 來表示。

Example 1.2 [Selection sort] Suppose we must devise a program that sorts a collection on n ≥ 1 integers. A simple solution is given by the following: From those integers that are currently unsorted, find the smallest and place it next in the sorted list.

for(i = 0; i < n; i++) { examine a[i] to a[n-1] and suppose the smallest element is at a[j]; interchange a[i] and a[j]; } void SelectionSort(Type a[ ], int n) { for(int i=0; i < n; i++) { int j = i; for(int k = i+1; k < n; k++) if (a[k] < a[j]) j = k; Type t = a[i]; a[i] = a[j]; a[j] = t;

Theorem 1.1: sort(a, n) correctly sorts a set of n ≥ 1 integers; the result remains in a[0] ... a[n-1] such that a[0] ≤ a[1] ≤ ... ≤ a[n-1]. Proof: 在前面的程式中，當 i = q 時，執行完後一定將 a[q]~a[n-1] 之間最小的值找出來放在 a[q] 中。當 i > q 之後，a[0]~a[q] 之間的值不會再改變，因此每個元素一定都不會比放在它後面的元素值更大，因此 a[0] ≤ a[1] ≤ ... ≤ a[n-1]。

Example 1.3 [Binary search]: Assume that we have n ≥ 1 distinct integers that are already sorted and stored in the array a[0] ... a[n-1]. Our task is to determine if the integer x is present and if so to return j such that x = a[j]; otherwise return -1. 令left與right代表要尋找之範圍的左右邊界，middle = (left+right)/2，先比x與a[middle] x < a[middle]: x只會出現在left ~ middle - 1間 x == a[middle] 找到，return middle X>a[middle]:x只會出現在middle + 1 ~ right 之間

int BinarySearch(int *a, const int x, const int n) { for(int left = 0, right = n – 1;left <= right;) { int middle = (left + right) / 2; switch(compare(x, a[middle])) { case '>' : left = middle + 1; break; case '<' : right = middle – 1; break; case '=' : return middle; } return -1; }//Program 1.9 C++ function for binary search

1.5.2 Recursive Algorithms 結構化程式設計強調到達到：readability、 correctness。遞迴程式有時可以達到這些效果。 direct recursion 與 indirect recursion 遞迴與數學歸納法哪些問題適合用遞迴函式來作？當問題本身可用遞迴定義時，例如：C(n, m) = C(n-1, m) + C(n-1, m-1)

Example 1.4 [Recursive binary search]: 遞迴版本的 binary search，left 與right 都當作參數，呼叫方式為： BinarySearch(a, x, 0, n-1); Example 1.5 [Permutation generator]: Given a set of n ≥ 1 elements, the problem is to print all possible permutations of this set. 若此集合為{a, b, c}, 則其排列方式有：(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)六種。用遞迴來作。

int BinarySearch(int *a, const int x, const int left, const int right) { if(left <= right) { int middle = (left + right) / 2; switch(compare(x, a[middle])) { case '>' : return BinarySearch(a, x, middle+1, right); case '<' : return BinarySearch(a, x, left, middle -1); case '=' : return middle; } return -1; }//Program 1.10 Recursive implementation for binary search

void perm(char *a, const int k, const int n) { // n is the size of a generate all the permutations of a[k], ..., a[n-1]. if(k == n – 1) { // output permutation for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; } else { // a[k], ..., a[n-1] has more than one permutation. 遞迴 for (i = k; i < n; i++) { char temp = a[k]; a[k] = a[i]; a[i] = temp; perm(a, k+1, n); temp = a[k]; a[k] = a[i]; a[i] = temp; } } // 程式1.11: 排列產生器的遞迴作法

p.42 習題 1.5 Exercise 1.5 第10題：Write an iterative function to compute a binomial coefficient; the transform it into an equivalent recursive function. C(n, m) = (n!) / (m! (n-m)!) C(n, m) = C(n-1, m) + C(n-1, m-1) 相關問題：輸入n，輸出(x + y)n之各項係數。其他參考習題 8. Fibonacci numbers, 11. Ackermann's function, 16.Towers of Hanoi,

p.43 習題 1.5 Exercise 1.5 第15題. If S is a set of n elements, the powerset of S is the set of all possible subsets of S. For example, if S = (a, b, c), then powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}. Write a recursive function to compute powerset(S). 輸入 3 代表 S = (a,b,c)；輸入4代表 S = (a,b,c,d) 順便寫個非遞迴版本的程式

1.6 PERFORMANCE ANALYSIS AND MEASUREMENT
判斷程式好壞的標準： Does it do what we want it to do ? Does it work correctly according to the original specifications of the task? Is there documentation that describes how to use it and how it works? Are functions created in such a way that they perform logical subfunctions? Is the code readable?

1.6 PERFORMANCE ANALYSIS AND MEASUREMENT
Definition: The space complexity of a program is the amount of memory it needs to run to completion. The time complexity of a program is the amount of computer time it needs to run to completion. Performance evaluation 可簡單分成：事先的估計與事後的測試，即 performance analysis 與 performance measurement.

1.6.1 Performance Analysis 1.6.1.1 Space Complexity
The space requirement S(P) of any program P may therefore be written as S(P) = c + SP(instance characteristics) where c is a constant. 主要放在 instance characteristics 的分析後面看三個例子

1.6.1 Performance Analysis float abc(float a, float b, float c) {
return (a + b + b*c + (a+b-c)/(a+b) + 4.0); } float Sum(float a[ ], int n) { float s = 0.0; for (int j = 1;j <= n;j++) s += a[ j ]; return s; float RSum(float a[], int n) { if (n <= 0) return (0.0); else return (RSum(a, n-1) + a[n]); 使用的 memory 是常數量使用的 memory 是常數量(陣列a不算) 使用的 memory 是常數量4(n+1)

1.6.1 Performance Analysis 1.6.1.2 Time Complexity
The time, T(P), taken by a program P is the sum of the compile time and the run(or execution) time. 實際上，我們的分析重點放在 run time tp. A program step is loosely defined as a syntactically or semantically meaningful segment of a program that has an execution time that is independent of the instance characteristics. 註解、宣告、函式名稱都算 0 step；運算式、函式呼叫、記憶體管理、跳躍指令都算1步；switch、if-else 就看每個部份的 step；迴圈就算其繼續條件會被執行幾次。可對每個 statement 計算一次。

1.6.1 Performance Analysis float Sum(float a[ ], int n) {
count++; //count is global; j = 1; for(int j = 1;j <=n; j++) { count++; // j <= n; s += a[j]; count++; // s+= a[j]; } count++; // j++; count++; // return s; return s; float Sum(float a[], int n) { for (int j = 1;j <= n;j++) count += 2; count += 3; 只計算 step 時，可簡化為如此，共 2n+3 步

1.6.1 Performance Analysis 遞迴函式的寫法：
float rsum(float *a, const int n) { count++; // for if conditional if(n <= 0) { count++; // for return return 0; } else { count++; //for return return (rsum(a, n-1) + a[n-1]); } 共 2n+2 步

1.6.1 Performance Analysis Example 1.11[Matrix addition]
void add(matrix a, matrix b, matrix c, int m, int n) { for(int i = 0;i < m;i++) for(int j = 0;j < n;j++) c[i][j] = a[i][j] + b[i][j]; } 共 2mn + 2m + 1 步

1.6.1 Performance Analysis Example 1.12[Fibonnaci numbers]
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... int fibonacci(int n) { if(n <= 1) return n; else { int fn, fnm2 = 0, fnm1 = 1; for (int i = 2;i <= n;i++) { fn = fnm1 + fnm2; fnm2 = fnm1; fnm1 = fn; } return fn; 共 4n + 1 步

1.6.1 Performance Analysis Step 比較少的程式是否就一定執行得比較快呢？
每次程式執行的時間不一定相同，例如作 binary search 時，search 不同的資料速度不一樣，因此討論時間複雜度時又可分為 best case、worst case 與 average。 The best-case step count is the minimum number of steps that can be executed for the given parameters. The worst-case step count is the maximum number of steps that can be executed for the given parameters. The average step count is the average number of steps executed on instances with the given parameters. (哪一種最重要？)

1.6.1 Performance Analysis 1.6.1.3 Asymptotic Notation (O, , )
要精確算法 step 數有時是很困難的，而且通常不太需要精確算出 step 步驟也可以比較兩個演算法的快慢。例如兩個演算法的時間分別為 c1n2 + c2n 與 c3n，其中 c1, c2, c3 都是非負的數字，可知當 n 大到某個程度以上時，第二個演算法的速度一定會比較快。 Definition [Big “oh"]: f(n) = O(g(n))(read as 'f of n is big oh of g of n') iff (if and only if) there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0. eg. 3n+2 = O(n), 10n2+4n = O(n2), 10n2+4n+2 = O(n4). f(n) = O(g(n)) 代表 g(n) 是 f(n) 的一個上界(upper bound)

p.55 1.6.1 Performance Analysis Theorem 1.2 If f(n) = amnm a1n + a0, then f(n) = O(nm). Definition [Omega]: f(n) = (g(n))(read as 'f of n is omega of g of n') iff (if and only if) there exist positive constants c and n0 such that f(n) ≥ cg(n) for all n, n ≥ n0. eg. 3n+2 = (n), 10n2+4n = (n2), 10n2+4n+2 =  (1). f(n) = (g(n)) 代表 g(n) 是 f(n) 的一個下界(lower bound) Theorem 1.3: If f(n) = amnm a1n + a0 and am > 0, then f(n) = (nm).

p.56 1.6.1 Performance Analysis Definition [Theta]: f(n) = (g(n))(read as 'f of n is theta of g of n') iff (if and only if) there exist positive constants c1, c2, and n0 such that c1g(n) ≤ f(n) ≤ c2g(n) for all n, n ≥ n0. eg. 3n+2 = (n), 10n2+4n = (n2), 6*2n+n2 ≠ (n100). f(n) = (g(n)) 代表 g(n) 是 f(n) 的上界、也是 f(n) 的下界， 是比較精確的符號。 Theorem 1.4: If f(n) = amnm a1n + a0 and am > 0, then f(n) = (nm). sum, rsum, add 三個例子的時間複雜度分別為 (n), (n),  (mn). Permutation generator 是 (n(n!)), Binary search 的 worst case 是 (log n)。

p.57 1.6.1 Performance Analysis Example 1.18[Magic square] 每一垂直行、水平列、對角線的數字總和都相等之方陣奇數魔方陣產生方法：從最上一列的中間開始寫，之後往左上方遞增，超出方陣範圍就作 modula 的動作。若該位置已經有數字了，就填在下方。(n2) 8 15 16 22 14 20 13 19 25 18 12 11 10 23 17 24 9 21 1 7 5 6 4 3 2

1.6.1 Performance Analysis 1.6.1.4 Practical Complexities
時間複雜度比較高的程式（如：2n, n10 等)，當參數 n 稍微大一點，就執行不完。

p.59 1.6.1 Performance Analysis Table 1.7 Function values

1.6.2 Performance Measurement
Performance measurement is concerned with obtaining the actual space and time requirements of a program. 會與所用的 compiler、電腦、程式語言有關。假設系統中存在一個時間函式 time, 可傳回目前的時間、到百分之一秒的精確度。 To time a short event, it is necessary to repeat it several times and divide the total time for the event by the number of repetitions. 多重複幾次，精確度會比較高；也可考慮將重複指令(如 for)所需之時間扣掉。有時需要將呼叫函式 time 的預估時間扣掉。要測試 worst-case 或 average 的時間呢？需要產生適當的資料。

1.6.3 Generating Test Data 要產生大量測量 worst-case 的 data 有時是很困難的。
p.61 1.6.3 Generating Test Data 要產生大量測量 worst-case 的 data 有時是很困難的。要測量 average-case 的時間，有時無法對「每一種」情形都產生 data，例如 sort 的程式就有 n! 種(n 是資料個數)，因此需要隨機並作簡化。

習題 1.6 9. Show that the following equalities are incorrect:
p.62 習題 1.6 9. Show that the following equalities are incorrect: 10n2 + 9 = O(n) n2log n = (n2) n2/ log n = (n2) n32n + 6n23n = O(n32n) 11. Analyze the computing time of function sort(Program 1.6). 其他參考習題：2.數學歸納法助教

習題 1.6 8.正確性證明 (a).5n2 – 6n = (n2) (b). n! = O(nn)
p.63 習題 1.6 8.正確性證明 (a).5n2 – 6n = (n2) (b). n! = O(nn) (f). 22n + 6*2n = (22n) (g). n n2 = (n3) 9.不正確的證明 (a) 10n2 + 9 = O(n) (b) n2log n = (n2) (c) n2 / log n = (n2) (d) n32n + 6n23n = O(n32n) 助教

資料結構 Fundamentals of Data Structures in C++

Similar presentations

Presentation on theme: "資料結構 Fundamentals of Data Structures in C++"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

資料結構 Fundamentals of Data Structures in C++

Similar presentations

Presentation on theme: "資料結構 Fundamentals of Data Structures in C++"— Presentation transcript:

Similar presentations

About project

反馈