数据结构授课教学课件Datastructure

1、Data structureBasic ConceptDataThe set of symbols which can be recognized, stored and processed by the computer.Is the carrier of information.ExamplesInteger or real. (processed by digital processing programs)Source program.( processed by compiler)Images. (processed by image processing programs)Basi

2、c ConceptData elementThe basic unit to compose a data.Can also be referred as element, record, node or vertex.Data itemData element is composed by data items.Is the smallest unit discussed in data structure.Data item is also called domain or field.Basic ConceptData structureThe set of data elements

3、which have some relationship between each other.Logical structureThe logical relationship between each other.Storage structureStorage map of logical structure in storage.Basic ConceptThe logical structure can be formally represented as : L = ( N, R )N: the set of the node. R: the set of relation on

4、N.ExamplesL = ( N, R )N = a0, a1, a2 R = r r = ( a0, a1 ), ( a0, a2 ) Basic ConceptLet L=( N, R ) is a logical structure, R= r ，If a, bN, and relation ( a, b )R， then ：a is predecessor node of bb is successor node of ba and b are adjacent nodes If a node dont have predecessor, it is called start nod

5、e. If a node dont have successor, it is called final node.If a node have both predecessor and successor, it is called internal node.Basic ConceptLogical structure of dataLiner structureTree structureGraph structureSet structureBasic StructureLinear StructureThere is only one start node and final nod

6、e, every internal node have one and only one predecessor and successor.None linear structureNodes in the structure can have more than one predecessor and successor.Basic conceptEvery line represents a node (element), every line is composed of 9 domains (data items). The first line is start node, the

7、 last line is final node. The lines between the first line and last line are internal nodes.The logical structure of a table is linear structure.Basic conceptStorage structure of dataThe mapping of data elementThe mapping of relationshipThe mapping of data elementrepresenting a data element using bi

8、nary bits. (321)10 = (101000001)2 A = (001000001)2Basic conceptMapping of relationshipSequential mappingrepresenting successor relationship using relative storage location.Chaining mappingrepresenting successor relationship using pointer. x ystorage structure only contains data element information.

9、No additional info. y xBesides data element information, there is additional information in storage structure to represent the logical structure.Basic ConceptAlgorithm: a limit sequence of instructions used to solve some problems.A algorithm can be described using nature language or pseudo programmi

10、ng language.An algorithm must meet the following 5 requirements: (1) finite (2) definitude (3) input (4) output (5) feasibilityBasic conceptFinite: terminate after a finite number of steps Definitude: clear and unambiguous Same input will get same output.Input: one algorithm can have zero or many in

11、put data. The input data get from definite object set.Output: an algorithm can have one or many output. The output has specific relationship with input.Feasibility: instruction is basic enough to be carried outBasic conceptThe principles of designing algorithm CorrectnessReadabilityrobustEfficient a

12、nd low storage requirement.Basic conceptCorrectness: for all legal input, after finite times of execution, the algorithm will generate correct result.Readability : easier for designer and others to read, understand, update and reuse. Robust: When input illegal data, the algorithm can react properly.

13、Efficient and low storage requirement: efficiency means the execution time of the algorithm; Amount of storage means the maximum storage requirement. Both of them related to the scale of the problem.Basic conceptCorrection of the algorithmThere is no grammar mistakes in the program.The program can o

14、utput correct results for several groups of input data. The program can output required output for typical ,selected input. The program can output required output for all legal input.Basic ConceptPerformance Analysis Analysis after execution(machine independent)Must execute the programAffected by so

15、me other factorsAnalysis before executionspace complexity: storage requirementtime complexity: computing timeBasic conceptFactors affect execution timeThe strategy selected by the algorithmThe scale of the problemThe programming languageThe machine language generated by the compiler.The speed the co

16、mputer executing instructions.It is not good for evaluating the efficiency of an algorithm based on absolute time unitBasic ConceptWithout considering the software and hardware factors affecting the efficiency of the algorithm, “the running workload ” of a specific algorithm depends only on the scal

17、e of the problem (represented using n). Or it is the function of the scale of the problem. For example, with the increment of the scale of the problem, the increasing ratio of the execution time is the same as f(n), then we denote it as: T (n) = O( f (n) )T (n) is called time complicity of the algor

18、ithmBasic conceptAlgorithm=control structures + basic operationsNormally the execution times of some basic operations are use as the time measurement of complicity of the algorithm.void mult(int an, int bn, int(&c)nn ) for (i=0; in; +i) for (j=0; jn; +j) cij = 0; for (k=0; kn; +k) cij += aik*bkj; /for /multO(n3)Basi