清华数据结构dsch1

2023/12/27数据结构1数据结构

——用C语言描述主讲楚蓓蓓辅导徐冰胡兆阳单位 信院一系二教Tel:313613052231109Email2023/12/27数据结构2教材：数据结构－－用C语言描述 －－高等教育出版社课程安排：

总学时80（20上机）学时

全书共分10章，教学内容为前9章

期中考试前：讲述前6章

期中考试后：讲述7、8、9章预备知识：熟练掌握C语言，尤其是指针和结构2023/12/27数据结构3上机时间：第4、6、8、10、12、13、14、16、18、20周

的周二辅导时间：三大队2队周二3、4节，

三大队3队、学员旅周三下午1、2节2023/12/27数据结构4参考书目：1

《数据结构》（c语言版）严蔚敏吴伟民---清华大学出版社

3

《数据结构算法设计指导》胡学钢---清华大学出版社 2

《DataStructuresandProgramDesignInC》

RobertKruse --清华大学出版社64《数据结构（C语言篇）习题与解析

---清华大学出版社5数据结构习题解析与上机实验指导

---中国水利水电出版社2023/12/27数据结构5第一章概论

什么是数据结构

为什么要学习数据结构

如何评价一个算法2023/12/27数据结构6第一章概论1.1数据结构的概念一、术语1.数据(Data):

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

数据的基本单位,即数据集合中的一个个体。也称元素、

结点、顶点、记录数据项是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素由数据项(dataitem)组成2023/12/27数据结构7第一章概论1.1数据结构的概念4、数据结构(DataStructure)

按某种逻辑关系组织起来的一批数据,应用计算机语言按一定的存储方式将其存储在计算机中,在这些数据上定义了若干基本运算,并且讨论这些基本运算基于存储方式上的实现。3、数据类型(DataType):

是具有相同性质的计算机数据的集合及在这个集合上的一组操作。原子数据类型(atomicdatatype)结构数据类型(aggregatedatatype)2023/12/27数据结构8第一章概论1.1数据结构的概念数据结构包括四方面的内容：

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/12/27数据结构9

数据的逻辑结构

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

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

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

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

数据的存储结构

指的是数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言。第一章概论1.1数据结构的概念2023/12/27数据结构12数据的存储结构可采用四种基本存储方法：（1）顺序存储方法

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

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

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

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

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/12/27数据结构15

逻辑结构上的基本运算

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

数据的逻辑结构

数据的存储结构

逻辑结构上的基本运算

存储结构上基本运算的实现2023/12/27数据结构17

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

运算的实现实际上指的是采用怎样的步骤或方法去实现定义在逻辑结构上的运算的功能。第一章概论1.1数据结构的概念

逻辑结构上定义的基本运算只有在逻辑结构的存储实现之后才能够在该存储结构上实现。2023/12/27数据结构18第一章概论1.1数据结构的概念例:计算机系学员的选课、业余爱好、担当职务情况统计如下：学号选修课程爱好职务1B.F无班长2A.C体育3A.D.F体育体委4D.E文艺5C.E文艺6D.F体育7B.E体育8A.E体育9B.F文艺文委10B.D文艺2023/12/27数据结构19第一章概论1.1数据结构的概念学号选修课程爱好职务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/12/27数据结构20第一章概论1.1数据结构的概念2、存储结构线性表1、逻辑结构a1+9顺序表a1a1+1a1+212310

••••••a10链表a112310

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

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

…1

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

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

a2a3a101…2023/12/27数据结构24第一章概论1.1数据结构的概念说明：同一批数据可以抽象出不同的逻辑结构同一逻辑结构采用不同的存储方法，可以得到不同的存储结构，并冠以不同的名称；存储方法可以单独使用，也可以结合起来使用；数据结构的逻辑结构、存储结构、运算三个方面是一个整体；运算是数据结构的重要方面2023/12/27数据结构251.2为什么要学习数据结构第一章概论一、数据结构的形成与发展背景二、数据结构在计算机科学中的地位算法＋数据结构＝程序

程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构科学计算->非数值计算数值->结构数据2023/12/27数据结构26第一章概论1.2为什么要学习数据结构例一：电话号码查询问题电话号码查询问题的索引存储2023/12/27数据结构27安排竞赛项目的数据结构模型ABCDEF第一章概论1.2为什么要学习数据结构参赛选手比赛项目表例二ACBDFE2023/12/27数据结构28

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

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

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

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

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

（1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（5）健壮性1.4算法分析2023/12/27数据结构32第一章概论二、算法运行时间要素（1）对源程序进行编译所需的时间（2）程序运行时所需数据输入的时间（3）机器执行每条指令所需时间（4）程序中的每条指令重复执行的次数。

假设每条指令执行所需时间为单位时间。算法的时间耗费T(n)可以用每条指令重复执行的次数（也称频度FrequencyCount）之和进行度量，1.4算法分析2023/12/27数据结构33例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/12/27数据结构34第一章概论为方阵的阶n的函数。当n趋于无穷大时，T(n)/n3

