數(shù)據(jù)結(jié)構(gòu)課件數(shù)據(jù)結(jié)構(gòu)chapter1

1、Data Structure & Algorithmin JavaAdamDrozdekFu XiaoChapter1IntroductionThe purpose and contents of the courseIntroduce most used data structures and algorithmsPrerequisite of other courses Introduce algorithm analysisReview JavaandC+The purpose and contents of the course1. Introduce most used data s

2、tructures and algorithms.Use proper data structures problems.Example :to solve differentGame problemManagement of library catalogue by computer Management of the traffic lights in intersections The book : selection problemsolve a popular word puzzleThe purpose and contents of the courseExample 1:Gam

3、e problem:Next step:x has five choices.The purpose and contents of the courseExample 1 uses a tree structure.The purpose and contents of the courseExample 2: Management of library catalogue by computerIt is a linear list.書名作者名登錄號分類出版年月D.S.Sartaj Sahni000001computer2000.1The purpose and contents of t

4、he courseExample 3:Management of the traffic lights in intersectionsC, E are one-way road, there are 13 path to go.Can go at the same time :CBDEABECACannot go at the same time:EBADThis is a graphThe purpose and contents of the course2 . Prerequisite of other courses:Principles of compiling : use sta

5、ck to compute expression and implement recursive procedureOperating System: use queue to schedulingDatabase: use B-tree,B+ tree to organize, store and load massive data in the hard memory.implement jobThe purpose and contents of the course3. Basic methods of algorithm analysisstandards of the perfor

6、mance of analgorithm:timecomplexity, and accuracyexample:sortingspace complexity,a1,a2,a3,an-1,ann-1+n-2+.+2+1= n(n-1)/2=(n2-n)/2 O(n2)O(n*log2n)4. Review JavaandC+What is Data Structure1. Datais the carrier of information.Data is a set of numbers , characters,and other symbolsthat can be used to de

7、scribe the objective things.These symbols can be input into computers , identified and processed by the computer program.What is Data StructureData can divided into two classes:numerical data: int, float, complex, non-numerical data: character, string,graph, voiceWhat is Data Structure. Data structu

8、reA data structure is a data object together with the relationships among the data members that compose the objectData_Structure=D,R is a data object，R is a limited set of relationships of all the data members in D.What is Data StructureLinear structureData structureNon-linear structureWhat is Data

9、Structurem數(shù)據(jù)結(jié)構(gòu)涉及三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)從用戶視圖看，是面向問題的。數(shù)據(jù)的物理結(jié)構(gòu)從具體實現(xiàn)視圖看，是面向計算機的。相關(guān)的操作及其實現(xiàn)。Example:學生表：邏輯結(jié)構(gòu)線性表物理結(jié)構(gòu)-數(shù)組, 拉鏈操作-插入, 刪除, 查找ADT and OO1. Data typeDefinition: is a set of values together with a operation set that operate on these values.Example: int typevalue set:,-2,-1,0,1,2,operation set:+, -, *, /, %,

10、ADT and OOMost of the programming languages providea group of predefined data type.Atom data type int, float, double Structure data typearray, struct,ADT and OO2. ADTs: Abstract Data Types是將類型和與這個類型有關(guān)的操作集合封裝在一起的數(shù)據(jù)模型。Abstract:Example:int x ;is a method used to hide the information.float x, y ;:x=x*y+

11、3.0;:abstract of float data type operation: x=735;:abstract of int data type assignmentADT and OOAbstract data type:is a new programming method thatpart the usage and implementation, in order to encapsulate and hide the information.思想：將數(shù)據(jù)類型的使用與它的表示（機內(nèi)存儲）、實現(xiàn)（機內(nèi)操作的實現(xiàn)）分開。更確切的說，把一個數(shù)據(jù)類型的表示及在這個類型上的操作實現(xiàn)封裝到

12、一個程序模塊中，用戶不必知道它。ADT NaturalNunber isobjects: 一個整數(shù)的有序子集合,它開始于0,結(jié)束于機器能表示的最大整數(shù)(MAXINT)。Function:Zero( ):NaturalNumber IsZero(x):Boolean Add(x,y):NaturalNumber Equal(x,y):Boolean Successor(x):NaturalNumber Subtract(x,y):NaturalNumberend NaturalNumberADT and OO3. OO:object-orientedobjectclassinheritcommu

