数据结构lecture1introduction

1、5Lecturel IntroductionPla n to give the lecture by clear expla nati on with particular examples.Make use of all kinds of in strume nts especially multimedia.To attract the atte nti on of stude nts through putt ing questi ons and other in teractive method.Try to lead the stude nts their way of thi nk

2、ing.Course Layout1. import2.newcontent3. summaryIn troduce the new course10 minu tes1. Pseudocode18 minu tes2. Abstract Data Type30 minu tes3. algorithm efficie ncy and big-O an alysis30 minu tes1. review the key points and the difficulties2. questions from students2 mi nutehomework3.ContentThis tex

3、t assumes that the student has a solid foundation in structured programming principles and has written programs of moderate complexity. Although the text uses C+ for all of its implementation examples, the design and logic of the data structure algorithms are based on pseudocode. This approach creat

4、es a Ian guage-i ndepe ndent environment for the algorithms. In this chapter we establish a backgro und for the tools used in the rest of the text, most specifically pseudocode, the abstract data type, and algorithm efficiency analysis. We also introduce the measures we use throughout the text to di

5、scuss algorithm efficie ncy.1-1 PSEUDOCODEAlthough several tools are used to defi ne algorithms, one of the most com mon is pseudocode Pseudocode is an English-like representation of the code required for an algorithm. It is part En glish, part structured code. The En glish part provides a relaxed s

6、yn tax that is easy to read. The code part con sists of an exte nded version of the basic algorithmic con structs-seque nee, select ion, and iteration.Note One of the most com mon tools for defi ning algorithms is pseudocode, which is part En glish, part structured code.In this text we use pseudocod

7、e for both data structures and code. The basic format for data types con sists of the n ame of the data and its type en closed in poin ted brackets as show n below count The structure of the data is indicated by indenting the data Items as shown below.n odedata Link end nodeThis data definition desc

8、ribes a node in a self-referential linked list that consists of a nested structure (data) and a pointer to the next node (link). It assumes that the data description for dataType has bee n previously defi ned.As mentioned, the pseudocode is used to describe an algorithm. To facilitate a discussion o

9、f the algorithm statements, we number them using the hierarchical system shown in Algorithm 1-1 and fully described in the followi ng sect ions.Algorithm HeaderEach algorithm beg ins with a header that n ames it, describes its parameters, and lists any pre- and postc on diti ons. This in formati on

10、is importa nt because the programmer using the algorithm often sees on ly the header In formatio n, not the complete algorithm. Therefore, the header in formatio n must be complete eno ugh to com muni cate to the programmer everyth ing he or she must know to use the algorithm.Purpose, Conditions, an

11、d ReturnThe purpose is a short statement about what the algorithm does. It needs to describe only the gen eral algorithm process in g, it should not attempt to describe all of the process ing. For example, in Algorithm 1-1, the purpose does not need to state that the file will be opened or how the r

12、eport will be prin ted. Similarly, in the search example, the purpose does not n eed to state which of the array searches will be used.The prec on diti on lists any precursor requireme nts for the parameters. For example, in Algorithm 1-1, the algorithm that calls sample must initialize the page num

13、ber. Sometimes there are no prec on diti ons, in which case we still listthe prec on diti on with the stateme nt nothing, as show nbelow.Pre Nothi ngIf there are several in put parameters, the n the prec on diti on should be show n for each. For example, a simple array search algorithm would have th

14、e follow ing header:In search, two parameters are passed by value (val) and one by reference (ref). The precondition specifies that the two input parameters, list and argument, must be initialized. If a binary search were being used, the precondition would also state that the array data must be orde

15、red.The postcondition identifies any action taken and the status of any output parameters. In Algorithm 1-1, the postcondition contains two parts. First, it states that the report has been printed. Second, the reference parameter, pageNumber, contains the updated number of pages in the report. In th

16、e search algorithm shown above, there is only one postcondition, which may be one of two different values.If a value is returned, it will be identified by a return condition. Often there is none, and no return condition is needed. In Algorithm 1-1, we return the number of lines printed. The search a

17、lgorithm returns a Boolean-true if the argument was found, false if it was not found.Statement NumbersStatements are numbered using an abbreviated decimal notation in which only the last of the number sequence is shown on each statement. The expanded number of the statement in Algorithm 1-1 that rea

18、ds the file is 3.1. The statement that writes the page heading is 3.2.3. This technique allows us to identify an individual statement while providing statements that are easily read.Algorithm 1-1 also provides an example of all three structured programming constructs. Statement 2 is an example of a

19、sequence, statement 3.2 is an example of a selection statement, and Statement 3 is an example of a loop. The end of the selection is indicated by the end in Statement 3.3. Similarly, the end of the loop is indicated by end loop in Statement 4.VariablesIt is not necessary to define every variable use

