数据结构（c语言）上ppt

《数据结构（c语言）上ppt》由会员分享，可在线阅读，更多相关《数据结构（c语言）上ppt（174页珍藏版）》请在金锄头文库上搜索。

1、数据结构（C语言）上,第1章 绪 论,（时间：1次课，2学时）,第1章 绪 论,教学提示：本章主要介绍数据结构的概念及有关术语，为后续章节做好铺垫。 教学目标：通过本章的学习，使读者能掌握数据结构的概念和有关的术语。,第1章 数据库系统的基本概念,1.1 什么是数据结构 1.2 基本概念和术语 1.3 运算、算法和算法分析 1.4 习题,1.1 什么是数据结构,数据结构这门学科主要是研究各种结构、定义在各种结构上的操作和这些操作在计算机中的实现方法。 提示：数据结构研究实际问题中元素之间的逻辑关系、元素及其关系在计算机中的表示和相关的操作。数据结构是一门综合性的专业基础课，它涉及到计算机硬件的

2、研究范围和软件的研究范围(存储装置和存取方法等)。,用计算机解决一个具体问题时要考虑以下步骤：,(1) 从具体问题中抽象出一个适当的数学模型。即从具体问题中找出操作对象之间含有的关系，然后用数学语言加以描述。 (2) 设计一个适合该数学模型的算法。 (3) 编写程序。 (4) 进行测试、调整、修改，直至解决问题。,在实际问题中，各个对象之间的关系有线性的、层次的和网状的等等. 实例1:,线性关系: 列车中各车箱之间的关系就是线性的。 排队买车票人之间的关系是线性的。 叠盘子中各盘子之间的关系是线性的。,实例2:,层次关系: 在军队的编制中，军下面是师，师下面是团，军、师、团之间是层次关系。 人

3、的辈分关系中，祖辈下是父辈，父辈下是子辈，这些是层次关系。 学校的编制中，学校分成若干个学院、学院下又分成若干个系、系下又分成若干个教研室，这些也都是层次关系。,实例3:,网状关系: 在城市铁路交通图中，各城市之间的关系是网状关系。 电话网中，各电话之间是网状关系。 计算机网络中，各计算机之间是网状关系。,1.2 基本概念和术语,数据(Data)： 数据是计算机表示客观事物的符号。在计算机科学中，所有能输入到计算机中并被计算机程序处理的符号统称为数据。它是计算机程序加工的“原料”。例如，一个用某种程序语言编写的源程序、一篇文章、一张地图、一幅照片、一首歌曲等等，都属于计算机能处理的数据。因此，

4、对计算机科学而言，数据的含义极为广泛；图象、声音等也都可以通过编码而归之于数据的范畴。,1.2 基本概念和术语,数据元素： 数据元素是数据的基本单位。数据的范围非常广泛，数据元素也是可大可小的。在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成。例如，一本书的书目信息为一个数据元素，而书目信息中的每一项(如书名、作者名)是数据项。,1.2 基本概念和术语,数据结构： 数据结构是彼此具有一定关系的数据元素的集合。这些关系反映了客观世界事物之间的联系。这种数据元素之间的相互关系称为结构。由于客观事物存在着各种不同的联系形式，因此在计算机内反映数据的关系时，可以用结

5、构来描述这些关系。数据结构分为逻辑结构和物理结构两个研究方面。逻辑结构是指数据元素之间的关系。,1.2 基本概念和术语,四种基本数据结构： 集合：这个结构中的数据元素之间同属于一个集合，除这一关系外没有其他关系。 线性结构：这个结构中数据元素存在着由依次排列的先后次序决定的关系。 树型结构：这个结构中数据元素之间存在着层次关系。 图结构：这个结构中数据元素之间相互连接成网状。,图1.1 四种基本数据结构,1.2 基本概念和术语,存储结构： 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。存储结构是指在计算机中存储数据和逻辑结构。同一种逻辑结构可以使用不同的物理结构来实现。 在计算机