13、nicateobject: attributevalues+ operates一個幾何對象example:rectangle:attribute values : 左上角坐標, 右下角坐標,邊線顏色, 內(nèi)部顏色operates : move(x,y);setEdgeColor( c ); setInterColor( c ) ;ADT and OOclass: objects of same attributes andoperates.an instance is an object of the class.different object has deferent attribute v

14、alueADT and OOInherit:base classintegrate the same part(includingattributes and operations) in all the derived classesderived classadd the specific attributes andoperationsExample:base classpolygonderived classquadrilateral,triangularADT and OOCommunication:each class objectcommunicate with others u

15、sing messages.Message: instructions that one class object used in order to require another class object to perform some operation.Algorithm definitionAlgorithm : an operation sequence of solutinga problem Characteristic: 1.finite2. deterministic3. initial action4. sequence endsAlgorithm definitionPr

16、ogram :is written by languages that can beperformed by machine.cantsatisfythe finiteness.For example, OS.has multiple descriptiveAlgorithm:methods,such as language, graph, table.Algorithm definitionvoid selectsort(int a ,int n)for (int i = 0; i n-1; i+)int k = i;for ( int j = i+1; j n;j+) if ( aj 0,

17、 A != 1 THEOREM 1.2logAB = log A + log B;A, B 03. SeriesN 2i = 1 + 21 + 22 +2N = 2N+1-1i=0N i = 1 + 2 + 3+N = (N+1)*N/2i=1Mathematics Review4. Modular ArithmeticWe say that A is congruent to B modular N,written A B ( mod N), if N divides A-B. Example : 81 61 1 (mod 10)Mathematics Review5. The P Word

18、 (證明方法)1). Proof by InductionThe first step is proving a base case.the Next stap an inductive hypothesis is assumed. theorem is assumed to be true for all cases up tosome limitk. Using this assumption, the theorem isthen shown to be true for the next value, which is typically k + 1. This proves the

19、theorem( as long as k is finite).Example:例如 等比級數(shù)的和以及整數(shù)平方和的證明等.Mathematics Review2). Proof by ContradictionProof by contradiction proceeds by assuming that the theorem is false and showing that this assumption implies that some known property is false, and hence the original assumption was erroneous.

20、Example: proof that there is an infinite number of primesA Brief Introduction to RecursionRecursive1.example:define a function f, valid on nonnegative integers02f(x-1) + x2x = 0x 0f(x) =f(1) = 1, f(2) = 6, f(3) =21, f(4) = 58public static int f ( int x)if ( x = = 0) /base case return 0;else return 2

21、*f(x-1) + x*x; /recursive callA Brief Introduction to RecursionA nonterminating recursive method: public static int bad( int n )if ( n = = 0) return 0;else return bad( n/3 + 1) + n-1;two fundamental rules of recursion:1) Base cases.2) Making progress.A Brief Introduction to Recursion1) direct recurs

