计算机设计语言(c语言)8

1、第第8章章 结构体结构体8.1 概述概述基本类型（简单类型）基本类型（简单类型） 整型、实型、字符型等。整型、实型、字符型等。构造类型构造类型 数组，数组中的各元素属于同一类型。数组，数组中的各元素属于同一类型。当若干个不同类型的数据项组成一个组合项时，用什么当若干个不同类型的数据项组成一个组合项时，用什么数据结构数据结构? 例如：例如：一个学生的学号，姓名，姓别，年龄，地址等。一个学生的学号，姓名，姓别，年龄，地址等。C语言中提供了一种实现这种组合的数据结构语言中提供了一种实现这种组合的数据结构 结构体类型（结构体类型（structure）.它相当于其它高级语言中的它相当于其它高级语言中的“

2、记录记录”。结构体类型定义的一般形式。结构体类型定义的一般形式: 第第8章章 结构体结构体 struct 结构体名结构体名 成员表列成员表列 ;结构体内的各个结构体内的各个成员成员（即（即分量分量）。）。对每个成员都应进行类型说明，成员对每个成员都应进行类型说明，成员的定名和类型说明与变量相同。的定名和类型说明与变量相同。分号不能忽略分号不能忽略结构体名的命名规则与变量名相同结构体名的命名规则与变量名相同num name sex age score addrBeijing87.518MLi Fun10010例如：例如： 将一个学生的学号、姓名、性别、年龄、成绩、地址等项定义将一个学生的学号、姓

3、名、性别、年龄、成绩、地址等项定义成一个结构体类型。成一个结构体类型。struct student int num; char name20; char sex ; int age; float score; char addr30; ;成员列表（称为成员列表（称为域表域表）分号不能漏掉分号不能漏掉 经过这样的定义，类型名经过这样的定义，类型名 struct student 就可以和其它类型（如就可以和其它类型（如 int 等）一样，用来定义等）一样，用来定义结构体类型的变量结构体类型的变量。例如例如struct student stu1, stud2; 这个定义就表示定义了一这个定义就表示定

4、义了一种种 类型名类型名为为 struct student 的的结构体类型，结构体类型，struct 是系统关是系统关键字，表示开始定义一个结构键字，表示开始定义一个结构体类型。体类型。1. 先声明结构体类型，再定义变量名先声明结构体类型，再定义变量名 例如例如:struct student int num; char name20; char sex ; int age; float score; char addr30;struct student student1, student2; student1 10001 Zhang Xin M 19 90.5 Shanghaistudent2

5、 10002 Wang Li F 20 98 Beijing 在定义了结构体变量后，系统会为之分配内存单元。例如在定义了结构体变量后，系统会为之分配内存单元。例如 student1 和和 student2 在内存中各占在内存中各占59个字节（个字节（2+20+1+2+4+30=59）8.2 定义结构体类型变量的方法定义结构体类型变量的方法声明结构体类型声明结构体类型 struct student定义了两个类型为定义了两个类型为struct student 的变量的变量student1和和student2为了使用方便，可以用宏定义为了使用方便，可以用宏定义 来定义一个来定义一个符号常量符号常量

6、代表一个结构体类型代表一个结构体类型.例如例如 struct student int num; char name20; char sex ; int age; float score; char addr30;#define STUD struct student STUD student1, student2; 对于较大的程序，对于较大的程序，往往将结构体类型的定义集中放到一个头文件中往往将结构体类型的定义集中放到一个头文件中，然后在需用到该结构体类型的源程序中用然后在需用到该结构体类型的源程序中用 #include 命令包含进来。命令包含进来。说明说明: 因为可以定义出许许多多种具体的结

7、构体类型，所以因为可以定义出许许多多种具体的结构体类型，所以定义结构体类型的定义结构体类型的变量变量时，必须时，必须指定具体的结构体类型。指定具体的结构体类型。例如例如struct student stu；struct worker w1, w2; 需要注意：需要注意：结构体类型名不是变量，结构体类型名不是变量，例如：例如：student、worker等不是变量。等不是变量。2. 在定义类型的同时定义变量在定义类型的同时定义变量 例如例如:struct student int num; char name20; char sex ; int age; float score; char add

