C语言程序设计基础电子教案 第5章 组合数据类型

第5章组合数据类型教案教学任务数组、结构、指针及链表等组合数据类型的含义及功能。理解数组、结构、指针及链表变量在内存中的分配和使用方式。数组的初始化及引用方法。字符数组及字符串的用法及基本操作。结构类型的定义方法。结构变量的定义、初始化及引用方法。指针变量的定义和使用方法。指针与数组、函数的关系。函数、数组、结构体、指针，以及链表的综合应用。授课课时总时长：学时包括：课堂讲授学时；实训学习学时一、教学分析教学重点数组的定义和使用教学难点字符数组、排序算法教学方法讲授法+导例教学二、教学基本内容一、一维数组一维数组用来存储具有相同类型的数据，类似于数学中的向量。（一）一维数组的定义数组与变量一样，需要先定义后引用，定义的作用是要求内存分配出连续的存储单元供数组使用。一维数组定义的一般形式：类型说明符数组名[正整型常量表达式]注意：（1）正整型常量表达式也可以是符号常量和字符常量。（2）数组名后面的常量表达式是用方括号括起来，不能使用圆括号。（3）数组名的命名同变量名的命名规则相同；数组定义中常量表达式的值表示数组元素的个数。一位数组定义示例：inta[5];//定义整型一维数组a，数组元素有5个，即可以存入5个整型数据floatb[N];//定义N个数据元素的浮点型数组，此处要求N是常数intc[‘A’];//定义具有65(’A’的ASCII码值）个数组元素的字符数组（二）一维数组的引用一维数组在定义后可以使用，但是只能引用单个元素，而不能一次引用整个数组。引用数组元素的形式为：数组名[下标]注意：（1）下标是整型表达式，可以是数值常量、符号常量、字符常量、变量、算术表达式、函数返回值。（2）如果下标是实型常量，则强制转化为整型数据。（3）下标的值是数组元素在数组中的序号，但是是从0开始的。对于n个元素的数组，下标值范围是0至n-1。注意数组使用不能越界。数组元素的引用等同于普通变量，例如：a[0]=1;a[i]=a[i]+1;（4）数组元素个数，即数组长度，是不可改变的；引用数组时的数值是下标，其指出元素在数组中的位置。（三）一维数组的初始化给数组赋初值称为数组的初始化。具体实现的方法如下：1.全部元素初始化定义时给所有元素赋初值，例如：inta[5]={1,2,5,7,3};初值依次写在一对花括号中。该例对数组a中的元素分别赋初值，数组中各元素的值为a[0]=1,a[1]=2,a[2]=5,a[3]=7,a[4]=3。数组a初始化后，其存储形式下所示。2.部分元素初始化给数组中部分元素赋初值，其它元素则系统默认值，整型数组元素的默认值为0，字符数组的默认值为结束符’\0’。例如：intb[5]={1,2,5};定义了整型数组b，但只给前三个数组元素赋值，即b[0]=1，b[1]=2，b[2]=3，其余b[3]和b[4]为0。3.不指定长度全部元素初始化对数组全部元素赋初值时，可以不指定数组的长度，系统根据初值的个数来定义该数组的长度。例如：intc[5]={1,2,5,7,3};可以写成intb[]={1,2,5,7,3};注意：初值的个数不允许大于数组的元素个数，否则会报错：errorC2078:toomanyinitializers。例如：intd[2]={1,2,5,7,3};//程序报错二、二维数组具有两个下标的数组元素构成的数组称为二维数组，二维数组形式类似于数学中的矩阵。（一）二维数组的定义二维数组定义的一般形式：类型说明符数组名[正整型常量表达式][正整型常量表达式]例如：inta[3][4];定义整型数组a是3行4列具有12个数组元素的二维整型数组，数组元素分别为a[0][0]、a[0][1]、a[0][2]、a[0][3]、a[1][0]、a[1][1]、a[1][2]、a[1][3]、a[2][0]、a[2][1]、a[2][2]、a[2][3]。可以把二维数组想象成矩阵。a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]二维数组的元素在内存中存储的顺序是“按行优先原则顺序存放”，即一行一行的存放，数组a的存储顺序如下所示。（二）二维数组的引用二维数组引用的一般形式：数组名[下标1][下标2]其中，下标1和下标2对本身值的范围和类型要求与一维数组的下标一致。例如：c[0][0];c[i][j]=c[i][j]+a[i][k]*b[k][j];注意若数组定义为inta[2][3],由于系统默认二维数组的下标值也是从0开始的，因此，在数组引用中不可能出现a[2][3]这个数组元素，也就是下标不能有2和3。（三）二维数组的初始化二维数组的初始化的方法如下：1.按行给二维数组置初值按行给二维数组置初值是把初值用大括号分成若干行，赋给不同的行。例如：inta[2][3]={{1,2,3},{4,5,6}};在赋值后边的一对大括号中，第一对大括号代表第一行的数组元素，第二对大括号代表第二行的数组元素。2.所有元素按顺序赋初值将所有的数组元素按行顺序写在一个大括号内，例如：inta[2][3]={1,2,3,4,5,6};此时与第一种赋初值效果相同。3.对部分数组元素赋初值。和一维数组相同，二维数组也允许给数组赋部分初值，例如：intb[2][3]={{1},{2,3}};数组b中元素值：b[0][0]为1，b[0][1]和b[0][2]为0，b[1][0]为2，b[1][1]为3，b[1][2]为0。4.省略下标如果对全部数组元素置初值，则二维数组的第一个下标可省略，系统会自动补上。但第二个下标不能省略。例如：inta[2][3]={1,2,3,4,5,6};可以写成inta[][3]={1,2,3,4,5,6};在数组中，若每个数组元素存放的都是字符型数据，则称为字符数组。（一）字符数组定义字符数组用关键词char来定义，但和字符定义不同，需要在数组名的后边加上下标，其定义的一般形式：char数组名[正整型常量表达式];例如：charc[10];该语句定义了一个字符数组c，数组c有10个元素，分别为c[0]、c[1]、c[2]、c[3]、c[4]、c[5]、c[6]、c[7]、c[8]、c[9]。数组c中的数组元素存放的内容是字符。在C语言中，字符对应ASCII码，而ASCII码是一个整数，因此字符型和整型在一定的条件下可以互相通用，所以字符数组c也可以定义为：intc[10];当将一个字符常量赋给整型字符数组元素时，是将该字符的ASCII码值赋给了相应的数组元素。（二）字符数组的初始化字符型数组的初始化方法与数值型数组的初始化方法类似。例如：charc[11]={‘H’,’e’,’l’,’l’,’o’,’’,’w’,’o’,‘r’,’l’,‘d’};则给数组元素赋初值。其中c[0]=’H’，c[1]=’e’，c[2]=’l’，c[3]=’l’，c[4]=’o’，c[5]=’’（注意：此处是空格字符，不是空），c[6]=’w’，c[7]=’o’，c[8]=’r’，c[9]=’l’，c[10]=’d’。注意：（1）初值个数不能大于数组的长度。（2）初值个数可以小于数组的长度，赋值从前到后，没有赋到值的元素为空字符’\0’。例如：charc[13]={‘H’,’e’,’l’,’l’,’o’,’’,’w’,’o’,‘r’,’l’,‘d’};则c[11]和c[12]为空字符’\0’。（3）数组元素全部赋值时可以省略数组长度，系统根据初值自动确定长度。例如：charc[]={‘H’,’e’,’l’,’l’,’o’,’’,’w’,’o’,‘r’,’l’,‘d’};系统将自动定义字符数组c的长度为11。（三）字符数组的引用字符数组与数值型数组在引用上完全相同，引用的一般形式：数组名[下标];（四）字符数组与字符串在C语言中，字符串存放在字符数组中，或者说字符串操作其实是对字符数组的操作。在定义数组时，可以用字符串为字符数组赋初值。例如：charc[]={“Helloworld”};或charc[]=”Helloworld”;注意：这时c数组的长度为12，”Helloworld”字符串本身长度为11，而系统在字符串的后边自动添加了空字符’\0’（字符串结束标志）。若采用下面的方法进行初始化：charc1[]={‘H’,’e’,’l’,’l’,’o’,’’,’w’,’o’,‘r’,’l’,‘d’};与charc2[]={“Helloworld”};数组c1和c2的长度相同，前者是11，后者是12.若初值个数小于定义数组的长度，则在后面以空字符’\0’填充。例如：charc3[13]={“Helloworld”}则数组c3的元素c3[12]和c3[13]均为空字符’\0’，但是字符串的长度为12，系统认为该字符串到第一个空字符’\0’为止。即“Helloworld”字符串的实际长度为12，而数组c3的长度为13。（五）字符数组的输入和输出字符数组的输入和输出有以下两种格式：（1）%c格式：输入和输出一个字符。（2）%s格式：输入和输出一个字符串。例如：charc1[]=”Helloworld”;printf(“%s”,c1);程序从数组c1的起始地址开始输出，直至遇到’\0’为止。注意：（1）以%s格式输出字符串时，在printf函数中输出相应写字符数组名，而不是数组元素。（2）在输出字符串时，遇到字符’\0’为就结束输出。’\0’是空字符，不输出任何字符。所以，无论后面还有多少个’\0’，只有第一个起作用。（3）在scanf函数中使用%s时，再输入项中不要地址符’&”，直接写出字符数组名即可，因为数组名表示该数组在内存的起始地址。例如：scanf(“%s”,c1);（4）在定义字符数组时，要考虑实际串长。（5）如果用scanf函数输入多个字符串，则字符串间用空格分隔。例如：charstr1[6],str2[6];scanf(“%s%s”,str1,str2,str3);若输入：Helloworld<回车>则数组str1、str2的存储情况如下所示。（6）如果输入带空格的字符串，通常用初始化的方法或用gets函数，若用函数scanf(“%s”，c1);，则只接收字符串第一个空格前的字符。例如输入Helloworld<回车>则字符串c1的值“Hello”。gets函数接收数据是以回车作为字符串结束标志，而scanf函数则以空格作为字符串结束标志。（六）字符串处理函数C语言函数库中提供了众多字符串处理函数，函数定义在string.h库文件中，用户使用#include”string.h”或#include<string.h>将头文件string.h包含到程序中，而后就可以直接引用字符串函数。本节介绍常用的字符串处理函数，其它函数参见附录内容。1.puts函数puts函数输出一个字符串（字符数组），其调用一般形式：puts(字符数组名)；例如：charc[]=”Helloworld”;puts(c);输出结果：Helloworld2.gets函数gets函数用于输入字符串函数，即从键盘输入一个字符串到字符数组中，并得到该字符数组的起始地址，函数的调用一般形式：gets(字符数组名)；例如：charc[12];gets(c);输入：Helloworld<回车>将Helloworld字符串送入字符数组c中，字符数组c的长度为12，因为包括字符串结束标志空字符。注意：puts函数和gets函数只能对一个字符数组进行操作。3.strcat函数strcat函数用来连接两个字符串，即把两个字符串连接在一起形成一个字符串，其调用一般形式;strcat(字符数组1，字符数组2)该功能是将字符数组2连接到字符数组1的后面，结果存放在字符数组1中，这样字符数组1的串值发生改变。例如：charstr1[12]=”Hello”;charstr2[6]=”world”;printf(“%s”,strcat(str1,str2));输出结果为：Helloworld注意：（1）第一个字符串定义的长度要有预留空间，以备保存第二个字符串。（2）字符串连接时，第一个字符串后面的空字符’\0’会被删除。4.strcpy函数strcpy函数用来赋值字符串，其调用的一般形式：strcpy(字符数组1，字符串2)；该语句功能是将字符串2复制到字符数组1中。例如：charc1[12],c2[12]=”Helloworld”;strcpy(c1,c2);此时c1字符数组中的内容为与数组c2的内容相同，均为字符串“Helloworld”。注意：（1）字符数组1必须写成数组名的形式，字符串2可以是字符数组名，也可以是字符串常量。（2）字符数组1的长度要大于字符串2的实际长度，复制时连同’\0’一同复制过去。（3）不能用赋值语句将一个字符串复制给一个字符数组。例如，c1=c2的写法是错误的。5.strcmp函数strcmp函数用来比较两个字符串的大小，其调用的一般形式：strcmp(字符串1，字符串2);该功能是将字符串1和字符串2从左向右逐个字符（按ASCII码值的大小）比较，直到出现不同字符或遇到’\0’时为止。这样，即可得出函数值。有以下三种情况：如果字符串1==字符串2，则函数值为0.如果字符串1>字符串2，则函数值为一个正整数。如果字符串1<字符串2，则函数值为一个负整数。注意：（1）字符串比较，不能使用“==”直接判断：c1==c2;只能用字符串比较函数，比如：strcmp(str1,str2)==0;（2）字符串大小比较规则和数字型大小比较规则不同，比如数值型2和10比较，2<10；但是作为字符串比较”2”>”10”，因为字符串第一个字符比较时’2’>’1’（字符’2’的ASCII码较大）。6.strlen函数strlen函数用来检测字符串长度，其调用一般形式：strlen(字符数组名)该功能测试字符串长度。该函数的值为字符串实际长度，不包括’\0’在内。例如：charstr[12]={“Helloworld”};printf(“%d”,strlen(str));输出结果为str的实际长度11，而不是12。7.strlwr函数strlwr函数用来将字符串改成小写，其调用一般形式：strlwr(字符串)该功能是将字符串中大写字母转换为小写字母。8.strupy函数strupy函数用来将字符串大写，与strlwr意义相反，用法相同。三、指针变量的定义和引用（一）指针的基本概念计算机内存是以字节为单位的连续存储空间，每个字节都有一个编号，这个编号称为地址。由于内存的存储空间是连续的，因此地址编号也是连续的。任何变量在生存期内都占据一定数量的字节。一个变量所占内存区域一段连续字节的第一个字节的地址，就称为该变量的地址。变量名与内存中的一个地址相对应。程序中通常使用变量名，而不必知道变量在内存中的具体地址。变量的存取操作是通过对该变量所对应地址的存储单元进行存取操作来实现的，这种直接按变量的地址存取变量值的方式称为直接存取方式。一个变量的内存地址称为该变量的指针。如果一个变量用来存放指针（即内存地址），则称该变量是指针类型的变量，简称为指针变量，也称为指针。如果指针变量a的值等于变量b的地址，则称指针变量a指向变量b。假定指针变量a的地址是10000，整型变量b的地址是20020，变量a中存放的是变量b的地址20020，变量b的值是100，这时要访问变量b的地址20020，然后再去访问以20020为首地址的存储单元。这种通过变量a间接得到变量b的地址，然后再存取变量b的值的方式称为间接存取方式，如图8-1所示。图8-1指针变量（二）指针变量的定义方法指针变量定义的一般形式：类型说明符*标识符；功能是定义名为“标识符”的指针变量，该指针变量只可以保存“类型说明符”指定类型的变量地址。注意：（1）指针变量定义中的“*”（星号）不是变量名的一部分，它说明定义的变量是指针变量。例如：int*a,*b;double*c;该语句功能是定义了三个指针变量a、b、c，其中a和b变量中只可以保存int型变量的地址，c变量中只可以保存double型变量的地址。或者说变量a和b是指向int型的指针变量，c是指向double型的指针变量。（2）如果一个表达式的值是指针类型的，即是内存地址，则称这个表达式是指针表达式。指针变量是指针表达式，数组名代表数组的地址，是地址常量（作为形参的数组名除外），数组名也是指针表达式。（3）无论指针变量指向何种类型，指针变量本身也有自己的地址。（三）指针运算1.赋值运算赋值运算的一般形式：指针变量=指针表达式该功能是将指针表达式的值赋给指针变量，即用指针表达式的值取代指针变量原来存储的地址值。注意：进行赋值运算时，赋值运算符右侧的指针表达式指向的数据类型和左侧指针变量所指向的数据类型必须相同。2.取地址运算取地址运算的一般形式：&标识符;功能是执行该表达式后，返回“&”（取地址运算符）后面名为“标识符”的变量（或数组元素）的地址值。注意：（1）“标识符”只能是一个除register类型之外的变量或数组元素。（2）“&标识符”的值就是运算符“&”后面变量或数组元素的地址，因此“&标识符”是一个指针表达式。（3）单目运算符“&”必须放在运算对象的左面。若将指针表达式“&标识符”的值赋给一个指针变量，则标识符的数据类型与被赋值的指针变量所指向的数据类型必须相同。例如：inta,*b;b=&a;scanf(“%d”,&a);（4）&标识符是地址常量，不能赋值，比如&d=10000是错误的。3.取内容计算取内容计算的一般形式：*指针表达式其中，“*”是取内容计算符，“指针表达式”是取内容运算符的运算对象。“*指针表达式”的功能与“*”后面“指针表达式”所指向的变量或数组元素等价。注意：（1）取内容计算符“*”是单目运算符，也称为指针运算符或间接访问运算符。（2）取内容运算符“*”必须出现在运算对象的左边，其运算对象可以是地址或者是存放地址的指针变量。例如：inta=1,b;b=*(&a);表达式&a求出变量a的地址，赋值语句b=*(&a);表示把变量a的地址所保存的内容赋给变量b，实际上该赋值语句与赋值语句b=a;等价。（3）指针运算符“*”和乘法运算符“*”不同，其实二者除了书写相同外没有任何联系。由于两个运算符出现的位置不同，系统会自动识别。（4）*指针表达式根据位置不同，意义也不同。例如：char*p={“Helloworld”};其中“*p”出现在赋值运算符“=”左边，该语句功能是给p所指向的变量赋值。再比如：inta=1,b,*p;p=&a;b=*p;其中*p出现的位置不在赋值运算符“=”的左边，该语句功能是把p指针所指向的变量的值赋给变量b。4.关系运算关系运算的一般形式：指针表达式关系运算符指针表达式结果值：若关系成立（为真），则其值为int型的1，否则其值为int型的0.说明：==（相等）和！=（不相等）是比较两个表达式是否指向同一个内存单元，地址值是否相同；<（小于）、<=（小于或等于）、>=（大于或等于）和>（大于）是比较两个指针所指内存区域的先后顺序。5.强制类型转换运算强制类型转换运算的一般形式：（类型说明符*）指针表达式功能是将指针表达式的值转换成“类型说明符“指定类型的指针。例如，将程序段floatq,*i=&q;int*p;p=(int*)i+1;是将i的值（而不是i+1的值）转换成与p同类型的指针。如果i的值（即q的地址）是无符号十进制整数50000，则i+1的值是在无符号十进制50000的基础上增加一个float类型的长度值，而（int*）i+1的值是在无符号十进制整数50000的基础上增加一个int型的长度值。6.空指针在没有对指针变量赋值以前，指针变量存储的地址值是不确定的，因此，没有对指针变量赋地址值而直接使用指针变量p可能产生不可预料的后果，甚至会导致系统不能正常运行，为了避免发生这种问题，通常给指针变量赋初值0。把值为0的指针变量称为空指针变量。空指针变量表示不指向任何地方，而表示指针变量的一种状态。如果给空指针变量所指内存区域赋值则会出错。p=’\0’;p=0;p=NULL;三个语句等价，其中p为指针变量，’\0’的ASCII码值为0；NULL是在stdio.h文件中定义的常数，其值为0。四、链表数组是一个元素的序列，使用下标访问元素随意而简单。但是数组有两个不足：（1）定义数组需要指定长度，当数组元素个数不能确定时会造成内存空间浪费。（2）数组的插入或删除元素需要移动其它元素。这些都极其不便。链表是一种有先后次序的序列，这点和数组一样，不同的是链表中的元素可以根据需要动态开辟内存单元，并且链表中各元素在内存中的地址可以是不连续的，因此链表可以克服数组的不足。（一）链表的概念在链表中，所有数据元素都分别保存在一个具有相同数据结构的结点中，结点是链表的基本存储单位，一个结点与一个数据元素相对应。每个结点在内存中使用一块连续的存储空间。把线性表的元素存放到一个由这种结点组成的链式存储中，每个结点之间可以占用不连续的内存空间，结点与结点之间通过指针连接在一起，这种存储方式称为链表。链表中的每个结点至少有两部分组成，即数据域和指针域。结点的定义需要采用结构类型，其一般形式为：structnode{intdata;//数据域structnode*link；//指针域};数据域存放线性表的一个元素，指针域存放其后继结点的地址，所有元素通过指针链成一个链式存储的结构，最后一个结点的指针域为空指针。采用这种存储结构，逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。具有这种链式存储结构的线性表也称为单向链表，这里只介绍单向链表。在实际应用中，要建立一个链表通常包括三部分内容：指向链表表头结点的指针，也称为头指针，通过头指针可以很方便的找到链表中的每一个数据元素。表头结点也称为头结点，头结点的数据域可以不存放任何信息，也可以存储线性表的长度等附加信息。表头结点不是链表中必可不少的组成部分，是为了操作方便而设立的。也可以采用不带表头的结点结构形式。带头结点的线性链表的逻辑状态如图1所示。头指针变量h指向链表的头结点。不带头结点的链表头指针直接指向第一个元素的结点，如图2所示。3）数据节点也称为结点，是实际存储数据信息的结点。数据结点的信息可以根据需要设立，也可以是多个不同类型的数据。链表的存储空间可在程序运行期间动态分配，如需要向链表中插入一个结点，只需要调用C语言动态空间分配函数（alloc或malloc函数）动态申请一个存储存放相应信息，并把新申请的结点插入到链表的适当位置上，删除一个结点意味着该结点将被系统回收，C语言中free函数用来动态回收结点。链式存储结构具有如下特点：插入，删除运算灵活方便，不需要移动结点，只需要改变结点中指针域的值即可。可以实现动态分配和扩展空间，当表中数据是动态产生的时候，最好使用链表。查找操作只能从链表的头结点开始顺序查找，不适合有大量频繁查找操作的表。（三）链表的基本操作链表的操作包括：建立链表、遍历链表、向链表中插入或删除结点、求链表长度等，这里仅介绍有关链表最基本的介绍和相关操作。1建立链表建立链表首先要定义一个包含数据域和指针域的结构类型，然后定义一个指向表头结点的指针，最后通过调用malloc函数动态申请结点的方法建立整个链表。链表的遍历所谓遍历就是逐一的访问链表中的每个结点。设线性链表头指针为h，设指针变量p指向不同的结点，沿着链头开始向后查找结点中学号为x的结点。若找到，则返回该结点在链表中的位置，否则返回空地址。由于各结点在内存中是不连续存放的，因此，不可以用p++来寻找下一个结点。图3给出了指针p移动的过程。单链表的查找操作的程序如下：NODE*1bcz(NODE*L,intx){NODE*p;p=L->link;//p先指向第一个结点while(p!=NULL&&