數(shù)據(jù)結構英文教學課件：chapter1 Introduction

1、Data StructureSoftware College Northeastern University1Data Structure in C + Data StructureSoftware College Northeastern University2Why Study Data structure Using ComputerWant it to go faster ? Process more data?Want it to do something that would otherwise be impossibleTechnology improves things by

2、a constant factorBut might be costlyGood algorithmic design can do much better and might be cheapSupercomputer cannot rescue a bad algorithm Data StructureSoftware College Northeastern University3Why Study Data Structure Present commonly used data structureIntroduce the idea of tradeoff; reinforce t

3、he concept of costs and benefits associated with every data structure.Measure the effectiveness of a data structure or algorithm.Data StructureSoftware College Northeastern University4What will you learn?What are some of the common data structuresWhat are some ways to implement themHow to analyze th

4、eir efficiencyHow to use them to solve practical problemsData StructureSoftware College Northeastern University5Prerequisitesfour important ideas Iteration - Do, While, RepeatData Representation - variables and pointers - class definitionSubprograms and Recursion - modular design and abstraction Inh

5、eritancediscrete mathData StructureSoftware College Northeastern University6ApproachProgramming by yourself imitate - implementation of data structure such as list etc. realize simple application - develop application using above Design large projects - project Language C + (Visual C +) Data Structu

6、reSoftware College Northeastern University7Course OrganizationChapter 1 IntroductionChapter 2 ArrayChapter 3 ListsChapter 4 Stacks, and QueuesChapter 5 RecursionChapter 6 TreesChapter 7 Priority QueuesChapter 8 SearchingChapter 9 SortingChapter 10 Graph AlgorithmsData StructureSoftware College North

7、eastern University8Course work and GradingProgramming assignments 10%exercises 30% Exams:Closed book Final 60%Data StructureSoftware College Northeastern University9Course MaterialsTextBook - Data Structures and Algorithm Analysis in C+ (second Edition) Mark Allen Weiss POSTS & TELECOM PRESS -數(shù)據(jù)結構與算

8、法分析（C語言描述） Mark Allen Weiss 馮舜璽譯 China Machine PressData StructureSoftware College Northeastern University10Course MaterialsRecommended readings:Herbert Schildt, C+: The Complete Reference, Fourth Edition, 周志榮等譯 ，電子工業(yè)出版社出版 殷人昆，陶永雷等編著：數(shù)據(jù)結構（用面向對象方法與C+描述），清華大學出版社，2005.11殷人昆，徐孝凱編著：數(shù)據(jù)結構習題解析（用面向對象方法與C+描述）

9、 清華大學出版社，2005.7Data StructureSoftware College Northeastern University11Course MaterialsUseful link:Dictionary of Algorithms and Data Structures /dads/Download from Data StructureSoftware College Northeastern University12Chapter 1 Introduction Data StructureSoftware College Northeastern University13O

10、verview Whats the course about The goal to study Data structure Concepts about data structure Review of C+ Algorithm Performance and analysis of algorithmData StructureSoftware College Northeastern University14Before we go into details, what is a data structure exactly?InputSome mysterious processin

11、gOutputWhat is a computer program?Whats the course aboutProgram = Data structure + AlgorithmData StructureSoftware College Northeastern University15An Example of programNetwork connectivityNodesAdd Connections between pairs of nodesIs there a path from Node A to Node B? V0 V2 V3 V1 V5 V4 V7 V6Data S

12、tructureSoftware College Northeastern University16An Example of program in out evidence 3 4 3 4 4 9 4 9 8 0 8 0 2 3 2 3 5 6 5 6 2 9 (234-9) 5 9 5 9 7 3 7 3 4 8 4 8 5 6 (5-6) 0 2 (23-48-0) 6 1 6 1 Data StructureSoftware College Northeastern University17Unionfind AbstractionWhat are critical operation

13、s we needs to support?N Objects cityFIND:test whether two objects are in the same set -Is there a connection between A and B UNION:merge two sets -add a connectionDesign efficient data structure to store connectivity information and algorithms of FIND and UNIONThe numbers of objects and operations c

14、an be hugeData StructureSoftware College Northeastern University18Another Example-Image ProcessingFind connected componentRead in a 2D color image and find regions of connected pixels that have the same colorData StructureSoftware College Northeastern University19Another Example-Image ProcessingData

