测试一下对不对

null数据结构 (BB002016)数据结构 (BB002016)信息学院计算机系 朱红梅 Office：北校区 文理大楼702 Tel: 8242497 13181822008 E-mail: sdaucs@163.com freesd@163.com psw:freesd2007教材教材主教材 王红梅，胡明，王涛.数据结构 （C＋＋版）. 清华大学出版社. 参考教材 王红梅.数据结构学习辅导与实验指导.清华大学出版社. 严蔚敏.数据结构.清华大学出版社. 严蔚敏,吴伟民.数据结构题集. 清华大学出版社.课程性质课程性质数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课 在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理…… 属于武术中的“练功”科目 “练武不练功，到头一场空” 考研学习目标学习目标掌握基本的数据结构 工具箱→复用、修改、重组 培养算法设计能力、程序设计能力 算法——程序的灵魂 问题求解过程：问题→想法→算法→程序 程序设计研究的层次：算法→方法学→语言→工具 培养算法分析能力 评价算法、改进算法学习学习要求循序渐进，切忌心浮气躁 提高课外学习的时间和内容 理解科学而不是背诵科学→读书 正确对待考试 作习题 华罗庚：“学数学不做习题等于入宝山而空返” 作实验 计算机学科是一门科学性与性并重的学科，表现为理论和实践紧密结合的特征。 成绩组成成绩组成学期成绩=平时成绩（30%）+期末成绩（70%） 说明： 平时成绩=作业/测验（ 70% ）+上课出勤（30%） 上课出勤：上课点名，请假要有假条。 要求大家课后务必复习！切记！！数据结构实验数据结构实验(BB002017)实验项目及内容提要一实验项目及内容提要一顺序表 2学时 掌握线性表的顺序存储结构和操作特性，实现基于顺序表的基本操作。 链表 2学时 掌握线性表的链式存储结构和操作特性，实现基于链表的基本操作。 栈 2学时 掌握栈的顺序存储结构和操作特性，实现基于顺序栈的基本操作。 队列 2学时 掌握队列的链式存储结构和操作特性，实现基于链队列的基本操作。实验项目及内容提要二实验项目及内容提要二二叉树 2学时掌握二叉树的二叉链表存储结构，实现二叉树的先、中、后序遍历。 图 4学时 建立无向图的邻接矩阵存储结构和有向图的邻接表存储结构，分别对其实现图的广/深度优先遍历。 顺序查找、折半查找 2学时 实现顺序查找、折半查找算法，在一数据表中查找一元素，若没有此元素则进行插入，并保持此数据表有序。 直接插入、起泡、简单选择排序 2学时 实现直接插入、起泡、简单选择排序算法。null第 1 章 绪 论数据结构的兴起和发展 数据结构的研究对象 数据结构的基本概念 算法及算法分析本章的基本内容是：null1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著： The Art of Computer Programming 他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。数据结构的创始人——克努思null1.1 数据结构的兴起和发展 程序设计的实质是什么?数据表示：将数据存储在计算机中 数据处理：处理数据，求解问题数据结构问题起源于程序设计 null 数据结构随着程序设计的发展而发展 数据结构的发展并未终结1. 无结构阶段 2. 结构化阶段：数据结构＋算法＝程序 3. 面向对象阶段： （数据结构＋算法）＝程序1.1 数据结构的兴起和发展 null1.2 数据结构的研究对象计算机求解问题: 问题→抽象出问题的模型→求模型的解 问题——数值问题、非数值问题 数 值 问 题→数学方程 非数值问题→数据结构 null例1 学籍管理问题——表结构1.2 数据结构的研究对象null例2 人机对弈问题——树结构1.2 数据结构的研究对象null例3 教学计划编排问题——图结构1.2 数据结构的研究对象null 数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。1.2 数据结构的研究对象null1.3 数据结构的基本概念数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项：构成数据元素的不可分割的最小单位。 数据对象：具有相同性质的数据元素的集合。 数据结构的基本概念数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据元素是由数据项组成。 数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。1.3 数据结构的基本概念null数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。1.3 数据结构的基本概念数据结构的基本概念数据的逻辑结构是从具体问题抽象出来的数据模型null数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。 存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。1.3 数据结构的基本概念数据结构的基本概念存储结构实质上是内存分配， 在具体实现时，依赖于计算机语言。null数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ；1.3 数据结构的基本概念数据结构的基本概念null数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念null数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念null数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系； ⑷ 图结构：数据元素之间存在 着多对多的任意关系。1.3 数据结构的基本概念数据结构的基本概念null通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。1.3 数据结构的基本概念数据结构的基本概念null通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。例：（bat, cat, eat）1.3 数据结构的基本概念数据结构的基本概念 bat 0200 cat 0325 eat ∧逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。 1.3 数据结构的基本概念null数据结构的访问接口对数据结构的访问是指对数据的读取、修改、加工、处理等操作。 数据结构的基本操作：各种应用都能通过这些操作实现对数据结构的各种访问。 基本操作的特性：抽象性、基本性、完备性、一般性 访问接口：操作的调用形式与规范（例如形参表、返回类型等）。 数据结构的访问接口：数据结构基本操作接口的全体。1.3 数据结构的基本概念null抽象数据类型1. 数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。 例如：C++中的整型变量 2. 抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。 例如： 地图、驾驶汽车 3. 抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。 1.3 数据结构的基本概念ADT是对数据类型的进一步抽象 ADT是对数据类型的进一步抽象 ADT的不同视图1.3 数据结构的基本概念ADT的定义形式ADT 抽象数据类型名 Data 数据元素之间逻辑关系的定义 Operation 操作1 前置条件：执行此操作前数据所必须的状态 输 入：执行此操作所需要的输入 功 能：该操作将完成的功能 输 出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 …… …… 操作n …… endADT ADT的定义形式1.3 数据结构的基本概念null1.3 数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等 null算法的相关概念1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。2. 算法的五大特性： ⑴ 输入：一个算法有零个或多个输入。 ⑵ 输出：一个算法有一个或多个输出。 ⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。1.4 算法及算法分析null 欧几里德算法 mnr例：欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数1.4 算法及算法分析null算法的描述方法——自然语言 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段1.4 算法及算法分析null① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束；否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。例：欧几里德算法自然语言1.4 算法及算法分析null优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次 算法的描述方法——流程图 1.4 算法及算法分析null流 程 图例：欧几里德算法1.4 算法及算法分析null优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数 算法的描述方法——程序设计语言 1.4 算法及算法分析null#include int CommonFactor(int m, int n) { int r=m % n; while (r!=0) { m=n; n=r; r=m % n; } return n; } void main( ) { cout<结论

圆锥曲线的二级结论椭圆中二级结论圆锥曲线的二级结论圆锥曲线的二级结论探究欧姆定律实验步骤