8、r30; student1, student2; 定义了两个类型为定义了两个类型为struct student的变量的变量 student1 和和 student23. 直接定义结构类型的变量（无结构体名）直接定义结构类型的变量（无结构体名） 一般形式为一般形式为: struct 成员表列成员表列 变量名表列变量名表列;注意注意: 这里不出现结构体名这里不出现结构体名!一般形式为一般形式为: struct 结构体名结构体名 成员表列成员表列 变量名表列变量名表列 ;注意注意;的位置的位置关于结构体类型的说明关于结构体类型的说明: “ 类型类型”与与“ 变量变量” 是不同的概念，不能混同。只能对

9、变量赋值、存取是不同的概念，不能混同。只能对变量赋值、存取或运算，而不能对一个类型赋值、存取或运算。在编译时，对类型是不分配或运算，而不能对一个类型赋值、存取或运算。在编译时，对类型是不分配空间的，只对变量分配空间。空间的，只对变量分配空间。 结构体中的结构体中的成员成员（即（即“域域”）可以单独使用可以单独使用，作用和地位相当于普通变量，作用和地位相当于普通变量。 结构体中的成员还可以是一个结构体变量。结构体中的成员还可以是一个结构体变量。 例如例如: struct date int month; int day; int year; ; struct student int num; ch

10、ar name20; int age; float score; struct date birthday; char addr30; student1, student2 ; birthday是是 struct date类型的变量类型的变量定义了两个具有定义了两个具有struct student类类型的变量型的变量student1和和student2 成员名可以和程序中的其它变量名相同，二者不代表同一对象。成员名可以和程序中的其它变量名相同，二者不代表同一对象。 例如，程序中可以定义一个变量例如，程序中可以定义一个变量num ，它与，它与 struct student 中的中的num是两回事

11、，两者互不干涉。是两回事，两者互不干涉。struct student 的结构：的结构： num name sex age birthdaymonth day yearaddrstruct datestudent1 0103 Li lin M 18 birthday 03 26 1983Hangzhou在定义了结构体变量以后，就可以引用这个变量以及变量中的各个成员。在定义了结构体变量以后，就可以引用这个变量以及变量中的各个成员。结构体变量中的成员的引用方式结构体变量中的成员的引用方式: 结构体变量名结构体变量名. 成员名成员名 结构体变量的成员变量的用法和一般变量一样，如结构体变量的成员变量的用

12、法和一般变量一样，如 被赋值、被赋值、 参与运算等参与运算等 。 如如 : student1. num=10010; 表示给变量表示给变量 student1中的成员中的成员num 赋值赋值10010。8 . 3 结构体类型变量的引用结构体类型变量的引用“.” 成员（分量）运算符，成员（分量）运算符，优先级最高优先级最高引用结构体变量时应遵守以下规则：引用结构体变量时应遵守以下规则： 不能将一个结构体变量作为一个整体进行输入输出，只能通过引用其成员不能将一个结构体变量作为一个整体进行输入输出，只能通过引用其成员分别输入输出。分别输入输出。 如如 ：不能用以下语句整体输入结构体变量，：不能用以下语

13、句整体输入结构体变量， scanf(%d, %s, %c, %d, %f, %s , &student1) ; 可用以下语句一个一个可用以下语句一个一个成员成员输入：输入： scanf (%d, %s, %c, %d, %f, %s, &student1.num, , ); 如果结构体变量成员本身又属于如果结构体变量成员本身又属于 一个结一个结构体类型，则需要用若干个成员运算符，构体类型，则需要用若干个成员运算符， 逐逐级找到最低一级的成员。级找到最低一级的成员。只能对最低级的成只能对最低级的成员进行赋值、存取以及运算。员进行赋值、存取以及运算。 如如

14、 : student1 . birthday . year注意：不能用注意：不能用 student1.birthday 来访问来访问student1.birthday 中的成员，因为中的成员，因为birthday本身是一个结构体变量。本身是一个结构体变量。也不能用也不能用 student1. year 来访问来访问birthday中的中的成员。成员。 struct date int month; int day; int year; ; struct student int num; char name20; int age; float score; struct date birthday

15、; char addr30; student1, student2 ; 但但C语言新标准允许语言新标准允许 将一个结构体变量直接赋值给另一个相同类将一个结构体变量直接赋值给另一个相同类型的结构体变量。型的结构体变量。 例如：例如： student2=student1 ;表示将表示将 student1中所有成员的值一中所有成员的值一 一赋给一赋给 student2 中相应的成员中相应的成员. 可以引用结构体变量可以引用结构体变量成员的地址成员的地址，也可以引用，也可以引用结构体变量的地址结构体变量的地址。如如 : &student1.num student1.num 的地址的地址 &am

