数据结构_第一章2.ppt

 Software College  Northeastern University Autumn 2005;本课程学习的目的;本课程学习要求;教材及参考书(1);教材及参考书(2);学时分配及考核方式;教师答疑方式;内容安排(1);内容安排(2);学时安排;上机实验内容;第一章 绪论; 第一章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法及其分析 ;本章教学要求： (1) 了解数据结构的基本概念，理解常用术语. (2) 了解抽象数据类型的定义、表示和实现方法. (3) 掌握算法的定义及特性，算法设计的要求. 重点: (1) 了解数据结构的基本概念，理解常用术语。 (2) 抽象数据类型表示法、类C语言语法。 (3) 算法的特性，算法设计要求，算法分析。 难点: (1) 数据元素间的四种结构关系。 (2) 抽象数据类型表示法。 (3) 算法分析。 ;1.1 什么是数据结构;二、 数值问题与非数值问题; 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机200102 石磊 男 83/12/21 汕头 512 00计算机1 00202 李梅 女 83/02/23 阳江 532 00计算机2 00301 马耀先 男 82/07/12 广州 509 00计算机3; 图书馆信息管理系统;1.1 什么是数据结构; 人机对奕; 多叉路口交通灯问题 ; 多叉路口交通灯问题;1.1 什么是数据结构;1．2 基本概念和术语;举例：数据、数据元素、数据项及其关系;4、数据对象：性质相同的数据元素的集合. 5、数据处理：指对数据进行检索、插入、删除、合并、拆分、排序、统计和转换等的操作。 6、数据结构：是相互间存在关系的数据元素集合。 例如： 一个含12位数的十进制数可以用三个4位的十进制数表示 3214,6587,9345 ━ 记 a1(3214),a2(6587),a3(9345) 在a1、a2和a3 之间存在“次序”关系 ?a1,a2?、?a2,a3? ;二、数据结构的三方面 1） 数据的逻辑结构  2） 数据的存储结构 3） 数据的运算; 某班学生基本情况登记表，记录了每个学生的学号、姓名 、专业、政治 面貌 ，表中的记录是按学生的学号顺序排列的。 ; 家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如右图表示。;? 图结构: 元素之间是多对多的关系。 如交通网、计算机网络等。 ? 集合: 元素间为松散的关系。例如： ;数据(逻辑)结构的二种常用表示方法;例如：学生基本情况表的二元组表示（D，S） ;1．2 基本概念和术语; ? 链接结构： 使用附加的 指针表示元素间的关系。;1．2 基本概念和术语;1．2 基本概念和术语;1．2 基本概念和术语;1．4 算法与算法分析;二、抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 数据对象和数据关系用伪码描述 基本操作名（参数表） 初始条件：（初始条件描述） 操作结果：（操作结果描述）;名称;1．3 抽象数据类型;1．3 抽象数据类型;1．3 抽象数据类型;类C语言语法(4);ADT List{ //线性表的类C表示数据对象: D={ai| ai(-