第10章_结构.ppt

1、结 构,北京理工大学,第十章,北京理工大学,学习 要点,重点,学习 建议,难点,理解结构体、共同体和枚举的概念，掌握结构体的定义、初始化，了解结构体变量的存储结构，比较共同体和枚举类型，能正确引用结构体数据。掌握结构体数组，结构体指针的应用。掌握函数之间传递结构体类型数据的特点。了解动态分配存储空间及其链表的应用。,结构体指针和结构体数组。,链表应用,与数组对照理解，与指针、函数结合学习，多做综合练习题。,共 60 页 第 3 页,第十章 结构,第一节 结构类型 第二节 结构数组 第三节 结构指针 第四节 在函数之间传递结构 第五节 联合 第六节 用typedef定义数据类型 第七节 枚举类型

2、 第八节 链表基础,共 60 页 第 4 页,10-1 结构类型,问题：,一个学生有学号/姓名/性别/年龄/地址等属性 int num;char name20;char sex; int age;int char addr30; 如果将这些属性分别定义为互相独立的简单变量，则难以反映相互间的内在联系(同一个学生的属性),结构是逻辑上相互联系的一组分量的集合。 结构中的分量可以是不同类型的数据，结构中的分量称为结构的成员,在使用结构之前，首先要对结构的组成进行描述，称为结构的定义。结构定义说明了该结构的组成成员，以及每个成员的类型。,共 60 页 第 5 页,10-1 结构类型,一个学生有学号/

3、姓名/性别/年龄/地址等属性 int num;char name20;char sex; int age;int char addr30;,NO MT EN PH SUM V 90 - 1 97 87 92 276 92 N 2 92 91 90 273 91 Y 3 90 81 82 253 84 N,NUM NAME SEX AGE ADDR V - 1 Caojun M 19 SHANGHAINANJINGL8# 86 2 Chenmengjuan W 18 BEIJINGLIGONG 92 3 Chenpengyuan M 20 xianjiaoda 78,共 60 页 第 6 页,s

4、truct 为关键字。 结构类型名称是所定义的结构类型标识，由用户自己定义； 中包围的是组成该结构的成员； 每个成员的数据类型既可以是简单的数据类型 (int、char、float、double.)，也可以是复杂的数据类型(数组类型或结构类型)。,10-1 结构类型,一、结构的定义,结构定义的一般形式,struct 结构类型名称 数据类型 成员名1; 数据类型 成员名2; 数据类型 成员名n； ;,说明：,共 60 页 第 7 页,为了处理通信录，可以定义如下结构： struct address char name30; /* 姓名。字符数组作为结构中的成员 */ char street40;

5、 /* 街道名称 */ char city20; /* 城市 */ char state2; /* 省市代码 */ unsigned long zip;/* 邮政编码。无符号长整型*/ ;,10-1 结构类型,结构定义实例,为了描述日期可以定义如下结构： struct date int year;/* 年，整型作为结构中的成员 */ int month;/* 月 */ int day;/* 日 */ ;,共 60 页 第 8 页,10-1 结构类型,二、结构变量的说明,定义结构是定义了一种由成员组成的复合类型，而只有用这种结构类型说明了一个变量，才会产生具体的实体(变量)。,C语言提供的基本数

6、据类型，例如 int/long/ double等，都是由系统事先定义好的，可直接使用。,结构是一种构造型数据类型，结构定义描述了结构的组成。要使用结构必须先说明结构类型的变量。,共 60 页 第 9 页,例：将变量today说明为date型的结构变量： struct date today; 说明多个address型的结构变量： struct address wang, li, zhang; 结构变量同样有存储类型，存储特性与一般变量完全相同。,10-1 结构类型,结构变量说明的一般形式,struct 结构类型名称 结构变量名；,系统为所说明的结构变量按照结构定义时说明的组成（成员分量），分配存