16、p;student1 结构体变量结构体变量student1的首地址的首地址 scanf (%d , &student1 . num) ; 输入输入 student1.num的值的值 printf(%o , &student1) ; 以八进制以八进制 输出输出 student1的地址的地址结构体变量的地址主要用于作函数参数，传递结构体的地址。结构体变量的地址主要用于作函数参数，传递结构体的地址。 结构体变量的成员变量可以像普通变量一样进行结构体变量的成员变量可以像普通变量一样进行各种运算各种运算（根据其类型（根据其类型决定可以进行的运算），例如：决定可以进行的运算），例如：stu

17、dent1 . score=student2 . score ;sum=student1 . score+student2 . score ;student1 . age+ ;+student1 . age ;注意：注意： 成员运算符成员运算符“.” 优先级最高优先级最高和其它类型变量一样，对结构体变量也可以和其它类型变量一样，对结构体变量也可以在定义时初始化。在定义时初始化。例例8.1 对结构体变量初始化。对结构体变量初始化。main( ) struct student long int num; char name20; char sex ; char addr20; a=89031,”L

18、i Lin“, M , 123 Beijing Road; printf(No. :%ldn, a . num) ; printf(name : %sn, a . name) ; printf(sex :%cn, a . sex) ; printf(address :%sn, a . addr) ;运行结果：运行结果：No. : 89031name : Li linsex : Maddress : 123 Beijing Road8.4 结构体变量的初始化结构体变量的初始化一个结构体变量中可以存放一组数据，如果有多组结构体数据参与一个结构体变量中可以存放一组数据，如果有多组结构体数据参与运算，

19、则应该用数组，这就是运算，则应该用数组，这就是结构体数组结构体数组。结构体数组中的每个元素都是一。结构体数组中的每个元素都是一个结构体类型的数据，而且都分别包括各个成员项。个结构体类型的数据，而且都分别包括各个成员项。8.5.1 定义结构体数组定义结构体数组 与结构体变量的定义类似，只需将变量与结构体变量的定义类似，只需将变量 说明为数组即可。说明为数组即可。 例如例如:struct student int num; char name20; char sex ; int age; float score; char addr30;struct student stu3;8.5 结构体数组结构

20、体数组定义了一个数组定义了一个数组stu3，其各元，其各元素为素为 struct student 类型的数据类型的数据定义结构体类型定义结构体类型 struct studentnumnamesexagescoreaddress10101Li LinM1887.5103 Beijing Road 10102Zhang FunM1999130 Shanghai Road10104Wang MinF2078.51010 Zhongshan Roadstu0stu1stu2也可以直接定义也可以直接定义:struct student. stu3;或或: struct. stu3;见下图所示。见下图所示。

21、stu0 10101 2B Li Lin 20B M 1B 18 2B 87.5 4B 103 Beijing Road 30B59 个字节个字节stu1stu2。数组中各元素在内存中是连续存放的：数组中各元素在内存中是连续存放的：说明：说明：1. 元素内部按成员元素内部按成员顺序初始化；顺序初始化；2. 按数组元素顺序，每个元素可用按数组元素顺序，每个元素可用 括起来；括起来；3. 元素个数如果缺省，则按初值个数来确定，例如：元素个数如果缺省，则按初值个数来确定，例如：struct student int num ; char name20 ;stu = 97001,Zhang,97002,

22、Li,97003,Wang ; 也可以先声明结构体类型，然后定义结构体数组及初始化。例如也可以先声明结构体类型，然后定义结构体数组及初始化。例如struct student int num ; char name20 ; ；struct student stu =97001,Zhang,97002,Li,97003,Wang ;8.5.2 结构体数组的初始化结构体数组的初始化只需在定义数组时在数组名后面加上只需在定义数组时在数组名后面加上 =初值表列初值表列;例如例如: struct student int num; char name20; stu3= 97001,Zhang,97002,L

23、i,97003,Wang ;#include struct person char name20; int count; leader3= Li,0,Zhang,0,Wang,0 ;main( ) int i , j; char leader_name20; /* 被选人的名字被选人的名字*/ for (i=1; i=10 ; i+) scanf(%s, leader_name); for (j=0 ; j3 ; j+) if (strcmp(leader_name , )=0) leaderj . count+ ; printf(n); for (i=0 ; i3 ;

