《数据结构》全册配套课件

《数据结构》全册配套课件2023/1/112023/1/11数据结构2数据结构

2023/1/11数据结构3教材：严蔚敏，吴伟民：《数据结构》，第三版，清华大学出版社，1992年课程安排：

总18周，授课16周，最后两周考核预备知识：熟练掌握C或C++语言，尤其是指针和类2023/1/11数据结构4前言开设和学习本课程的意义所在：生产方式的变革：材料、能源、信息；材料和能源的迅速减少，使得人们最终将开发和应用的重点日益转向到信息中来；人们必须更加集约地利用地球上有限的物质资源，同时，必须掌握更加有效的加工自然物手段高新技术；信息技术（InformationTechnology，简称IT）一直处于高新技术的核心地位；2023/1/11数据结构5前言计算机硬件技术计算机软件技术计算机通信技术数据的组成常用的算法软件设计和开发软件的实现原理和技术IT计算机软件技术数据的组成常用的算法软件的实现原理和技术2023/1/11数据结构6课程的目标加强“每一种数据结构都存在代价与效益”的概念。学习一些最基本、最常用的数据结构。它们组成了一个程序员的基本数据结构工具箱（toolkit）。掌握如何评估一个数据结构和算法的有效性。这些技术也使程序员能够判断自己或别人发明的新数据结构的价值。2023/1/11数据结构7第一章概论

什么是数据结构

为什么要学习数据结构

如何评价一个算法2023/1/11数据结构81.1为什么要学习数据结构第一章概论一、数据结构的形成与发展背景科学计算->非数值计算数值->结构数据随着社会的发展，计算机应用的范围已经深入到社会的各个领域，计算机的应用已经不在局限于科学计算，而是更多用于控制、管理及数据处理等非数值计算。相应的计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等具有一定结构的数据。为了编写一个好程序，必须分析待处理对象的特性以及各处理对象之间存在的关系。2023/1/11数据结构9二、数据结构的地位数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。1.1为什么要学习数据结构2023/1/11数据结构10数据结构在计算机科学中的地位1、算法和数据结构是计算机科学的两大支柱计算机科学早期定义为：研究算法的科学近期定义为：研究数据的科学2、数据结构是程序设计的基础3、是信息类学科的专业基础课程。算法＋数据结构＝程序

程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构1.1为什么要学习数据结构2023/1/11数据结构11要求：1、掌握各类基本数据结构类型和相应的存储结构2、提高阅读和编写算法的能力3、能针对给定问题，选择相适应的数据结构，并能设计和分析算法。2023/1/11数据结构12什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。1.1为什么要学习数据结构2023/1/11数据结构13例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。第一章概论1.1为什么要学习数据结构2023/1/11数据结构14第一章概论1.1为什么要学习数据结构例一：电话号码查询问题电话号码查询问题的索引存储2023/1/11数据结构15算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法第一章概论1.1为什么要学习数据结构2023/1/11数据结构16数据结构研究的内容(cont’d)图书目录文件示例001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数栾汝书S02………………高等数学001,003,…理论力学002,…线性代数004,………樊映川001,…华罗庚003,…栾汝书004,………L002,…S001,003,………2023/1/11数据结构17数据结构的定义

通过以上例子可以直接认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。研究内容：1、数据结构是研究数据的逻辑结构和物理结构以及它们之间相互关系2、并对每种结构定义相适应的各种运算3、设计出相应的算法4、分析算法的效率2023/1/11数据结构18第一章概论1.2数据结构的概念一、术语1.数据(Data):

是信息的载体，能被计算机识别、存储、加工处理。2.数据元素(DataElement):

数据的基本单位,即数据集合中的一个个体。也称元素、结点、顶点、记录数据项是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素由数据项(dataitem)组成2023/1/11数据结构193.数据对象具有性质相同的数据元素的集合，是数据的子集。例如：数据集合D={0，1，。。。A，B，。。。Z}正整数N={0,1,…}字符C={A,B,…,Z}2023/1/11数据结构20第一章概论1.2数据结构的概念4、数据结构(DataStructure)

按某种逻辑关系组织起来的一批数据,应用计算机语言按一定的存储方式将其存储在计算机中,在这些数据上定义了若干基本运算,并且讨论这些基本运算基于存储方式上的实现。这种逻辑关系称为结构。常见结构：1、集合2、线性结构（1对1）3、树形结构；（1对多）4、图状结构或网状结构。（多对多）2023/1/11数据结构21数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。2023/1/11数据结构22数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。2023/1/11数据结构235、数据类型(DataType):