7、储数据的实际内存单元。,共 60 页 第 10 页,结构变量的各个成员占用连续的内存区域，所占内存大小为各成员分量占用内存的长度之和。,求结构变量占用内存大小 使用 sizeof 运算。sizeof 是单目运算，其功能是求出运算对象所占的内存空间的字节数目。 使用的一般形式为：sizeof (变量或类型说明符),10-1 结构类型,三、结构变量占用内存情况,共 60 页 第 11 页,例：sizeof运算的意义。 main ( ) char str20; struct date/* 定义结构date */ int year, month, day; today; /* 说明结构变量today

8、*/ struct address/* 定义结构address */ char name30, street40, city20, state2; unsigned long int zip; wang;/* 说明结构变量wang */ printf(char: %dt, sizeof(char); /* char型的长度 */ printf(int: %dt, sizeof(int); /* int型的长度 */ printf(long: %dt, sizeof(long); /* long型的长度 */ printf(float: %dn, sizeof(float); printf(do

9、uble: %dt, sizeof(double); printf(str: %dt, sizeof(str); /* 变量str的长度 */ printf(date: %dt, sizeof(struct date printf(wang: %dn, sizeof(wang); /*变量wang的长度 */ ,共 60 页 第 12 页,成员名可以与程序中的变量名相同，二者代表不同的对象。,四、关于结构类型的说明,10-1 结构类型,类型与变量是不同的概念。 在定义结构变量时一般先定义一个结构类型，然后再说明变量为该结构类型。 只能对变量赋值、存取或运算，而不能对一个类型赋值、存取或运算。

10、在编译时，对类型是不分配空间的，只对说明的变量分配空间。,对结构中的成员，可以单独使用，它的作用与地位相当于普通变量。,成员也可以是结构变量。,共 60 页 第 13 页,10-1 结构类型,例如： struct date int month; int day; int year; ; struct student int num;char name20; char sex; int age; struct date birthday; char addr30; student1, student2;,程序中可以另定义一个变量 year，它和 struct date 中的成员 year 是两回

11、事，互不干扰。,共 60 页 第 14 页,“.”操作的优先级最高。结合性为从左到右。,10-1 结构类型,五、引用结构变量中的成员分量,访问成员是通过成员的名字，称为“按名引用”。在程序中使用结构中成员的方法为： 结构变量名成员名称 例如：将“1992/10/01”送入结构变量today，要对其各个成员分别赋值： today.year = 1992; today.month = 10; today.day = 1;,指明结构成员的符号“.”是运算符，含义是访问结构中的成员。,共 60 页 第 15 页,11-1 结构类型,例：用结构描述一个人的情况，可以定义如下结构： struct pers

12、on/* 定义person结构类型 */ char name 30; char sex; struct date birthday;/* 结构的嵌套定义 */ man; 如果要在变量man中存入一个1980年3月28日出生的zhang先生，可以采用如下赋值语句： strcpy(, ”zhang”); /* 注意：不能写成=zhang; */ man.sex = M; /* 为结构中的字符成员赋值 */ man.birthday.year = 1980; man.birthday.month = 3; man.birthday.day = 28; /* 为嵌套定义

13、的结构中的成员赋值 */,共 60 页 第 16 页,对结构变量的整体操作 要对结构进行整体操作有很多限制，C语言中能够对结构进行整体操作的运算不多，只有赋值“=”和取地址“ /* 结构变量整体赋值 */,10-1 结构类型,如果要将“zhang”改为“zhong”，只要将结构变量man 中的数组成员name 下标为2的元素a改为o即可。可以使用下列语句： 2 = o; /* 为结构变量中的数组成员的一个元素赋值 */,共 60 页 第 17 页,只能对最低级的成员进行赋值或存取以及运算。例如，对上面定义的结构变量 student1，可以这样访问各个成员： student1.n

14、ame student1.sex student1.birthday.month student1.birthday.day student1.birthday.year,10-1 结构类型,结构类型的引用说明,不能将一个结构变量作为一个整体直接访问。例如，已定义 student1 为结构变量并且已有值。不能这样引用： printf (”%s,%c,%d,%d,%dn”, student1);,如果成员本身又是一个结构类型，则要用若干个成员运算符，一级一级地找到最低的一级的成员。,共 60 页 第 18 页,可以引用成员的地址，也可以引用结构变量的地址。 例如： scanf (”%d”, ,1

15、0-1 结构类型,对成员变量可以象普通变量一样进行各种运算。 student2.birthday.year = student1.birthday.year; sum = student1.birthday.month + 12; student1.age +; + student1.age;,共 60 页 第 19 页,例：输入今天的日期，然后输出该日期。 #include main ( ) struct date /* 在函数中定义结构类型date */ int year, month, day; ; struct date today; /* 说明结构变量today */ printf

16、(Enter today date:); scanf(%d%d%d, ,共 60 页 第 20 页,六、对结构变量进行初始化,在说明结构变量的同时，可以对每个成员置初值，称为结构的初始化。和数组一样，只有当结构体变量为全局变量或静态变量时，才能进行初始化。,结构初始化的一般形式： struct 结构类型名称 结构变量 = 初始化数据;,初始化数据的个数与结构成员的个数应相同，按成员的先后顺序一一对应赋值。 每个初始化数据必须符合与其对应的成员的数据类型。,共 60 页 第 21 页,例： struct date /* 在函数的外部定义结构date */ int year, month, day

17、; ; struct person /* 在函数外定义结构person */ char name 14, sex; struct date birthday; /* 嵌套定义 */ ; 对date类型的变量，用如下形式进行初始化： struct date today = 1992, 10, 1 ; 如对变量man的初始化可用如下形式： struct person man zhao, M, 1960,3,28 ;,共 60 页 第 22 页,例：用结构描述个人基本情况，打印个人档案。 struct person xu = Xu lihui, M, 1962, 10, 4 ; main ( ) s

18、tatic struct person fang=Fang jin,M,1963,9,13 ; static struct person yuan= Yuan zhiping,M,1963,10,5; /* 说明内部静态结构变量fang、yuan，并初始化结构变量 */ printf (name sex birthdayn); printf (-n); printf (%-14s %-4c%4d.%2d.%2dn, , xu.sex, xu.birthday.year, xu.birthday.month, xu.birthday.day); printf (%-14s %-4c

19、%4d.%2d.%2dn, ,fang.sex, fang.birthday.year,fang.birthday.month,fang.birthday.day); printf (%-14s %-4c%4d.%2d.%2dn, , yuan.sex,yuan.birthday.year, yuan.birthday.month, yuan.birthday.day); ,共 60 页 第 23 页,10-2 结构数组,在结构中使用数组类型作为结构的一个成员； 用结构类型作为数组元素的基类型构成数组。,一、结构与数组的关系,例： struct xs uns

20、igned xh; char xm14; char xb; float sx; int ty; xscj96;,96个元素都具有 结构数据类型,共 60 页 第 24 页,结构数组是一个数组，数组中的每一个元素都是结构类型。 说明结构数组的方法：先定义一个结构，再用结构类型说明一个数组变量。,10-2 结构数组,二、结构数组的定义,例：为记录100个人的基本情况，说明一个有100个元素的数组。数组的基类型为结构： struct person man 100 ; man就是有100个元素的结构数组，数组的每个元素为 person 型。,共 60 页 第 25 页,三、访问结构数组的成员,10-2

21、 结构数组,访问结构数组中的具体元素，必须遵守数组使用的规定按下标进行访问。,要访问结构数组中某个具体元素下的成员，又要遵守有关访问结构成员的规定,使用“.”访问运算符和成员名,共 60 页 第 26 页,strcpy ( , Fangjin” ); man3.sex = M; man3.birthday.year = 1963; man3.birthday.month = 9; man3.birthday.day = 13; /* 为数组中一个元素的一个成员赋值 */,10-2 结构数组,例如：要将数组man中的 3 号元素赋值为： Fangjin, M, 1963, 9,

22、 13， 使用下列语句：,共 60 页 第 27 页,结构数组存放在连续的内存区域中，所占内存大小为结构类型的大小乘以数组元素的数量。 struct person man100 占 37*100 = 3700字节,10-2 结构数组,为了将“Fangjin”改为“Fangjun”： 5 = u; /*为数组中元素的数组成员中的一个字符赋值*/,共 60 页 第 28 页,例：简单的密码加密程序。 加密规则：先定义一张字母加密对照表。将需要加密的一行文字输入加密程序，程序根据加密表中的对应关系，可以很简单地将输入的文字加密输出，对于表中未出现的字符则不加密。 输入 输出 输入

23、输出 输入 输出 输入 输出 a d b w c k d ; ei i a k b ; c w e,共 60 页 第 29 页,struct table /* 定义结构 table */ char input; /* 成员 input 存输入的字符 */ char output; /* 成员output存输出的字符 */ ; struct table translate = /* 外部结构数组translate并初始化 */ a,d, b,w, c,k, d,;, e,i, i,a, k,b, ;,c, w,e ; /* 建立加密对照表 */,共 60 页 第 30 页,main( ) cha

24、r ch; int str_long, i; str_long=sizeof(translate)/sizeof(struct table); /* 计算元素个数 */ while ( (ch=getchar( ) != n) for( i=0; translatei.input!=ch /* 原样输出 */ ,共 60 页 第 31 页,例：分析程序运行结果 struct s int x; int *y; /* y: 结构中的成员是指向整型的指针 */ int data5 = 10,20,30,40,50; /* 整型数组 */ struct s array5=100, /* array:

25、结构数组，初始化 */ 数组array的每个元素有两个成员，初始化状态如下。,共 60 页 第 32 页,11-2 结构数组,main ( ) int i=0; /* 说明变量i并赋初值 */ struct s s_var;/* s_ver: 一般的结构变量 */ s_var = array0; /* 整体赋给s_var */ printf (%dn, s_var.x); printf (%dn, *s_var.y); printf (%dn, arrayi.x); printf(%dn, *arrayi.y); printf (%dn, +arrayi.x); printf(%dn, + *

26、 arrayi.y); printf (%dn, array+i.x); printf(%dn, * + arrayi.y); printf (%dn,(* arrayi.y) +); printf(%dn, * (arrayi.y +); printf (%dn, * arrayi.y +); printf (%dn, * arrayi.y); ,共 60 页 第 33 页,程序各个printf语句中对数组操作的含义如下（i=0）： s_var.x 取s_var的成员x的值 * s_var.y 取s_var的成员指针y所指的内容 arrayi.x 取arrayi的x的值 * arrayi.y

27、 取arrayi的指针y所指的内容,100,10,100,10-2 结构数组,100,10,100,10,共 60 页 第 34 页, + arrayi.x + * arrayi.y array +i .x * + arrayi.y,100,101,10,11,1,200,30,10-2 结构数组,取arrayi的x的值，x加1后输出 101,取arrayi的y所指的内容加1输出 11,i先加1后取array1的成员x的值 200,将arrayi的指针y先加1后再取y所指的内容输出 30,共 60 页 第 35 页, (*arrayi.y)+ * (arrayi.y+) * arrayi.y

28、+ * arrayi.y,30,31,40,50,10-2 结构数组,取arrayi的指针y的内容， 输出 30，y的内容再加 1,取arrayi的指针y的内容， 输出 31，指针y再加 1,同 *(arrayi.y+)，根据运算符的结合性，隐含了括号，输出 40,输出 50,共 60 页 第 36 页,例如： struct date * pdate, today; 说明了两个变量，一个是指向结构 date 的结构指针pdate，today是一个 date 结构变量。 执行语句：pdate = ,10-3 结构指针,一、结构与指针的关系,其一是将指针作为结构中的一个成员； 其二是指向结构的指针

29、（称为结构指针）。,二、结构指针说明的一般形式,struct 结构类型名称 * 结构指针变量名；,共 60 页 第 37 页,采用运算符“-”进行操作。 结构指针-成员名 “-”运算符优先级是最高的(15级)，从左至右结合 注：C语言中优先级为15的运算符有4种： ( ) . - 通过结构指针pdate访问成员year的操作可以写成： pdate-year = 1963; 等价于： today.year = 1963; ( * pdate).year = 1963; /* 必须加括号 */ 如果结构指针p指向一个结构数组，那么对指针p的操作等价于对数组下标的操作。,10-3 结构指针,三、通过

30、指针访问结构中的成员,共 60 页 第 38 页,11-3 结构指针,例：用结构指针改写加密程序 struct table char input, output; ; struct table translate =a,d,b,w,c,k,d,;, e,i,i,a,k,b,;,c,w,e; /* 加密对照表 */ main ( ) char ch; struct table *p, *pend; /* p和pend:指向结构的指针 */ pend= ,共 60 页 第 39 页,11-3 结构指针,例：分析程序的运算结果 struct s int x, *y;/* y: 结构中的成员是指向整型

31、的指针 */ * p; /* p: 指向结构的指针 */ int data5=10,20,30,40,50,;/* data: 整型数组 */ struct s array5=100, （p296,例10-8）,共 60 页 第 40 页,100,10,100,11-3 结构指针, p-x (*p).x *p-y *(*p).y + p-x,取结构指针p指向的结构的成员x的值，输出 100,取结构指针p的内容所指的成员x的值，输出 100,取结构指针p的指针成员y所指的内容，输出 10,取指针p的内容的指针成员y的内容，输出 10,p所指的 x 加1，x先加1后再输出 101。p不加1,分析程

32、序的运算结果： 结构数组 array 的初始化后的状态如下。,*p-y 等于 *（p-y）, *(*p).y 等于 *(*p).y),共 60 页 第 41 页,由运算符的优先级和结合性决定+操作的对象； 由+的前缀/后缀形式，决定操作的时机。 +p-x p-x+ + * p-y * + p-y *(+p)-y * p-y + * (p-y) + * p + -y,10-3 结构指针,四、指针运算与+运算规律小结,共 60 页 第 42 页,struct stuinf int stid; /* 学生学号 */ int score; /* 学生成绩 */ stu STNUM ; /* stu:

33、结构数组 */ struct stuinf * pSTNUM; /* p: 由指向结构的指针构成的指针数组 */,10-3 结构指针,例 ：用结构表示学生的学号和成绩，编写程序，对班中30名学生按成绩进行排序，并输出排序后的学号、成绩和全班平均分。,共 60 页 第 43 页,若是5个学生的数据，则在完成初始化操作后，数组的关系如下：,算法分析： 程序中使用结构数组stu，指针数组p; 程序在结构数组和指针数组之间建立指针关系。 程序中只用对指针数组进行排序，就可以实现对指向的成绩的排序（选择排序）。,10-3 结构指针,共 60 页 第 44 页,11-3 结构指针,#define STNU

34、M 5 . main ( ) struct stuinf * ptemp, * pSTNUM; int i,j,k,sum=0; for ( i=0; iscore score ) k=j; if ( k != i ) ptemp = pi; pi=pk; pk=ptemp; for (i=0; iscore); printf (average score = %dn, sum/STNUM); ,共 60 页 第 45 页,实例 printf(%d, man.birthday.year); 传递结构成员的值 scanf(%d, 传递结构成员的地址,10-4 在函数之间传递结构,结构与函数的关系

35、,向函数中传递结构的成员； 在函数之间传递整个结构； 向函数传递结构的地址（指针）。,向函数中传递结构的成员,在函数中传递结构成员的方法与传递简单变量的方法相同： 在函数之间传递成员的值； 在函数之间传递成员的地址。,共 60 页 第 46 页,例：利用结构变量求解两个复数之积。 、(3+4i)(5+6i) 、(10+20i)(30+40i) struct complx int real, im; /* real:复数的实部 im:复数的虚部 */ ; struct complx cmult ( za, zb ) /* 返回值为结构类型 */ struct complx za, zb; /*

36、形参为结构类型 */ struct complx w; w.real = za.real * zb.real - za.im * zb.im; w.im = za.real * zb.im + za.im * zb.real; return ( w ); /* 返回结果，为结构 */ ,10-4 在函数之间传递结构,将结构作为整体，在函数之间传递： 将结构变量作为形参； 函数的返回值为一个结构类型。,在函数之间传递整个结构,共 60 页 第 47 页,例：利用结构变量求解两个复数之积 void cpr (za,zb,z)/* 输出复数zazb=z */ struct complx za, zb

37、, z;/* 形式参数为结构类型 */ printf (%d+%di)*(%d+%di)=, za.real, za.im, zb.real, zb.im); printf (%d+%di)n, z.real, z.im); main ( ) static struct complx za = 3, 4 ; static struct copmlx zb = 5, 6 ; struct complx z, x, y; struct complx cmult( ); /* 说明返回值是complx型 */ void cpr( ); z = cmult(za, zb); cpr (za, zb,

38、z); x.real = 10; x.im = 20; y.real = 30; y.im = 40; z = cmult (x, y); cpr (x, y, z); ,10-4 在函数之间传递结构,共 60 页 第 48 页,例：输入10本书的名称和单价，按照单价排序。 程序中使用插入排序算法。 插入排序的基本思想是：在数组中，有 N 个已经从小到大已经排好序的元素，要加入 1个新的 元素时，可以从数组的第 1 个元素开始，依次与新元素进行比较。 当数组中首次出现第i个元素的值大于新元素时，则新的元素就应当插在原来数组中的第i-1个元素与第i个元素之间。此时可以将数组中第i个元素之后(包括

39、第i个元素)的所有元素向后移动 1个 位置，将新元素插入，使它成为第i个元素。这样就可以得到已经排好序的 N+1个 元素。,10-4 在函数之间传递结构,向函数传递结构的地址 向函数中传递结构的地址要将函数的形参定义为指向结构的指针，在调用时要用结构的地址作为实参。,共 60 页 第 49 页,例：输入10本书的名称和单价，按照单价排序 #define NUM 10 struct book char name20; float price; ; main ( ) struct book term, booksNUM; int count; for ( count=0; countNUM; )

40、printf(“Enter book name and price. book %d=, count+1); scanf (”%s%f”, , /* 输出 */ ,10-4 在函数之间传递结构,共 60 页 第 50 页,sortbook ( term, pbook, count ) struct book term; /* 形参：结构变量term */ struct book *pbook;/* 指向结构数组首元素的指针pbook */ int count;/* 数组中已存入count个有序元素 */ int i; struct book *q, *pend = pbook

41、; for (i=0; iprice term.price) break; for ( q=pend-1; q=pbook; q- ) *(q+1) = *q; * pbook = term;/* 在pbook处插入新元素term */ printbook (pbook) struct book *pbook; printf(%-20s%6.2fn,pbook-name, pbook-price); ,10-4 在函数之间传递结构,共 60 页 第 51 页,联合：多个成员分量共同占用同一存储空间；成员分量之间是相互联系的，所进行的操作相互依赖。,10-5 联合,一、联合与结构的异同,联合与结

42、构都是由多个成员分量组成的一个整体；,联合与结构在定义、说明和使用(成员引用、指针)上十分相似。,结构：多个成员分量分别占用不同的存储空间构成一个整体；成员分量之间是相互独立的，所进行的各种操作互不影响。,共 60 页 第 52 页,实例 union u_type /* 定义联合类型u_type */ char ch; int i; long li; cnvt, * pcnvt; /* 说明联合类型的变量 */,10-5 联合,二、定义联合定义一般形式,union 联合类型名 数据类型 成员名1； 数据类型 成员名2； 数据类型 成员名n； ; 其中union为关键字。,共 60 页 第 53

43、 页,联合类型的变量占用内存空间的大小等于成员分量中最长的成员分量所占用内存的长度。 对于联合变量cnvt，其内存占用情况如图所示：,10-5 联合,占用4个字节,三、联合类型占用内存情况,共 60 页 第 54 页,例：分析以下程序的运行结果。 main ( ) union /* 定义联合并说明联合变量mix */ long i;/* 定义long型成员 */ int k;/* 定义int型成员 */ char ii;/* 定义char型成员 */ char s4;/* 定义char型数组成员 */ mix ; mix.i=0 x12345678; /* 通过联合中的long型成员i为联合赋

44、初值 */ printf (“mix.i=%lxn”, mix.i); printf (mix.k=%xn, mix.k); printf (mix.ii=%xn, mix.ii); printf (mix.s0=%xt mix.s1=%xn, mix.s0, mix.s1); printf (mix.s2=%xt mix.s3=%xn, mix.s2, mix.s3); ,10-5 联合,共 60 页 第 55 页,联合在内存中的数据存储情况： mix.i=0 x12345678,mix.i mix.k mix.ii mix.s0 mix.s1 mix.s2 mix.s3,= 1234567

45、8 = 5678 = 78 = 78 = 56 = 34 = 12,10-5 联合,共 60 页 第 56 页,10-6 用typedef定义数据类型,一、用户自定义类型,标准类型（如int、char、long、double等）：系统已经定义好的类型，用户可以直接使用，无须再进行定义。,用户自定义类型：用户根据自己的实际要求，自己定义的新的数据类型。 除结构和联合等类型之外，还可以用类型说明语句typedef定义新的类型来代替已有的类型。,共 60 页 第 57 页,实例 typedef int INTEGER; typedef float REAL; 在具有上述typedef语句的程序中，下

46、列语句就是等价的： int i,j; float pai； 等价于 INTEGER i, j; REAL pai;,二、typedef语句的一般形式,typedef 已定义的类型 新的类型,10-6 用typedef定义数据类型,共 60 页 第 58 页,例：改写“用结构变量求解两个复数之积”的程序 typedef int INTEGER; typedef struct complx /* 定义新的类型COMP（结构） */ INTEGER real, im; /* real为复数的实部，im为复数的虚部 */ COMP; main ( ) static COMP za=3,4, zb=5,

47、6; COMP z, cmult( ); /* 说明COMP型的变量z和函数cmult */ void cpr( );z=cmult(za, zb); cpr (za, zb, z); COMP cmult (za, zb)/* 计算复数zazb，返回COMP类型结果 */ COMP za, zb; COMP w; w.real = za.real * zb.real - za.im * zb.im; w.im = za.real * zb.im + za.im * zb.real; return (w); void cpr (za,zb,z) /* 输出复数zazb=z */ COMP za

48、, zb, z; printf (%d+%di)*(%d+%di)=, za.real, za.im, zb.real, zb.im); printf (%d+%di)n, z.real, z.im); ,10-6 用typedef定义数据类型,共 60 页 第 59 页,例： enum weekday 1,2,3,4,5,6,7; 定义变量：enum weekday a,b; 引用： a=1;b=7; 正确 a=8;b=0; 错误,10-7 枚举类型,枚举类型：列举出变量可能的取值,定义：enum 变量名 数据表列;,共 60 页 第 60 页,例： enum weekday 1,2,3,4

49、,5,6,7; 定义变量：enum weekday a,b; 引用： a=1;b=7; 正确 a=8;b=0; 错误,10-7 枚举类型,枚举类型：列举出变量可能的取值,定义：enum 变量名 数据表列;,共 60 页 第 61 页,10-8 链表,问题：,同样的数据结构，不同的数据量。例如：统计学生成绩，课程相同（数据的结构），统计方法相同（程序），但不同院系学生人数大不相同（数组元素个数）。,例：成绩 通信录 体检 奖学金 1 院 1800人 4 院 450人 7 院 230人,一、链表的基本概念,数组大小如何确定？ 如何合理使用内存空间？ 任意开辟或释放内存！,数组？结构数组问题？,共

50、60 页 第 62 页,10-8 链表,解决思路,共 60 页 第 63 页,10-8 链表,方法：,不用事先定义的固定大小的数组存储数据，而是利用结构变量按需动态分配。,按需要动态分配存储。 及时释放不必要的内存消耗。,作用：,共 60 页 第 64 页,10-8 链表,新问题：,用动态链表替代了固定规模的数组,动态存储分配函数每次分配的存储单元地址不一定是连续的，而所需处理的批量数据通常是一个整体（例如一个班的若干人的数据应该是连续的），各数据之间存在着接序关系。,解决方法用结构指针构成链表,在各动态数据区增加一个指针，通过这些指针将各动态数据区相互链接起来，形成动态链接存储链表。,共 6

51、0 页 第 65 页,10-8 链表,2、链表的功能,链表是一种重要的数据结构。它通过指针（链）将一组节点链接在一起，动态分配存储。,用链表处理不定长的结构数组。 链表是结构体类型的典型应用。,如何实现？,共 60 页 第 66 页,3、链表的组成,10-8 链表,链表: 由结点组成 头指针: 指向链表的开始，每个链表都必须有。 头结点：链表的第一个节点不存数据，可没有。 数据结点：保存数据和指针（指向其他结点）。 尾结点：没有指针的节点，置为“0”(NULL)。,头指针,表头结点,共 60 页 第 67 页,10-8 链表,4、链表的分类,链表分为单向链表和双向链表等。 单向链表：每个结点只

52、有一个指针，存放下一个结点的地址，所以只能从当前结点找到后续结点。,注意：动态链表中各结点元素没有自己的名字，只能靠指针维系元素之间的接续关系，一旦某个指针断开，后续元素就无法寻找。,共 60 页 第 68 页,10-8 链表,5、结点类型定义 结点特点：结构类型 struct stu unsigned num; /* 数据 */ float score; struct stu * next;/*递归定义指针*/ ; typedef struct stu XS；,共 60 页 第 69 页,10-8 链表,链表的建立 结点数据域的输出（数据访问） 结点的插入 结点的删除,6、单向链表的基本算法

53、,共 60 页 第 70 页,10-9 链表-建立链表的基本方法,定义结点的结构类型，说明表头指针 申请存储空间建立表头节点 从表头开始将数据节点插入到链表中 读取数据 生成新节点 将数据存入节点的成员变量中 将新节点插入到链表中 重复上述操作至输入结束,二、创建单向链表,共 60 页 第 71 页,10-8 链表-建立链表的基本方法,创建步骤： 按照结构的大小分配一块内存区域 将该区域的首地址赋给一个头指针 继续分配一块内存区域 将该区域的首地址分配给前一个结点的指针变量 继续上述过程，直到链表的尾。,共 60 页 第 72 页,10-8 链表-建立链表的基本方法,1、两个重要的库函数 动态

54、存储分配函数 原型：void * malloc(int size) 头文件：stdlib.h 。 功能：动态分配长度为size个字节的存储区。 返回值：分配成功，返回所分配区域的首地址。 分配失败，返回 0 。 注意：一般系统返回指向字符型数据的指针，而应用时需要指向结构类型的指针，所以要用强制类型转换。,例如： struct student * ps; ps=(struct student *)malloc(sizeof(struct student);,共 60 页 第 73 页,10-8 用指针处理链表(续1）,释放内存函数 原型：void free(void *p) 头文件：stdli

55、b.h 。 功能：释放p所指向的内存空间。 返回值：无 。 例如： free(ps); Ps是最近一次调用malloc函数时返回的值，,共 60 页 第 74 页,定义结点的结构，说明表头指针 例如：定义描述学生（姓名/住址/电话）的结点 struct node char name20,address20,phone15; struct node * link; /*定义node型结构指针 */ ; /* 定义结构 */ typedef struct node NODE /* 定义结点类型 */ NODE * head ; /* 说明头指针head */,10-8 链表-建立链表的基本方法,创

56、建链表的步骤：,共 60 页 第 75 页,申请存储空间建立表头节点 NODE * p; p = ( NODE * ) malloc ( sizeof (NODE) ) ; /* 开辟新存储区，申请表头节点 */ p-link = NULL;/* 将表头节点的link置为NULL*/ head = p;/* head指向表头节点 p */,(不含数据节点的空链表),10-8 链表-建立链表的基本方法,将malloc的返回值强制转换为NODE型,P指向最后 一个结点,共 60 页 第 76 页,插入第一个数据结点 NODE * p; p = ( NODE * ) malloc ( sizeof

57、(NODE) ) ; /* 申请新数据结点 */ gets(p-name );gets(p-address);gets(p-phone ); /* 用访问结构的方法将数据读入p所指向的结点成员 */ p-link=head-link; /*将头结点的NULL存入p的link中 */ head -link = p; /* 将数据结点 p 插在表头结点之后 */,10-8 链表-建立链表的基本方法,共 60 页 第 77 页,从表头开始将数据节点插入链表中（插下一个数据节点） p = ( NODE * ) malloc ( sizeof (NODE) ) ; /* 申请数据节点 */ gets(p-name); gets(p-address);gets(p-phone ); /* 按照访问结构的方法，将数据存入p所指向的节点 */ p-link = head-link; /* 将表头节点的link存入 p 的link中 */ head-link = p; /* 将数据结点 p 插在表头结点之后 */,数据节点,name2,10-8 链表-建立链表的基本方法,共 60 页 第 78 页,将节点插入到链表的链头（程序） 建立有 n 个数据