20、d in the algorithm, especially when the context of the data is indicated by its name. To ensure that the meaning is understood, we use intelligent data names-that is, names that describe the meaning of the data. In Algorithm 1-1, pageNumber is an example of an intelligent data name.The selection of

21、the name for an algorithm or variable goes a long way toward making the algorithm and its coded implementation more readable. In general, you should follow these rules:1. Do not use single character names. Even the traditional for loop variables of i and j should be avoided, although we sometimes us

22、e them in C+ for loops. There is always a better name. For example, if you are searching a two-dimensional array in which each row represents a different student and each column represents a quiz score, then student would be a better Index for the rows than i. Likewise, quiz would be a better index

23、for the columns than j.2. Do not use generic names. Examples of generic names are count, sum, total, row, column, and file. In a program of any size there will be several counts, sums, and totals. Rather, add an intelligent qualifier to the generic name so that the reader knows exactly which piece o

24、f data is being referred to. For example, studentCount and numberOfStudents are both better than count.3. Abbreviations are not excluded as Intelligent data names. For example, stuCnt is a good abbreviation for studentcount and numOiStu is a good abbreviation for numberOf Students. Note, however, th

25、at noStu would not be a good abbreviation for numberOfStudents because it is too easily read as no students,Algorithm AnalysisFor all but the simplest algorithms, we follow the algorithm with an alysis sect ion that expla ins some of its salie nt poin ts. Not every line of code is expla in ed. Rathe

26、r, the an alysis exam ines only those points that either need to be emphasized or that may require some clarification. It also often in troduces style or efficie ncy con sideratio ns.Statement ConstructsWhen he first proposed the structured programming modeL, Niklaus WJrth stated that any algorithm

27、could be writte n with only three program ming con structs: seque nee, select ion, and loop.Our pseudocode contains only these three basic constructs. The implementation of these constructs relies on the richness of the Implementation Ianguage. For example, the loop can be impleme nted as a while, d

28、o. while, or for stateme nt in the C+ Ian guage.SequenceA sequence is a series of statements that do not alter the execution path within an algorithm. Although it is obvious that stateme nts such as assig n and add are seque nee stateme nts, it is not so obvious that a call to other algorithms is al

29、so con sidered a seque nee stateme nt. The reas on it is lies in the structured programming concept that each algorithm has only one entry and one exit. Furthermore, when an algorithm completes, it returns to the statement immediately after the call that in voked it. Therefore, we can properly con s

30、ider an algorithm call a seque nee stateme nt.SelectionSelect ion stateme nts evaluate one or more alter natives. If the alter natives are true, one path is taken. If the alternatives are false, a different path is taken. The typical selection statement is the two-way selection if (condition) action

31、l else action2. Whereas most Ianguages provide for multiway select ions, such as the switch In C+, we provide none in the pseudocode. The parts of the select ion are ide ntified by inden tati on, as show n in the short pseudocode stateme nt below.Pseudocode ExampleAs an example of pseudocode, con si

32、der the logic required to calculate the deviati on from a mean.In this problem, we must first read a series of numbers and calculate their average. Then, we subtract the mean from each number and print the number and its deviation. At the end of the calculation, we also print the totals and the aver

33、age.The obvious solution is to place the data in an array as they are read. Algorithm 1-2 contains the code for this simple problem as it would be implemented in a callable algorithm.1-2 THE ABSTRACT DATA TYPEIn the history of program ming con cepts, we started with non structured, li near programs,

34、 known as spaghetti code in which the logic flow wound through the program like spaghetti on a plate. Next came the concept of modular programming , in which programs were organized in functions, each of which still used a linear coding technique. The structured programming concepts we still use tod

35、ay were formulated in the 1970s.A data type con sists of two parts, a set of data and the operati ons that can be performed on the data. Thus we see that the in teger type con sists of values (whole nu mbers in some defi ned ran ge) and operations add, subtract, multiply, divide, and any other opera

36、tions appropriate for the applicati on).The latest development in the theory of program design is object- oriented programming .In an object-orie nted approach, the functions are developed around an object, such as a lin ked list. One part of the object-orie nted con cept is encapsulation, in which

37、all process ing for an object is bundled together in a library and hidden from the user. All the programmer knows is the call formats that are required to com muni cate with the object and its fun cti ons. En capsulati on is one of the primary concepts behind the abstract data type. As we will see,

38、the abstract data type is impleme nted as a C+ class.Atomic and Composite DataAtomic data are data that we choose to con sider as a sin gle, non decomposable en tity. For example, the integer 4562 may be considered as a single integer value. Of course, you can decompose it into digits, but the decom

39、posed digits will not have the same characteristics of the original Integer; they will be four single-digit integers in the range 0 to 9. In some Ianguages, atomic data are known as scalar data because of their nu meric properties.An atomic data type is a set of atomic data with identical properties

