Board logo

标题: C基础教程 第十二章 结构与链表 [打印本页]
作者: 苹果也疯狂    时间: 2011-10-21 12:36     标题: C基础教程 第十二章 结构与链表

为将不同数据类型、但相互关联的一组数据，组合成一个有机整体使用，C语言提供一种称为“结构”的数据结构。

10.1
结构类型与结构变量的定义
10.2
结构变量的引用与初始化
10.3
结构数组

10.4
指向结构类型数据的指针

10.5
链表处理──结构指针的应用

10.6
共用型和枚举型

10.7
定义已有类型的别名

10.1
结构类型与结构变量的定义

C语言中的结构类型，相当于其它高级语言中的“记录”类型。

10.1.1
结构类型定义

struct
结构类型名
/* struct是结构类型关键字*/

{数据类型
数据项1;

数据类型
数据项2;

……
……

数据类型
数据项ｎ;

};
/* 此行分号不能少！*/



[案例10.1] 定义一个反映学生基本情况的结构类型，用以存储学生的相关信息。
/*案例代码文件名：AL10_1.C。*/
/*功能：定义一个反映学生基本情况的结构类型*/

struct
date
/*日期结构类型：由年、月、日三项组成*/


{int year;



int month;



int day;


};

struct
std_info /*学生信息结构类型：由学号、姓名、性别和生日共4项组成*/


{char
no[7];


char
name[9];


char
sex[3];


struct date birthday;


};


struct
score
/*成绩结构类型：由学号和三门成绩共4项组成*/


{char
no[7];


int
score1;


int
score2;


int
score3;


};

（1）“结构类型名”和“数据项”的命名规则，与变量名相同。

（2）数据类型相同的数据项，既可逐个、逐行分别定义，也可合并成一行定义。


例如，本案例代码中的日期结构类型，也可改为如下形式：


struct
date


{int
year, month, day;


};

（3）结构类型中的数据项，既可以是基本数据类型，也允许是另一个已经定义的结构类型。


例如，本案例代码中的结构类型std_info，其数据项“birthday”就是一个已经定义的日期结构类型date。

（4）本书将１个数据项称为结构类型的１个成员（或分量）。

10.1.2
结构变量定义

用户自己定义的结构类型，与系统定义的标准类型（int、char等）一样，可用来定义结构变量的类型。


1.定义结构变量的方法，可概括为两种：

（1）间接定义法──先定义结构类型、再定义结构变量

例如，利用[案例10.1]中定义的学生信息结构类型std_info，定义了一个相应的结构变量student：


struct
std_info
student;

结构变量student：拥有结构类型的全部成员，其中birthday成员是一个日期结构类型，它又由3个成员构成。

注意：使用间接定义法定义结构变量时，必须同时指定结构类型名。

（2）直接定义法──在定义结构类型的同时，定义结构变量

例如，结构变量student的定义可以改为如下形式：

struct
std_info


{……


}student;

同时定义结构类型及其结构变量的一般格式如下：


struct
[结构类型名]


{ ……


} 结构变量表；

2.说明

（1）结构类型与结构变量是两个不同的概念，其区别如同int类型与int型变量的区别一样。

（2）结构类型中的成员名，可以与程序中的变量同名，它们代表不同的对象，互不干扰。

10.2
结构变量的引用与初始化


[案例10.2] 利用[案例10.1]中定义的结构类型struct
std_info，定义一个结构变量student，用于存储和显示一个学生的基本情况。


/*案例代码文件名：AL10_2.C*/
#include"struct.h"
/*定义并初始化一个外部结构变量student */
struct
std_info
student={"000102","张三","男",{1980,9,20}};
main()

{ printf("No: %s\n",student.no);

printf("Name: %s\n",student.name);

printf("Sex: %s\n",student.sex);

printf("Birthday: %d-%d-%d\n",student.birthday.year,


student.birthday.month, student.birthday.day);

}