24、 i+) printf(%s : %dn,leaderi . name , leaderi . count); 例例8.2 有三个候选人，统计得票次数。（有有三个候选人，统计得票次数。（有10个选民）个选民） 执行执行10次次leader 3 name count Li 0 Zhang 0 Wang 08.5.3 结构体数组应用举例结构体数组应用举例“.” 比比+ 优先级高优先级高一个一个结构体变量的指针结构体变量的指针就是指向一个结构变量所占据的内存段的起始地址。就是指向一个结构变量所占据的内存段的起始地址。 8.6.1 指向结构体变量的指针指向结构体变量的指针 例例8.3 指向结构体变量的

25、指针的应用。指向结构体变量的指针的应用。#include main( ) struct student long int num; char name20; float score; ; struct student stu; /* 定义结构体变量定义结构体变量 stu */ struct student *p; /* 定义指向定义指向 struct student 型数据的指针变量型数据的指针变量 p */ p=&stu; /* p指向指向str的起始地址的起始地址 */ stu. num=89101;/* 变量成员赋值变量成员赋值 */ strcpy(stu . name,Li);

26、 stu . score=89. 5; printf(No.%ld name %s score %6.2fn, stu.num, , stu.score); printf(No.%ld name %s score %6.2f, (*p).num , (*p).name, (*p).score); 8.6 指向结构体类型数据的指针指向结构体类型数据的指针注意：注意： (*p ) . num中的中的 ( ) 不可省，因为不可省，因为 “ .” 的优先级最高，的优先级最高，(*p) 表示表示 p 所指向的所指向的结构体变量，而结构体变量，而*p.num 等价于等价于*(p.num)。

27、 C语言中，为了使用方便和使之直观，可以语言中，为了使用方便和使之直观，可以 将指针将指针p 所指向的结所指向的结构体变量中的成员构体变量中的成员 表示为表示为: p-成员名成员名，它等价于，它等价于: (*p). 成员名。成员名。其中其中 “ ” 称为称为指向运算符。指向运算符。由由“-”和和“”构构成成也就是说，若也就是说，若 p=&stu ，以下三种形式等价：以下三种形式等价： （1）结构体变量名）结构体变量名. 成员名成员名 stu . num （2） ( * p ) . 成员名成员名 (*p) . num （3） p- 成员名成员名 p-num 象一般数组一样，对于结构体数组

28、和数组元素，也可以使用指针或象一般数组一样，对于结构体数组和数组元素，也可以使用指针或指针变量来指向。指针变量来指向。例：若有如下的定义例：若有如下的定义: struct student long int num; . ; struct student stu3; struct student *p;则则: p=stu; 表示令表示令 p 指向数组指向数组 stu 的首地址。的首地址。 p+1 表示数组中下一个元素的起始地址，即表示数组中下一个元素的起始地址，即 &stu1。 (+p)-num 表示先使表示先使 p 指向下一个元素，然后得到该元素中的指向下一个元素，然后得到该元素中的n

29、um值，值， 即即stu1. num。 (p+)-num 表示先得到当前元素的表示先得到当前元素的num值，值，,然后使然后使 p 指向下一指向下一个元素，即取出个元素，即取出stu0. num 成员，然后使指针成员，然后使指针 p + ，指向结构元素，指向结构元素 stu1 。 8.6.2 指向结构体数组的指针指向结构体数组的指针例例8.4 指向结构体数组的指针的应用。指向结构体数组的指针的应用。struct student int num; char name20; char sex ; int age ; ;struct student stu3=10101, Li Lin,M,18 ,

30、 10102, Zhang Fun, M,19, 10104, Wang Min , F , 20 ;main( ) struct student *p ; printf( No. name sex agen ) ; for( p=stu ; pnum , p-name , p-sex , p-age) ;运行结果：运行结果：No. Name sex age10101 Li Lin M 1810102 Zhang Fun F 1910104 Wang Min F 2020FWang Min1010419FZhang Fun1010218MLi Lin10101stu0stu1stu2p=stu