15、 StructureSoftware College Northeastern University20ObjectsElements are arbitrary objects in a network Pixels in a digital photo Computers in a network Transistors in a computer chip Web pages on the Internet When programming, convenient to name them 0 to N-L When drawing,fun to use animalsData Stru

16、ctureSoftware College Northeastern University21Data StructureSoftware College Northeastern University22Data StructureSoftware College Northeastern University23Data StructureSoftware College Northeastern University24Quick-find AlgorithmData structure Maintain array id with name for each component If

17、p and q are connected,then same id Initialize idi = iFIND.to check if p and q are connected,check if they have the same id UNION. To merge components containing p and q ,change all entries with idp to idqanalysis FIND takes constant number of operations UNION takes time proportional to NData Structu

18、reSoftware College Northeastern University25Another Example: Selection ProblemDescription: Given a group of N numbers, determine the kth largest, where N k .Solution 1:(1) read N numbers into an array, (2) sort the array in decreasing order by some simple algorithm (such as bubblesort), (3) return t

19、he element in position k.Data StructureSoftware College Northeastern University26Another Example:Selection ProblemSolution 2:(1) read the first k elements into an array and sort them in decreasing order, (2) each remaining element is read one by one,(2.1) If it is smaller than the kth element in the

20、 array, it is ignored;(2.2) Otherwise, it is placed in its correct spot in the array, bumping one element out of the array.(3) the element in the kth position is returned as the answerData StructureSoftware College Northeastern University27Another Example:Selection ProblemWhich solution is better wh

21、en (1) N k (2) N k ? why?Data StructureSoftware College Northeastern University28What do these examples illustrate?more than one solutions to a given problemEach solution has its advantages and disadvantages - time - spacePerformance of AlgorithmsAlways ask: How can we do better?Data StructureSoftwa

22、re College Northeastern University29Data Structure?Data structures Representations of data/Methods of organizing datausually in memory, for better algorithm efficiency The data structure selected has a great effect on the details and the efficiency of the algorithm.The algorithm chosen to solve a pa

23、rticular programming problem helps to determine which data structure should be used.Data StructureSoftware College Northeastern University30arrayLinked listtreequeuestackData StructureSoftware College Northeastern University31student tableData StructureSoftware College Northeastern University32Cours

24、e table Linear structureData StructureSoftware College Northeastern University33UNIX file system/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cppData StructureSoftware College Northeastern University34TreeGraph setJIACBDHGFEData StructureSoftware College Northeastern University35Conce

25、pts about Data Structure Data: everything can store in computers data elementdata itemdata objectData StructureSoftware College Northeastern University36Concepts about Data Structure Data structures data object relations of each other Data_Structure = D, R relation nothing -set 1 to 1 -linear struct

26、ure 1 to N -tree N to N -graph or networkLogical structureData StructureSoftware College Northeastern University37Concepts about Data Structure representations of data structure in memory representations of data object representations of relations representation of relations static dynamic hash inde

27、xphysical structureData StructureSoftware College Northeastern University38Concepts about Data StructureData type ADT - abstract data type A set of objects together with a set of operations. It is mathematical abstraction ADT data object; relations of data element; operations; .Data StructureSoftwar

28、e College Northeastern University39Concepts about Data StructureADT NaturalNumber isObjects:An ordered subrange of the integer,starting at zero and ending at the maximum integer(MAXINT) on the computer.Functions:Boolean Is_Zero();Not_num Zero() ;Add(x,y)Equal(x,y) Data StructureSoftware College Nort

29、heastern University40Concepts about Data StructureThe use of ADT divides the programming task into two steps: Implement the operations of the ADT, choose a particular data structure to represent the ADT, and write the functions to implement the operations. Write the main program which calls the func

30、tions of the ADT.Data StructureSoftware College Northeastern University41ADTselect insert delete update Records of studentData StructureSoftware College Northeastern University42Something about C+ Dynamic Memory Management Shallow copy and deep copy Template Inheritance Exception Handling Design pat

31、tern STLData StructureSoftware College Northeastern University43Dynamic Memory ManagementC: malloc() and free()C+: new and deleteData StructureSoftware College Northeastern University44Dynamic Memory ManagementMemory Allocation The new operator works for all data types int* i_ptr = new int;char* c_p