是具有相同性质的计算机数据的集合及在这个集合上的一组操作。按数据的不同特性：原子数据类型(atomicdatatype)：不可分结构数据类型(aggregatedatatype)：可分2023/1/11数据结构24例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而结构类型可以看成由一种数据结构和定义在其上的一组操作组成。2023/1/11数据结构256、抽象数据类型（abstractdatatype）：“抽象”的意义在于数据类型的数学抽象特性一个数学模型以及定义在该模型上的一组操作。（ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。）抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。一个含抽象数据类型的软件模块应包括定义、表示和实现3个部分用三元组描述如下：（Ｄ，Ｓ，Ｐ）D是数据对象，S是D上的关系集，P是对D的操作集2023/1/11数据结构26格式：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名基本操作定义格式：基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>2023/1/11数据结构27第一章概论1.2数据结构的概念数据结构包括四方面的内容：

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/1/11数据结构28

数据的逻辑结构

指的是数据之间的逻辑关系，其独立于具体的计算机，为具体问题抽象出来的数学模型。第一章概论1.2数据结构的概念（1）线性结构（2）非线性结构特征：一个结点可能有多个直接前趋和直接后继。

特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。逻辑结构的分类：2023/1/11数据结构29第一章概论1.2数据结构的概念数据结构包括四方面的内容：

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/1/11数据结构30

数据的存储结构

指的是数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言。第一章概论1.2数据结构的概念数据的逻辑结构和物理结构是密切联系的两个方面，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构2023/1/11数据结构31数据的存储结构可采用四种基本存储方法：（1）顺序存储方法

将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。采用顺序存储方法所得到的存储表示称为顺序存储结构。（2）链接存储方法

不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由存储结点时附加的指针字段表示。采用链接存储方法所得到的存储表示称为链式存储结构。第一章概论1.2数据结构的概念2023/1/11数据结构32（4）散列存储方法

根据结点的关键字直接计算出该结点的存储地址，以实现对结点的存储和访问。第一章概论1.2数据结构的概念

在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，其一般形式为：（关键字，地址）。（3）索引存储方法2023/1/11数据结构33第一章概论1.2数据结构的概念数据结构包括四方面的内容：

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/1/11数据结构34

逻辑结构上的基本运算

每种逻辑结构都涉及到一些基本运算，这些基本运算实际上是定义在抽象的数据上的一系列操作。最常用的运算有：检索、插入、删除、更新、排序等。第一章概论1.2数据结构的概念2023/1/11数据结构35第一章概论1.2数据结构的概念数据结构包括四方面的内容：

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/1/11数据结构36

存储结构上基本运算的实现

运算的实现实际上指的是采用怎样的步骤或方法去实现定义在逻辑结构上的运算的功能。第一章概论1.2数据结构的概念逻辑结构上定义的基本运算只有在逻辑结构的存储实现之后才能够在该存储结构上实现。2023/1/11数据结构37第一章概论1.2数据结构的概念例:计算机系学员的选课、业余爱好、担当职务情况统计如下：学号选修课程爱好职务1B.F无班长2A.C体育3A.D.F体育体委4D.E文艺5C.E文艺6D.F体育7B.E体育8A.E体育9B.F文艺文委10B.D文艺2023/1/11数据结构38第一章概论1.2数据结构的概念学号选修课程爱好职务1B.F无班长2A.C体育3A.D.F体育体委4D.E文艺5C.E文艺6D.F体育7B.E体育8A.E体育9B.F文艺文委10B.D文艺建立数据元素之间的逻辑结构：1。按学号顺序建立并表示该集合的关系12345678910线性结构：线性表2。按职务和爱好建立关系1

2396784510非线性结构：树2023/1/11数据结构39第一章概论1.2数据结构的概念2、存储结构线性表1、逻辑结构a1+9顺序表a1a1+1a1+212310

••••••a10链表a112310

a2a32023/1/11数据结构40第一章概论1.2数据结构的概念2、存储结构树1、逻辑结构a1+9顺序存储a1a1+1a1+213910

••••••-1a1a1a1+2链式存储391^^2….^^^^^^^^^10

…1

23967845102023/1/11数据结构413、数据的运算：退学插班查看删除插入查找4、运算的实现：a1+9a1a1+1a1+212310••••第一章概论1.2数据结构的概念a12310

a2a3a101…2023/1/11数据结构42第一章概论1.2数据结构的概念4、运算的实现：3、数据的运算：退学插班查看删除插入查找a1+9a1a1+1a1+212310••••••a1+9a12310

a2a3a101…2023/1/11数据结构43第一章概论1.2数据结构的概念说明：同一批数据可以抽象出不同的逻辑结构同一逻辑结构采用不同的存储方法，可以得到不同的存储结构，并冠以不同的名称；存储方法可以单独使用，也可以结合起来使用；数据结构的逻辑结构、存储结构、运算三个方面是一个整体；运算是数据结构的重要方面2023/1/11数据结构44

逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义

算法（algorithm）是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。第一章概论1.3算法描述2023/1/11数据结构45第一章概论

二、算法应具有的五个特性：（1）输入(Input)一个算法有零个或多个的输入，它们 是算法开始前给出的最初量。（2）输出(Output)一个算法至少有一个输出，它们是同输入 有某种关系的量（3）有穷性(Finite)算法执行有穷步运算后能够终止，且每一步都可以在有穷时间内完成。（4）确定性(Definite)每一条指令必须有确切的含义，无二义性。相同输入只能产生相同输出。（5）可行性(Effective)每种运算都是相当基本的、行得通的，原则上能精确实施。

1.3算法描述2023/1/11数据结构46第一章概论1.3算法描述一个算法可以用自然语言、数学语言或约定的符号语言来描述。本书用C语言描述算法。四、算法描述三、算法与程序的关系区别：1、程序不一定满足有穷性

2、程序中的指令必须是机器可执行的，算法中的指令则无此限制联系：算法用机器可执行的语言来书写，就变成一个程序。2023/1/11数据结构47第一章概论一、算法评价五要素

（1）正确性（correctness）（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（readability）（5）健壮性（robustness）1.4算法分析1、程序不包含语法错误；2、程序对于几组输入数据能够得出满足规格说明要求的结果3、程序对于精心选择的典型、苛刻而带有刁难性的几组数据都能产生满足规格说明要求的结果，4、程序对于一切合法输入数据都能产生满足规格说明要求的结果2023/1/11数据结构48第一章概论二、算法运行时间要素（1）对源程序进行编译所需的时间（2）程序运行时所需数据输入的时间（3）机器执行每条指令所需时间（4）程序中的每条指令重复执行的次数。

假设每条指令执行所需时间为单位时间。算法的时间耗费T(n)可以用每条指令重复执行的次数（也称语句频度FrequencyCount）之和进行度量，1.4算法分析2023/1/11数据结构49例1.4求两个n阶方阵的乘积C=A×B,其算法描述如下：

#definen自然数

matrixmlt(a,b,c)floata[][n],b[][n],c[][n];

{

inti,j,k;

(1)for(i=0;i<n;i++)(2)for(j=0;j<n;j++)(3){c[i][j]=0;(4)for(k=0;k<n;k++)(5)c[i][j]=c[i][j]+a[i][k]*b[k][j];}}

n+1n(n+1)n2n2(n+1)n3T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

2023/1/11数据结构50第一章概论为方阵的阶n的函数。当n趋于无穷大时，T(n)/n32即T(n)与n3是同阶的，可记为T(n)=O(n3),并将其称为该算法的（渐进）时间复杂度(timecomplexity)。1.4算法分析T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

2023/1/11数据结构51第一章概论1.4算法分析记号“O”是数学符号，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，当存在两个正的常数c和n0时，使得对所有的n>=n0,都有T(n)<=c.f(n)成立，则称T的阶不高于f的阶，并记作T(n)=O(f(n))。该式表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度三、（渐进）时间复杂度(O(f(n))2023/1/11数据结构52常见的时间复杂度有：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……、k次方阶O(nk)、指数阶O(2n)。三、（渐进）时间复杂度(O(f(n))第一章概论1.4算法分析2023/1/11数据结构53第一章概论1.4算法分析例一：交换a和b的内容temp=a;a=b; b=temp;T(n)=O(1)2023/1/11数据结构54例二：变量记数之一(1)x=0;y=0;(2)for(k=1;k<=n;k++)(3)x++;(4)for(i=1;i<=n;i++)(5)for(j=1;j<=n;j++)(6)y++;频度最大的语句是（6），且f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)第一章概论1.4算法分析2023/1/11数据结构55例二：变量记数之二(1)x=1；(2)for(i=1;i<=n;i++)(3)for(j=1;j<=i;j++)(4)for(k=1;k<=j;k++)(5)x++;频度最大的语句是（5），且f(n)=?。所以该程序段的时间复杂度为T(n)=O(n3)2023/1/11数据结构56第一章概论1.4算法分析四、最坏时间复杂度和平均时间复杂度很多算法的时间复杂度不仅仅是问题规模的函数，还与它所处理的数据集的状态有关，在这种情况下，通常是根据数据集中可能出现的最坏情况，估计出算法的最坏时间复杂度。有时对数据集的分布作出某种假设（如等概率），讨论算法的平均时间复杂度。2023/1/11数据结构57例：在数组A[n]中查找值为K的元素，若找到，则返回位置I(0<=I<=n-1)；否则返回-1，算法如下：第一章概论1.4算法分析(1) I=n-1(2) while((I>=0)&&(A[I]!=K))(3) I--;(4)returnI;最坏事件时间复杂度T(n)=n2023/1/11数据结构58五、空间复杂度(SpaceComplexity)S(n)：

算法所耗费的存储空间，仍是问题规模n的函数。记作：S(n)=O(f(n))2023/1/11数据结构59第一章概论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。2023/1/11数据结构60习题1、简述下列术语：数据、数据元素、数据对象、数据结构2、判断以下算法A和B处语句的语句频度，并计算该算法的时间复杂度。for（i=1,i<n-1,i++){y++,for(j=0,j<2n,j++){x=x+1;}}2023/1/11数据结构61习题：3、计算机算法指的是____A、计算方法B、排序方法C、解决某一问题的有限指令序列D、调度方法2023/1/11数据结构62

