第1章数据结构.ppt
算法与数据结构,课程成绩,考勤（面授、直播、点播、下载)10平时成绩 20：请务必做作业期末考试 70,教材及参考书,数据结构（C语言版）严蔚敏 吴伟民编 清华大学出版社数据结构题集（C语言版）严蔚敏 吴伟民编 清华大学出版社数据结构及应用算法教程 严蔚敏等编 清华大学出版社数据结构C+语言描述 刘卫东等译 清华大学出版社,课程简介,数据结构是一门专业技术基础课程，课程分析、研究计算机加工数据的特征、数据的逻辑结构、数据的存储结构、数据涉及的算法、以及不同特征数据应用情况。,结构化程序（算法）（数据结构）,面向对象的程序（算法数据结构）,本课程主要内容,线性的数据结构树图查找排序,非线性的数据结构,第一章 绪论,本章重点：“数据结构”的基本概念算法和算法设计的要求,寻径问题,寻径问题,邻接矩阵、邻接表等,数组、链表等,C,C+,Java,VB,C,C+,Java,VB,逻辑结构,物理（存储）结构,具体问题,语言描述,1.1 什么是数据结构,计算机解决问题的一般步骤,建立数学模型：从具体问题中抽象出来。,数学模型：数值问题（数学方程）非数值问题（集合、线性表、树、图等）注：更多的非数值问题无法用数学方程描述,例1：图书馆书目检索系统自动化问题系统中的数学模型：图书目录卡片(如P2图1.1)线性的数据结构例2：人机对弈问题数据模型：“树”型数据结构例3：多叉路口交通灯的管理问题数据模型：“图”型数据结构,综上可以得出：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,1.2 基本概念和术语,数据(Data)：客观事务的符号表示；所有能够输入到计算机中并被计算机程序处理的符号的总称；信息在计算机中的表现形式图象、声音、符号等等数据元素(Data Element)：数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。一个数据元素可以有若干个数据项(Data Item)组成。数据对象(Data Object)：性质相同的数据元素的集合,数据结构：相互之间存在一种或多种关系的数据元素的集合。数据元素之间的关系结构四种基本结构集合线性结构树形结构图状结构/网状结构,数据结构的形式定义：一个二元组：Data_Structure=(D,S)其中：D是数据元素的集合，S是D上的关系集合例：学科研究课题小组 Group=(People,Relation)其中：People=T,G1,G2,Gn,S11,S12,Snm Relation=R1,R2 R1=i=1,2,3 R2=i=1,2,3 j=1,2,数据的逻辑、物理（存储）结构逻辑结构：数据元素之间的逻辑关系物理结构：数据元素在计算机中的存储方法（表现和实现）数据结构的分类：按照逻辑结构的不同分为：集合、线性结构、树状结构、网状结构按照物理结构的不同分为：顺序结构：利用在存储器中的物理关系来表示逻辑关系。链式结构：用在存储器中附加指针的方式来表示逻辑关系。,数据类型：一个值的集合和定义在该集合上的一组操作的总称。例如：高级语言中的数据类型抽象数据类型(ADT)：数据结构+定义在此结构上的一组操作（和其表示实现无关）注：抽象数据类型和数据类型实质上是同一个概念；ADT的范畴更广，“抽象”的意义在于数据类型的数学抽象特性 抽象数据类型 的三元组表示（D,S,P）D:数据，S:D上的关系，P:D上基本操作,抽象数据类型定义：ADT 抽象数据类型名 数据对象：数据对象定义 数据关系：数据关系定义 基本操作：基本操作定义 ADT 抽象数据类型名,1.3 抽象数据类型的表示和实现,通过固有数据类型表示和实现，即利用处理器中已经存在的数据类型来说明新的结构。由此利用类C语言描述：P10-11(1)typedef 数据类型定义 ElemType数据元素类型(2)Status 函数结果状态的整数描述(3)几组特殊的赋值形式：交换赋值，数组赋值，条件赋值(4)三种结束语句 return,break,exit(5)与运算&,或运算|(6)形参中T为值参，值不可变，&T为引用参数，值可变。,1.4 算法与算法设计,算法：对特定问题求解步骤的一种描述，是指令的有序序列算法的五个特性：有穷性、确定性、可行性、输入、输出算法设计的要求：时间复杂度，空间复杂度,时间复杂度：算法执行时间随规模增长而增长的趋势 T(n)=O(f(n)f(n)算法规模，T(n)称算法复杂度 估算办法：以算法中重复执行的次数作 为算法时间复杂度的依据。三种最常见时间复杂度：O(1)常量级 O(n)线性级 O(n2)平方级,算法的空间复杂度 S(n)=O(f(n)算法执行过程中所需的最大空间 估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间,本章小结,算法与数据结构的基本概念数据、数据类型、抽象数据类型几种基本的数据结构数据的物理结构和逻辑结构,