程序运行结果：

No: 000102

Name: 张三

Sex: 男

Birthday:1980-9-20

1.结构变量的引用规则

对于结构变量，要通过成员运算符“.”，逐个访问其成员，且访问的格式为：

结构变量.成员
/*其中的“.”是成员运算符*/

例如，案例中的student.no，引用结构变量student中的no成员；student.name引用结构变量student中的name成员，等等。

如果某成员本身又是一个结构类型，则只能通过多级的分量运算，对最低一级的成员进行引用。

此时的引用格式扩展为：


结构变量.成员.子成员.….最低1级子成员

例如，引用结构变量student中的birthday成员的格式分别为：

student.birthday.year

student.birthday.month

student.birthday.day

（1）对最低一级成员，可像同类型的普通变量一样，进行相应的各种运算。

（2）既可引用结构变量成员的地址，也可引用结构变量的地址。

例如，&student.name ，&student 。

2.结构变量的初始化

结构变量初始化的格式，与一维数组相似：


结构变量={初值表}

不同的是：如果某成员本身又是结构类型，则该成员的初值为一个初值表。

例如，[案例10.2]中的student={"000102","张三", "男", {1980,9,20}}。

注意：初值的数据类型，应与结构变量中相应成员所要求的一致，否则会出错。

10.3
结构数组

结构数组的每一个元素，都是结构类型数据，均包含结构类型的所有成员。

[案例10.3] 利用[案例10.1]中定义的结构类型struct
std_info，定义一个结构数组student，用于存储和显示三个学生的基本情况。


/*案例代码文件名：AL10_3.C*/
#include"struct.h"
/*定义并初始化一个外部结构数组student[3] */
struct
std_info
student[3]={{“000102”,“张三”,“男”,{1980,9,20}},

{“000105”,“李四”,“男”,{1980,8,15}},

{“000112”,“王五”,“女”,{1980,3,10}}
};

/*主函数main()*/

main()


