成果数据结构-structure

1、Data StructureYin LiangInstitute of Geophysics and GeomaticsPrerequisite(预备知识)Computer Architecture (计算机体系结构)C Programming (C语言编程)Discrete Mathematics (离散数学)Probability (概率论)OutlinesTextbooks and ReferencesWhy Data Structure?What is Data Structure?What is Algorithms?Designing AlgorithmsAnalysis of A

2、lgorithmsTextbooks and References严蔚敏、吴伟民编著，数据结构(C语言版)，清华大学出版社。（Textbook）Donald E. Knuth，The Arts of Computer Programming (Volume I、II、and III) ，Addison Wesley.Donald E. KnuthTuring Prize Winner (图灵奖)Professor Emeritus at Stanford UniversityWebsite: The Arts of Computer Programming(7 Volumes)Volume I

3、: Fundamental AlgorithmsVolume II: Semi-numerical Algorithms(半数值算法)Volume III: Sorting and SearchingVolume 4A: Combinatorial Algorithms, Part I (2011)Textbooks and ReferencesThomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、Clifford Stein，Introduction to Algorithms，The MIT Press.The 1996 vers

4、ion only Contains the previous 3authors.Introduction to AlgorithmsCharles Leiserson in MITYou can also access the videotaped course on the website: Textbooks and ReferencesMark Allen Weiss, Data Structure and Algorithm Analysis in C (Second Edition), Addison Wesley.Why Data Structure?Rapid developme

5、nt of computer industries and applicationsNot only numerical analysis, but also computers are supposed to process characters, tables and pictures, etc.Data Structure can deal with those non-numerical things and also improve your programming skills. Why Data Structure?Real World InformationMappingDat

6、a StructureDigital Data Stored in ComputersWhat is Data Structure?Organization of DataSet of data, which have some special relations to each otherSet (集合)Linear Structure (线性结构)Tree Structure (树型)Network Structure (网状结构)Algorithm HistoryOrigin from the name of the 9th century Persian Muslim mathemat

7、ician Abu Abdullah Muhammad ibn Musa Al-KhwarizmiAl-Khwarizmis name was translated into algorithm by the 18th century via European Latin.Algorithm HistoryEuclid has created an algorithm that has been given its name.The algo serves to calculate the greatest common divisor, here is it:divide the numbe

8、r a by b, the remainder is r replace a by b replace b by r continue until a cant be more divided. In this case, a is the gcd. What is Algorithms?Set of simple instructions to be followed to solve a problemFeatures of Algorithms:Finity （有限性）Determinacy （确定性）Executability （可执行性）Input/Output （输入/输出）Alg

9、orithms Design CriteriaCorrectness （正确性）Readability （可读性）Robustness （健壮性、稳定性）Efficiency and low memory requirement （效率）Algorithm AnalysisThe theoretical study of computer program performance and resource usage.Is it the most important thing that we should concern in the software engineering?Correctn

10、ess, readability, robustness, security(安全性), modularity(模块化), reusability(可重用性), user friendliness(用户友好性)Why Algorithms?Feasibility vs. infeasibilityClean way to think about solving problemsUnity equivalent to pay for security, user friendliness, functionality and so on.Challenge for speedRunning Ti

11、meDepends on inputs (sorting pokers)Depends on input size (parameterized by input size, asymptotic notation)Upper bound of running timeguarantee to usersRunning TimeHow to estimate the running time of algorithmsPost-statistics (事后统计)Asymptotic notation (渐进表示、事前估计)Running TimePost-statisticsExecute the algorithms on almost the same environment over tons of inputs and compare their perfor