数据结构与算法课件01 绪论

唐懿芳数据结构与算法---C语言和Java语言描述01学习数据结构的意义02数据结构的基本概念03算法及其描述针对实际问题，编写出一个高效率的处理程序，就需要解决如何合理地组织数据，建立合适的数据结构，设计较好的算法，来提高程序执行效率这样的问题。数据结构和算法就是在此背景下形成和发展起来的。简而言之，软件开发要多动脑筋、想到好的解决办法才能更快更好地编写出效率更高的程序。数据结构和算法这门课程的目的正是使学生更快地编写出更高效的程序。后两个条件比较容易实现，而第一个条件则需要花很多时间和精力才能够达到，而它恰恰是区分程序设计人员水平高低的一个重要标志。数据结构贯穿程序设计的始终，缺乏数据结构和算法的功底，很难设计出高水平的具有专业水准的应用程序。瑞士著名的计算机科学家尼古拉斯·沃思（Niklaus·Wirth）提出了“算法+数据结构=程序”的观点，这正说明了数据结构的重要性。即使是在广泛采用可视化程序设计的今天，借助于集成开发环境可以很快地生成程序，但要想成为一个专业的程序开发人员，至少需要以下三个条件：（1）能够熟练地选择和设计各种业务逻辑的数据结构和算法。（2）至少能够熟练地掌握一门程序设计语言。（3）熟知所涉及的相关应用领域知识。1.1.1引言2逻辑结构的延伸及基本算法3.物理结构4.运算集合（基本操作）1.逻辑结构(1)线性结构。结构中的数据元素之间存在着一对一的线性关系。(2)树结构。结构中的数据元素之间存在着一对多的层次关系。(3)图结构。结构中的数据元素之间存在着多对多的任意关系。1.1.2数据结构研究什么数据的逻辑结构线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。树结构：除根结点外，每个数据元素只有一个前驱数据元素，可有０个或若干个后继数据元素。图结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。01学习数据结构的意义02数据结构的基本概念03算法及其描述例如，学生信息可包括学生的学号、姓名、性别、年龄等数据。这些数据构成学生情况的描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。数据元素：表示一个事物的一组数据。数据项：构成数据元素的数据。抽象数据元素：没有实际含义的数据元素。抽象数据元素的数据类型：没有确切定义的数据类型。数据的逻辑结构：数据元素之间的相互联系方式。数据的存储结构：数据元素在计算机中的存储方式。数据的操作：对一种数据类型的数据进行的某种处理。数据的操作集合：对一种数据类型的数据进行的所有操作。基本术语数据的存储结构顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。顺序存储结构链式存储结构数据的操作从抽象角度，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论；具体来说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。

数据结构课程主要讨论线性表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。01学习数据结构的意义02数据结构的基本概念03算法及其描述算法是描述求解问题方法的操作步骤集合。描述算法的语言形式文字形式:用中文或英文这样的文字来描述算法。伪码形式:用一种仿程序设计语言的语言来描述算法。程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。1.3.1算法的概念和特定算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列五个重要特性:有穷性确定性可行性输入输出现在，品牌忠诚度成为最热门的词，消费者的“情感”被当作品牌要攻陷的最后堡垒。于是品牌整合营销、客户关系管理等成为了巩固品牌的热门手段，精耕细作、不盲目追求销售量的提升速度是这个阶段的特征。1.3.2算法设计的要求算法设计的好坏关乎程序的执行效率，算法设计必须满足以下要求：正确性可读性健壮性效率与低存储量需求现在，品牌忠诚度成为最热门的词，消费者的“情感”被当作品牌要攻陷的最后堡垒。于是品牌整合营销、客户关系管理等成为了巩固品牌的热门手段，精耕细作、不盲目追求销售量的提升速度是这个阶段的特征。1.3.3算法的分析1.算法效率的度量算法执行的时间是其对应的程序在计算机上运行所消耗的时间。程序在计算机上运行所需时间与下列因素有关：算法本身选用的策略；书写程序的语言；编译产生的机器代码质量；机器执行指令的速度；1.3.3算法的分析2.算法的时间复杂度可用算法中语句的执行次数来度量一个算法的效率。语句频度是指语句在一个算法中重复执行的次数。以下给出了两个n×n阶矩阵相乘算法中的各条语句以及每条语句的语句频度。语句 语句频度

for（i=0；i<n;i++） n＋1for（j=0；j<n;j++） n2＋n{c[i][j]=0; n2for(k=0;k<n;k++) n3＋n2c[i][j]=c[i][j]+a[i][k]*b[k][j];n3}1.3.3算法的分析所有语句的总执行次数为Tn=2n3+3n2+2n+1,即语句总的执行次数是问题的规模（矩阵的阶）n的函数f(n)（Tn=f(n)）。上式是Tn=f(n)中忽略其系数的n的最高幂次项，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。如上算法的时间复杂度T(n)=O(n3)。算法中n的最高次幂项与算法中称作原操作的语句的语句频度对应，原操作是算法中实现基本运算的操作，在上面的算法中的原操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]。一般情况下原操作由最深层循环内的语句实现。算法的时间复杂度记作：

T(n)=O(f(n))1.3.3算法的分析T(n)随n的增大而增大，增长的越慢，其算法的时间复杂度越低。下列三个程序段中分别给出了原操作count++的三个不同数量级的时间复杂度。（1）count++；其时间复杂度为O(1)，称之为常量阶时间复杂度（2）for(i=1;i<=n;i++)count++;其时间复杂度为O(n)，是线性阶时间复杂度（3）for(i=1;i<=n;i++)for(j=1;j<=n;j++)count++;其时间复杂度为O(n2)，平方阶时间复杂度此外，算法能呈现的时间复杂度还有：对数阶O(log2n),指数阶O(2n)等1.3.3算法的分析常见的时复杂度O(1)常数阶、O(n)线性阶、O(n2)平方阶、O(n3)立方阶、O(2n)指数阶、O(log2n)对数阶与O(nlog2n)。时间复杂度（从小到大排列）的比较如表1.2所示:表

常用的时间复杂度的比较log2nnnlog2nn2

n3

2n

0101121224842481664163824645122564166425650966553653216010243276821474836481.3.3算法的分析3.算法的空间复杂度采用空间复杂度作为算法所需存储空间的量度，记作：

S(n)=O(f(n))其中n为问题的规模。程序执行时，除了需存储本身所用的指令，