31、stu+38.6.3 用结构体变量和指向结构体的指针作函数参数用结构体变量和指向结构体的指针作函数参数将一个结构体变量的值传递给另一个函数时，有三种方法将一个结构体变量的值传递给另一个函数时，有三种方法:1.用结构体变量的用结构体变量的成员成员作为实参，将实参的值传递给形参作为实参，将实参的值传递给形参 ( 值传递值传递 )。用法。用法和普通变量作实参一样，但应当注意实参与形参的类型必须保持一致。和普通变量作实参一样，但应当注意实参与形参的类型必须保持一致。2.用结构体变量作实参（用结构体变量作实参（值传递值传递）。函数调用期间，形参也要占用内存单）。函数调用期间，形参也要占用内存单元，在时间

32、上和空间上开销较大，此方法较少用。元，在时间上和空间上开销较大，此方法较少用。3.用指向结构体变量用指向结构体变量(或数组或数组)的的指针指针作实参作实参,将地址传递给形参将地址传递给形参 ( 地址传递地址传递 ) 注意注意: 如果指针如果指针 p 已定义为指向结构体类型数据的变量（如已定义为指向结构体类型数据的变量（如struct student 类型），则它类型），则它只能指向结构体变量或结构体数组的一个元素（只能指向结构体变量或结构体数组的一个元素（p 的值是的值是stu 数组的一个元素的起始地址）数组的一个元素的起始地址），而不能指向某个成员。，而不能指向某个成员。若若 p=stu ;

33、 /* 指向结构体数组指向结构体数组 stu */则则 p=&stu1. name ; 编译时出错，编译时出错， p不能指向结构体元素不能指向结构体元素 stu1的成员的成员如果地址类型不同，可以使用强制类型转换，例如如果地址类型不同，可以使用强制类型转换，例如p=(struct student *)&;例例 8.5 有一个结构体变量，包含学生学号、姓名、和三门课成绩。要求在有一个结构体变量，包含学生学号、姓名、和三门课成绩。要求在main( ) 函数中赋以值，在另一个函数函数中赋以值，在另一个函数print( ) 中将它们打印输出。中将它们打印输出。#incl

34、ude #define FORMAT %dn%sn%fn%fn%fnstruct student int num ;char name20 ;float score3 ; ;main( ) void print(struct student ) ; struct student stu1 ; stu1.num=12345 ; strcpy( , Li Li ) ; stu1.score0=67.5 ; stu1.score1=89 ; stu1.score2=78.6 ; print(stu1) ; /* 结构体变量为形参结构体变量为形参 */void print(stuct

35、 student stu) printf(FORMAT , stu.num , , stu.score0, stu.score1, stu.score2) ; printf(n) ;运行结果：运行结果：12345Li Li67.50000089.00000078.599998实参数组实参数组 stu1 形参数组形参数组 stu例例8.6 上例改为指针方式。上例改为指针方式。#define FORMAT %dn%sn%fn%fn%fnstruct student int num ;char name20 ;float score3 ; stu1=12345 , Li Li , 6

36、7.5 , 89 , 78.6 ;main( ) void print(struct student *) ; print(&stu1) ;void print(stuct student *p) /* 结构指针变量为形参结构指针变量为形参 */ printf(FORMAT , p-num , p-name , p-score0, p-score1, p-score2) ; printf(n) ;指针作参数能提高运行效率。指针作参数能提高运行效率。score0score1score2namenumstupmain 函数中对各成员的赋值，也可以改用函数中对各成员的赋值，也可以改用scan

37、f 函数输入，即函数输入，即scanf(%d%s%f%f%f,&stu.num, ,&stu.score0,&stu.score1,&stu,score2); 前没有前没有&main( ) struct student int num; char name8; float score; stu4=10,A1,78,15,A2,89,20,B1,90,25,B2,70; struct student *p; float max ; int temp , i ; max=stu0.score; for (i=1 ; imax)

38、 max=stui . score; temp=i ; /* temp 成绩最高者下标成绩最高者下标 */ p=stu+temp ; /* 使使 p 指向指向 stu成绩最高者成绩最高者 */ printf(No.%d , name %s , %dn, p-num , p-name , p-score) ;例、已知例、已知 学生的学生的 学号、姓名、成绩，找出成绩最高者的学号、姓名、成学号、姓名、成绩，找出成绩最高者的学号、姓名、成绩绩8.7.1 链表概述链表概述 链表是一种链表是一种动态动态地进行存储分配的地进行存储分配的数据结构数据结构，用数组存放数据时，必须，用数组存放数据时，必须申请一

