1、面向对象程序设计面向对象程序设计C+全册全册 配套最完整精品课件配套最完整精品课件(英文版）英文版） CS 1032 Introduction (Outline) The Software Development Process Performance Analysis: the Big Oh. Abstract Data Types Introduction to Data Structures CS 1033 The Software Development Process CS 1034 Software Development Requirement analysis, leading
2、 to a specification of the problem Design of a solution Implementation of the solution (coding) Analysis of the solution Testing, debugging and integration Maintenance and evolution of the system. CS 1035 Specification of a problem A precise statement/description of the problem. It involves describi
3、ng the input, the expected output, and the relationship between the input and output. This is often done through preconditions and postconditions. CS 1036 Design Formulation of a method, that is, of a sequence of steps, to solve the problem. The design “language” can be pseudo-code, flowcharts, natu
4、ral language, any combinations of those, etc. A design so expressed is called an algorithm(s). A good design approach is a top-down design where the problem is decomposed into smaller, simpler pieces, where each piece is designed into a module. CS 1037 Implementation Development of actual C+ code th
5、at will carry out the design and solve the problem. The design and implementation of data structures, abstract data types, and classes, are often a major part of design implementation. CS 1038 Implementation (Good Principles) Code Re-use Re-use of other peoples software Write your software in a way
6、that makes it (re)usable by others Hiding of implementation details: emphasis on the interface. Hiding is also called data encapsulation Data structures are a prime instance of data encapsulation and code re-use CS 1039 Analysis of the Solution Estimation of how much time and memory an algorithm tak
7、es. The purpose is twofold: to get a ballpark figure of the speed and memory requirements to see if they meet the target to compare competing designs and thus choose the best before any further investment in the application (implementation, testing, etc.) CS 10310 Testing and Debugging Testing a pro
8、gram for syntactical correctness (no compiler errors) Testing a program for semantic correctness, that is, checking if the program gives the correct output. This is done by having sample input data and corresponding, known output data running the programs against the sample input comparing the progr
9、am output to the known output in case there is no match, modify the code to achieve a perfect match. One important tip for thorough testing: Fully exercise the code, that is, make sure each line of your code is executed. CS 10311 Integration Gluing all the pieces (modules) together to create a cohes
10、ive whole system. CS 10312 Maintenance and Evolution of a System Ongoing, on-the-job modifications and updates of the programs. CS 10313 Preconditions and Postconditions A semi-formal, precise way of specifying what a function/program does, and under what conditions it is expected to perform correct
11、ly Purpose: Good documentation, and better communications, over time and space, to other programmers and user of your code CS 10314 Precondition It is a statement of what must be true before function is called. This often means describing the input: the input type the conditions that the input value
12、s must satisfy. A function may take data from the environment Then, the preconditions describe the state of that environment that is, the conditions that must be satisfied, in order to guarantee the correctness of the function. The programmer is responsible for ensuring that the precondition is vali
13、d when the function is called. CS 10315 Postcondition It is a statement of what will be true when the function finishes its work. This is often a description of the function output, and the relationship between output and input. A function may modify data from the environment (such as global variabl
14、es, or files) the postconditions describe the new values of those data after the function call is completed, in relation to what the values were before the function was called. CS 10316 Example of Pre/Post-Conditions void get_sqrt( double x) / Precondition: x = 0. / Postcondition: The output is a nu
15、mber / y = the square root of x. CS 10317 C+ Way of Asserting Preconditions Use the library call assert (condition) You have to include #include It makes sure that condition is satisfied (= true), in which case the execution of the program continues. If condition is false, the program execution term
16、inates, and an error message is printed out, describing the cause of the termination. CS 10318 Performance Analysis and Big-O CS 10319 Performance Analysis Determining an estimate of the time and memory requirement of the algorithm. Time estimation is called time complexity analysis Memory size esti
17、mation is called space complexity analysis. Because memory is cheap and abundant, we rarely do space complexity analysis Since time is “expensive” , analysis now defaults to time complexity analysis CS 10320 Big-O Notation Let n be a non-negative integer representing the size of the input to an algo
18、rithm Let f(n) and g(n) be two positive functions, representing the number of basic calculations (operations, instructions) that an algorithm takes (or the number of memory words an algorithm needs). CS 10321 Big-O Notation (contd.) f(n)=O(g(n) iff there exist a positive constant C and non-negative
19、integer n0 such that f(n) Cg(n) for all nn0. g(n) is said to be an upper bound of f(n). CS 10322 Big-O Notation (Examples) f(n) = 5n+2 = O(n) / g(n) = n f(n) 6n, for n 3 (C=6, n0=3) f(n)=n/2 3 = O(n) f(n) 0.5 n for n 0 (C=0.5, n0=0) n2-n = O(n2) / g(n) = n2 n2-n n2 for n 0 (C=1, n0=0) n(n+1)/2 = O(n
20、2) n(n+1)/2 n2 for n 0 (C=1, n0=0) CS 10323 Big-O Notation (In Practice) When computing the complexity, f(n) is the actual time formula g(n) is the simplified version of f Since f(n) stands often for time, we use T(n) instead of f(n) In practice, the simplification of T(n) occurs while it is being c
21、omputed by the designer CS 10324 Simplification Methods If T(n) is the sum of a constant number of terms, drop all the terms except for the most dominant (biggest) term; Drop any multiplicative factor of that term What remains is the simplified g(n). amnm + am-1nm-1+.+ a1n+ a0=O(nm). n2-n+log n = O(
22、n2) CS 10325 Big-O Notation (Common Complexities) T(n)=O(1)/ constant time T(n)=O(log n)/ logarithmic T(n)=O(n)/ linear T(n)=O(n2)/quadratic T(n)=O(n3)/cubic T(n)=O(nc), c 1/ polynomial T(n)=O(logc n), c 1/ polylogarithmic T(n)=O(nlog n) CS 10326 Big-O Notation (Characteristics) The big-O notation i
23、s a simplification mechanism of time/memory estimates. It loses precision, trading precision for simplicity Retains enough information to give a ballpark idea of speed/cost of an algorithm, and to be able to compare competing algorithms. CS 10327 Common Formulas 1+2+3+n= n(n+1)/2 = O(n2). 12+22+32+n
24、2= n(n+1)(2n+1)/6 = O(n3) 1+x+x2+x3+xn=(x n+1 1)/(x-1) = O(xn). CS 10328 Example of Time Complexity Analysis and Big-O Pseudo-code of finding a maximum of xn: double M=x0; for i=1 to n-1 do if (xi M) M=xi; endif endfor return M; CS 10329 Complexity of the algorithm T(n) = a+(n-1)(b+a) = O(n) Where “
25、a” is the time of one assignment, and “b” is the time of one comparison Both “a” and “b” are constants that depend on the hardware Observe that the big O spares us from Relatively unimportant arithmetic details Hardware dependency CS 10330 Abstract Data Types CS 10331 Abstract Data Types An abstract
26、 data type is a mathematical set of data, along with operations defined on that kind of data Examples: int: it is the set of integers (up to a certain magnitude), with operations +, -, /, *, % double: its the set of decimal numbers (up to a certain magnitude), with operations +, -, /, * CS 10332 Abs
27、tract Data Types (Contd.) The previous examples belong to what is called built-in data types That is, they are provided by the programming language But new abstract data types can be defined by users, using arrays, enum, structs, classes (if object oriented programming), etc. CS 10333 Introduction t
28、o Data Structures CS 10334 Data Structures A data structure is a user-defined abstract data type Examples: Complex numbers: with operations +, -, /, *, magnitude, angle, etc. Stack: with operations push, pop, peek, isempty Queue: enqueue, dequeue, isempty Binary Search Tree: insert, delete, search.
29、Heap: insert, min, delete-min. CS 10335 Data Structure Design Specification A set of data Specifications for a number of operations to be performed on the data Design A lay-out organization of the data Algorithms for the operations Goals of Design: fast operations CS 10336 Implementation of a Data S
30、tructure Representation of the data using built-in data types of the programming language (such as int, double, char, strings, arrays, structs, classes, pointers, etc.) Language implementation (code) of the algorithms for the operations CS 10337 Object-Oriented Programming (OOP) And Data Structures
31、When implementing a data structure in non-OOP languages such as C, the data representation and the operations are separate In OOP languages such as C+, both the data representation and the operations are aggregated together into what is called objects The data type of such objects are called classes
32、. Classes are blue prints, objects are instances. CS 10338 The C+ Language C Evolves into C+ Object Oriented Programming Classes and Objects Operator Overloading Inheritance Polymorphism Template classes CS 10339 C Evolves into C+ CS 10340 C is Alive in C+ C+ is a superset of C. Any correct C progra
33、m is also a correct C+ program, except for some loopholes in C that are not allowed in C+. CS 10341 What is still the same The syntax of statements if-else, switch, the “?:” conditional for/while/do-while loops assignments arithmetic/logic/relational/ bitwise expressions declarations, struct/union/e
34、num types, typedef pointers, arrays, casting Same preprocessor commands in C / i is an integer that will index the next array double x10; / an array that will store user input / and will then be sorted. CS 10344 Declaration Anywhere Declarations need no longer be at the head of blocks. Variables and
35、 functions can be declared any time, anywhere in a program, preferably as close to where a variable is used the first time. For example: note i is declared within for for (int i=0;i= b) return a; else return b; float max(float a, float b) if (a= b) return a; else return b; CS 10346 Default Arguments
36、 A default argument is a value given in the function declaration that the compiler automatically inserts if the caller does not provide a value for that argument in the function call. Syntax: return_type f(, type x = default_value,); CS 10347 Default Arguments (Examples) The default value of the 2nd
37、 argument is 2. This means that if the programmer calls pow(x), the compiler will replace that call with pow(x,2), returning x2 double pow(double x, int n=2) / computes and returns xn CS 10348 Default Arguments (Rules) Once an argument has a default value, all the arguments after it must have defaul
38、t values. Once an argument is defaulted in a function call, all the remaining arguments must be defaulted. int f(int x, int y=0, int n) / illegal int f(int x, int y=0, int n=1) / legal CS 10349 Examples of Legal/Illegal Defaulting in Function Calls Let substring be a function whose prototype is: Ass
39、ume Which call to substring is OK and which is not OK? If OK, what is it equivalent to? substring(p) substring(p,10) substring( ) char * substring (char *p, int length=10, int pos=0) char *p=“hello”; CS 10350 Default Arguments and Function Overloading Default arguments and function overloading can g
40、ive rise to an ambiguity Consider an overloaded function f where one declaration has default arguments that, if removed, makes the function look identical to a second declaration, as in 1. int f(int x, int y=0); returns xy 2. int f(int x); / returns 2x If we call f(2), is it to f in (1) or (2)? The
41、1st returns 1. The 2nd returns 4. CS 10351 Default Arguments and Function Overloading (Contd.) If overloaded declarations of a function with default arguments cause ambiguity, the compiler gives an error message. It is the responsibility of the programmer not to cause such ambiguities. CS 10352 Exam
42、ple of Function Overloading and Default Args / Precondition: x is a double array of length n. / n is a positive integer. If missing, it defaults to 10 / Postcondition: the output is the maximum in x double max(double x, int n=10) double M = x0; / M is the maximum so far for (int i=1;iM) M=xi; return
43、 M; CS 10353 Overloading / M is the maximum so far for (int i=1;iM) M=xi; return M; CS 10354 Simplified IO Instead of the complicated syntax of printf and scanf, and the many variations of print and scan, C+ offers a much simpler syntax For standard output, use cout For standard input, use cin File
44、IO is also simpler, and will be discussed later Note: one can still use the IO syntax of C in C+ CS 10355 Cout For printing output, use this syntax: This prints out the string or the value of the extpression. For output chaining, use this syntax Each Si is a string or an expression. The effect is to
45、 print out the value of S1 followed by the value of S2, followed by the value of S3. cout a string or an expression; cout S1 S2S3endl; CS 10356 Cout (Contd.) The reserved word, endl, ensures that the next cout command prints its stuff on a new line. New lines can also be added using “n”. CS 10357 Co
46、ut (Examples) StatementsOutput int x=3; double y =4.5; cout “the value of x=“x; cout“; y=“yendl; cout “x+y”x+y; the value of x=3; y=4.5 x+y=7.5 int x=3; double y =4.5; cout “x = “x“n”; cout“y=“y; cout “nx+y” variableName1 variableName2 variableName3; CS 10359 Cin (Examples) Suppose you want to read
47、an int value and a double value into variables n and x. This code will do it (see next slide): int n; double x; coutnx;/ use of cin cout“You entered int n=“n; cout“, and double x=“xendl; CS 10360 If you run that code, you first get: Lets say, you enter: -3 9.8 The code next will store 3 in n, and 9.
48、8 in x, and print out to you: Enter an int, a space, and a double: Enter an int, a space, and a double: -3 9.8 You entered int n=-3, and double y=9.8 CS 10361 A new Boolean data type: bool A bool variable is a variable that can have only two values: true or false. C does not have Boolean values or v
49、ariables Instead, any non-zero was considered the equivalent of true , and 0 the equivalent of false. CS 10362 Example of bool / Precondition: x is an integer array of length n. / n is a positive integer. / Postcondition: The output is true if the elements / of the input array are all positive,. Els
50、e, false. bool isAllPositive(int x, int n) for(int i=0;in;i+) if (xi = 0) return false; return true; CS 10363 A Comprehensive Example #include #include using namespace std; / codes for isAllPositive( ), and for overloaded / function max( ) should be inserted here int main(int argc, char *argv) cout
