数据结构课件第1章

《数据结构课件第1章》由会员分享，可在线阅读，更多相关《数据结构课件第1章（31页珍藏版）》请在装配图网上搜索。

1、数据结构课件第1章数据结构（C C语言版）数据结构课件第1章课时安排课时安排 专业必修，专业必修，4.5学分学分 总学时：总学时：70小时小时 上课：上课：54小时小时 试验：试验：16小时小时 考试考试数据结构课件第1章 平时成绩：平时成绩：30%考勤考勤+课堂表现课堂表现+作业作业+上机实验报告上机实验报告+上上机考察机考察 考试成绩：考试成绩：70%要求：上机不能做与该课程无关的内容。要求：上机不能做与该课程无关的内容。注意：无故缺勤或上机时间玩游戏等第注意：无故缺勤或上机时间玩游戏等第1次次平时成绩扣平时成绩扣5分，第分，第2次扣次扣10分，第分，第3次扣次扣15分，第分，第4次扣次扣

2、20分，第分，第5次扣次扣30分，第分，第6次平次平时成绩为时成绩为0。数据结构课件第1章教材与参考书教材与参考书 教材：苏德富，教材：苏德富，数据结构（数据结构（C语言）语言），重庆大学出版社重庆大学出版社 参考书：严蔚敏，参考书：严蔚敏，数据结构数据结构，清华大学，清华大学出版社出版社 李勤，李勤，数据结构数据结构，中国电力出版社，中国电力出版社 Clifford A.Shaffer，数据结构与算法分数据结构与算法分析析，电子工业出版社，电子工业出版社数据结构课件第1章课程重要性简介课程重要性简介是计算机相关专业考研的重点内容是计算机相关专业考研的重点内容大公司笔试的主要内容大公司笔试的主

3、要内容 是计算机专业核心必修课，是其它后续是计算机专业核心必修课，是其它后续计算机课程的重要基础计算机课程的重要基础是非计算机专业的主要选修课是非计算机专业的主要选修课数据结构课件第1章v 数据结构在学科中的地位数据结构在学科中的地位 数据结构是计算机科学中一门综合性的专业基础课。数据结构的研究不仅涉及计算机的硬件的研究范围，而且和计算机软件的研究有着更为密切的关系，无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件、计算可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。机软件三者之间的一门核心课程。数据结构 所处的地

4、位 数据结构课件第1章课程主要内容简介课程主要内容简介数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构(顺序与链式顺序与链式)及其操作及其操作(算法算法)（插入、删除（插入、删除与遍历等）与遍历等）线性表、树和图线性表、树和图查找与排序查找与排序（属常用算法总结）（属常用算法总结）算法的时空效率分析法算法的时空效率分析法数据结构课件第1章本课程章节主要内容本课程章节主要内容 第一章：绪论第一章：绪论 第二章：线性表和数组第二章：线性表和数组 第三章：栈和队列第三章：栈和队列 第四章：串第四章：串 第五章：树和二叉树第五章：树和二叉树 第六章：图第六章：图 第七章：排序第七章：排序 第八

5、章：查找第八章：查找 第九章：文件第九章：文件数据结构课件第1章第一章第一章 绪绪 论论v 数据结构的引论数据结构的引论例例1 1 图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题 线形数据结构，线形数据结构，1：1的关系的关系 在书目自动检索系统中可以建立一张按登录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示：什么是数据结构什么是数据结构001002003004.高等数学理论力学高等数学线形代数樊映川罗远祥华罗庚栾汝书S01L01S01S02.书目卡片书目卡片数据结构课件第1章高等数学理论力学线形代数001,003,002,004,.LS002,

6、001,003.特点：计算机按某个特定的计算机按某个特定的要求进行查询要求进行查询.处理对象之间处理对象之间存在一种简单的线形关系存在一种简单的线形关系,这这类模型可以称为简单的线形类模型可以称为简单的线形数据结构数据结构.按书名排列按书名排列樊映川华罗庚栾汝书001,003,004,.按作者排列按作者排列按索引号排列按索引号排列数据结构课件第1章例2 计算机和人的对弈问题“树树”形数据结构形数据结构，1：N的关系 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图:“树根”是对奕

7、开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程.*(a)棋盘格式示例(b)井字棋对弈树的局部*数据结构课件第1章例3 多叉路口交通灯的管理问题“图图”形数据结构形数据结构，M：N的关系 可以把这类交通,道路的问题当作一种“图图”的结构：一个顶点表示一条通道,而通道之间的矛盾的关系以两个顶点之间的连线表示.如下图所示:结论结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构.数据结构数据结构:数据结构是一门非数值计数据结构是一门非数值计算的程序设计问题中计算机的算的程序设计问题中计算机的操作

