【文档说明】数据结构(C语言版)课件.ppt，共(59)页，805.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-7188.html

以下为本文档部分文字说明：

第一章绪论1.3算法和算法的描述1.1什么是数据结构1.2基本概念和术语1.1什么是数据结构当今计算机应用的特点：l计算机应用领域从科学计算到非数值计算,更多地是需要对其进行组织、管理和检索;l所处理的数据量

大且具有一定的关系.下面举几个非数值计算的例子线性表例1学生档案管理系统学生基本情况学号姓名性别出生年月......99070101李军男80．12......99070102王颜霞女81．2.......99070103孙涛男80．9......99070104单晓宏男81．3..

..................................假设一个学生档案管理系统应包含如下表所示的学生信息特点：l每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；l表中每个学生的信息依据学号的大小存在着一种前后关

系，这就是我们所说的线性结构；l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。例2人机对奕问题树……..……..…...…...…...…...例3制定教学计划图计算机专业学生的必修课程课程编号课程名称需要的先导课

程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1在制定教学计

划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：c1c9c4c2c12c10c11c5c3c6c7c8课程先后关系的图形描形式：特点：•课程之间的先后关系用图结构描述；•通过实施创建图结构

，按要求将图结构中的顶点进行线性排序。结论计算机的操作对象的关系复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理

，就必须弄清楚这些数据之间的关系，在计算机中的存储方式以及各个操作的具体实现。数据结构的研究内容为：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。课程目的•能够分析研究计算机加工的对象的特性，获得其逻辑结构，

根据需求，选择合适存贮结构及其相应的算法；•学习一些常用的算法；•复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；•初步掌握算法的时间分析和空间分析技术。1.2基本概念和术语一、基本概念二、数据类型三、抽象数据类型学生

基本情况学号姓名性别出生年月......99070101李军男80．12......99070102王颜霞女81．2.......99070103孙涛男80．9......99070104单晓宏男81．3...

.................................1.数据:所有能被输入到计算机中，且能被计算机处理的符号的集合。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等数据形式。2.数据元素:数据的基本单位，也称结点（node）或记录（re

cord）。3.数据项:是数据结构中讨论的最小单位。一个数据元素可由若干数据项组成。数据元素数据项一、基本概念三者之间的关系：数据>数据元素>数据项例：学生表>个人记录>学号、姓名……4.数据对象：是性质相同的数据元素的集合，是数据的一个子集。整数数据对象N={0,1,2,…}学生数据对象

学生记录的集合5、数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。6逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。

集合数据元素间除“同属于一个集合”外，无其它关系线性结构一对一的关系，如线性表、栈、队列树型结构一对多的关系，如树图状结构或网状结构多对多的关系，如图。数据之间的关系分为四类：7.存储结构（物理结构）：数据在计算机中的存储表示。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关

系。(可以占用不连续的存储单元）分为两种：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。(占用连续的存储单元）head990180990290990375NULLa0123456789顺序存储结构链式存储结构l

逻辑结构和存储结构都相同,但运算不同,则数据结构不同.例如,栈与队列l对于一种数据结构,常见的运算插入删除修改查找排序数据的运算数据的逻辑结构数据的存储结构数据的运算：插入、删除、修改、查找、排序线性结构非线性结构顺序存储链式存储线性表栈、队列串、数

组树形结构图形结构逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构二、数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现

了的数据结构。C语言：基本数据类型：charintfloatdoublevoid构造数据类型：数组、结构体、共用体、文件三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型实际

上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组操作。ADT有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外

界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{数

据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式抽象数据类型的描述方法例如，抽象数据类型复数的定义：数据对象：D＝{e1,e2｜e1,

e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分|e2是复数的虚数部分}ADTComplex{基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyC

omplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用Ima

gPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的

结果抽象数据类型的表示与实现抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。教材中用的是类C语言（介于伪码和C语言之间）作为描述工具但上机时要用具体语言实现，如C或C++等例如，对前面定义的复数。typedefstruct{floatrealpart；flo

atimagpart；}complex；//-----存储结构的定义//-----基本操作的实现voidadd(complexz1,complexz2,complex&sum){//以sum返回两个复数z1,z2的和sum.realpart=z1.realpart+z2.realpart;su

m.imagpart=z1.imagpart+z2.imagpart;}{其它省略}1.3算法和算法的衡量一、算法二、算法设计的原则三、算法效率的衡量方法和准则四、算法的描述算法是对特定问题求解步骤的一种描述，是指

令的有限序列。一、算法计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。设计算法的基本过程1.通过对问题进行

详细地分析，抽象出相应的数学模型；2.确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；3.选用某种语言将算法转换成程序；4.调试并运行这些程序。例如：复数运算的实现一个算法必须满足以下五个重要特性：1．有穷性:一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

2．确定性：算法的每一步必须是确切定义的，不能产生二义性3．可行性：算法是能够实现的.即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4．有输入：一个算法有零个或多个输入5．有输出：一个算法有零个或多个输出二、算

法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性:2.可读性:3．健壮性:4．高效率与低存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。标准：通常对于精心选择的典型、苛刻而带有刁难性的几组输入数据程序能够得出满足规

格说明要求的结果。算法应易于阅读和理解，以便于调试和修改。算法应具有容错处理。当输入数据非法时，算法能做出适当的反应和进行特殊处理，而不是产年莫名其妙的输出结果。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法

：事前分析估算法1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计：一个高

级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———使用绝对时间单位衡量算法效率不合

适算法=控制结构+基本操作算法的执行时间=基本操作(i)的执行次数×基本操作(i)的执行时间∑算法的执行时间与基本操作执行次数之和成正比如何估算算法的时间复杂度？从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间

的衡量准则。算法中基本操作（循环）重复执行的次数是问题规模n的某个函数f(n),它是一个算法运行时间的相对量度,算法的时间量度记作：T(n)=O(f(n))时间复杂度的渐进表示法它表示随着问题规模n的增长，算法执行

时间的增长率和f(n)的增长率相同，T(n)称作算法的(渐近)时间复杂度。例1：{++x;s=0;}1O(1)for(i=1;i<=n;++i){++x;s+=x;}nO(n)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++

x;s+=x;}n*nO(n2)例2：例3：频度时间复杂度程序时间复杂度的计算：例4：voidmult(inta[],intb[],int&c[]){//以二维数组存储矩阵元素，c为a和b的乘积for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0

;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];//语句的频度:重复执行的次数：n3;}//for}//mult基本操作:乘法操作时间复杂度:O(n3)T(n)=O(n3)即：

矩阵乘法的运算量和问题的规模n的立方是同一个量级x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n

)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)例5：voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行数据累