40、. These properties distinguish one atomic data type from another. Atomic data types are defined by a set of values and a set of operati ons that act on the values.Note Atomic Data Type1.A set of values2.A set of operati ons on valuesFor example, we can defi ne the three atomic data types show n belo

41、w.The opposite of atomic data is composite data. Composite data can be broken out into subfields that have meaning. As an example of a composite data Item, consider your telephone number. A teleph one nu mber actually has three differe nt parts. First, there is the area code. Then, what you consider

42、 to be your phone number is actually two different data items, a prefix consisting of a three-digit excha nge and the nu mber with inthe excha nge, con sisti ng of four digits. In the past,these prefixes were n ames such as DAvenport and CYpress. You will sometimes hear composite data referred to as

43、 structured data because they are impleme nted using structure stateme nts such as struct. We do not use this term because it is easily con fused with data structure.Data StructureA data structure is an aggregation of atomic and composite data types into a set with defined relati on ships. In this d

44、efi niti on, structure mea ns a set of rules that hold the data together. I n other words, if we take a comb in ati on of data types and fit them into a structure such that we can defi ne its relati ng rules, we have made a data structure. Data structures can be n ested. We can have a data structure

45、 that con sists of other data structures. For example, we can defi ne the two structures array and record as show n in Table 1-1.Note Data Structure1. A comb in ati on of eleme nts each of which is either a data type or ano ther data structure2. A set of associati ons or relati on ships (structure)

46、in volvi ng the comb ined eleme ntsArrayRecordHomogeneous sequence of data or data types known as eleme ntsHeteroge neous comb in ati on of data into a sin gle structure with an identified keyPositi on associatio n among the eleme ntsNo associati onMost of the programming Ianguages support several d

47、ata structures. In addition, modem program ming Ian guages allow programmers to create new data structures for an applicatio n.Abstract Data TypeGen erally speak ing, programmers capabilities are determ ined by the tools in their tool kits. These tools are acquired by educati on and experie nee. You

48、r kno wledge of data structures is one of your tools.Whe n we first started program ming there were no abstract data types. If we wan ted to read a file, we wrote the code to read the phys teal file device. It did not take long to realize that we were writ ing the same code over and over aga in. So

49、we created what is known today as an abstract data type (ADT) . We wrote the code to read a file and placed it in a library for all programmers to use.This con cept is found in modem Ian guages today. The code to read the keyboard is an ADT. It has a data structure, character, and a set of operation

50、s that can be used to read that data structure. The rules allow us to not only read the structure but also convert it into differe nt data structures such as In tegers and stri ngs.With an ADT, users are not concerned with how the task is done but rather with what it can do. In other words, the ADT

51、consists of a set of definitions that allow programmers to use the functions while hiding the implementation. This generalization of operations with unspecified impleme ntatio ns is known as abstract ion. We abstract the esse nce of the process and leave the impleme ntati on details hidde n.Note The

52、 con cept of abstract ion means:We know what a data type can do.How It is done is hidde n.Con sider the con cept of a list. At least three data structures will support a list. We can use an array, a linked list, or a file. If we place our list in an ADT, users should not be aware of the structure we

53、 use. As long as they can in sert and retrieve data, it should make no differe nce how we store the data. Figure 1-1 shows four logical structures that might be used to hold a list.(b) A linked list何 A tree糾 A network但)A matrixAs another example, consider the system analyst who needs to simulate the

54、 waiting line of a bank to determine how many tellers are needed to serve customers efficiently. This analysis requires the simulation of a queue. However, queues are not gen erally available in program ming Ian guages. Even if a queue type were available, ouranalyst would still need some basic queu

55、e operations, such as enqueuing (Insertion) and dequeu ing (deleti ng), for the simulati on.There are two pote ntial soluti ons to this problem: (1) we can write a program that simulates the queue our an alyst n eeds (In this case, our soluti on is good only for the one applicati on at hand) or (2)

56、we can write a queue ADT that can be used to solve any queue problem. If we choose the latter course, our analyst will still need to write a program to simulate the banking application, but doing so will be much easier and faster because he or she will be able to concentrate on the applicati on rath

57、er tha n the queue.Let us now fin ally defi ne an ADT. An abstract data type is a data declarati on packaged together with the operati ons that are meanin gful for the data type. In other words, we en capsulate the tha and the operations on data and we hide them from the user.Note Abstract Data Type

58、1.Declaratio n of data2.Declaratio n of operati ons3.En capsulati on of data and operati onsWe cannot overstress the importa nee of hidi ng the impleme ntati on. The user should not have to know the data structure to use the ADT. Referring to our queue example, the application program should have no kno wledge of the data structure. All references to and man ipulati on of the data in the queue must be han dled through defi ned in terfaces to the structure. Allow ing the applicati on program to directly refere nee the data structure is a com mon fault in many