PPT《*》

* 数据结构计算机学院肖明军Email: xiaomj@ustc.

edu.cnhttp://staff.ustc.edu.cn/~xiaomj * 课程简介 先修课程及条件 程序设计的经验、C、离散数学、概率分析教材:数据结构(C语言版),严蔚敏,清华大学出版社考核:考试+作业+上机参考书 C++ 数据结构,William Ford 清华影印版 数据结构和程序设计, Robert,Kruse.2nd版*§Ch.1 绪论 重要性人类社会已步入信息社会计算机不再仅仅局限于科学计算,已深入到社会生活的各个领域 当前热点领域智能感知与物联网大数据与云计算人工智能量子计算 * * § Ch.1 绪论 重要性计算机:硬件+软件 算法+数据结构=程序设计(N.Wirth,84年图灵奖得主)两个问题:信息的表示和处理 信息的表示和组织又直接关系到处理信息的程序的效率.随着应用问题的不断复杂,导致信息量剧增与信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂.因此,必须分析待处理问题中的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题. * 编写解决实际问题的程序的一般过程: 如何用数据形式描述问题?―即由问题抽象出一个适当的数学模型;

问题所涉及的数据量大小及数据之间的关系;

如何在计算机中存储数据及体现数据之间的关系?处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好?上面所列举的问题基本上由数据结构这门课程来回答. § Ch.1 绪论 * 姓名 电话号码 陈海

13612345588 李四锋

13056112345 ... ... 例1:电话号码查询系统 设有一个电话号码薄,它记录了N个人的名字和其相应的电话号码,假定按如下形式安排:(a1, b1),(a2, b2),…(an, bn),其中ai, bi(i=1,2…n) 分别表示某人的名字和电话号码. 本问题是一种典型的表格问题.如表所示,数据与数据成简单的一对一的线性关系. 线性表结构 * 例2:磁盘目录文件系统 磁盘根目录下有很多子目录及文件,每个子目录里又可以包含多个子目录及文件,但每个子目录只有一个父目录,依此类推:本问题是一种典型的树型结构问题,如图所示,数据与数据成一对多的关系,是一种典型的非线性关系结构―树形结构. 树形结构 * 例3:交通网络图 从一个地方到另外一个地方可以有多条路径.本问题是一种典型的网状结构问题,数据与数据成多对多的关系,是一种非线性关系结构. 佛山 惠州 广州 中山 东莞 深圳 珠海 网状结构 * §1.1 基本概念和术语 数据:信息载体 客观事物的符号表示,能由计算机程序识别、存储和加工处理的符号集合 所有能够数字化的信息均可认为是数据数据元素:数据的基本单位,在程序中通常作为一个整体来进行考虑和处理 同义词:元素、结点、顶点、记录、对象、元组等数据项:具有独立含义的最小标识单位,客观事物某一方面特性的数据描述 同义词:字段、域、属性等 * §1.1 基本概念和术语 数据结构:相互之间存在一种或多种特定关系的数据元素的集合,即数据的组织形式数据的逻辑结构:数据元素之间的逻辑关系数据的存储结构:数据元素及其关系在计算机存储器内的表示数据的运算:对数据施加的操作 * §1.1 基本概念和术语 数据结构举例 系别 姓名 职称 SCI EI 经费

1 张明 教授

5 1

20 1 王华 教授

6 3

15 …

23 李立 教授