（ data structures, Algorithms and Applications in C++) 马军 信息检索实验室 majun@sdu.edu.cn http://ir.sdu.edu.cn Tel: 91528

自我介绍 本科山东大学计算机 硕士：日本茨城大学 博士：日本九州大学 日本茨城大学访问教授 德国国家计算机研究所(fruanhofer)高级研究员 计算机学院智能信息处理中心，信息检索与知识发现实验室

Content How to represent and store the data in real applications in computer systems? How to design efficient algorithms based on the data structures. How to code the algorithms in C++

Why Data structure Data structures: conceptual and concrete ways to organize data for efficient storage and efficient manipulation Employment of this data structures in the design of efficient algorithms

The Importance of the course The fundamental knowledge for the students in computer science in programming, exams for master and PhD course and the interview for job search.

Tips to learn Data structure understand the concepts on data structure and ideas of algorithms and be be able to explain them in natural languages. Code and run the algorithms given in textbook or exercises in C++ by yourselves.

Textbook Data Structures, Algorithms, And Applications In C++ , by Sartaj Sahni references 该书的中文版 数据结构， 严尉民等编著，清华大学出版社 数据结构, 殷人昆等编著 清华大学出版社

Why Data structure in C++ advantage Master C++ while studying data structure and know how to represent these data structure in C++。 Shortcoming Increasing the difficulty of the study if you are not familiar with C++ suggestion Be able to explain the data structures and algorithms in natural language, and then implement all C++ programs given in this textbook.

Two layers in data structure Logical architecture 数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。队列（queue),栈 (stack） Physical storage 数据元素及其关系在计算机存储器中的存储方式。

Logical structure （逻辑结构） （1）linear structures （线性结构） having one start and end elements respectively. At most have one precursor and one succeed. E.g. list, stack, queue, strings of chars. （2）dynamical structures (动态结构） E.g. trees, graphs, …

Storage structures 顺序（success）存储——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系，如对数组数据的存放 链式（link) 存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系

顺序存储 元素n …….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 10:04

h h ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 1345 链式存储 1345 h 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 10:04

定义：在一种程序设计语言中，变量所具有的数据种类 数据类型 定义：在一种程序设计语言中，变量所具有的数据种类　 　基本数据类型： char int float double void 　构造数据类型：数组、结构体 类Class 数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称 10:04

抽象数据类型 (ADTs: Abstract Data Types) 更高层次的数据抽象 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的操作，如stack, queue, list,.. 10:04

1.4 算法和算法分析 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 算法的描述： 自然语言 流程图 1.4 　算法和算法分析 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 算法的描述： 自然语言 流程图 程序设计语言 伪码 10:04

算法的特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 10:04