c语言教程-第17章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！


示意图。

　　在图7。3中，第0个结点称为头结点，　它存放有第一个结点的首地址，它没有数据，只是一个指针变量。　以下的每个结点都分为两个域，一个是数据域，存放各种实际的数据，如学号num，姓名name，性别sex和成绩score等。另一个域为指针域，　存放下一结点的首地址。链表中的每一个结点都是同一种结构类型。例如，　一个存放学生学号和成绩的结点应为以下结构：
struct　stu
｛　int　num；
int　score；
struct　stu　*next；
｝
　　前两个成员项组成数据域，后一个成员项next构成指针域，　它是一个指向stu类型结构的指针变量。链表的基本操作对链表的主要操作有以下几种：　
1。建立链表；
2。结构的查找与输出；
3。插入一个结点；
4。删除一个结点；
下面通过例题来说明这些操作。
＇例7。10＇建立一个三个结点的链表，存放学生数据。　为简单起见，　我们假定学生数据结构中只有学号和年龄两项。
可编写一个建立链表的函数creat。程序如下：
#define　NULL　0
#define　TYPE　struct　stu
#define　LEN　sizeof　（struct　stu）
struct　stu
｛
int　num；
int　age；
struct　stu　*next；
｝；
TYPE　*creat（int　n）
｛
struct　stu　*head；*pf；*pb；
int　i；
for（i=0；inum；&pb…》age）；
if（i0）
pf=head=pb；
else　pf…》next=pb；
pb…》next=NULL；
pf=pb；
｝
return（head）；
｝
　　在函数外首先用宏定义对三个符号常量作了定义。这里用TYPE表示struct　stu，用LEN表示sizeof（struct　stu）主要的目的是为了在以下程序内减少书写并使阅读更加方便。结构stu定义为外部类型，程序中的各个函数均可使用该定义。

　　creat函数用于建立一个有n个结点的链表，它是一个指针函数，它返回的指针指向stu结构。在creat函数内定义了三个stu结构的指针变量。head为头指针，pf　为指向两相邻结点的前一结点的指针变量。pb为后一结点的指针变量。在for语句内，用malloc函数建立长度与stu长度相等的空间作为一结点，首地址赋予pb。然后输入结点数据。如果当前结点为第一结点（i0），则把pb值　（该结点指针）赋予head和pf。如非第一结点，则把pb值赋予pf　所指结点的指针域成员next。而pb所指结点为当前的最后结点，其指针域赋NULL。　再把pb值赋予pf以作下一次循环准备。
　　creat函数的形参n，表示所建链表的结点数，作为for语句的循环次数。图7。4表示了creat函数的执行过程。

＇例7。11＇写一个函数，在链表中按学号查找该结点。
TYPE　*　search　（TYPE　*head；int　n）
｛
TYPE　*p；
int　i；
p=head；
while　（p…》num！=n　&&　p…》next！=NULL）
p=p…》next；　/*　不是要找的结点后移一步*/
if　（p…》numn）　return　（p）；
if　（p…》num！=n&&　p…》nextNULL）
printf　（〃Node　％d　has　not　been　found！n〃；n
｝
　　本函数中使用的符号常量TYPE与例7。10的宏定义相同，等于struct　stu。函数有两个形参，head是指向链表的指针变量，n为要查找的学号。进入while语句，逐个检查结点的num成员是否等于n，如果不等于n且指针域不等于NULL（不是最后结点）则后移一个结点，继续循环。如找到该结点则返回结点指针。　如循环结束仍未找到该结点则输出“未找到”的提示信息。

＇例7。12＇写一个函数，删除链表中的指定结点。删除一个结点有两种情况：
1。　被删除结点是第一个结点。这种情况只需使head指向第二个结点即可。即head=pb…》next。其过程如图7。5所示。
2。　被删结点不是第一个结点，这种情况使被删结点的前一结点指向被删结点的后一结点即可。即pf…》next=pb…》next。其过程如图7。6所示。
函数编程如下：
TYPE　*　delete（TYPE　*　head；int　num）
｛
TYPE　*pf；*pb；
if（headNULL）　/*如为空表，　输出提示信息*/
｛　printf（〃nempty　list！n〃）；
goto　end；｝
pb=head；
while　（pb…》num！=num　&&　pb…》next！=NULL）
/*当不是要删除的结点，而且也不是最后一个结点时，继续循环*/
｛pf=pb；pb=pb…》next；｝/*pf指向当前结点，pb指向下一结点*/
if（pb…》numnum）
｛if（pbhead）　head=pb…》next；
/*如找到被删结点，且为第一结点，则使head指向第二个结点，
否则使pf所指结点的指针指向下一结点*/
else　pf…》next=pb…》next；
free（pb）；
printf（〃The　node　is　deletedn〃）；｝
else
printf（〃The　node　not　been　foud！n〃）；
end：
return　head；
｝　
　　函数有两个形参，head为指向链表第一结点的指针变量，num删结点的学号。　首先判断链表是否为空，为空则不可能有被删结点。若不为空，则使pb指针指向链表的第一个结点。进入while语句后逐个查找被删结点。找到被删结点之后再看是否为第一结点，若是则使head指向第二结点（即把第一结点从链中删去），否则使被删结点的前一结点（pf所指）指向被删结点的后一结点（被删结点的指针域所指）。如若循环结束未找到要删的结点，　则输出“末找到”的提示信息。最后返回head值。