C语言语法结构简介

1.C程序是由函数构成的2.函数的组成函数说明部分:[函数类型]函数名([形式参数表列])函数体:{变量说明部分

语句部分

}intmax(x,y)函数类型函数名形参表列[形式参数说明]intx,y;形参类型形参

一个Ｃ程序有且仅有一个main函数．函数是程序的基本单位，被调函数既可以是系统提供的库函数，也可以是自定义函数。一、函数形式2023/1/11数据结构633.一个C程序总是从main函数开始执行，而不论main在整个函数中的位置如何

4.C程序书写格式自由，一行内可以写几个语句，一个语句也可以写在几行上

5.分号；是语句结束符，是语句的一部分

6.函数通常结束于return语句。2023/1/11数据结构64二、条件语句的两种格式1.格式1：

if(表达式)语句例:if(a<0)a=-a;printf(“a=%d\n”,a);2.格式2：

if(表达式)

语句1else

语句23.功能：把(表达式)作为条件，根据其值真假选择所要执行的操作条件语句真(非0)假(0)格式1条件语句1真(非0)假(0)语句2格式22023/1/11数据结构651、while循环语句2）执行过程:①计算E的值②若E非0,则执行S,然后转①若E为0,则退出循环,执行该循环后的语句1）格式

while(表达式E){

循环体语句序列S}ES0非03）特点:

先判断表达式，后执行语句,因此,若进入while循环时E的值就是0，则语句S一次也不执行三、循环语句的三种格式2023/1/11数据结构662、do~while循环语句2）执行过程:①执行循环体S②计算E值若E的值为真(非0),则转①若E的值为假(0),则结束循环1）格式:do{

循环体语句序列S}while(表达式E);ES0非03）特点:

先执行循环体，再判断表达式，因此循环体至少执行一次三、循环语句的三种格式2023/1/11数据结构673、for循环语句2）执行过程:①计算E1②计算E2值若E2非0,则执行循环体S,再计算E3,转②若E2为0,则结束循环1）格式:for(表达式E1;表达式E2;表达式E3){

循环体语句序列S}计算E2S假(0)真(非0)计算E1计算E3三、循环语句的三种格式注意：上述的三种循环体语句中，均可使用break语句退出循环体。2023/1/11数据结构68四、情况语句(开关语句)1.格式:switch(表达式){case常量表达式1:语句1；break；

case常量表达式2:语句2；break；

case常量表达式n:语句n；break；

default:语句n+1；break；

}2.执行过程:①先计算表达式的值;②按case语句的顺序测试表达式的值与哪个case常量值相同若与某一常量相同,控制转向该case常量后面的语句开始执行;③否则,在有default时,执行default后的语句,无default时,什么也不执行2023/1/11数据结构69五、赋值语句1.

<变量>=<表达式>；或

<变量>op=<表达式>；

例sum=3*75;sum+=25;2.变量++

变量加1后赋值给变量3.变量--

变量减1后赋值给变量2023/1/11数据结构70六、输入、输出语句1、字符：用函数getchar和putchar实现。

1）putchar(c);

功能：输出字符变量c的值，c可以是字符变量或整型变量．

2）getchar();

功能：从终端(或系统隐含的输入设备)输入一个字符,并把得到的字符作为函数的返回值.2023/1/11数据结构712、其它数据：用函数scanf和printf实现其输入和输出。1）printf(格式控制，输出表列)printf(“a=%d,b=%d”,a,b);2）scanf(格式控制参数,地址1,地址2,…);

功能:按格式控制参数的要求从终端上把数据传送到地址参数所指的内存空间中，其中地址可以是变量的地址，也可以是字符串的首地址七、注解形式