39、块申请一块连续空间连续空间，若元素有，若元素有100个，则必须申请长度为个，则必须申请长度为100个元素的数组，个元素的数组，若数组元素个数不定，则需要定义足够大的数组长度，这势必浪费内存。而若数组元素个数不定，则需要定义足够大的数组长度，这势必浪费内存。而 用链表可以根据需要来开辟内存单元。用链表可以根据需要来开辟内存单元。 一种简单的链表结构图示如下一种简单的链表结构图示如下 : 链表有一个链表有一个头指针变量头指针变量head，指向第一个元素指向第一个元素(表头表头)。 链表中的每一个元素称为链表中的每一个元素称为结点。结点。 一个结点包括两个部分一个结点包括两个部分: 实际数据实际数据

40、 下一个下一个同类型同类型结点的地址结点的地址。 链表有一个链表有一个表尾表尾，该元素不再指向其它元素，它的地址部分存放一，该元素不再指向其它元素，它的地址部分存放一个个空地址空地址(NULL)， ( NULL 是一个符号常量，是一个符号常量，代表整数代表整数 0， 指针变量指针变量等于等于0(NULL) 表示一个表示一个空指针空指针 )。 A1356headB1475C1021DNULL1249 1356 1475 102112498.7 用指针处理链表用指针处理链表可见可见: 1.链表中的各元素链表中的各元素 在内存中可以在内存中可以不连续存放。不连续存放。2.整个链表的访问，整个链表的访

41、问，必须从表头指针开始必须从表头指针开始，根据上一个元素所提供的，根据上一个元素所提供的地址找到下一个元素。地址找到下一个元素。3.链表的数据结构链表的数据结构必须利用指针变量必须利用指针变量才能实现，一个结点中除了包含才能实现，一个结点中除了包含 数据变量外，还应包含一个指针变量，用来存放下一结点的地址。数据变量外，还应包含一个指针变量，用来存放下一结点的地址。因此，前面介绍的因此，前面介绍的结构体类型用作链表中的结点结构体类型用作链表中的结点是最合适的：是最合适的： 例如，例如， 要建立一个链表，首先要定义结点的类型要建立一个链表，首先要定义结点的类型 ：struct student in

42、t num; float score ; struct student *next; /* next 是指针变量，指向下一个结点是指针变量，指向下一个结点*/ ；数据数据指针指针指向下一个结点指向下一个结点89.59910190991038599107nextscorenum#define NULL 0struct student long int num ;float score ;struct student *next ; ;/* 声明一个结构体声明一个结构体 */ 建立链表是指从无到有地建立起一个链表建立链表是指从无到有地建立起一个链表，包括一个一个地输入各，包括一个一个地输入各结点数

43、据结点数据, 并建立起前后相链的关系。并建立起前后相链的关系。例例11.7 建立如下图所示的链表，它由建立如下图所示的链表，它由3各学生数据的结点组成。各学生数据的结点组成。8.7.2 建立简单链表建立简单链表 a b cnumnextscore &b &c NULL 89.5 90.0 85.0 99101 99103 99107main( ) /* a,b,c 是结构变量，是结构变量，head 和和 p是指针是指针 */ struct student a, b, c , *head , *p ; a. num=99101 ; a. score=89.5 ; b. num=9

44、9103 ; b. score=90.0 ; c. num=99107 ; c . score=85.0 ; a. next=&b ; b. next=&c ; c. next=NULL ; p=head=&a ; while( p !=NULL) printf(%ld %5.1f n , p-num , p-score) ; p=p-next ; /* 建立链表建立链表 */* 输出各结点内容输出各结点内容 */ a b cnumnextscore &b &c NULL 89.5 90.0 85.0 99101 99103 99107/* 结点赋值结点

45、赋值 */ 链表是动态地分配存储的，链表是动态地分配存储的，C语言中提供了语言中提供了动态地开辟和释放存储单动态地开辟和释放存储单元的库函数元的库函数（其信息包含在（其信息包含在 malloc.h 文件中）。文件中）。1. malloc 函数函数 函数原型为：函数原型为： void *malloc(unsigned int size) ; 其作用是：在内存的动态存储区中分配一个长度为其作用是：在内存的动态存储区中分配一个长度为size的连续空间。的连续空间。此此 函数的值（即返回值）是一个指向函数的值（即返回值）是一个指向该分配域起始地址该分配域起始地址的指针（基类型为的指针（基类型为 voi