2即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/12/27数据结构35第一章概论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/12/27数据结构36常见的时间复杂度有：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……、k次方阶O(nk)、指数阶O(2n)。三、（渐进）时间复杂度(O(f(n))2023/12/27数据结构37第一章概论1.4算法分析例一：交换a和b的内容temp=a;a=b; b=temp;T(n)=O(1)2023/12/27数据结构38例二：变量记数之一(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)2023/12/27数据结构39例二：变量记数之二(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/12/27数据结构40第一章概论1.4算法分析四、最坏时间复杂度和平均时间复杂度很多算法的时间复杂度不仅仅是问题规模的函数，还与它所处理的数据集的状态有关，在这种情况下，通常是根据数据集中可能出现的最坏情况，估计出算法的最坏时间复杂度。有时对数据集的分布作出某种假设（如等概率），讨论算法的平均时间复杂度。2023/12/27数据结构41例：在数组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/12/27数据结构42五、空间复杂度(SpaceComplexity)S(n)：

算法所耗费的存储空间，仍是问题规模n的函数。记作：S(n)=O(f(n))2023/12/27数据结构43第一章概论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。2023/12/27数据结构44

C语言语法结构简介

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

语句部分

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

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

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

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

6.函数通常结束于return语句。2023/12/27数据结构46二、条件语句的两种格式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/12/27数据结构471、while循环语句2）执行过程:①计算E的值②若E非0,则执行S,然后转①若E为0,则退出循环,执行该循环后的语句1）格式

while(表达式E){

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

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

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

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

循环体语句序列S}计算E2S假(0)真(非0)计算E1计算E3三、循环语句的三种格式注意：上述的三种循环体语句中，均可使用break语句退出循环体。2023/12/27数据结构50四、情况语句(开关语句)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/12/27数据结构51五、赋值语句1.

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

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

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

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

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

1）putchar(c);

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

2）getchar();

功能：从终端(或系统隐含的输入设备)输入一个字符,并把得到的字符作为函数的返回值.2023/12/27数据结构532、其它数据：用函数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/12/27数据结构55

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

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

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

例如：1.2，3，‘a’

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

符号常量：是在一个程序(或程序的一部分)中指定一符号或标识符代表一个常量。一、(直接)常量和符号常量：2023/12/27数据结构58例：#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/12/27数据结构59存储单元所存储的数据称为变量的值，这个存储空间的首地址就称为该变量的地址。

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

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

①if()~else~条件语句②for()~③while()~④do~while()⑤continue结束本次循环⑥break终止循环或switch⑦switch多路分支语句⑧goto转移语句⑨return返回语句循环语句上面9种语句中的括号()表示其中是一个条件，~表示内嵌的语句．2023/12/27数据结构61如：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/12/27数据结构62逻辑运算符及优先级：

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

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

数组必须先定义,后使用,而且只能逐个引用数组元素,而不能一次引用整个数组。数组的表示形式:

数组名[下标]下标可以是整型常量或整型表达式inta[N];下标变化范围0到N-1for(i=0;i<N;i++){scanf(“%d”,&a[i]);printf(“%d”,a[i]);}2023/12/27数据结构655函数

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

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

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

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

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

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

运行情况如下：******************Ｈowdoyoudo!******************2023/12/27数据结构67指针

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

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

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

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

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

&233,&(i+233)&：(取地址运算符)取当前变量的地址运算对象不能是常量表达式或寄存器变量

请区别：指针：就是地址变量的指针：就是变量的地址指针变量：存放地址的变量2023/12/27数据结构73指针变量定义的一般形式：类型标识符*标识符；注1.标识符前面的“*”标示该变量为指针变量。2.一个指针变量只能指向同一类型的变量。请区别：指针：就是地址变量的指针：就是变量的地址指针变量：存放地址的变量2023/12/27数据结构74int*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/12/27数据结构75C语言中有关指针的运算符◆&运算符:取地址运算符◆*运算符:指针运算符或指明运算符，*p代表p所指变量注意：此处的*p与定义指针变量时用的*p的含义是不同的。定义int*p;中的*不是运算符,它只是表示其后的变量是一指针变量程序中的*p，其中的*是一个指针运算符，*p表示p指向的变量如：printf(“%d”,*p);printf(“%d”,a);结果都为3P3i&iP3i2023/12/27数据结构76main(){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/12/27数据结构77三、指针变量的运算●当指针指向一个具有基本类型或组合类型中具有基本类型的成分分量时,则它可以象基本变量一样使用。inti,*pi;pi=&i;i=0;&iPi0i*pi=0;i+=1;*pii++;*pi+=1;(*pi)++;2023/12/27数据结构78C语言的函数的参数传递是以“传值”方式进行变量参数的信息传递，被调函数不能直接改变主调函数中参数的值。当引入指针的概念后，我们可以在主调函数中将要改变内容的变量地址作为参数传递给被调函数，而被调函数执行时，就按这个地址去访问变量参数的值，相应的参数要被说明成指针类型。2023/12/27数据结构79swap(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/12/27数据结构80

其中：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/12/27数据结构81◆指针与数组的一致性: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/12/27数据结构82注意：不能用以下方法输出a数组的5个元素，因为a是起始地址，是个常数。for(i=0;i<5;i++)printf(“%d”,*a++);p=a;for(i=0;i<5;i++)printf(“%d”,*p++);而应写成：2023/12/27数据结构83结构

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

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

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

2023/12/27数据结构84

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

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

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

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

或struct{结构成员表};

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

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

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

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

如：&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/12/27数据结构914.对结构变量可以像普通变量一样进行各种运算(根据其类型决定可以进行的运算)如：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/12/27数据结构922.如果成员本身又属于一个结构体类型，则要用若干个成员运算符，一级一级地找到最低的一级的成员。只能对最低级的成员进行赋值或存取以及运算。如：employ.birthday.daystructdate{intmonth;intday;intyear;};structperson{charname[20];structdatebirthday;charsex;longnum;charnation;}employ;2023/12/27数据结构93

当数组中的每个元素都是同一结构类型变量时，称该数组为结构体数组。这种构造类型在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/12/27数据结构94(2)structstudentstudent1[1000];student1是有1000个元素的数组，其中每个元素都是具有student结构类型的变量，每个student1[i]反映了某个学生的个人资料。结构体数组的定义(1)和定义结构体变量的方法相仿，只需说明其为数组即可。如：structstudentstu[3];(2)也可以直接定义一个结构数组。如：structstudent{intn