22、ive2) indirect recursive2.Example 1factorial functionf(n)=n!1n1 (recursive component)f(5)=5f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120static long factorial (int n)if ( n = 1)return 1;else return n* factorial( n-1 )A Brief Introduction to Recursionpublic class ComputeFactorialpublic static void main( Str

23、ing args )System.out. Println( “please enter a nonnegative integer” ); int n = MyInput.readInt( );Syatem.out.println( “Factorial of “ + n + “ is “ + factorial( n ) );static long factorial (int n) if (n=2public static long fib(long n)if ( ( n = = 0) | ( n = = 1 ) ) return n;elsereturn fib(n-1) + fib(

24、n-2);Compute fib(4):A Brief Introduction to Recursionpublic class ComputeFibonaccipublic static void main( String args )System.out.println( “Enter an index for the Fibonacci number “);int n = MyInput.readInt( );System.out.println( “Fibonacci number at index “ + n + “ is “ +fib(n);public static long

25、fib(long n)if ( n = = 0) | ( n = = 1) return 1;elsereturn fib( n-1) + fib(n-2);A Brief Introduction to RecursionExample 3:computesthe sum of the elements a0 through an-1 a0, a1, , an-2, an-1A Brief Introduction to Recursionpublic static int Rsum(int a , int n) if (n0)return Rsum(a,n-1)+an-1; return

26、0;a0a1 a2 a3Rs(a,4)Rs(a,3)+a3Rs(a,2)+a2Rs(a,1)+a1Rs(a,0)+a00A Brief Introduction to RecursionExample 4: Permutationa,b,c :abc, acb, bac, bca, cab, cbapermutation of n elements has n!下面在黑板上來分析該問題：A Brief Introduction to Recursionpublic static void perm(Char list ,int k,int m)int i;if (k= =m) for (i=0

27、; i=m; i+) cout listi; cout endl; else for (i=k; i=m; i+) swap(listk, listi); perm(list, k+1, m); swap(listk, listi);A Brief Introduction to RecursionExample 5 : Hanoi tower problemABCpublic void moveDISKs(int n, char fromTower, chartoTower, char auxTower)if ( n= =1)Move disk 1 from the fromTower to

28、 the toTower; else moveDISKs(n-1, fromTower, auxTower, toTower); Move disk n from the fromTower to the toTower; moveDISKs(n-1, auxTower, toTower, fromTower);A Brief Introduction to Recursionpublic class TowersOfHanoipublic static void main(String args)System.out.printLn( “Enter number of disks” );in

29、t n = MyInput.readInt( );System.out.printLn( “The move are:”);moveDISKs(n, A, B, C);public static void moveDISKs(int n, char fromTower, chartoTower, char auxTower) if ( n= =1)System.out.printLn( “move disk “ + n + “from “+fromTower +” to” + toTower);elsemoveDISKs(n-1, fromTower, auxTower, toTower);

30、System.out.printLn( “Move disk “ + n + “from “ +fromTower + “ to “ + toTower );moveDISKs(n-1, auxTower, toTower, fromTower); Generic Objects in JavaThroughout this text, we will describe algorithms and data structures that are type independent.IntCellnongeneric classMomoryCellgeneric classGeneric Ob

31、jects in Java1.IntCell class public class IntCellpublic IntCell ( ) this ( 0 ); public IntCell( int initialValue )storedValue = initialValue ; public int read ( ) return storedValue; public void write ( int x ) storedValue = x; private int storedValue;Generic Objects in Javapublic and privatememble

32、of public : may be accessed by any method in anyclass .member of private : may only be accessed by methods inits class.specifier is omitted (package-friendly visibility) :a data member whose visibility specifier is omitted is visible to other classes in the same package.1)Generic Objects in Java2) c

33、onstructorA class may define methods that describe how an instance of the class is constructed; these are called constructors.If no constructor is explicitly defined, one that initializes the fields using language defaults is automatically generated.Generic Objects in Java3) ThisIn many cases,the ze

34、ro-parameter constructor can beimplemented by calling anather constructor.By using this , weseparate constructors.avoidreplicatingcodelogicinA different use of this is as a reference to the object being acted upon.Generic Objects in Javapublic class TestIntCellpublic static void main ( String args )

35、IntCell m = new IntCell ( );m. write( 5 );System.out.println( “Cell contents: “ + m.read( ) );Generic Objects in Javastatic and mainThe main method must be static , meanimg that it applies to the TestIntCellclass instead of a single instance of the class.Each class may declare a main method that wil

36、l be used when the java interpreter is called for that class.1)復習一下static2)Object creation.Objects are created by using new.Generic Objects in Java3) Method calls. m.write(5); m.read( )m.storedValue/be illegalGeneric Objects in JavaMemoryCell classdesign a class that works for any type of Object.2.e

37、xample:C+:sorting of arrayusetempletea0, a1, a2, a3,an-1program1.1:int Abc(int a,int b,int c)return a+b+b*c+(a+b-c)/(a+b)+4;program1.2:float Abc(float a,float b,float c)return a+b+b*c+(a+b-c)/(a+b)+4;Generic Objects in Javaprogram1.1 and 1.2 differ only in thedatatype of the formal parameters and of

