




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
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:學(xué)生表:邏輯結(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 : 左上角坐標(biāo), 右下角坐標(biāo),邊線顏色, 內(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)復(fù)習(xí)一下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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 七年級英語聽力強化計劃他
- 人教版七年級科學(xué)教學(xué)計劃
- 人教版PEP小學(xué)英語四年級上冊課時安排計劃
- 2025年中國半導(dǎo)體激光市場供需預(yù)測及投資戰(zhàn)略研究咨詢報告
- 2025年鋇氧化物項目安全風(fēng)險評價報告
- 2025年中國雞飼料行業(yè)市場運行現(xiàn)狀及未來發(fā)展預(yù)測報告
- 2025年中國智能公交系統(tǒng)行業(yè)投資研究分析及發(fā)展前景預(yù)測報告
- 中國牛仔衣褲行業(yè)市場發(fā)展前景及發(fā)展趨勢與投資戰(zhàn)略研究報告(2024-2030)
- 高鐵聲屏障項目可行性研究報告
- 2025年中國鮑魚養(yǎng)殖市場競爭策略及行業(yè)投資潛力預(yù)測報告
- 天津大洋寧夏隆德萬頭高端肉牛全產(chǎn)業(yè)鏈建設(shè)項目環(huán)境影響報告書
- 濟源市新紀(jì)元礦業(yè)有限公司蓮東鐵礦礦山地質(zhì)環(huán)境保護與土地復(fù)墾方案
- 壯醫(yī)藥水蛭療法
- 中職學(xué)校招生介紹課件
- 《繃帶包扎法》課件
- 南京中聯(lián)水泥有限公司石灰石礦礦山地質(zhì)環(huán)境保護與土地復(fù)墾方案
- 打印-初升高銜接教材物理
- 2023年湖北省高中學(xué)業(yè)水平合格性考試語文試卷真題(答案詳解)
- 中國現(xiàn)代文學(xué)中的革命文學(xué)思潮
- 寧夏銀川外國語實驗學(xué)校2024屆數(shù)學(xué)七下期末教學(xué)質(zhì)量檢測試題含解析
- 農(nóng)村集體聚餐食品安全管理培訓(xùn)課件
評論
0/150
提交評論