＇例7。13＇写一个函数，在链表中指定位置插入一个结点。在一个链表的指定位置插入结点，　要求链表本身必须是已按某种规律排好序的。例如，在学生数据链表中，　要求学号顺序插入一个结点。设被插结点的指针为pi。　可在三种不同情况下插入。
1。　原表是空表，只需使head指向被插结点即可。见图7。7（a）
2。　被插结点值最小，应插入第一结点之前。这种情况下使head指向被插结点，被插结点的指针域指向原来的第一结点则可。即：pi…》next=pb；
head=pi；　见图7。7（b）
3。　在其它位置插入，见图7。7（c）。这种情况下，使插入位置的前一结点的指针域指向被插结点，使被插结点的指针域指向插入位置的后一结点。即为：pi…》next=pb；pf…》next=pi；
4。　在表末插入，见图7。7（d）。这种情况下使原表末结点指针域指向被插结点，被插结点指针域置为NULL。即：
pb…》next=pi；
pi…》next=NULL；　TYPE　*　insert（TYPE　*　head；TYPE　*pi）
｛
TYPE　*pf；*pb；
pb=head；
if（headNULL）　/*空表插入*/
（head=pi；
pi…》next=NULL；｝
else
｛
while（（pi…》num》pb…》num）&&（pb…》next！=NULL））
｛pf=pb；
pb=pb…》next；　｝/*找插入位置*/
if（pi…》numnum）
｛if（headpb）head=pi；/*在第一结点之前插入*/
else　pf…》next=pi；/*在其它位置插入*/
pi…》next=pb；　｝
else
｛pb…》next=pi；
pi…》next=NULL；｝　/*在表末插入*/
｝
return　head；｝
　　本函数有两个形参均为指针变量，head指向链表，pi　指向被插结点。函数中首先判断链表是否为空，为空则使head指向被插结点。表若不空，则用while语句循环查找插入位置。找到之后再判断是否在第一结点之前插入，若是则使head　指向被插结点被插结点指针域指向原第一结点，否则在其它位置插入，　若插入的结点大于表中所有结点，则在表末插入。本函数返回一个指针，　是链表的头指针。　当插入的位置在第一个结点之前时，　插入的新结点成为链表的第一个结点，因此head的值也有了改变，　故需要把这个指针返回主调函数。
＇例7。14＇将以上建立链表，删除结点，插入结点的函数组织在一起，再建一个输出全部结点的函数，然后用main函数调用它们。
#define　NULL　0
#define　TYPE　struct　stu
#define　LEN　sizeof（struct　stu）
struct　stu
｛
int　num；
int　age；
struct　stu　*next；
｝；
TYPE　*　creat（int　n）
｛
struct　stu　*head；*pf；*pb；
int　i；
for（i=0；inum；&pb…》age）；
if（i0）
pf=head=pb；
else　pf…》next=pb；
pb…》next=NULL；
pf=pb；
｝
return（head）；
｝
TYPE　*　delete（TYPE　*　head；int　num）
｛
TYPE　*pf；*pb；
if（headNULL）
｛　printf（〃nempty　list！n〃）；
goto　end；｝
pb=head；
while　（pb…》num！=num　&&　pb…》next！=NULL）
｛pf=pb；pb=pb…》next；｝
if（pb…》numnum）
｛　if（pbhead）　head=pb…》next；
else　pf…》next=pb…》next；
printf（〃The　node　is　deletedn〃）；　｝
else
free（pb）；
printf（〃The　node　not　been　found！n〃）；
end：
return　head；
｝
TYPE　*　insert（TYPE　*　head；TYPE　*　pi）
｛
TYPE　*pb　；*pf；
pb=head；
if（headNULL）
｛　head=pi；
pi…》next=NULL；　｝
else
｛
while（（pi…》num》pb…》num）&&（pb…》next！=NULL））
｛　pf=pb；
pb=pb…》next；　｝
if（pi…》numnum）
｛　if（headpb）　head=pi；
else　pf…》next=pi；
pi…》next=pb；　｝
else
｛　pb…》next=pi；
pi…》next=NULL；　｝
｝
return　head；
｝
void　print（TYPE　*　head）
｛
printf（〃NumberttAgen〃）；
while（head！=NULL）
｛
printf（〃％dtt％dn〃；head…》num；head…》age）；
head=head…》next；
｝
｝
main（）
｛
TYPE　*　head；*pnum；
int　n；num；
printf（〃input　number　of　node：　〃）；
scanf（〃％d〃；&n）；
head=creat（n）；
print（head）；
printf（〃Input　the　deleted　number：　〃）；
scanf（〃％d〃；&num）；
head=delete（head；num）；
print（head）；
printf（〃Input　the　inserted　number　and　age：　〃）；
pnum=（TYPE　*）malloc（LEN）；
scanf（〃％d％d〃；&pnum…》num；&pnum…》age）；
head=insert（head；pnum）；
print（head）；
｝
　　本例中，print函数用于输出链表中各个结点数据域值。函数的形参head的初值指向链表第一个结点。在while语句中，输出结点值后，head值被改变，指向下一结点。若保留头指针head，　则应另设一个指针变量，把head值赋予它，再用它来替代head。在main函数中，n为建立结点的数目，　num为待删结点的数据域值；head为指向链表的头指针，pnum为指向待插结点的指针。　main函数中各行的意义是：
第六行输入所建链表的结点数；
第七行调creat函数建立链表并把头指针返回给head；
第八行调print函数输出链表；
第十行输入待删结点的学号；
第十一行调delete函数删除一个结点；
第十二行调print函数输出链表；
第十四行调malloc函数分配一个结点的内存空间，　并把其地址赋予pnum；
第十五行输入待插入结点的数据域值；
第十六行调insert函数插入pnum所指的结点；
第十七行再次调print函数输出链表。