{ int i;


/*打印表头: "
"表示1个空格字符*/


printf("No.
Name
Sex Birthday\n");



/*输出三个学生的基本情况*/


for(i=0; i<3; i++)


{ printf("%-7s",student.no);


printf("%-9s",student.name);


printf("%-4s",student.sex);


printf("%d-%d-%d\n",student.birthday.year,



student.birthday.month,student.birthday.day);


}


}


[程序演示]

程序运行结果：

No.
Name
Sex
Birthday

000102
张三
男
1980-9-20

000105
李四
男
1980-8-15

000112
王五
女
1980-3-10


与结构变量的定义相似，结构数组的定义也分直接定义和间接定义两种方法，只需说明为数组即可。


与普通数组一样，结构数组也可在定义时进行初始化。初始化的格式为：

结构数组[n]＝{{初值表1}，{初值表2}，...，{初值表n}}

例如，本案例中的结构数组student[3]。


10.4
指向结构类型数据的指针


结构变量在内存中的起始地址称为结构变量的指针。

10.4.1
指向结构变量的指针

[案例10.4] 使用指向结构变量的指针来访问结构变量的各个成员。
/*案例代码文件名：AL10_4.C*/
#include“struct.h”
struct
std_info
student={“000102”,“张三”,“男”,{1980,9,20}};
main()


{struct
std_info
*p_std=&student;


printf("No: %s\n", p_std->no);


printf("Name: %s\n", p_std->name);


printf("Sex: %s\n", p_std->sex);


printf("Birthday: %d-%d-%d\n", p_std->birthday.year,


p_std->birthday.month,p_std->birthday.day);


}
[程序演示]

通过指向结构变量的指针来访问结构变量的成员，与直接使用结构变量的效果一样。一般地说，如果指针变量pointer已指向结构变量var，则以下三种形式等价：

（1）var.成员

（2）pointer->成员

（3）(*pointer).成员
/* “*pointer”外面的括号不能省！*/

注意：在格式（1）中，分量运算符左侧的运算对象，只能是结构变量，；而在格式（2）中，指向运算符左侧的运算对象，只能是指向结构变量（或结构数组）的指针变量，否则都出错。

思考题：如果要求从键盘上输入结构变量student的各成员数据，如何修改程序？

10.4.2
指向结构数组的指针

[案例10.5] 使用指向结构数组的指针来访问结构数组。

/*案例代码文件名：AL10_5.C*/

#include"struct.h"

/*定义并初始化一个外部结构数组student */

struct
std_info
student[3]={{"000102","张三","男",{1980,5,20}},


{"000105","李四","男",{1980,8,15}},


{“000112”,“王五”,“女”,{1980,3,10}} };

main()


{struct
std_info
*p_std=student;



int i=0;


/*打印表头*/


printf("No.
Name
Sex Birthday\n");

/*输出结构数组内容*/

for( ;
i<3;
i++, p_std++)


{printf("%-7s%-9s%-4s",
p_std->no,
p_std->name,
p_std->sex);


printf("%4d-%2d-%2d\n", p_std->birthday.year,


p_std->birthday.month,
p_std->birthday.day);


}

}

[程序演示]

如果指针变量p已指向某结构数组，则p+1指向结构数组的下一个元素，而不是当前元素的下一个成员。

另外，如果指针变量p已经指向一个结构变量（或结构数组），就不能再使之指向结构变量（或结构数组元素）的某一成员。

10.4.3
指向结构数据的指针作函数参数

[案例10.6] 用函数调用方式，改写[案例10.5]：编写一个专门的显示函数display()，通过主函数调用来实现显示。

/*案例代码文件名：AL10_6.C*/

#include"struct.h"

/*定义并初始化一个外部结构数组student */

struct
std_info
student[3]={{"000102","张三","男",{1980,5,20}},


{"000105","李四","男",{1980,8,15}},


{“000112”,“王五”,“女”,{1980,3,10}} };

/*主函数main()*/

main()


{void display();
/*函数说明*/


int i=0;


/*打印表头*/


printf("No.
Name
Sex Birthday\n");


/*打印内容*/


for( ;
i<3;
i++)


{ display( student + i );


printf("\n");


}


}

void
display(struct
std_info
*p_std)

{
printf("%-7s%-9s%-4s",
p_std->no,


p_std->name,
p_std->sex);


printf("%4d-%2d-%2d\n",
p_std->birthday.year,



p_std->birthday.month,
p_std->birthday.day);

}


[程序演示]

10.5
链表处理──结构指针的应用

10.5.1
概述

1．链表结构

链表作为一种常用的、能够实现动态存储分配的数据结构，在《数据结构》课程中有详细介绍。为方便没有学过数据结构的读者，本书从应用角度，对链表作一简单介绍。图10-1所示为单链表。

（1）头指针变量head──指向链表的首结点。

（2）每个结点由2个域组成：

1）数据域──存储结点本身的信息。

2）指针域──指向后继结点的指针。

（3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志。

2．对链表的基本操作

对链表的基本操作有：创建、检索（查找）、插入、删除和修改等。

（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。

（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。

（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k’，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：

插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k’成为ki-1的后继、ki的前驱，如图10-2所示。

（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：

删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继，如图10-3所示。

3．Ｃ语言对链表结点的结构描述

在Ｃ语言中，用结构类型来描述结点结构。例如：

struct
grade


{char
no[7];
/*学号*/


int
score;
/*成绩*/


struct
grade
*next;
/*指针域*/


};

10.5.2
创建一个新链表

[案例10.7] 编写一个create()函数，按照规定的结点结构，创建一个单链表（链表中的结点个数不限）。

基本思路：

首先向系统申请一个结点的空间，然后输入结点数据域的（2个）数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。对于链表的第一个结点，还要设置头指针变量。

另外，案例代码中的3个指针变量head、new和tail的说明如下：

（1）head──头指针变量，指向链表的第一个结点，用作函数返回值。

（2）new──指向新申请的结点。

（3）tail──指向链表的尾结点，用tail->next=new，实现将新申请的结点，插入到链表尾，使之成为新的尾结点。

/*案例代码文件名：AL10_7.C*/

#define
NULL
0

#define
LEN
sizeof(struct grade)
/*定义结点长度*/

/*定义结点结构*/

struct
grade


{char
no[7];
/*学号*/


int
score;
/*成绩*/


struct
grade
*next;
/*指针域*/


};

/*create()函数: 创建一个具有头结点的单链表*/

/*形参：无*/

/*返回值：返回单链表的头指针*/

struct grade *create( void )


{struct grade *head=NULL, *new, *tail;


int count=0;
/*链表中的结点个数(初值为0)*/


for(
;
;
)
/*缺省3个表达式的for语句*/


{ new=(struct grade*)malloc(LEN); /*申请一个新结点的空间*/

/*1、输入结点数据域的各数据项*/

printf("Input the number of studentNo.%d(6 bytes): ", count+1);

scanf("%6s", new->no);

if(strcmp(new->no,"000000")==0)
/*如果学号为6个0，则退出*/


{ free(new);
/*释放最后申请的结点空间*/


break;
/*结束for语句*/


}

printf("Input the score of the studentNo.%d: ", count+1);

scanf("%d", &new->score);

count++;
/*结点个数加1*/

/*2、置新结点的指针域为空*/

new->next=NULL;

/*3、将新结点插入到链表尾，并设置新的尾指针*/


if(count==1)
head=new;
/*是第一个结点, 置头指针*/


else
tail->next=new;
/*非首结点, 将新结点插入到链表尾*/


tail=new;
/*设置新的尾结点*/


}


return(head);

}
[程序演示]

思考题：在设计存储学号数据的字符数组时，其元素个数应为学号长度+1。为什么？

10.5.3
对链表的插入操作

[案例10.8] 编写一个insert()函数，完成在单链表的第i个结点后插入1个新结点的操作。当i=0时，表示新结点插入到第一个结点之前，成为链表新的首结点。

基本思路：

通过单链表的头指针，首先找到链表的第一个结点；然后顺着结点的指针域找到第i个结点，最后将新结点插入到第i个结点之后。

/*案例代码文件名：AL10_8.C*/

/*函数功能：在单链表的第i个结点后插入1个新结点*/

/*函数参数：head为单链表的头指针，new指向要插入的新结点，i为结点索引号*/

/*函数返回值：单链表的头指针*/

struct grade *insert(struct grade *head,struct grade *new, int i)


{struct grade *pointer;


/*将新结点插入到链表中*/

if(head==NULL) head=new,new->next=NULL;
/*将新结点插入



到1个空链表中*/

else
/*非空链表*/


if(i==0) new->next=head,
head=new;
/*使新结点成为链表


新的首结点*/


else
/*其他位置*/


{
pointer=head;


/*查找单链表的第i个结点(pointer指向它)*/


for(;
pointer!=NULL && i>1;
pointer=pointer->next,
i--)
;


if(pointer==NULL)
/*越界错*/


printf("Out of therange, can’t insert new node!\n");


else
/*一般情况：pointer指向第i个结点 */


new->next=pointer->next, pointer->next=new;


}


return(head);


}


10.6
共用型和枚举型简介

10.6.1
共用型

1．概念

使几个不同的变量占用同一段内存空间的结构称为共用型。

2．共用类型的定义──与结构类型的定义类似

union
共用类型名

{成员列表;};

3．共用变量的定义──与结构变量的定义类似

（1）间接定义──先定义类型、再定义变量

例如，定义data共用类型变量un1,un2,un3的语句如下：
union
data
un1,un2,un3；

（2）直接定义──定义类型的同时定义变量

例如，union
[data]


{ int i;


char ch;


float f;


}
un1, un2, un3;

共用变量占用的内存空间，等于最长成员的长度，而不是各成员长度之和。

例如，共用变量un1、un2和un3，在16位操作系统中，占用的内存空间均为４字节（不是2+1+4=7字节）。

４．共用变量的引用──与结构变量一样，也只能逐个引用共用变量的成员

例如，访问共用变量un1各成员的格式为：un1.i、un1.ch、un1.f。

5．特点

（1）系统采用覆盖技术，实现共用变量各成员的内存共享，所以在某一时刻，存放的和起作用的是最后一次存入的成员值。

例如，执行un1.i=1,un1.ch='c', un1.f=3.14后，un1.f才是有效的成员。

（2）由于所有成员共享同一内存空间，故共用变量与其各成员的地址相同。

例如，＆un1＝＆un1.i＝＆un1.ch＝＆un1.f。

（3）不能对共用变量进行初始化（注意：结构变量可以）；也不能将共用变量作为函数参数，以及使函数返回一个共用数据，但可以使用指向共用变量的指针。

（4）共用类型可以出现在结构类型定义中，反之亦然。

10.6.2
枚举型

1．枚举类型的定义


enum
枚举类型名
{取值表}；

例如，enum
weekdays {Sun,Mon,Tue,Wed,Thu,Fri,Sat}；

２．枚举变量的定义──与结构变量类似

（1）间接定义

例如，enum
weekdays
workday;

（2）直接定义

例如，enum
[weekdays]


{Sun,Mon,Tue,Wed,Thu,Fri,Sat }workday;

３．说明

（1）枚举型仅适应于取值有限的数据。

例如，根据现行的历法规定，１周７天，１年１２个月。

（2）取值表中的值称为枚举元素，其含义由程序解释。

例如，不是因为写成“Sun”就自动代表“星期天”。事实上，枚举元素用什么表示都可以。

（3）枚举元素作为常量是有值的──定义时的顺序号（从０开始），所以枚举元素可以进行比较，比较规则是：序号大者为大！

例如，上例中的Sun=0、Mon=1、……、Sat=6，所以Mon>Sun、Sat最大。

（4）枚举元素的值也是可以人为改变的：在定义时由程序指定。

例如，如果enum weekdays {Sun=７, Mon＝１ ,Tue, Wed, Thu, Fri,Sat}；则Sun=７，Mon=１，从Tue=2开始，依次增１。

10.7
定义已有类型的别名

除可直接使用Ｃ提供的标准类型和自定义的类型（结构、共用、枚举）外，也可使用typedef定义已有类型的别名。该别名与标准类型名一样，可用来定义相应的变量。

定义已有类型别名的方法如下：

（1）按定义变量的方法，写出定义体；

（2）将变量名换成别名；

（3）在定义体最前面加上typedef。



[案例10.9]
给实型float定义1个别名REAL。

（1）按定义实型变量的方法，写出定义体：float
f;

（2）将变量名换成别名： float
REAL;

（3）在定义体最前面加上typedef：typedef
float REAL;

[案例10.10]
给如下所示的结构类型struct date定义1个别名DATE。

struct date


{ int year,
month, day;


};

（1）按定义结构变量的方法，写出定义体：struct date {……} d;

（2）将变量名换成别名：
struct date {……} DATE;

（3）在定义体最前面加上typedef：
typedef struct date {……} DATE;

说明：

（1）用typedef只是给已有类型增加１个别名，并不能创造１个新的类型。就如同人一样，除学名外，可以再取一个小名（或雅号），但并不能创造出另一个人来。

（2）typedef与#define有相似之处，但二者是不同的：前者是由编译器在编译时处理的；后者是由编译预处理器在编译预处理时处理的，而且只能作简单的字符串替换。



欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0