加sum[i]=0.0;for(intj=0;j<n;j++)sum[i]+=x[i][j];//关键操作}for(i=0;i<m;i++)//打印各行数据和cout<<i<<“:”<<sum[i]<<endl;//关键操作}渐进时

间复杂度为O(max(m*n,m))算法的时间复杂度是由嵌套最深层语句的频度决定的例6：for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;

niniijniijjkiij1111112)1(16)2)(1(2)1(6)12)(1(2121112nnnnnnnniinini语句频度

=例7：例8：分析以下程序段的时间复杂度i=1;①while(i<=n)i=i*2;②nnf)(2即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=O(log2n)【例9】顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置

。for(i=0;i<n;i++)if(a[i]==e)returni+1;return0;有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同最好情况：1次最坏情况：n平均时间复杂度为:O(n

)时间复杂度T(n)按数量级递增顺序为：复杂度高复杂度低指数时间的关系为：O(2n)<O(n!)<O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊空间复杂度:算法所需存储空间的度量，

记作:S(n)=O(g(n))其中n为问题的规模(或大小)算法要占据的空间算法本身要占据的空间输入数据所占空间算法要使用的辅助空间若输入数据所占空间和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。渐进

空间复杂度一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用C语言作为描述算法的工具。四、算法的描述1．预定义常量和类型：简单说明C语言的

语法结构：typedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//函数结果状态代码#defineOK1#defineERROR0#defineINFEASIBLE-1#defi

neOVERFLOW-2//Status是函数返回值类型，其值是函数结果状态代码。typedefintStatus;函数类型函数名(参数表){//算法说明语句组}/*函数名*/2．函数的形式简单赋值：〈变量名〉=〈表达式〉，

它表示将表达式的值赋给左边的变量；〈变量〉++，它表示变量加1后赋值给变量；〈变量〉--，它表示变量减1后赋值给变量；3．赋值语句成组赋值：1.（<变量1>,<变量2>，…,<变量k>）=（<表达式1>，<表达式2>，…,<表达式k>）；2.<数组名1>[下标1…下标2]=<数组

名2>[下标1…下标2]串联赋值：〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；条件赋值：〈变量名〉=〈条件表达式〉？〈表达式1〉：〈表达式2〉；交换赋值：〈变量1〉←→〈变量2〉，表示变量1和变量2互换；情况语句:switch（表达

式）{case值1；语句组1；break；case值2；语句组2；break；……case值n；语句组n；break；[default：语句组；break；]}4．条件选择语句if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；⑴for语句for（表达式1；表达式2

；表达式3）{循环体语句；}5．循环语句⑵while语句while（条件表达式）{循环体语句；}⑶do-while语句do{循环体语句}while（条件表达式）输入语句：用函数scanf实现，当数据为字符时，用getchar函数实现。输出语句：用printf函数

实现，当要输出字符数据时，用putchar函数实现。6．输入、输出语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语

句：表示出现异常情况时，控制退出语句。8．注释形式可用/*字符串*/单行注释或//文字序列。7．其他一些语句如：max函数，用于求一个或几个表达式中的最大值；min函数，用于求一个或几个表达式中的最小

值；abs函数，用于求表达式的绝对值；9．一些基本的函数1.数据、数据结构等基本概念2.对数据结构的两个方面的理解逻辑结构的四种形式线性和非线性结构的逻辑特征存储结构的两种形式本章学习要点3.掌握计算语句频度和估算算法时间复杂度的方法。