数1-绪论 数据结构 教学课件.pptVIP

数据结构华中科技大学计算机学院(1) --------------------------------------------- 本课程的任务 1.基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈,队列,双队列；数组,串。 1.2 非线性结构：树,二叉树；图,网络。 2.数据结构的存储结构与实现 选择存储结构,设计算法 3.查找算法：顺序,折半,分块,哈希,二叉排序树等 4.排序算法：内部排序,外部排序 5.文件 6.基本应用与综合应用 **不要求了解和掌握第8章和其它各章中带**号 的小节 基本要求 1.阅读教材与参考书、听课、记笔记； 2.完成一定数量的书面作业； 3.使用C或C++完成5个以上的上机作业 。 第一章 绪 论 1.1什么是数据、结构(关系)、数据结构？ 建立数学模型是分析具体问题的过程，包括： 分析具体问题中操作对象 找出这些对象间的关系，并用数学语言描述 数学模型分两类： 1）数值计算类： 例：根据三条边，求三角形面积。 假定：三条边依次为a,b,c三个实型数， 满足：a0 , b 0 ,c0 ,a+bc ,b+ca, c+ab, 例3 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)； (姓名，性别，年龄)是记录(record), C语言将记录(record)定义为”结构”(struct)； 登记表也是一个线性表。 例4 树状结构 例5 图状结构 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.抽象数据对象 ElemSet={某种同类型的数据元素} 逻辑结构:带有结构的数据元素的集合数据结构(逻辑结构)分类 1.线性表 2.栈 线性结构 3.队列,双队列 4.数组 数据结构 5.字符串 非 线 性 1.树,二叉树 结 构 2.图 6.存储结构 ---- 数据结构在计算机存储器中的映象(mapping)。 存储结构也称为：存储表示,物理结构,物理表示。 (1)顺序存储结构(向量,一维数组) 例. char a[4]={A,B,C,D‘}； A B C D 0 1 2 3 a是一维数组 (2)非