8、对象以及它们之间的关系操作对象以及它们之间的关系和操作等等的学科和操作等等的学科.AEDCB(a)五叉路口数据结构课件第1章v 数据（数据（Data)客观事物的符号表示，能输入到计算机中并被计算机中程序处理的符号的总称。v 数据元素数据元素(Data element)数据的基本单位，可由数据项组成。v 数据类型数据类型(Data Type)是一个值的集合和定义在这个值集上的一组操作的总称。如：int数据类型，取值范围为3276832767，操作运算有加、减、乘、除、取模、乘方等。基本概念基本概念数据结构课件第1章v数据对象数据对象(Data Object)性质相同的数据元素的集合，是数据的子集

9、。v数据结构数据结构(Data Structure)相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构：（1）集合（）集合（2）线形结构（）线形结构（3）树形结构（）树形结构（4）图状结构）图状结构(网状结构）。网状结构）。集合线性树图数据结构课件第1章数据结构数据结构DS的形式定义的形式定义：数据结构是一个二元组。数据结构是一个二元组。DS（K，R）其中：其中：K是数据元素的是数据元素的有限集有限集 R是数据元素之间关系的是数据元素之间关系的有限集有限集 对于R中任意二元关系（x，yK），称x为第一元素（或y的前驱），y为第二元素（或x的后继）

10、。v 数据元素之间的相互关系数据元素之间的相互关系数据元素之间的相互关系包括三个方面：数据的逻辑结构、存储结构、三个方面：数据的逻辑结构、存储结构、操作集合。操作集合。数据元素之间的逻辑关系，称为数据的逻辑结构逻辑结构。数据的逻辑结构分两大类：线性结构线性结构（线性表、栈、队列、字符串、数组、广义表）；非线性结构非线性结构（树、二叉树、图）。数据结构课件第1章 数据元素之间的关系在计算机中的表示数据元素之间的关系在计算机中的表示：有顺序映象和非顺序映象两种方法，由此得到两种存储结构：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：借助指示元素存储地址的指针

11、表示数据元素之间的逻辑关系。数据结构在计算机中的表示，称为数据的物理结构物理结构（存储结构）。逻辑结构是面向用户的、是抽象的；存储结构是面向计算机的、面向实现的。数据结构课件第1章v 数据操作描述数据操作描述数据的基本操作：插入插入：在数据结构的指定位置添加新的数据元素。删除删除：去掉数据结构中某个指定的数据元素。更新更新：改变数据结构中某个数据元素的值。查找查找：在数据结构中寻找某个满足特定要求的数据元素。排序排序：重新安排数据元素的逻辑顺序关系，使其值按从小到大或从大到小的顺序排列。：加工型操作加工型操作操作改变了（操作之前的）结构的值。引用型操作引用型操作不改变值，只是查询或求得结构的值

12、。数据结构课件第1章 算法算法：是：是对特定问题求解步骤的一种描述对特定问题求解步骤的一种描述，是指令的有限序列。，是指令的有限序列。什么是算法什么是算法算法的五个特征算法的五个特征：1、输入：可有、输入：可有0个或多个输入；个或多个输入；2、输出：至少有、输出：至少有1个或多个输出；个或多个输出；3、确定性：算法中每一步骤必须有确切含义，无二义性；、确定性：算法中每一步骤必须有确切含义，无二义性；4、有限性：能够在有限步骤内结束，不能形成无限循环；、有限性：能够在有限步骤内结束，不能形成无限循环；5、有效性：算法可以在纸上作业方式跟踪其结果。、有效性：算法可以在纸上作业方式跟踪其结果。算法设

13、计的要求算法设计的要求：1、正确性：当输入数据合法时，能够得到满足要求的结果；、正确性：当输入数据合法时，能够得到满足要求的结果；2、可读性：算法简单明了，便于别人对算法的理解和对程序的维护；、可读性：算法简单明了，便于别人对算法的理解和对程序的维护；3、低存储规模：存储规模是指算法在执行过程中所需的最大存储空间，、低存储规模：存储规模是指算法在执行过程中所需的最大存储空间，也称为算法的空间复杂性；也称为算法的空间复杂性；4、高效率：执行时间短的算法其效率就高，算法的执行时间也称为算、高效率：执行时间短的算法其效率就高，算法的执行时间也称为算法的时间复杂性。法的时间复杂性。数据结构课件第1章

14、算法与程序的区别算法与程序的区别：计算机科学家计算机科学家 N.沃思沃思 给出一个著名公式：给出一个著名公式：数据结构算法程序数据结构算法程序1、程序是在特定计算机上执行的算法，是具体、程序是在特定计算机上执行的算法，是具体的；而算法与具体计算机无关，是抽象的；的；而算法与具体计算机无关，是抽象的；2、程序可以不满足有限性要求；而算法必须满、程序可以不满足有限性要求；而算法必须满足有限性。足有限性。如：操作系统程序，除非关机，否则一直在如：操作系统程序，除非关机，否则一直在等待循环中等待下一个工作进入系统，所以只要等待循环中等待下一个工作进入系统，所以只要系统是在运作下，则操作系统程序就不会终

15、止。系统是在运作下，则操作系统程序就不会终止。数据结构课件第1章 v算法效率需通过该算法编制的程序在计算机上运行所算法效率需通过该算法编制的程序在计算机上运行所消耗的时间多少以及所需辅助空间的大小来度量。消耗的时间多少以及所需辅助空间的大小来度量。算法效率的度量算法效率的度量算法效率的衡量指标：算法效率的衡量指标：时间复杂度和空间复杂度。时间复杂度和空间复杂度。时间复杂度：时间复杂度：从算法中选取一个对于所研究的问题来说是基本操作的原操作（指固有数据类型的操作），以该基本操作重复执行的次数作为算法的时间量度。计作：T（n）=O（f（n）。它表示随着它表示随着n的增大，算法执行时间的增长率和的增

16、大，算法执行时间的增长率和 f(n)的增长率相同。的增长率相同。数据结构课件第1章空间复杂度：空间复杂度：一个上机执行的程序除了需要存储空间来积存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间。该辅助空间的大小及反映了该算法的空间复杂性。计作：S（n）=O（f（n）。频度：频度：某语句重复执行的次数。数据结构课件第1章程序段一：程序段一：+x;s=0；该程序中该程序中“+x”是基本操作语句，其频是基本操作语句，其频度为度为1，其时间复杂度为，其时间复杂度为O(1)，为常量阶。，为常量阶。例：求下面程序的时间复杂度。例：求下面程序的时

17、间复杂度。数据结构课件第1章程序段二：程序段二：for(i=1;i=n;+i)+x;s+=x;该程序中该程序中“+x”是基本操作语句，其频是基本操作语句，其频度为度为n，其时间复杂度为，其时间复杂度为O(n)，为线性阶。，为线性阶。数据结构课件第1章程序段三：程序段三：for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;该程序中该程序中“+x”是基本操作语句，其频度是基本操作语句，其频度为为n2，其时间复杂度为，其时间复杂度为O(n2)，为平方阶。，为平方阶。数据结构课件第1章程序段四：程序段四：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;ai

18、j=x;语句语句“+x”的执行次数关于的执行次数关于n的增长率的增长率为为n2,它是语句频度表达式它是语句频度表达式(n-1)(n-2)/2中增中增长最快的项长最快的项,时间复杂度为时间复杂度为O(n2)。vi=2，执行0次；vi=3，执行1次；vi=4，执行2次；vi=n，执行n-2次；v总共执行次数123(n-2)=(n-2)(n-2+1)/2=(n-2)(n-1)/2=(n2-3n+2)/2数据结构课件第1章常见的几种时间复杂度数量级O(1)常量级O(log2 n)对数级（较好）O(n)线性级O(nlog2 n)线性对数乘积级O(n2)平方级O(2n)指数级（很差）O(n!)阶乘级（很差

19、）v一般情况下，随着一般情况下，随着n的增大，的增大，T(n)增长较慢的算法为最优的算法。增长较慢的算法为最优的算法。v应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。数据结构课件第1章v衡量衡量两个算两个算法的好法的好坏，应坏，应当是在当是在n足够大足够大的情形的情形下，对下，对算法的算法的工作量工作量进行比进行比较，即较，即对算法对算法进行渐进行渐近性态近性态分析。分析。vn n较小时难辨优劣较小时难辨优劣数据结构课件第1章算法的阶 设非负函数设非负函数f(n)和和g(n)，nN，如果存在正常数，如果存在正常数c和正和正整数整数n

20、0，使得当，使得当nn0 时，有时，有f(n)cg(n)，则称，则称f(n)的阶的阶小于或等于小于或等于g(n)的阶；记为的阶；记为 f(n)O(g(n)，读作，读作f(n)是是 g(n)的大的大O。一般采用求极限的方法，来比较两个算法时间复杂一般采用求极限的方法，来比较两个算法时间复杂性函数的阶：性函数的阶：当当n时，时，lim f(n)/g(n)=c (1)当当c0，f(n)比比g(n)低阶，记为低阶，记为f(n)O(g(n)；(2)当当c0，f(n)和和g(n)同阶，记为同阶，记为f(n)(g(n)；(3)当当c，f(n)比比g(n)高阶，记为高阶，记为f(n)(g(n)；数据结构课件第

21、1章算法的阶写法写法条件假设条件假设近似近似f O(g)nn0,f(n)cg(n)f(g)f O(g)and g O(f)f(g)g O(f)数据结构课件第1章算法的阶 例如：例如：2n-5 O(n2)，因为当，因为当n时，时，lim(2n-5)/n2=2/n-5/n2 0-0=0；-低阶低阶 例如：例如：5n2-3n=(n2)，因为当，因为当n时，时，lim(5n2-3n)/n2=5-3/n5-0=5；-同阶同阶 例如：例如：n2+5n=(n)，因为当，因为当n时，时，lim(n2+5n)/n=n+5；-高阶高阶v注意：在求时间复杂度时，不需要严格区分同阶的注意：在求时间复杂度时，不需要严格区分同阶的情况下，把低阶或同阶的情况下，把低阶或同阶的f和和g统一写成统一写成 f O(g)数据结构课件第1章本章重点1.数据结构的有关基本概念2.数据结构的类型（逻辑结构）和存储方式（物理结构）3.算法及算法分析（算法评价）