计算机专业基础课 《数据结构》 教师:邵定宏
计算机专业基础课 《数据结构》 教师：邵定宏
《数据结构》是计算机程序设计的重要理论技术基础,它主 要研究在计算机上有效地组织数据和处理数据的方法,它不仅是 计算机学科的核心课程,而且已成为其他理工专业的热门选修课 在计算机科学中,数据结构不仅是一般程序设计的基础,而 且是设计和实现编译程序、操作系统数据库系统及其它系统程 序和大型应用程序的重要基础。 数据结构作为计算机的一门学科主要研究和讨论以下三个方 面的问题: 数据集合中各数据元素之间所固有的逻辑关系即数据的 逻辑结构 (2)在对数据进行处理时各数据元素在计算机中的存储关系 即数据的存储结构 3)对各种数据结构进行的运算 通过本课程的学习,使我们能够系统地掌握表、栊、队列 树和图等数据结构的基本特征和在计算机上实现的技术;学会怎 样对处理的数据建立抽象数据类型,利用抽象数据类型进行程序 设计的方法从而培养我们软件设计和编程能力
序 《数据结构》是计算机程序设计的重要理论技术基础，它主 要研究在计算机上有效地组织数据和处理数据的方法，它不仅是 计算机学科的核心课程，而且已成为其他理工专业的热门选修课。 在计算机科学中，数据结构不仅是一般程序设计的基础，而 且是设计和实现编译程序、操作系统、数据库系统及其它系统程 序和大型应用程序的重要基础。 数据结构作为计算机的一门学科,主要研究和讨论以下三个方 面的问题: (1) 数据集合中各数据元素之间所固有的逻辑关系,即数据的 逻辑结构. (2)在对数据进行处理时,各数据元素在计算机中的存储关系, 即数据的存储结构. (3)对各种数据结构进行的运算. 通过本课程的学习，使我们能够系统地掌握表、栈、队列、 树和图等数据结构的基本特征和在计算机上实现的技术；学会怎 样对处理的数据建立抽象数据类型，利用抽象数据类型进行程序 设计的方法；从而培养我们软件设计和编程能力
第一章:绪论(学时 什么是数据结构 基本概念和术语 算法和算法分析
第一章：绪论（2学时） • 什么是数据结构 • 基本概念和术语 • 算法和算法分析
11什么是数据结构 计算机解题的步骤 提出问题(目标函数)建模设计算法编程调试结果 建模的实质 提取操作对象找出对象间的关系数学语言描述 例 圆的面积(函数) 应力分析(线性方程组) 人口增长预报(微分方程) 例: 书目检索自动化(表) 人机对弈(树) 交通灯管理(图 什么是数据结构 数据结构是—门研究 的程序设计中计算机的 以及它们之间的关和等的 的
1.1 什么是数据结构 • 计算机解题的步骤 提出问题（目标函数）→建模→设计算法→编程→调试→结果 • 建模的实质 提取操作对象→找出对象间的关系→数学语言描述 例：数值计算问题 圆的面积（函数） 应力分析 （线性方程组） 人口增长预报（微分方程） 例：非数值计算问题 书目检索自动化（表） 人机对弈（树） 交通灯管理（图） • 什么是数据结构 数据结构是一门研究非数值计算的程序设计中计算机的操作 对象以及它们之间的关系和操作等的学科
12》基本概念和术语 数据:符号的总称(数串、国象和声音等)。 数据元素数据的基本单位(本书 个学生一个班级 年级和个学校等)。 数据对象:性质相同的数据元素的集合(整数集、字母集等) 数据结构:相互间存在某种特定关系的数据元素的集合,这种数 据元素之间的关系称为结构。 四种基本结构 集合(松散)、线性(一对 树型(对多)、图状或网状(多对多) 形式定义: Data Structure=(D,S 其中D是数据元素的有限集 S是D上关系的有限集
1.2 基本概念和术语 • 数据：符号的总称（数、串、图象和声音等）。 • 数据元素：数据的基本单位（一本书、一个学生、一个班级、一 个年级和一个学校等）。 • 数据对象：性质相同的数据元素的集合（整数集、字母集等） • 数据结构：相互间存在某种特定关系的数据元素的集合，这种数 据元素之间的关系称为结构。 四种基本结构： 集合（松散）、线性（一对一）、 树型（一对 多）、图状或网状（多对多）。 形式定义：Data_Structure=(D, S) 其中：D是数据元素的有限集。 S是D上关系的有限集
1,2)基本概念和术语 例:复数: Complex=(CR 课题小组: group=(PR) 逻辑结构:关系 存储结构:表示(映象) (在高级语言层次上 顺序位置相邻(一维数组) 链式:指针(指针或数组) 计算设计:取决于选定的逻辑结构 算法实现:依赖于采用的存储结构
1.2 基本概念和术语 例: 复数: Complex=(C,R) 课题小组: Group=(P,R) 逻辑结构: 关系 存储结构: 表示(映象) (在高级语言层次上) 顺序: 位置相邻(一维数组) 链式: 指针(指针或数组) 计算设计: 取决于选定的逻辑结构 算法实现: 依赖于采用的存储结构
1,2)基本概念和术语 数据类型刻画了操作对象的特性 规定值的集合和一组操作 整数的范围:(16位)-32768~32767 操作:+ DIV、% 抽象数据类型(ADT):数学模型和一组操作。 “抽象”的定义在于数据类型的数学抽象特性) 分类∵原子类型:100整数。 固定聚合类型:复数(C1,C2) 可变聚合类型:有序整数类型。 抽象数据类型的形式定义∵ ADT=(D, S, P 其中D是数据对象;S是D上的关系集;P是对D的基本操作集 (用类C作为描述工具,来讨论数据结构及其算法
1.2 基本概念和术语 • 数据类型: 刻画了操作对象的特性 规定: 值的集合和一组操作 (整数的范围: (16位) -32768～32767 操作：+、-、 * 、DIV、%） 抽象数据类型（ADT）：数学模型和一组操作。 （“抽象”的定义在于数据类型的数学抽象特性） 分类：原子类型：100整数。 固定聚合类型：复数（C1，C2）。 可变聚合类型：有序整数类型。 抽象数据类型的形式定义： ADT=（D，S，P） 其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。 （用类C作为描述工具，来讨论数据结构及其算法）
1.3算法和算法分析 算法;解题步骤的描述,指令的有限序列 算法的特性:有穷性、确定性、可行性、输入、输出。 算法评价标准佳可读性、健壮性效率(时间、空间) (前提:正确性 无语法错误 (2)随意数据 3)刻意数据 (4)切合法数据) 算法效率的度量 1)事后统计法 2)事前估算法(最大语句频度
1.3 算法和算法分析 • 算法：解题步骤的描述，指令的有限序列。 • 算法的特性：有穷性、确定性、可行性、输入、输出。 • 算法评价标准：可读性、健壮性、效率（时间、空间） （前提：正确性： （1）无语法错误 （2）随意数据 （3）刻意数据 （4）一切合法数据） • 算法效率的度量： （1）事后统计法 （2）事前估算法（最大语句频度）
1.3算法和算法分析 时间复杂度:T(n)=0(f(n) 例:(,=n n+ tor + n米(n {c[1j=0 n'n for(k-1: k<en, k++) n(n+1) c[0]+=alijlk]*b[kIG tnn (n)=2n3+3n2+2n+1=O(n (渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度 空间复杂度S(n)=O((m)
1.3 算法和算法分析 • 时间复杂度：T（n）=O（f（n）） 例：for ( i=1; i<=n; i++) n+1 for ( j=1; j<=n; j++) n*(n+1) { c[i][j]=0; n*n for (k=1; k<=n; k++) n*n*(n+1) c[i][j]+=a[i][k]*b[k][j]; n*n*n } T(n)=2n3+3n2+2n+1=O( n3 ) （渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度） • 空间复杂度：S（n）=O（f（n））
练习题 下列是几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表 示,并指出它们分别属于何种结构 (1)A=(K,R)其中:K=a,b,,d,e;R= r=a, b>, b, c>, ,sd, e> (2)C(K,R 其中:K={1234R= r={12),(1,3),(2,4)(3,4)} 2.指出下列各算法的时间复杂度 1)=1 while (i = i3 ( 2) fact(int n) tif (n<=1) return(1); else return(n fact(n-1))
练习题 1. 下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表 示，并指出它们分别属于何种结构。 （1） A=（K，R） 其中：K={a，b，c，d，e}； R={r}； r={,,,} （2） C=( K,R ) 其中: K={1,2,3,4}; R={r}; r={(1,2),(1,3),(2,4),(3,4)} 2. 指出下列各算法的时间复杂度。 （1） i=1; while (i<=n) i=i*3; （2） fact(int n) { if (n<=1) return(1); else return(n*fact(n-1)); }