46、d）。如果函数未能成功地执行，则返回值为）。如果函数未能成功地执行，则返回值为NULL。8.7.3 处理处理动态链表动态链表所需的函数所需的函数2. calloc函数函数 函数原型为：函数原型为： void * calloc(unsigned n, unsigned size) ; 其作用是：在内存的动态存储区中分配其作用是：在内存的动态存储区中分配 n 个长度为个长度为 size 的连续空间。的连续空间。 函数返回一个函数返回一个 指向该分配指向该分配空间的起始地址的指针；空间的起始地址的指针； 如果函数不能成功执如果函数不能成功执行行,则返回值为则返回值为NULL。链表的操作包括：链表的操

47、作包括： 建立链表、插入或建立链表、插入或 删除链表中的一个结点等。删除链表中的一个结点等。8.7.4 建立动态链表建立动态链表例例 11.8 写一个函数，建立有三个学生数据的单向动态链表。写一个函数，建立有三个学生数据的单向动态链表。head num score *next 1 2 3 NULL3. free 函数函数 函数原型为：函数原型为：void free(void *ptr) 作用是：释放由作用是：释放由 ptr 所指向的内存区，所指向的内存区， ptr 是最近一次调用是最近一次调用malloc 或或 calloc 函数函数 时返回的地址。时返回的地址。free 函数无返回值。函数无

48、返回值。注意：以前注意：以前C版本提供的版本提供的malloc 和和 calloc 函数得到的是指向字符型函数得到的是指向字符型数据的指针。数据的指针。ANSI C 规定为规定为 void * 类型。类型。步骤步骤:1. 定义结点类型（结构体类型）：定义结点类型（结构体类型）： struct student2. 定义指向结点的指针变量定义指向结点的指针变量 head, p1, p2： head 指向表头，指向表头，p1 指向指向当前当前新建立的结点新建立的结点， p2 指向链表中最后一个结点指向链表中最后一个结点；3. 新建一个结点新建一个结点 （开辟内存单元，（开辟内存单元， 输入学号和成绩

49、输入学号和成绩 数据）；数据）；4. 建立表头建立表头5. 建立链表建立链表 如果新结点是第一个结点，如果新结点是第一个结点，则表头则表头 head 指向该结点指向该结点， 否则该结点链否则该结点链入链表，并让入链表，并让 p2 指向新链入的这个结点，重复指向新链入的这个结点，重复3、 5； 如果是第如果是第3个结点，则个结点，则让让 p1 所指的结点中的指向下一个结点的指针为所指的结点中的指向下一个结点的指针为空指针空指针NULL，链表建立结束。，链表建立结束。head num score *next 1 p1 1 23head num score *nextp2p1*nextNULL#in

50、clude #define NULL 0struct student long num; float score; struct student *next; ; void main( ) struct student *head , *p1 , *p2 ; int n ; head=NULL ; for(n=1 ; n num , &p1 - score) ;if(head = NULL) head=p1 ;else p2-next=p1 ;p2=p1 ; p1-next=NULL ; free(p1) ; /* 释放结点空间释放结点空间*/ return ;三次动态三次动态申请空间

51、申请空间定义结点的数据结构定义结点的数据结构 现在，我们用一个现在，我们用一个函数函数来建立一个有来建立一个有若干若干个学生的学号和成绩数据的个学生的学号和成绩数据的单向链表（假设输入学号为单向链表（假设输入学号为 0 时结束）。时结束）。步骤步骤:1. 定义结点类型（结构体类型）：定义结点类型（结构体类型）： struct student2. 定义指向结点的指针变量定义指向结点的指针变量 head, p1, p2； head 指向表头，指向表头，p1 指向指向当前当前新建立的结点新建立的结点，p2 指向表中最后一个结点指向表中最后一个结点。 把把p1所指的结点连接在所指的结点连接在p2所指的

52、结点后面，用所指的结点后面，用“p2-next=p1; ”来实现来实现。3. 新建一个结点新建一个结点 （开辟内存单元、输入学号、成绩等数据）；（开辟内存单元、输入学号、成绩等数据）；4. 建立表头建立表头 （head=NULL;）5. 建立链表建立链表 如果新结点是第一个结点，如果新结点是第一个结点，则表头则表头 head 指向该结点指向该结点， 否则该结点否则该结点链入链表，并让链入链表，并让 p2 指向新链入的这个结点，重复指向新链入的这个结点，重复 3、5； 如果输入学号为如果输入学号为0，则该结点不链入链表，前一个结点是表尾，即，则该结点不链入链表，前一个结点是表尾，即让让 p2 所