/*字符串*/1C语言的数据类型一、为什么要规定数据类型：C语言规定，在程序中用到的每一个变量都要指定它们属于哪一种类型，这是因为：1.不同类型的数据在内存中占不同长度的存储区，而且数据在计算机内的表示形式也不同.

例如：一般微机2bytes存放一个整型

4bytes存放一个实型2.一种数据对应着一个值的范围int-32768∼32767float10-38∼1038之间2023/1/11数据结构73

例如：整型数据可以进行求余(5%2=1)，而实数不能进行求余运算。数值型数据可以进行四则运算，而结构型数据就不能进行四则运算。

※一个变量应有确定的类型，在一个程序中一个变量只能属于一个类型，不能先后被定义为二个或多个不同的类型。3.一种数据类型对应一组允许的操作2023/1/11数据结构74二、C的数据类型：数据类型基本类型整型短整型(short)整型(int)长整型(long)实型(浮点型)单精度型(float)双精度型(double)数值类型字符类型(char)枚举类型(enum)

构造类型(组合类型)数组类型结构体类型(struct)共同体类型(union)文件类型(file)指针类型空类型(void)不返回任何类型的数据2023/1/11数据结构75在程序中，不同类型的数据既可以以常量形式出现，也可以以变量形式出现。所谓常量是指在程序执行期间其值是不能发生变化。变量则其值可以变化的。2常量与变量

例如：1.2，3，‘a’

都是常量，分别代表实型、整型和字符型常量。它们的特点是从字面上即可判断它们是某一类型的常量，所以又称为字面常量或直接常量。

符号常量：是在一个程序(或程序的一部分)中指定一符号或标识符代表一个常量。一、(直接)常量和符号常量：2023/1/11数据结构76例：#definePRICE30main(){intnum,total;num=10;total=num*PRICE;printf(“total=%d”,total);}输出结果：total=300说明：(2)符号常量不同于变量，它的值在其作用域内不能改变，也不能再被赋值．(1)习惯上符号常量用大写，变量用小写以示区别PRICE=50╳注意：‘a’和“a”的区别：‘a’是单个字符常量，一个字符“a”是字符串常量，含有二个字符‘a’,‘\0’charc;c=‘a’;√c=“a”;×2023/1/11数据结构77存储单元所存储的数据称为变量的值，这个存储空间的首地址就称为该变量的地址。

二、变量：变量是其值可以改变的量称为变量。每一个变量都有一个名字，称之为变量名，它代表了某个存储空间及其所存储的数据。※标识符是以字母或下划线开头，由字母、数字或下划线组成的字符序列

2023/1/11数据结构783C语言概述一、控制语句:完成一定的控制功能．

①if()~else~条件语句②for()~③while()~④do~while()⑤continue结束本次循环⑥break终止循环或switch⑦switch多路分支语句⑧goto转移语句⑨return返回语句循环语句上面9种语句中的括号()表示其中是一个条件，~表示内嵌的语句．2023/1/11数据结构79如：i++；a=3；i=i+1；都是赋值语句

二、表达式语句:

表达式加分号构成表达式语句

典型的是：由赋值表达式构成赋值语句．1.i的初值为3k=(i++)+(i++)+(i++)

值为9(3+3+3),i的值为6k=(++i)+(++i)+(++i)

值为18(6+6+6),i的值为62023/1/11数据结构80逻辑运算符及优先级：

&&(与)||(或)!(非)二元一元三、逻辑运算符：2023/1/11数据结构814一维数组一、一维数组的定义：定义方式:类型说明符数组名[常量表达式];例:inta[10];floatfa[100],fb[100];chars1[20],s2[40];1.常量表达式表示数组元素个数,下标变化范围0到N-1

2.C不允许动态数组常量表达式中只能有常量和符号常量,不能有变量。2023/1/11数据结构82二、一维数组的引用：

数组必须先定义,后使用,而且只能逐个引用数组元素,而不能一次引用整个数组。数组的表示形式:数组名[下标]下标可以是整型常量或整型表达式inta[N];下标变化范围0到N-1for(i=0;i<N;i++){scanf(“%d”,&a[i]);printf(“%d”,a[i]);}2023/1/11数据结构835函数

一个较大的程序一般应分为若干个程序模块，每一个模块用来实现个定的功能。所有的高级语言中都有子程序这个概念,用子程序来实现模块功能。在Ｃ语言中，子程序的作用是由函数来完成的。一个Ｃ程序可由一个主函数和若干个函数构成。由主函数调用其它函数，其它函数也可以互相调用。同一个函数可以被一个或多个函数调用任意多次。在程序设计中，常将一些常用的功能模块编写成函数，放在函数库中供公共选用。要善于用函数库，以减少重复编写程序段的工作量。