　　从运行结果看，首先建立起3个结点的链表，并输出其值；再删103号结点，只剩下105，108号结点；又输入106号结点数据，　插入后链表中的结点为105，106，108。联合“联合”也是一种构造类型的数据结构。　在一个“联合”内可以定义多种不同的数据类型，　一个被说明为该“联合”类型的变量中，允许装入该“联合”所定义的任何一种数据。　这在前面的各种数据类型中都是办不到的。例如，　定义为整型的变量只能装入整型数据，定义为实型的变量只能赋予实型数据。

　　在实际问题中有很多这样的例子。　例如在学校的教师和学生中填写以下表格：　姓　名　年　龄　职　业　单位　“职业”一项可分为“教师”和“学生”两类。　对“单位”一项学生应填入班级编号，教师应填入某系某教研室。　班级可用整型量表示，教研室只能用字符类型。　要求把这两种类型不同的数据都填入“单位”这个变量中，　就必须把“单位”定义为包含整型和字符型数组这两种类型的“联合”。　

　　“联合”与“结构”有一些相似之处。但两者有本质上的不同。在结构中各成员有各自的内存空间，　一个结构变量的总长度是各成员长度之和。而在“联合”中，各成员共享一段内存空间，　一个联合变量的长度等于各成员中最长的长度。应该说明的是，　这里所谓的共享不是指把多个成员同时装入一个联合变量内，　而是指该联合变量可被赋予任一成员值，但每次只能赋一种值，　赋入新值则冲去旧值。如前面介绍的“单位”变量，　如定义为一个可装入“班级”或“教研室”的联合后，就允许赋予整型值（班级）或字符串（教研室）。要么赋予整型值，要么赋予字符串，不能把两者同时赋予它。联合类型的定义和联合变量的说明一个联合类型必须经过定义之后，　才能把变量说明为该联合类型。

一、联合的定义

定义一个联合类型的一般形式为：　
union　联合名　
｛　
成员表　
｝；
成员表中含有若干成员，成员的一般形式为：　类型说明符　成员名　成员名的命名应符合标识符的规定。
例如：　
union　perdata
｛
int　class；
char　office＇10＇；
｝；
　　定义了一个名为perdata的联合类型，它含有两个成员，一个为整型，成员名为class；另一个为字符数组，数组名为office。联合定义之后，即可进行联合变量说明，被说明为perdata类型的变量，可以存放整型量class或存放字符数组office。

二、联合变量的说明

　　联合变量的说明和结构变量的说明方式相同，　也有三种形式。即先定义，再说明；定义同时说明和直接说明。以perdata类型为例，说明如下：　
union　perdata
｛
int　class；
char　officae＇10＇；
｝；
union　perdata　a；b；　/*说明a；b为perdata类型*/
或者可同时说明为：　
union　perdata
｛　int　class；
char　office＇10＇；　｝a；b；或直接说明为：　union
｛　int　class；
char　office＇10＇；　｝a；b　
经说明后的a；b变量均为perdata类型。　它们的内存分配示意图如图7—8所示。a；b变量的长度应等于　perdata　的成员中最长的长度，　即等于
office数组的长度，共10个字节。从图中可见，a；b变量如赋予整型值时，只使用了2个字节，而赋予字符数组时，可用10个字节。

联合变量的赋值和使用

　　对联合变量的赋值，使用都只能是对变量的成员进行。　联合变量的成员表示为：　联合变量名。成员名　例如，a被说明为perdata类型的变量之后，可使用　a。class　a。office　不允许只用联合变量名作赋值或其它操作。　也不允许对联合变量作初始化赋值，赋值只能在程序中进行。还要再强调说明的是，一个联合变量，　每次只能赋予一个成员值。换句话说，一个联合变量的值就是联合变员的某一个成员值。
＇例7。15＇设有一个教师与学生通用的表格，教师数据有姓名，年龄，职业，教研室四项。学生有姓名，年龄，职业，班级四项。
编程输入人员数据，　再以表格输出。
main（）
｛
struct
｛
char　name＇10＇；
int　age；
char　job；
union
｛
int　class；
char　office＇10＇；
｝　depa；
｝body＇2＇；
int　n；i；
for（i=0；i