53、指的结点中的指向下一个结点的指针为空指针所指的结点中的指向下一个结点的指针为空指针NULL（p2 - next=NULL;），链表建立结束。），链表建立结束。int n; /* 全局变量全局变量 n 统计结点数统计结点数 ，本模块中各函数，本模块中各函数 均可使用它均可使用它*/struct student * creat (void) /* 定义函数定义函数 。此函数带回一个。此函数带回一个指向链表头的指针指向链表头的指针*/ struct student *head, *p1 , *p2 ; head=NULL; n=0; p1= (struct student *) malloc (si

54、zeof (struct student) ; /* 开辟内存单元准备建立第一个结点开辟内存单元准备建立第一个结点 */ scanf(%ld , %f, &p1-num , &p1-score) ; while ( p1-num != 0) n+; if (head= NULL) head=p1; /* head 指向第一个结点指向第一个结点 */ else p2-next=p1 ; /* 将新结点将新结点 p1 链入链表链入链表 */ p2=p1 ; /* 保留当前保留当前结点的地址结点的地址 */ p1=(struct student *) malloc(sizeof (s

55、truct student) ; scanf(%ld,%f, &p1-num , &p1-score) ; p2 - next=NULL ; free(p1) ; return (head);p2p18.7.5 输出链表输出链表 将链表中各个结点的数据依次输出。将链表中各个结点的数据依次输出。 首先要知道链表表头首先要知道链表表头head的地的地址，再定义一个指向结点的指针变量址，再定义一个指向结点的指针变量 p ，使，使p先指向第一个结点，输出先指向第一个结点，输出该该 结点的数据，然后让结点的数据，然后让 p 指向下一个结点，再输出，直到表尾为止。指向下一个结点，再输出，直

56、到表尾为止。 例例11.9 编写一个输出链表的函数编写一个输出链表的函数print。void print(struct student *head) struct student *p; printf(n输出输出结点结点数据数据 :n) ; p=head; if(head!=NULL) /* 如果不是空链表，则输出如果不是空链表，则输出 */ do printf(%ld %fn, p-num , p-score) ; p=p-next ; /* 使使 p 指向下一个结点指向下一个结点 */ while( p!=NULL) ;可以在可以在main 函数中调用函数中调用 creat 函数：函数：m

57、ain( ) creat( ); 调用调用creat 函数后建立函数后建立一个单向动态链表一个单向动态链表 从一个动态链表中删除一个结点，并不是真正从内存中把它抹掉，而是从一个动态链表中删除一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离出来，只要改变原来的连接关系即可，即让该结点的前一把它从链表中分离出来，只要改变原来的连接关系即可，即让该结点的前一个结点直接指向该结点的下一个结点。个结点直接指向该结点的下一个结点。注意注意: 如果如果删除的是第一个结点删除的是第一个结点，则要修改表头，则要修改表头 head。 如果链表是空表（无结点）或表中找不到要删除的结点如果链表是空表（无结点

58、）或表中找不到要删除的结点 , 不删除。不删除。p2. . .p1 删除删除headp18.7.6 删除一个结点删除一个结点进行操作：进行操作：head = p1-next ;用函数来删除一个指定的结点，方法如下：用函数来删除一个指定的结点，方法如下：1. 用一个指向结点的指针变量，从表头开始用一个指向结点的指针变量，从表头开始查找查找需要删除的结点。需要删除的结点。2. 定义两个指针变量定义两个指针变量 p1 和和 p2 ，其中：，其中： p1 指向要删除的结点，指向要删除的结点，p2 是指向是指向 p1前面的一个结点。前面的一个结点。要删除要删除 p1，使，使p2-next = p1-ne

59、xt ; 就从链表中删除了就从链表中删除了p1 所指的结点。所指的结点。struct student *del (struct student *head, long num) struct student *p1,*p2; if (head = NULL) printf(空链表空链表n) ; goto end; p1=head; while( p1 - num != num & p1-next != NULL) p2=p1; p1=p1-next ; /* 后移一个结点后移一个结点, 继续查找继续查找 */ if( p1 - num = num) /* 找到找到 */ if ( p1 = head) /* 如果删除第一个结点如果删除第一