C语言提倡把一个大问题划分成许多个小块，每一小块编制一个函数。这样C程序是由大量小函数而不是由少量大函数构成。这样作的好处:

各部分充分独立，任务单一，便于书写和调试。有些小函数还可以作为构件,被别的程序利用。2023/1/11数据结构84先看一个简单的例子例7.1main(){printstar();/*调用prinstar函数*/print_message();

/*调用print_message函数*/printstar();

/*调用printstar函数*/}printstar()

/*printstar函数*/{printf(“******************\n”);}print_message()/*printmessage函数*/{printf(“Howdoyoudo!\n”);}

运行情况如下：******************Ｈowdoyoudo!******************2023/1/11数据结构85指针

指针类型是C语言中使用十分普遍的数据类型，它与一般的变量不同之处是它包含的不是数据的值，而是一变量的地址。指针是C语言中的一个重要概念，也是一个比较难掌握的概念，正确而熟练地掌握了指针的概念和指针的使用，就能设计出复杂的数据结构和高效的程序，没有掌握指针就没有掌握C语言的精华。凡是程序中定义的变量，在编译时系统都给他们分配相应的存贮单元，一般微机C系统给整型分配2个字节，给实型分配4个字节，每个变量所占的存贮单元都有确定的地址，具体地址在编译时分配。2023/1/11数据结构86例:inta=3,b=4;floatc=4.5,d=8.6;chare=‘x’,f=‘y’;101010121014a101810221023bcdef344.58.6xy

要访问内存中的变量，在程序中是通过变量名来引用变量的值。但实际上，在编译时将每个变量名对应一个地址，在内存中不再出现变量名而只有地址。若程序中引用变量a，系统找到对应地址1010，然后从1010，1011两个字节中取出其中的值。2023/1/11数据结构87直接访问：通过变量名或地址访问一个变量的方式为“直接访问”。间接访问：把地址存放在一个变量中，然后通过先找出地址变量中的值(一个地址)，再由此地址找到最终要访问的变量的方法称为“间接访问”。存放地址的变量是一种特殊的变量，它只能用来存放地址而不能用来存放其它类型的数据，需要专门加以定义。2023/1/11数据结构88y101010121014a101810221023bcdef344.58.6x200220042006pa201010141016pbpcpdpepf10101012101410181022102320082012物理关系角度pa3apb4bpcpdpe4.5c8.5dxepfyf逻辑关系角度2023/1/11数据结构89一、指针变量的定义在程序中对于存放地址的变量要专门定义。如：int*p;

定义了一个指针变量p，它指向一个整型变量指针int*p,i=3;p=&i;P3i&iP3i2023/1/11数据结构90例：&k取变量k地址

&c[2]取数组元素c[2]的地址

&()取结构st变量name项的地址

&233,&(i+233)&：(取地址运算符)取当前变量的地址运算对象不能是常量表达式或寄存器变量请区别：指针：就是地址变量的指针：就是变量的地址指针变量：存放地址的变量2023/1/11数据结构91指针变量定义的一般形式：类型标识符*标识符；注1.标识符前面的“*”标示该变量为指针变量。2.一个指针变量只能指向同一类型的变量。请区别：指针：就是地址变量的指针：就是变量的地址指针变量：存放地址的变量2023/1/11数据结构92int*p,a;printf(“%o”,p);以八进制形式输出指针变量p的值(地址)p=&a;将整型变量a的地址赋给指针变量p，此时p指向a二、指针变量的引用在定义了指针变量之后，可以对指针变量进行各种操作。例如：给指针变量赋地址;输出指针变量的值;访问指针变量所指的变量等。scanf(“%d”,p);

向p所指的整型变量输入一个整型值printf(“%d”,*p);

将指针变量p所指向的变量的值输出*p=5;