38、 thevalue returned.We can write a generic code in which the data type is a variable whose value is determined by the compiler.This generic code is written using the template statement in program1.3Generic Objects in JavaProgram1.3template T Abc(T a,T b,T c)return a+b+b*c+(a+b-c)/(a+b)+4;From this ge

39、neric code the compiler canconstruct 1.1 by substituting int for T and1.2 by substituting float for T.Generic Objects in JavaJava:1)use inheritance(pre-java 5)all objects are subclasses of Object.public class MemoryCellpublic Object read( )return storedValue; public void write( Object x )storedValue

40、 = x; privateObject storedValue;1.5Ageneric MemoryCellclass (pre-java 5)Generic Objects in JavaTwo problem:First problem:We must downcast to the correct typepublic class TestMemoryCellpublic static void main( String args )MemoryCell m = new MemoryCell ( ) ;m.write( “37 “ );string val = ( String) m.r

41、ead( ); System.out.println( “Contents are : “ + val )Using the generic MemoryCell class (pre-Jave 5)the read method for MemoryCell returns an Object.Generic Objects in JavaSecond problemAlthough all objects are subclasses ofObject, the primitive types boolean, short, char, byte, int, long, float, do

42、uble are not objects. Thus we cannot directly use MemoryCell to store a primitive value.We must use wrapper class provide by Jave. Wrapper class store a single primitive value and can be used wherever an Object is need.the wrapper class provides a method that can be used to access the primitive valu

43、e it stores.two example:a) For the Integer wrapper, this method is named intValue.Generic Objects in Javapublic class IntegerpublicInteger( int x)value = x; publicint intValue( )return value; private int value;Generic Objects in Javapublic class wrapperdemopublic static void main ( String args )Memo

44、ryCell m = new Memorycell ( ) ;m.write ( new Integer ( 37 ) ) ;Integer wrapperVal = ( Integer ) m . Read ( ) ; int val = wrapperVal . intValue ( ) ;System . Out . Println ( “ Contents are : “ + val ) ;1.7An illustration of Integer wrapper classTo get the int value that is hidden inside the Integer o

45、bject, we must convert the result of read back to an Integer , and then use mathod intValue access the value . This involves using a type conversion.Generic Objects in Java2) Java 5 supports generic classes that are very easy to usepublic class GenericMemoryCell public AnyType read( )return storedVa

46、lue; public void write( AnyType x )storedvalue = x; private AnyType storedvalue ;1.9Generic implementation of the MemoryCell classGeneric Objects in JavaWhen a generic class is specified,the class declaration includes one or more type parameters after the class nameUser can create types such as Gene

47、ricMemoryCellGenericMemoryCell but can not createGenericMemoryCellInside the GenericMemoryCell class declaration, we can declare fields of the generic type andmethods that use the generic type as a parameter or return typeGeneric Objects in JavaInterfaces can also be declared as generic.prior to Jav

48、a 5,the Comparable interface was not generic. In Java 5,the Comparable class is generic.package java.lang;public interface Comparablepublic int compareTo (AnyType other ) ;1.10Comparable interface, Java 5 version which is genericGeneric Objects in Javaclass BoxingDemopublic static void main ( String

49、 args )GenericMemoryCell m =new GenericMemoryCell ( ) ;insert a call to the Integer constructor behind the scenesm . Write ( 37 ) ;insert a call to the intValue method behind theint val = m . Read ( ) ;scenesSystem . Out . Println ( “ contents are : “ + val ) ;1.11 Autoboxing and unboxing*編譯程序在箭頭處分別

50、調(diào)用Integer構(gòu)造函數(shù)與intValue方法Generic Objects in Javab)Implementing Generic findMaxThe MemoryCell class required no special properties of Object ;the only operations performed were reference assignments, which are always available.Finding the maximum item in an array of items does require a special proper

51、ty; we must be able to compare two items and decide which is larger.Generic Objects in JavaComparable findMax ( Comparable a )Comparable maxValue = a 0 ; for ( int i = 1; i a.length; i+ )if ( maxValue.lessThan ( ai ) )maxValue = ai;return maxValue;a generic findMax algorithm.Notice that the objects that are