数据结构华中科技大学计算机学院1)
数据结构华中科技大学计算机学院(1) ---------------------------------------------
本课程的任务 1.基本数据结构的定义、特性、运算与算法 1.1线性结构:线性表;栈,队列,双队列;数组,串。 1.2非线性结构:树,二叉树;图,网络 2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法:顺序,折半,分块,哈希,叉排序树等 4.排序算法:内部排序,外部排序 5.文件 6.基本应用与综合应用 **不要求了解和掌握第8章和其它各章中带**号 的小节
本课程的任务 1.基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈,队列,双队列；数组,串。 1.2 非线性结构：树,二叉树；图,网络。 2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法：顺序,折半,分块,哈希,二叉排序树等 4.排序算法：内部排序,外部排序 5.文件 6.基本应用与综合应用 **不要求了解和掌握第8章和其它各章中带**号 的小节
基本要求 1.阅读教材与参考书、听课、记笔记; 2.完成一定数量的书面作业; 3.使用C或C++完成5个以上的上机作业
基本要求 1.阅读教材与参考书、听课、记笔记； 2.完成一定数量的书面作业； 3.使用C或C++完成5个以上的上机作业
第一章绪论 1.1什么是数据、结构(关系)、数据结构? 建立数学模型是分析具体问题的过程,包括: 分析具体问题中操作对象 找出这些对象间的关系,并用数学语言描述 数学模型分两类: 1)数值计算类 例:根据三条边,求三角形面积。 假定:三条边依次为a,b,c三个实型数, 满足:a>0,b>0,c>0,a+b>c,b+c>a,c+a>b, 则 a+b+c area=s*(s-a)*(s-b)*(s-c
第一章 绪 论 1.1什么是数据、结构(关系)、数据结构？ 建立数学模型是分析具体问题的过程，包括： ⬧ 分析具体问题中操作对象 ⬧ 找出这些对象间的关系，并用数学语言描述 数学模型分两类： 1）数值计算类： 例：根据三条边，求三角形面积。 假定：三条边依次为a,b,c三个实型数， 满足：a>0 , b> 0 ,c>0 ,a+b>c ,b+c>a, c+a>b, s*(s-a)*(s-b)*(s-c) 2 a + b + c 则 s= area=
2)非数值计算类 例1:5个整数组成的集合: D={20,-5,66,15,44 其中:20,-5,66等称为数据元素(元素), 元素与元素之间关系是它们同属于集合D D={20,-5,66,15,44是一个数据对象 例2:一列整数:(线性结构) L=(20,-5,66,15,44) 其中:元素与元素之间在L中是前后关系或线性关系。 L=(20,-5,66,15,44)是一个线性表
2）非数值计算类： 例1: 5个整数组成的集合： D={20,-5，66, 15,44} 其中:20,-5,66等称为数据元素(元素)， 元素与元素之间关系是它们同属于集合D。 D={20,-5,66,15,44}是一个数据对象 例2: 一列整数：(线性结构) L=(20,-5，66, 15,44） 其中:元素与元素之间在L中是前后关系或线性关系。 L=(20,-5,66,15,44)是一个线性表
例3一张登记表DL 序号姓名性别年龄 1李刚男25记录1 2王霞女29记录2 3刘大海男40记录3 4李爱林男44记录4 其中:姓名、性别、年龄是数据项(item)、数据域( field); (姓名,性别,年龄)是记录( record), C语言将″记录"( record)定义为”结构”( struc t); 登记表也是一个线性表
例3 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)； (姓名，性别，年龄)是记录(record), C语言将"记录"(record)定义为”结构”(struct)； 登记表也是一个线性表
例4树状结构 华中科技大学(A) 计算机学院(B)管理学院(C)成教学院D 科学系(E)应用系(F)工程系(G) 其中:A、B、C等是结点(node) A与B,B与E,A与C之间是层次 关系或父子关系
例4 树状结构 其中:A、B、C等是结点(node)； A与B, B与E, A与C之间是层次 关系或父子关系。 华中科技大学(A) 计算机学院(B) 管理学院(C) 成教学院(D) 科学系(E) 应用系(F) 工程系(G)
例5图状结构 G B E 其中:A、B、C等是顶点( vertex) 图中任意两个顶点之间都可能有关系
例5 图状结构 A B D C E F G 其中：A、B、C 等是顶点(vertex), 图中任意两个顶点之间都可能有关系
1.2基本概念和术语 1.数据(data) 所有能输入到计算机中并被计算机程序加工、处理 的符号的总称 如:整数、实数、字符、声音、图象、图形等。 2.数据元素( data element) 数据的基本单位。(元素、记录、结点、顶点) 在计算机程序中通常作为一个整体进行考虑和处理 3.数据项( data item)- 是数据的不可分割的最小单位。如:姓名、年龄等 个数据元素可由一个或多个数据项组成。 如:(姓名、年龄)
1.2 基本概念和术语 1.数据（data) ---- 所有能输入到计算机中并被计算机程序加工、处理 的符号的总称。 如：整数、实数、字符、声音、图象、图形等。 2.数据元素(data element)--- 数据的基本单位。（元素、记录、结点、顶点） 在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项(data item)---- 是数据的不可分割的最小单位。如：姓名、年龄等 一个数据元素可由一个或多个数据项组成。 如: (姓名、年龄)
4.数据对象( data object) 由性质相同(类型相同)的数据元素组成的集合 数据对象是数据的一个子集。 例1由4个整数组成的数据对象 D1={20,30,88,45} 例2由正整数组成的数据对象 D2={1,2,3,,.} 例3由26个字母组成的数据对象 D3={A,B,C,,Z} 其中:D1,D3是有穷集,D2是无穷集 5.抽象数据对象 ElemNet={某种同类型的数据元素}
4.数据对象(data object)—— 由性质相同(类型相同)的数据元素组成的集合。 数据对象是数据的一个子集。 例1 由4个整数组成的数据对象 D1={20,-30,88,45} 例2 由正整数组成的数据对象 D2={1,2,3,...} 例3 由26个字母组成的数据对象 D3={A,B,C,...,Z} 其中：D1，D3是有穷集，D2是无穷集。 5.抽象数据对象 ElemSet={某种同类型的数据元素}