6、中表示信息的最小单位是一个二进制位，叫做bit位。一个数据元素的“bit位串”通常称为“结点”。 当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据字段。 数据元素之间的关系在计算机中有两种基本的存储结构：顺序存储结构和链式存储结构。 在高级语言的指针类型中，不是针对计算机的实际地址进行存储，称这种存储为数据结构的虚拟存储结构。,1.2 基本概念和术语,数据类型： 高级程序设计语言中的数据类型分为原子类型和结构类型。原子类型的值是不可分解的。C语言中的基本类型(整型、实型、字符型和枚举类型)、指针类型和空类型都是原子类型。结构类型是由若干类型组成的，是可以分解的。例如C语言中

7、数组的类型和结构体类型是由其他类型定义的。 在计算机中，数据类型并非局限于高级语言中的一个具体类型，而是通常用抽象数据类型表示类型。上机实现时，再把抽象数据类型用具体的类型代替。,1.3 运算、算法和算法分析,1.3.1 运算 1.3.2 算法及其描述 1.3.3 算法分析和算法复杂度,1.3.1 运算,运算可以分为下列两种基本类型： 加工型运算：运算后改变了原结构中数据元素的个数或数据元素的内容。 (2) 引用型运算：运算不改变结构中数据元素的个数和元素的内容，只从结构中提取某些信息作为运算的结果。,1.3.1 运算,基本运算主要包括下列几种： 插入运算：属于加工型运算，在原结构的指定位置上

8、增添新的数据元素。 删除运算：属于加工型运算，将原结构中的某个指定的数据元素删除。 查找运算：属于引用型运算，从结构中找出满足条件的数据元素的位置。 读取运算：属于引用型运算，使用结构中满足条件的数据元素的内容。 更新运算：属于加工型运算，更换结构中某个数据元素的内容。 使用这些基本运算，可以构成其他的复杂运算 。,1.3.2 算法及其描述,定义： 算法是计算机科学的一个概念，也是程序设计的一个重要概念。 算法是对求解某个问题的步骤的一种描述方法。 算法是描述操作步骤的有限序列。,1.3.2 算法及其描述,算法要具备下列五个特性： 有穷性：算法必须在执行有穷步之后结束，而每一步都必须在有穷时间

9、内完成。 确定性：算法中每一步操作的含义都必须是确定的，不能有二义性。 可行性：一个算法必须是可行的，即算法中每一操作都能通过已知的一组基本操作来实现。 输 入：一个算法可以有零个或多个输入。 输 出：一个算法有一个或多个输出。,1.3.3 算法分析和算法复杂度,通常用以下几个标准来评价其优劣： 正确性：算法必须能正确解决问题。 易读性：算法应当便于阅读和理解，以利于修改和改写成程序。 健壮性：当输入非法数据时，算法也能做出特殊处理，不会继续操作或死机。 高效率：算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少，则是算法高效率的体现。,1.3.3 算法分析和

10、算法复杂度,算法分析： 研究算法的效率称为算法复杂度的分析(简称算法分析)。简单地说，一个算法所进行的计算次数的多少称为时间复杂度，一个算法所需要辅助存储空间的多少称为空间复杂度。 在算法分析中绝对的量不能反映时间复杂度，使用一个函数T(n)表示一个算法的复杂度。一个算法所解决问题的规模n增大时，时间的增长率越小，时间复杂度越好，反之时间复杂度越坏。也就是说，时间复杂度是n的一个函数。从好到坏表示时间复杂度的函数依次是：常量阶O(1)；对数阶O(log n)；线性阶O(n)；平方阶O(n2)；多项式阶O(nk)；指数阶O(2n)等。,1.3.3 算法分析和算法复杂度,算法复杂度，举例： x+;