将5赋给p所指的变量2023/1/11数据结构93C语言中有关指针的运算符◆&运算符:取地址运算符◆*运算符:指针运算符或指明运算符，*p代表p所指变量注意：此处的*p与定义指针变量时用的*p的含义是不同的。定义int*p;中的*不是运算符,它只是表示其后的变量是一指针变量程序中的*p，其中的*是一个指针运算符，*p表示p指向的变量如：printf(“%d”,*p);printf(“%d”,a);结果都为3P3i&iP3i2023/1/11数据结构94main(){int*p1,*p2,i,j,k;i=3;j=5;p1=&i;p2=&j;k=*p1;*p1=*p2;*p2=k;printf(“i=%d,j=%d\n”,i,j);}例：交换两指针变量所指向的值运行情况:i=3，j=5&i1P15i&i2P23j*p1*p22023/1/11数据结构95三、指针变量的运算●当指针指向一个具有基本类型或组合类型中具有基本类型的成分分量时,则它可以象基本变量一样使用。inti,*pi;pi=&i;i=0;&iPi0i*pi=0;i+=1;*pii++;*pi+=1;(*pi)++;2023/1/11数据结构96C语言的函数的参数传递是以“传值”方式进行变量参数的信息传递，被调函数不能直接改变主调函数中参数的值。当引入指针的概念后，我们可以在主调函数中将要改变内容的变量地址作为参数传递给被调函数，而被调函数执行时，就按这个地址去访问变量参数的值，相应的参数要被说明成指针类型。2023/1/11数据结构97swap(intx,inty){intt;t=x;x=y;y=t;}main(){inta,b;a=3;b=5;swap(a,b);printf(“%d,%d”,a,b);}swap(int*x,int*y){intt;t=*x;*x=*y;*y=t;}main(){inta,b;a=3;b=5;swap(&a,&b);printf(“%d,%d”,a,b);}2023/1/11数据结构98

其中：a是数组名，它表示该数组的起始地址，是个常量。

a恒等于&a[0],&a[i]是a[i]元素的地址,

即a+i==&a[i]

四、一维数组的指针表示法inta[10];/*a[0],a[1],a[2],a[3],a[4]...a[9]*/在编译系统计算实际地址时，a+i中的i要乘上数据元素所占的字节数，即：a+i×(一个元素所占字节数)例如：若整型数组a的起始地址为1010，则a+1的实际地址是1010+1×2=1012a数组a[0]a[1]a[2]

a[i]a[9]aa+1a+ia+92023/1/11数据结构99◆指针与数组的一致性:inta[10],*p;p=a;p=&a[0]p+1:指向a[1]p+i:指向第i个元素p-i:指向p前的第i个元素*p所以*(a+i)a[0]*(p+1)a[1]*(p+i)a[i]要引用一个数组元素，有两种不同的方法：

(1)下标法a[i](2)地址法*(a+i)a[i]

&a[i]而且*(p+i)a+ip[i],a[i]a数组a[0]a[1]a[2]

a[i]a[9]p,ap+1,a+1p+i,a+ip+9,a+92023/1/11数据结构100注意：不能用以下方法输出a数组的5个元素，因为a是起始地址，是个常数。for(i=0;i<5;i++)printf(“%d”,*a++);p=a;for(i=0;i<5;i++)printf(“%d”,*p++);而应写成：2023/1/11数据结构101结构

“结构”数据类型，与组合数据类型数组一样，在结构类型的变量中，可以有若干个成分分量(成员、元素)，并且这些成分分量的个数是确定的。但结构与数组不同:

(1)数组表示的是同一数据类型的集合

(2)结构表示的是不同数据类型的集合(也可以相同)

2023/1/11数据结构102

在数据处理领域，常常要求把一些属于不同类型的数据作为一个整体来处理。如一个学生的信息包括：一、结构体类型概述

它们是同一个处理对象(学生的属性)，但又不属于同一类型。如果用简单来分别代表各个属性，就难以反映出它们之间的内在联系，而且使程序冗长难读。用数组则无法容纳不同类型的元素。学号姓名性别年龄成绩地址2023/1/11数据结构103C语言用结构体类型来描述一个学生的信息。

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;关键字结构名结构成员表变量说明表2023/1/11数据结构104二、结构体的定义及结构体变量的说明例:对一个学生的描述1.结构体定义的一般形式

struct标识符{结构成员表};

或struct{结构成员表};

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};struct{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};2023/1/11数据结构105(1)先定义结构类型再定义变量名

struct标识符{结构成员表};struct标识符(同上)结构变量标识符;例:structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};structstudentstudent1,student2;2.结构体变量的说明2023/1/11数据结构106例:structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}student1,student2;(2)在定义结构类型的同时定义变量

struct标识符{结构成员表}结构变量标识符;2023/1/11数据结构107(3)直接定义结构类型变量(无名定义)struct{结构成员表}结构变量标识符;例:struct{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}student1,student2;2023/1/11数据结构1081.对结构可以取地址

&结构名(取结构的地址)

如：&student1&成员名(取结构成员的地址)

如：&student1.num

其中：&为取地址运算符三、对结构体的操作3.访问结构的成员

a.“.”方式：student1.numb.“->”方式：(*p).age或p->age，二者等价2.可定义指向结构的指针