32、tr = new char;float* f_ptr = new float;double* d_ptr = new double;string* str_ptr = new string;/ Dynamically allocate an array of size 100float* ptr1 = new float100;/ Prompt the user for the size of the second arrayint size = 0; cin size;float* ptr2 = new floatsize; Data StructureSoftware College No

33、rtheastern University45Dynamic Memory ManagementObjects can also be dynamically allocated. The new operator, in addition to allocating the memory for an object, will call a constructor for the object. Data StructureSoftware College Northeastern University46#include #include using namespace std;class

34、 my_class private: int x;public: my_class() : x(0) my_class(int p) : x(p) int value() return x; int main(int argc, char* argv) / Allocate a single object my_class* ptr1 = new my_class(4); / Allocate an array of objects my_class* ptr2 = new my_class10; cout value() endl; cout value() endl; return EXI

35、T_SUCCESS; Data StructureSoftware College Northeastern University47Dynamic Memory ManagementMemory Allocation The new operator always returns a memory address. / Allocate a single integerint* ptr = new int;*ptr = 10;cout Address: ptr endl;cout Value: *ptr FirstName=new string(*(rhs.FirstName); this-

36、LastName= new string(*(rhs.LastName); this-EmployeeNum = rhs.EmployeeNum; Teacher & Teacher: operator= (const Teacher & rhs) *(this-FirstName) = *(rhs.FirstName); *(this-LastName)= *(rhs.LastName); this-EmployeeNum = rhs.EmployeeNum; Data StructureSoftware College Northeastern University54TemplatesM

37、any algorithms are type independent. We will describe how type-independent algorithms are written in C+ using the template.Template Functions Template Classes Data StructureSoftware College Northeastern University55Template FunctionsTemplate functions allow the programmer to create functions indepen

38、dent of the data types of their parameters. Function overloading int max(int x, int y) return x y ? y : x; float max(float x, float y) return x y ? y : x; string max(string& x, string& y) return x y ? y : x;A template function template T my_max(T x, T y) return x y ? y : x; Data StructureSoftware Co

39、llege Northeastern University56Template function : Insertion sort fuctiontemplate void insertionSort(vector & a) for(int p = 1;p 0 & tmp aj-1;j-) aj = aj-1; aj = tmp; int main() vector array; int x; cout “Enter items to sort:” x) array.push_back(x); insertionSort(array); cout“Sorted items are:”endl;

40、 for(int i = 0;iarray.size();i+) coutarrayiendl; return 0;Data StructureSoftware College Northeastern University57Function Objectstemplate const comparable& findMax(vector & a) int maxIndex = 0 ; for(int i = 1;i a.size() ; i+) if(amaxIndex ai) maxIndex = i; return ai;The function templateIt works on

41、ly for objects that have an operator function definedFor the class Teacher, sometimes we want to compare by Firstname, sometimes by Lastname. How to do?Data StructureSoftware College Northeastern University58Function objectsThe solution is to pass the comparison function as a second parameter to fin

42、dMax findMax use the fuction of paramenter instead of the existence of an operator.findMax will now have two parameters: a vector of Object and a comparison function.Function object funtor often contains no data but does contain a single method with a given name specified by the generic algorithm. D

43、ata StructureSoftware College Northeastern University59Function objecttemplate Const object& findMax(const vector & a, comparable isLessThan) int maxIndex = 0 ; for(int i = 1;i a.size() ; i+) if( isLessThan(amaxIndex , ai) ) maxIndex = i; return a; if(isLessThan.operator()(amaxIndex,ai) )class LessT

44、hanByFirstName public Bool operator ( ) (const Teacher &lhs, const Teacher &rhs) const return lhs.FirstName rhs.FirstName; ;main() vector a; cout findMax(a,LessThanByFirstName()endl;Data StructureSoftware College Northeastern University60The template class dataList #ifndef DATALIST_H #define DATALIS

45、T_H #include template class dataList private: Type *Element; int ArraySize; void Swap (const int m1, const int m2); int MaxKey (const int low, const int high);Template class declarationTemplate ClassesData StructureSoftware College Northeastern University61 public: dataList (int size = 10) : ArraySi

46、ze (size), Element (new Type Size) dataList ( ) delete Element; void Sort ( ); friend ostream& operator (ostream& outStream, const datalist& outList); friend istream& operator (istream& inStream, const datalist& inList); ; #endifTemplate ClassesData StructureSoftware College Northeastern University6

47、2dataList類中所有操作作為模板函數(shù)的實現(xiàn) template void dataList : Swap (const int m1, const int m2) /交換由m1, m2為下標的兩個數(shù)組元素的值 Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; Data StructureSoftware College Northeastern University63 template int dataList: MaxKey (const int low, const int high) /查找數(shù)組E

48、lementlowElementhigh中 /的最大值，函數(shù)返回其位置 int max = low; for (int k = low+1, k = high, k+) if ( Elementmax Elementk ) max = k; return max; Data StructureSoftware College Northeastern University64 template ostream&operator (ostream& OutStream, const dataList OutList) OutStream “Array Contents : n”; for (in

49、t i = 0; i OutList.ArraySize; i+) OutStream OutList.Elementi ; OutStream endl; OuStream “Array Current Size : ” OutList.ArraySize endl; return OutStream; Data StructureSoftware College Northeastern University65 template istream& operator (istream& InStream, dataList InList) /輸入對象為InList，輸入流對象為InStre

50、am cout InList.ArraySize; cout “Enter array elements : n”; for (int i = 0; i InList.ArraySize; i+) cout “Elememt” i InList.Elementi; return InStream; Data StructureSoftware College Northeastern University66 template void dataList:Sort ( ) /按非遞減順序對ArraySize個關鍵碼 /Element0ElementArraySize-1排序。 for ( in

51、t i = ArraySize -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) swap (j, i); #endifData StructureSoftware College Northeastern University67Inheritance and derivationwe can build a new class by deriving the new class from an already existing class. The mechanism for this derivation is inheritance,

52、 and the derived class is said to be inherited from the original class.Base classParent classDerived classChild classData StructureSoftware College Northeastern University68Inheritance and derivationSyntax:class DerivedClass：Inheritance Mode BaseClasspublic:/protected:/private:/;Data StructureSoftwa

53、re College Northeastern University69Public, Private, and Protected InheritanceProtected Inheritancecant accessprivateprivateprivateprivateprotectedprivateprivatepubliccant accessprotectedprivateprotectedprotectedprotectedprotectedprotectedpubliccant accesspublicprivateprotectedpublicprotectedpublicp

54、ublicpublicin derived classinheritance mode members in base classData StructureSoftware College Northeastern University70virtual functionIf a member function is declared to be virtual, dynamic binding is used. The decision about which function to use to resolve an overload is made at run time, if it

55、 cannot be determined at compile timeVirtualness is inherited. It is override but not overload.A run-time decision is needed only when an object is accessed through a pointer or reference to a base class. Data StructureSoftware College Northeastern University71Example:#include using namespace std;cl

56、ass B0 / the declaration of base class B0public: / public methodsvirtual void display() / virtual member function coutB0:display()endl; ;class B1: public B0/public derivation public: void display() coutB1:display()endl; ;class D1: public B1/public derivation public: void display() coutD1:display()di

57、splay(); void main() /main functionB0 b0, *p; /declare object and pointer of base class B0B1 b1; /declare object of derived class B1D1 d1; /declare object of derived class D1p= &b0;fun(p);/ call the member function of base class B0p= &b1;fun(p);/call the member function of derived class B1p= &d1;fun

58、(p);/call the member function of derived class D1Result： B0:display() B1:display() D1:display()72Data StructureSoftware College Northeastern University73Abstract Method (Pure Virtual Function) and Abstract Base ClassA method is declared abstract by specifying that it is virtual and by supplying = 0

59、in the interface in place of an implementation.An abstract method has no meaningful definition and is thus always defined in the derived class.A class that has at least one abstract method is called an abstract classBecause the behavior of an abstract class is not completely defined, abstract classe

60、s can never be instantiated. When a derived class fails to override an abstract method with an implementation, it remains abstract, and the compiler reports an error if an attempt to instantiate the abstract derived class is made.Data StructureSoftware College Northeastern University74void display(