11、 s=x+2; 时间复杂度为O(1) for(k=1; k=n; k+) s=k+2； 时间复杂度为O(n) for(k=1; k=n; k+) for(j=1; j=n; j+) s=k+j； 时间复杂度为O(n2),1.4 习 题,1 填空题 2 选择题 3 简答题,1.4 习 题_填空题,(1) 从数据结构S中找出满足条件的结点在S中位置的运算是_型运算。 (2) 从数据结构S中读出结构中指定位置上内容运算是_型运算。 (3) 从数据结构S中的某指定位置上增加一个新结点的运算是_型运算。 (4) 从数据结构S中撤消结构中指定位置上结点的运算是_型运算。 (5) 从数据结构S中修改结构中某

12、指定结点内容的运算是_型运算。,1.4 习 题_选择题,(1) 数据表示是指数据_。 A. 书写在纸上 B. 从机外转为机内 C. 磁盘中的数据 D. 光盘中的数据 (2) 数据元素是数据的基本单位，其内_数据项。 A. 只能包括一个 B. 不包含 C. 可以包含多个 D. 必须包含多个 (3) 逻辑关系是指数据元素间的_。 A. 类型 B. 存储方式 C. 结构 D. 数据项,1.4 习 题_选择题,(4) 逻辑结构是_关系的整体。 A. 数据元素之间逻辑 B. 数据项之间逻辑 C. 数据类型之间 D. 存储结构之间 (5) 数据结构有_种基本逻辑结构。 A. 1 B. 2 C. 3 D.

13、4 (6) 下列四种基本的逻辑结构中，数据元素之间关系最弱的是_。 A. 集合 B. 线性结构 C. 树形结构 D. 图状结构,1.4 习 题_选择题,(7) 一个存储结点存放一个_。 A. 数据项 B. 数据元素 C. 数据结构 D. 数据类型 (8) 用类C语言描写的算法_。 A. 可以直接在计算机上运行 B. 可以描述解题思想和基本框架 C. 不能改写成C语言程序 D. 与C语言无关 (9) 算法能正确地实现预定功能的特性称为_。 A. 正确性 B. 易读性 C. 健壮 D. 高效率,1.4 习 题_选择题,(10) 下列时间复杂度中最坏的是_。 A. O(1) B. O(n) C. O

14、(log2n) D. O(n2) (11) 下列时间复杂度中最好的是_。 A. O(1) B. O(n) C. O(log2n) D. O(n2) (12) 下列算法的时间复杂度是_。 for(i=0; in; i+ ) for(j=0; jn; j+ ) cij=i+j; A. O(1) B. O(n) C. O(log2n) D. O(n2),1.4 习 题_选择题,(13) 下列算法的时间复杂度是_。 for(i=0; in; i+ ) cii=i+i ; A. O(1) B. O(n) C. O(log2n) D. O(n2) (14) 在计算机中存储一个数据元素的位串称为_。 A.

15、结点 B. 数据项 C. 数据字段 D. 字符串 (15) 记录中的各个数据项的类型_。 A. 必须相同 B. 不必相同 C. 不能相同 D. 不确定,1.4 习 题_简答题,(1) 简述数据与数据元素的关系与区别。 (2) 说出数据结构中的四类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。 (3) 画出线性结构的示意图。 (4) 画出树形结构的示意图。 (5) 画出图状结构的示意图。 (6) 什么是逻辑结构、存储结构？有哪几种存储结构？ (7) 简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 (8) 简述逻辑结构与存储结构的关系。 (9) 通常从哪几个方面评价算法的质量？ (10) 算法的时间复杂度主要有那几种？按从优到劣的顺序写出各种表示形式。,Q & A? Thanks!,第2章 线 性 表,（时间：2次课，4学时）,第2章 线 性 表,教学提示：本章介绍的线性表结构是最基本的数据结构，也是学习后边章节重要的基础。重点介绍线性表的概念、运算、存储结构和算法。 教学目标：通过本章的学习，使读者能掌握线性表的概念、有关术语、存储方式、相关运算和算法