版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构,张敬敏,个人邮箱: 公共邮箱: 密码:zjmds_2012,课程简介,主要内容: 1.什么是数据结构,为什么学习数据结构 2.几种常规的数据结构:线性表,栈和队列,树和二叉树,图 3.排序和查找 教材 数据结构C语言版 严蔚敏、吴伟民,清华大学出版社 参考书 数据结构 题型 题集 题解,刘坤起,科学出版社 课时安排 授课 :64+24学时 考核方式 本课程的考核方式为考试。总成绩由平时成绩和考试成绩组成。平时成绩占30%,考试成绩占70%。 平时成绩=到课率(缺一次扣2分)+实验报告(少一次扣5分)+闪光点(2次,则平时成绩为满分),1.1 什么是数据结构 1.2 基本概念和术语 (
2、重点) 1.3 抽象数据类型的表示与实现(难点) 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 (重点、难点) 1.4.4 算法的存储空间需求,第一章 绪论,数据结构的非形式定义 数值计算问题的求解 特征:基于代数运算的计算问题,例如,矩阵运算、方程组的求解和数字信号处理,等等。 举例 百鸡百钱问题。公元前五世纪末,我国数学家张丘建在算经中提出了该问题。问题是这样的:“鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。凡百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?” 分析并建立数学模型:设鸡翁的个数为:cock只,鸡母的个数为:hen只, 鸡雏的个数为:c
3、hick只。依题意得到下列方程组: cock+hen+chick=100 5cock+3hen+chick/3=100 这就是描述该问题的数学模型。它是一个不定方程组,其解即为问题的解。,算法设计 基本思想:用穷举方法求解不定方程,即先穷举满足百鸡条件的鸡翁、鸡母、鸡雏的数目,然后再从这些数目中挑选出满足百钱条件的鸡翁、鸡母、鸡雏的数目。 算法如下: 循环:cock从0到19,步长为1,做 循环:hen从0到33,步长为1,做 chick100-cock-hen; 若5cock+3hen+chick/3=100,则 输出 cock,hen,chick的值(得到一个解); 编码:略。 上机调试程
4、序 利用计算机解题的过程 首先经过分析问题,从中抽象出一个适当的数学模型,然后设计或选择一个解此数学模型的算法,最后编出程序进行调试、测试,直至得到最终的解答。解决问题的关键在于数学模型的建立和算法的设计。,例1 书目自动检索系统,书目文件,非数值计算问题,例2 人机对奕问题,非数值计算问题,例3 多叉路口交通灯管理问题,非数值计算问题,求解非数值计算的问题: 主要考虑的是设计出合适的数据结构及相应的算法。 首先要考虑对相关的各种信息如何表示、组织和存储? 因此,可以认为: 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据结构是指带运算的具有一
5、定逻辑关系的数据构成的集合。,数据结构课程的形成和发展: 形成阶段: 60年代初期,“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年,“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段: 数据结构的概念不断扩充,包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期,我国高校陆续开设该课程。,数据结构课程所处的地位,为什么要学习数据结构 1、什么是程序、软件? 程序=算法+数据结构 N.沃思(Niklaus Wirth) 算法是程序的骨架,而数据结构是程序的血脉; 数据结构是研究非数值数据的数学建模和数据表示的; 软件=程序+文档(软件工
6、程的观点),Niklaus Wirth(尼克劳斯沃思,1934)男,瑞士人,1963年获得加州大学伯克利分校哲学博士,苏黎士联邦高等工业学校教授。他是Pascal语言之父及结构化程序设计的首创者,提出了著名的“数据结构+算法=程序”公式。因开发了EULER、ALGOL-W、 MODULA和PASCAL一系列崭新的程序设计语言而获得1984年图灵奖。,2.电子计算机的主要用途 (1) 数值计算 早期 求解梁架结构中的应力问题 线性方程 人口增长情况预报 微分方程 (2) 非数值计算 后来,3.现实问题求解的一般步骤 (1)数值计算 数学模型选择计算机语言 编出程序测试最终解答 关键是:如何得出数
7、学模型(方程)? 程序设计人员比较关注程序设计的技巧。 (2)非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述,1.2 基本概念和术语(重点) 数据(data)所有能输入到计算机中去的描述客观事物的符号 整数的子集是数据 中文文字组成的任何形式的信息是数据 图像、声音和视频是数据 甲骨文不是数据 某些少数民族文字不是数据,左边示意图中的每个小方框再进一步缩小就成为一个点,称为像点,每个像点可以用行号、列号、色彩来表示(或存储),将所有像点存储起来,就存储了一幅图像。这就是图像的数字化。,以图像为例说明图像是数据,数据元素(data element)数据的基本单位,也称节点(no
8、de)或记录(record) 数据项(data item)有独立含义的数据最小单位,也称域(field) 数据对象(data object)性质相同的数据元素的集合,是数据的一个子集。,客观世界中的数据都不是孤立存在的,换句话说数据之间是有联系的。人们应用计算机处理各种各样的数据,必然要涉及到数据之间的联系。 数据结构(data structure)指相互之间存在一种或多种特定关系的数据元素的集合。 教师手中的学生花名册是数据结构 列车时刻表是数据结构 某大学全体师生是数据结构 某城市公共交通地理图是数据结构,数据结构的形式定义 数据结构是一个二元组: Data-Structure=(D,S)
9、 其中: D是数据元素的有限集, S是D上关系的有限集。,例 复数的数据结构定义如下: Complex=(C,R) 其中: C是含两个实数的集合C1,C2,分别表示复数的实部和虚部。 R=P,P是定义在集合上的一种关系C1,C2。元素之间存在多对多的关系。,数据结构包括数据的逻辑结构和数据的物理结构。 数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储(物理)结构数据的逻辑结构在计算机存储器中的实现/在计算机中的表示/在计算机中的映像,数据的逻辑结构,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,本课程授课内容的体系组织与主线,授课内容的体系组织
10、 利用抽象数据类型组织数据结构的内容,与现代程序理论与技术的发展形成了一致。 主线 以每一种“ADT的定义ADT的实现ADT的应用”为主线展开。,线索构成了知识体系的骨架。,数据类型高级语言中指数据的取值范围及其上可进行的操作的总称,例 C语言中,提供int, char, float, double基本 数据类型,数组、结构体、共用体、枚举等构造数据类型,还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,
11、1.3 抽象数据类型的表示和实现,本节是难点,重在理解,抽象数据类型(abstract data type) 指数学模型以及定义在该模型上的一组操作. 抽象数据类型和数据类型实质上是一个概念。 抽象数据类型的三元组表示 ADT=(D,S,P) 其中: D:数据对象 S:D上的关系集 P:对D的基本操作集,本书采用如下格式定义抽象数据类型 ADT 抽象数据类型名 数据对象: 数据关系: 基本操作: ADT 抽象数据类型名 其中: 数据对象和数据关系的定义可以用伪码表示 基本操作的定义格式为 基本操作名(参数表) 初始条件: 操作结果: 例 抽象数据类型“三元组”的定义,ADT Triplet 数
12、据对象:D=e1,e2,e3|e1,e2,e3ElemSet(定义了关系运算的某个集合) 数据关系:R1=, 基本操作: InitTriplet(i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,语句的频度:是指该语句重复执行的次数,例2 +x;s=0; f(n)=1 T(n)=O(f(n)=(1) 例3 for(i=1;i=n;+i) +x;s+=x; f(n)=n T(n)=O(f(n)=O(n) 一些特殊情况采用平均复杂度、最好复杂度、最坏复杂度 如 冒泡排序 本书以后各章,无特殊说明都指,最坏情况下的复杂度
13、,以下六种计算算法时间的多项式是最常用的。其关系为: O(1)O(logn)O(n) O(nlogn)O(n2)O(n3) 指数时间的关系为: O(2n)O(n!)O(nn),当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。因此,只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法,那就取得了一个伟大的成就。,算法的存储空间的需求 空间复杂度: S(n) = O(f(n) n:问题的规模,数据、数据结构等基本概念(掌握) 数据结构的三个方面的内容(掌握) 线性和非线性结构的逻辑特征(掌握) 数据存储的2种基本方法(掌握) ADT(理解) 算法、算法的时间复杂度(掌
14、握), 本章小结,课 堂 练 习,1. 设数据结构A=(D,R),其中D=a,b,c,d,R=r,r=,则数据结构A是( )。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 2. 计算机中的算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、( )等五个特征。 (A) 有效性、可移植性和可扩充性 (B) 有效性、有穷性和确定性 (C) 确定性、有穷性和稳定性 (D) 易读性、稳定性和确定性,3.设n为偶数,试计算运行下面的C语言程序段后m的值,并给出该程序段的时间复杂度。(要求给出分析计算过程) m=0; for (i=1;i=n; i+) for (j=2*i; j=n; j+) m+;,课堂练习答案 1. C 2. B 3. 答案: 首先分析出程序段的基本操作是m+ ,然后计算出基本操作的重
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年猎头行业行业痛点与解决方案报告
- 2026年保健食品细分市场研究报告:行业增长潜力分析
- 2026年物流行业组织架构优化与部门职责流程再造报告
- 2026年写字楼市场政策影响与商业地产投资策略报告
- 2026年汽车行业智能化升级报告及未来五年发展趋势分析
- 2026年医药行业报告:创新药物发展与市场前景分析
- 2026年电子信息制造行业分析报告:智能技术绿色生产新篇章
- 2026年健康产业市场细分与消费者需求分析报告
- 2026年区块链技术应用行业硬件销售前景研究报告
- 2026年信息技术行业资金链稳定与分红策略报告
- 2026年医疗保险审核部门面试题及应对策略
- 2026-2031中国法兰行业市场前景分析预测报告
- 施工便道临时方案
- 信息科技课程标准2025年版
- 眼科手术并发症处理规定
- 风机叶片覆冰安全培训课件
- 2025云南曲靖市人力资源和社会保障局招聘公益性岗位工作人员3人考试参考题库及答案解析
- 医院服务接待礼仪
- 腹部超声常见疾病诊断要点
- 《中职语文基础知识手册》全套教学课件
- 【MOOC】人工智能与信息社会-北京大学 中国大学慕课MOOC答案
评论
0/150
提交评论