structstudent*p;structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}student1;2023/1/11数据结构1094.对结构变量可以像普通变量一样进行各种运算(根据其类型决定可以进行的运算)如：student2.score=student1.score;sum=student1.score+student2.score;student1.age++;++student1.age;printf(“%d\n”,student1);scanf(“%d”,&student1);printf(“%d,%s,%c,%d,%f,%s”,student1);printf(“%d,%s\n”,student1.num,);scanf(“%d,%s\n”,&student1.num,);注意1.C不允许把一个结构体变量作为一个整体进行输入/输出操作╳√√╳╳2023/1/11数据结构1102.如果成员本身又属于一个结构体类型，则要用若干个成员运算符，一级一级地找到最低的一级的成员。只能对最低级的成员进行赋值或存取以及运算。如：employ.birthday.daystructdate{intmonth;intday;intyear;};structperson{charname[20];structdatebirthday;charsex;longnum;charnation;}employ;2023/1/11数据结构111

当数组中的每个元素都是同一结构类型变量时，称该数组为结构体数组。这种构造类型在C程序中得到了广泛的使用。(1)计算C语言中每一个关键字出现的次数。char*keyword[NKEYS];intkeycount[NKEYS];可以用结构数组表示成:structkey{char*keyword;intkeycount;}key_tab[NKEYS];key_tab[0]intintintkey_tab[1]key_tab[2]...…..\0四、结构体数组2023/1/11数据结构112(2)structstudentstudent1[1000];student1是有1000个元素的数组，其中每个元素都是具有student结构类型的变量，每个student1[i]反映了某个学生的个人资料。结构体数组的定义(1)和定义结构体变量的方法相仿，只需说明其为数组即可。如：structstudentstu[3];(2)也可以直接定义一个结构数组。如：structstudent{intnum;…}stu[3];或：struct{intnum;…}stu[3];2023/1/11数据结构113五、指向结构体类型数据的指针1、指向结构的指针定义描述及访问方式：

structkey*p;(*p).keycount;p->keyword;(*p).keyword;2、指向结构数组的指针structst{inta;floatb;}arr[3],*p;33.544.555.5arr[0]p=arr;pp->aarr[0].ap->barr[0].bp++;p+1p->aarr[1].ap->barr[1].barr[1]arr[2]p->keycount;/*p指向结构变量的起始地址*/2023/1/11数据结构114◆结构体变量可以作函数的参数进行传递；函数的返回值也可以是一个结构体变量◆指向结构体的指针可作函数的参数进行传递；函数的返回值也可以是一个指向结构体的指针。2023/1/11数据结构115typedef语句用来对基本数据类型或导出数据类型赋以新名。typedef并不定义新的数据类型，只是把一个已经存在的类型赋以新名而已。例如：typedefstruct{floatx;floaty;}POINT;POINTstr1,str2;2023/1/11数据结构116共用体(联合)一、共用体的概念：它的定义形式举例如下：unionexam{inta;floatb;charc;}x;cab10101013

所谓共用体数据类型是指将不同的数据组织为一个整体，它们在内存中占同一段存储单元。2023/1/11数据结构117一、共用体的概念：共用体变量的形式和结构体很相似，但是它们二者概念是不同的※共用体变量中的各个成员共占内存中同一段空间；结构体变量中各个分别占其所需的内存单元。※一个共用体变量的长度是其成员中长度最长的成员的长度；一个结构体变量的长度是其各成员长度之和。2023/1/11数据结构118定义共用体变量的方式与结构体相似。即：(1)union共用体名{成员表列}；

union共用体名(同上)变量表列；(2)union共用体名{成员表列}变量表列；(3)union{成员表列}变量表列；unionexam{inta;floatb;charc;}unionexamx,y;unionexam{inta;floatb;charc;}x,y;union{inta;floatb;charc;}x,y;2023/1/11数据结构119二、共用体变量的引用(1)可以引用一个共用体变量的某个成员项。引用方式与引用结构体变量中的成员项相似。例如：x.a,x.b,x.c(2)可以通过指针变量引用共用体变量的成员。例如：unionexam*p,x;pt=&x;pt->a=3;printf(“%d\t”,pt->a);pt->b=4.5;printf(“%f\t”,pt->b);pt->c=‘A’;printf(“%c\n”,pt->c);2023/1/11数据结构120(1)一个共用体变量不是同时存放多个成员的值，而只能存放其中的一个值，这就是最后赋予它的值。例如：x.a=3;x.b=4.5;x.c=‘A’;(2)共用体变量的地址和它的各成员的地址都是同一地址。例如：&x,&x.a,&x.b,&x.c都是同一地址值。(3)不能对共用体变量名赋值，也不能企图引用变量名来得到成员的值，也不能在定义共用体变量时对它初始化。三、共用体类型数据的特点①union{inti;char