第八章第八章第八章第八章 结构和联合类型结构和联合类型结构和联合类型结构和联合类型武武汉汉大大学学计计算算机机学学院院武武汉汉大大学学计计算算机机学学院院主主讲讲：：谭谭成成予予nadinetan@教教 材材 : C程程 序序 设设 计计 导导 论论 结构类型定义与引用结构类型和指针结构数组链表联合类型本讲重点本讲重点本讲重点本讲重点 &结构类型是结构类型是一种一种构造数据类型构造数据类型&用途：把用途：把不同类型不同类型的数据组合成一个整体的数据组合成一个整体-------自定义自定义数据类型数据类型struct [结构名结构名]{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}；；成员类型可以是基本型或构造型(数组、指针或其他结构类型）struct是关键字,不能省略合法标识符可省:无名结构类型结构类型结构类型 例 struct student { long int order; char name[20]; char sex; short int age; int score[10]; char addr[30]; }; 结构类型定义描述结构的组织形式,不分配内存结构类型定义的作用域nameordersexagescoreaddr4字节2字节20字节1字节20字节30字节……..…..结构类型结构类型 例 struct id_card { char name[30]; char sex; char nationality[20]; struct date {int year,month,day; }birthday; char *p_addr; struct date signed_date; long number; char *office;}; 同一结构类型各成员不能同名,不同结构类型成员可以同名结构类型可以嵌套定义结构类型结构类型 例 struct wrong { char name[30]; int count; struct wrong a; }; ×结构类型不能递归定义结构类型结构类型 一般形式：一般形式：struct 结构名结构名{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}；；struct 结构名结构名 变量名表列变量名表列；；结构变量的定义结构变量的定义先定义先定义结构类型结构类型，再定义，再定义结构变量结构变量 例 struct student { long int order; char name[20]; char sex; short int age; int score[10]; char addr[30]; }; struct student stu1,stu2; /*struct coord表示屏幕上一个点的坐标表示屏幕上一个点的坐标*/例 struct coord{ float x;float y;}; struct coord first,second;结构变量的定义结构变量的定义 例 #define STUDENT struct student STUDENT { long int order; char name[20]; char sex; short int age; int score[10]; char addr[30]; }; STUDENT stu1,stu2; 结构变量的定义结构变量的定义 struct 结构名结构名{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}变量名表列变量名表列；；一般形式：定义结构类型的定义结构类型的同时同时定义定义结构变量结构变量结构变量的定义结构变量的定义 例 struct student { long int order; char name[20]; char sex; short int age; int score[10]; char addr[30]; }stu1,stu2; 例 struct coord{ float x;float y;}first,second;/*struct coord表示屏幕上一个点的坐标表示屏幕上一个点的坐标*/结构变量的定义结构变量的定义 struct{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}变量名表列变量名表列；；用用无名结构类型无名结构类型直接定义直接定义变量变量只能一次只能一次一般形式：一般形式：直接定义结构类型变量直接定义结构类型变量结构变量的定义结构变量的定义 例 struct { long int order; char name[20]; char sex; short int age; int score[10]; char addr[30]; }stu1,stu2; 例 struct { float x;float y;}first,second;/*struct coord表示屏幕上一个点的坐标表示屏幕上一个点的坐标*/结构变量的定义结构变量的定义 –说明说明•结构类型与结构类型变量概念不同结构类型与结构类型变量概念不同–类型类型:不分配内存；不分配内存； 变量变量:分配内存分配内存–类型类型:不能赋值、存取、运算不能赋值、存取、运算; 变量变量:可以可以•结构类型结构类型可嵌套可嵌套•结构类型成员名与程序中变量名可相同，不会混淆结构类型成员名与程序中变量名可相同，不会混淆•结构类型及变量的结构类型及变量的作用域与生存期作用域与生存期结构变量的定义结构变量的定义 例 struct date { int month; int day; int year; }; struct student { int num; char name[20]; struct date birthday; }stu;numnamebirthdaymonthdayyear结构变量的定义结构变量的定义 例 struct student { int num; char name[20]; struct date { int month; int day; int year; }birthday; }stu;numnamebirthdaymonthdayyear结构变量的定义结构变量的定义 结构类型变量的引用结构类型变量的引用引用规则引用规则• 结构类型变量结构类型变量不能整体引用不能整体引用,只能引用变量成员只能引用变量成员 引用方式：结构类型变量名引用方式：结构类型变量名.成员名成员名•可以将一个结构类型变量赋值给另一个结构类型变量可以将一个结构类型变量赋值给另一个结构类型变量•结构类型嵌套时结构类型嵌套时逐级引用逐级引用 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2; stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score; stu1.age++;成员成员(分量分量)运算符运算符优先级优先级: 1结合性结合性:从左向右从左向右结构类型变量结构类型变量不能整体引用不能整体引用,只能引用变量成员只能引用变量成员引用方式：引用方式： 结构类型变量名结构类型变量名.成员名成员名结构类型变量的引用结构类型变量的引用 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2; printf(“%d,%s,%c,%d,%f,%s\n”,stu1); ( )stu1={101,“Wan Lin”,‘M’,19,87.5,“DaLian”}; ( )结构类型变量的引用结构类型变量的引用不能整体引用不能整体引用 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2; if(stu1==stu2)…….. ( )结构类型变量的引用不能整体引用不能整体引用 结构类型嵌套时结构类型嵌套时逐级引用逐级引用例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2; stu2=stu1; ( )结构类型变量的引用结构类型变量的引用 例 struct student { int num; char name[20]; struct date { int month; int day; int year; }birthday; }stu1,stu2;numnamebirthdaymonthdayyearstu1.birthday.month=12;结构类型嵌套时结构类型嵌套时逐级引用逐级引用结构类型变量的引用结构类型变量的引用 /*L8-1.C: 计算某个同学计算某个同学5门课程成绩的平均分。
门课程成绩的平均分/#include int main(void){ struct student{char *name; /*姓名姓名*/long order; /*学号学号*/int score[5]; /*成绩成绩*/float average; /*平均分平均分*/}who;int sum=0,n;printf(“input name,order and 5 scores\n”);scanf(“%s%ld”,who.name,&who.order);char name[20]; for(n=0;n<5;n++)scanf(“%d”,&who.score[n]);who.average=0.0;for(n=0;n<5;n++)sum+=who.score[n];who.average=(float)sum/5; printf(“\nname=%s\torder=%ld\n”,who.name.who.order); printf(“average=%f\n”,who.average); return 0;} /*L8-2.C: 输入矩形左上角和右下角坐标，计算该矩形长和宽及面积。
输入矩形左上角和右下角坐标，计算该矩形长和宽及面积/#include #include int main(void){ float length,width,area; struct coord{float x,y; }; struct rectangle{ struct coord topleft,bottomrt；；}mybox; printf(“enter the top left x,y coordinate:\n”); scanf(“%f%f”,&mybox.topleft.x,&mybox.topleft.y); printf(“enter the bottom right x,y coordinate:\n”); scanf(“%f%f”,&mybox.bottomrt.x,&mybox.bottomrt.y); length=fabs((double)(mybox.bottomrt.x-bybox.topleft.x)); width=fabs((double)(mybox.topleft.y-mybox.bottomrt.y)); area=length*width; printf(“\nlength=%f\twidth=%f\n”,length,width); printf(“area=%f\n”,area); return 0; } struct 结构类型名结构类型名{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}；；struct 结构类型名结构类型名 结构类型变量结构类型变量={初始数据初始数据}；；形式一：形式一：结构变量的初始化结构变量的初始化 例 struct student { int num; char name[20]; char sex; int age; char addr[30]; }; struct student stu1={112,“Wang Lin”,‘M’,19, “200 Beijing Road”};结构变量的初始化结构变量的初始化 例 struct student { char name[20]; long order; int score[5]; float average; }; struct student who={“Wang Lin”,031112,{92,91,89,87,94},0.0};结构变量的初始化结构变量的初始化 例 struct coord { float x,y;}; struct rectangle{struct coord topleft;struct coord bottomrt; }; struct rectangle mybox={{1.8,8.3},{12.4,1.29}};结构变量的初始化结构变量的初始化 struct 结构类型名结构类型名{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}结构类型变量结构类型变量={初始数据初始数据}；；形式二：形式二：结构变量的初始化结构变量的初始化 例 struct student { int num; char name[20]; char sex; int age; char addr[30]; }stu1={112,“Wang Lin”,‘M’,19, “200 Beijing Road”}; 初值表中初值的个数初值表中初值的个数<=结构结构变量长远的个数变量长远的个数结构变量的初始化结构变量的初始化 例 struct student { char name[20]; long order; int score[5]; float average; }who={“Wang Lin”,031112,{92,91,89,87,94},0.0};例 struct coord { float x,y;}; struct rectangle{struct coord topleft;struct coord bottomrt; } mybox={{1.8,8.3},{12.4,1.29} };结构变量的初始化结构变量的初始化 struct{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}结构类型变量结构类型变量={初始数据初始数据}；；形式三：形式三：结构变量的初始化结构变量的初始化 例 struct { int num; char name[20]; char sex; int age; char addr[30]; }stu1={112,“Wang Lin”,‘M’,19, “200 Beijing Road”}; 结构变量的初始化结构变量的初始化 例 struct { char name[20]; long order; int score[5]; float average; }who={“Wang Lin”,031112,{92,91,89,87,94},0.0};例 struct coord { float x,y;}; struct {struct coord topleft;struct coord bottomrt; } mybox={{1.8,8.3},{12.4,1.29}};结构变量的初始化结构变量的初始化 结构类型定义与引用结构类型和指针结构数组链表联合类型本讲重点本讲重点本讲重点本讲重点 指向结构类型变量的指针指向结构类型变量的指针–定义形式：定义形式：struct 结构类型名结构类型名 *结构类型指针名结构类型指针名;例例 struct student *p;存放结构类型变量在内存的起始地址struct student stu1;struct student *p=&stu1;stu1.num=101; (*p).num=101结构类型和指针结构类型和指针 numnamesexagestupstruct student { int num; char name[20]; char sex; int age; }stu;struct student *p=&stu;结构类型和指针结构类型和指针 (*结构类型指针名结构类型指针名).成员名成员名结构类型指针名结构类型指针名->成员名成员名结构类型变量名结构类型变量名.成员名成员名•使用结构类型指针变量引用成员形式指向运算符优先级: 1结合方向：从左向右例 int n; int *p=&n; *p=10; n=10结构类型和指针结构类型和指针 int main(void){ struct student { long int num; char name[20]; char sex; float score; }stu_1,*p; p=&stu_1; stu_1.num=89101; strcpy(stu_1.name,"Li Lin"); p->sex='M'; p->score=89.5; printf("\nNo:%ld\nname:%s\nsex:%c\nscore:%f\n", (*p).num,p->name,stu_1.sex,p->score); return 0;}例例8.3 指向结构类型的指针变量指向结构类型的指针变量 struct student{ int num; char name[20]; char sex; int age;}stu[3]={{10101,"Li Lin",'M',18}, {10102,"Zhang Fun",'M',19}, {10104,"Wang Min",'F',20}};int main(void){ struct student *p; for(p=stu;pnum,p->name,p->sex,p->age); return 0;}例 指向结构类型数组的指针numnamesexagestu[0]pstu[1]stu[2]p+1 /*L8-3.C: 分析下面程序的运行结果*/#include int main(void){struct {int x;int y;}a[2]={{1,2},{3,4}},*p=a;printf(“%d,”,++p->x);printf(%d\n”,(++p)->x);return 0;}pa[0]a[1]p123422,3结构类型和指针结构类型和指针 结构类型定义与引用结构类型和指针结构数组链表联合类型本讲重点本讲重点本讲重点本讲重点 形式一: struct student { int num; char name[20]; char sex; int age; };struct student stu[2];numnamesexagenumnamesexagestu[0]stu[1]25B结构数组的定义结构数组的定义三种形式：三种形式： 形式二: struct student { int num; char name[20]; char sex; int age; }stu[2];numnamesexagenumnamesexagestu[0]stu[1]25B结构数组的定义结构数组的定义 形式三: struct { int num; char name[20]; char sex; int age; }stu[2];numnamesexagenumnamesexagestu[0]stu[1]25B结构数组的定义结构数组的定义 分行初始化: struct student { int num; char name[20]; char sex; int age; };struct student stu[ ]={{100,“Wang Lin”,‘M’,20}, {101,“Li Gang”,‘M’,19}, {110,“Liu Yan”,‘F’,19}}; 全部初始化时维数可省全部初始化时维数可省结构数组初始化结构数组初始化 顺序初始化: struct student { int num; char name[20]; char sex; int age; };struct student stu[ ]={100,“Wang Lin”,‘M’,20, 101,“Li Gang”,‘M’,19, 110,“Liu Yan”,‘F’,19}; 结构数组初始化结构数组初始化 例 struct { int num; char name[20]; char sex; int age; }stu[ ]={{……},{……},{……}};例 struct student { int num; char name[20]; char sex; int age; }stu[ ]={{……},{……},{……}};结构数组初始化结构数组初始化 结构数组引用结构数组引用引用方式：引用方式： 结构数组名结构数组名[下标下标].成员名成员名 struct student { int num; char name[20]; char sex; int age; }str[3];stu[1].age++;strcpy(stu[0].name,”ZhaoDa”); 例例8.4 统计后选人选票统计后选人选票struct person{ char name[20]; int count;}leader[3]={“Li”,0,“Zhang”,0,”Wang“,0}; int main(void){ int i,j; char leader_name[20]; for(i=1;i<=10;i++) { scanf("%s",leader_name); for(j=0;j<3;j++)if(strcmp(leader_name,leader[j].name)==0) leader[j].count++; } for(i=0;i<3;i++) printf("%5s:%d\n",leader[i].name,leader[i].count); return 0;}namecountLiZhangWang000 应用举例应用举例 例例8.5 8.5 编程，输入编程，输入1010个学生的姓名和数学、英语和语文三门功个学生的姓名和数学、英语和语文三门功课的成绩，计算每个学生的平均成绩，并输出学生姓名和平均课的成绩，计算每个学生的平均成绩，并输出学生姓名和平均成绩。
成绩include #define N 30struct student{char name[20]; /*学生姓名学生姓名*/float math; /*数学成绩数学成绩*/float eng; /*英语成绩英语成绩*/float cuit; /*语文成绩语文成绩*/float aver; /*平均成绩平均成绩*/}; int main( void){ struct student s[N];int i;for(i=0;i
输输出出排序以后的每个整数和它原来的序号排序以后的每个整数和它原来的序号include #define N 10struct data{int no;int num;};int main(void ){struct data x[N],temp;int i,j;/*输入输入10个整数个整数*/printf(“输入输入10个整数：个整数：”);for(i=0;i
老师指定从第个小孩围成一圈，依次编号老师指定从第w个小孩开始个小孩开始报数，报数为报数，报数为s的小孩出列；然后从下一个小孩开始重新报数，重复上述过程，的小孩出列；然后从下一个小孩开始重新报数，重复上述过程，直到所有小孩都出列直到所有小孩都出列分析：数据结构，如何表示队列和小孩？分析：数据结构，如何表示队列和小孩？ 每个小孩用一个结构类型表示：每个小孩用一个结构类型表示： struct child{ int ino; /*当前小孩编号当前小孩编号*/ int next; }; /*下一个小孩编号下一个小孩编号*/ n个小孩组成队列用结构数组表示：个小孩组成队列用结构数组表示： struct child link[N+1]; /*下标为下标为0的元素不使用的元素不使用*/ N为可以容纳的人数上限为可以容纳的人数上限约瑟夫问题约瑟夫问题 分析：算法：分析：算法： （（1）初始化队列）初始化队列link: link[k].nextk+1 k=1,……,n-1 link[n].next1 （（2）开始报数）开始报数 if(link[k].ino!=0) 如果第如果第k个小孩在队列中个小孩在队列中 I+1I 报数变量报数变量I 加加1 （（3）如果）如果I >=s，则第，则第k个人出列，转（个人出列，转（5），否则转（），否则转（4）） （（4）） k更新为下一个小孩编号更新为下一个小孩编号 klink[k].next, 转（转（2）） （（5）输出第）输出第k个小孩编号个小孩编号link[k].ino （（6））link[k].ino0表示已经出列表示已经出列 （（7）已经出列人数加）已经出列人数加1count （（8）） 如果如果count等于总人数等于总人数n，则转（，则转（9）） ，否则转（，否则转（2）） （（9）算法结束）算法结束约瑟夫问题约瑟夫问题 #include #define N 100 /*程序能够处理的人数上限程序能够处理的人数上限*/int main(){struct child{ int ino,next;}link[N+1]; int I,n_child,which,com_out,k,count;/*输入已知数据：小孩实际人数、初始报数小孩编号、出列的编号输入已知数据：小孩实际人数、初始报数小孩编号、出列的编号*/ scanf(“%d%d%d”,&n_child,&which,&come_out);if(n_child>N) printf(“too many to hold\n”);else {/*初始化队列初始化队列*/ for(I=1;I<=n_child;I++){ if(I==n_child) link[I].next=1; else link[I].next=I+1; link[I].ino=I;} /*开始报数开始报数*/ k=which;/*初始报数小孩编号初始报数小孩编号*/ count=0;/*出列人数出列人数*/ while(count!=n_child) {I=0;/*报数的数值报数的数值*/while(1){if(link[k].ino!=0) I++;if(I>=come_out) break;k=link[k].next;}printf(“%d\t”,link[k].ino);/*输出出队小孩编号输出出队小孩编号*/link[k].ino=0;/*第第k个小孩出队个小孩出队*/count++; /*出队人数加出队人数加1*/if(count%10==0)printf(“\n”); } printf(“bye!\n”); } return 0;} 例例8.8 编程实现两个复数的乘法运算。
编程实现两个复数的乘法运算分析：分析：一个复数由实部和虚部组成，可以用含有两个浮点数类型的成员的结构类型一个复数由实部和虚部组成，可以用含有两个浮点数类型的成员的结构类型来表示：来表示：struct complex{ float re; /*实部实部*/ float im; /*虚部虚部*/ }; struct complex x,y; x*y的结果的实部为的结果的实部为x.re*y.re-x.im*y.im x*y的结果的虚部为的结果的虚部为x.re*y.im +x.im*y.re #include struct complex{ float re; float im;};int main( void){ struct complex x, y, z; printf(“请输入第请输入第1个复数个复数\n”);printf(“实部：实部：”);scanf(“%f”,&x.re);printf(“虚部虚部”);scanf(“%f”,&x.im);printf(“请输入第请输入第2个复数个复数\n”);printf(“实部：实部：”);scanf(“%f”,&y.re);printf(“虚部虚部”);scanf(“%f”,&y.im);z.re=x.re*y.re - x.im*y.im;z.im=x.re*y.im + x.im*y.re;printf(“两个复数相乘，结果：两个复数相乘，结果：”);if (z.im<0)printf(“%8.2f%8.2fi\n”,z.re,z.im);else printf(“%8.2f+%8.2fi\n”,z.re,z.im);return 0; } 例例8.9 编程计算当前时间的下一秒的时间。
编程计算当前时间的下一秒的时间分析：分析：时间由时、分、秒构成，采用一个结构类型来表示时间：时间由时、分、秒构成，采用一个结构类型来表示时间：struct time{ int hour; /*时时*/ int minutes; /*分分*/ int second; /*秒秒*/ }; #include struct time{ int hour; int minutes; int second;};int main(void ){ struct time now,ntime; printf(“请输入当前时间，时间格式：时：分：秒请输入当前时间，时间格式：时：分：秒\n”); scanf(“%d:%d:%d”,&now.hour,&now.minutes,&now.second); ntime=now; ntime.second++; if (ntime.second>=60) { ntime.second=0; ntime.minutes++; if (ntime.minutes>=60) { ntime.minutes=0; ntime.hour++; if (ntime.hour>=24) ntime.hour=0; } } printf(“下一秒时间：下一秒时间：%d:%d:%d\n”,ntime.hour, ntime.minutes, ntime.second);return 0;} 结构类型定义与引用结构类型和指针结构数组链表联合类型本讲重点本讲重点本讲重点本讲重点 引用自身的结构引用自身的结构例如，例如， struct tnode{char word[20];int count;struct tnode*left;struct tnode*right;};结构成员：指向自身所属的结结构成员：指向自身所属的结构类型的对象构类型的对象常用于构造各种数据结构：队列、链表、树、图等。
常用于构造各种数据结构：队列、链表、树、图等 链接方式存接方式存储的的线性表性表简称称为链表（表（Linked List）），是常，是常见的数据结构见的数据结构链表的具体存表的具体存储表示表示为：： ①① 用一用一组任意的存任意的存储单元来存放元来存放线性表的性表的结点（点（这组存存储单元既可以是元既可以是连续的，也可以是不的，也可以是不连续的）的） ②② 链表中表中结点的点的逻辑次序和物理次序不一定相同次序和物理次序不一定相同为了能正确表示了能正确表示结点点间的的逻辑关系，在存关系，在存储每个每个结点点值的同的同时，，还必必须存存储指示其后指示其后继结点的地址（或位置）信息点的地址（或位置）信息（称（称为指指针（（pointer）或）或链(link)））什么是链表？什么是链表？ ┌──┬──┐│data│next│└──┴──┘ data域域--存放结点值的数据域存放结点值的数据域 next域域--存放结点的直接后继的地址（位置）的指针域存放结点的直接后继的地址（位置）的指针域（链域）（链域）例如：例如：struct node{ int data; struct node *next;};链表的结点结构链表的结点结构 单链表：单链表：每个每个结点只有一个点只有一个链域的域的链表表。
NULLheadhead：链表的头指针：链表的头指针链表分类链表分类 headhead循环链表循环链表链表分类链表分类 双向链表：双向链表：每个每个结点有点有两个两个链域的域的链表表headNULLheadNULL链表分类链表分类 NULLhead123链表中结点都在程序中定义，不是临时开辟的，链表中结点都在程序中定义，不是临时开辟的，用完后用完后不能释放不能释放，并且，链表中可以创建的，并且，链表中可以创建的结点数有限制结点数有限制称为为“静态链表静态链表”静态链表静态链表 #include #include struct node{ int data; struct node *next;};int main(){ struct node a,b,c,*head;*p; a.data=1; b.data=2; c.data=3; head=&a; a.next=&b; b.next=&c; c.next=NULL; p=head; do{printf(“%d\t”,p->data); p=p->next; }while(p!=NULL); return 0;} «建立链表建立链表«遍历链表遍历链表«删除链表中的结点删除链表中的结点«插入结点插入结点 以单链表为例进行说明。
以单链表为例进行说明对链表的操作对链表的操作 结点类型：结点类型： struct child{ char name[20];struct child *next; }*new,*head,*tail;headnewNULL先进先出链表先进先出链表(1)头指针置空头指针置空head=NULL;(2)创建新结点创建新结点new=(struct child*)malloc(sizeof(struct child));new->next=NULL; (3)新结点连入链表新结点连入链表 if(head==NULL){ head=new; tail=new;} else tail->next=new;重复（重复（2）、（）、（3）步直到链表创建完成步直到链表创建完成建立链表建立链表(尾插法建表）尾插法建表） 建立链表建立链表(尾插法建表）尾插法建表）#include #include struct node{int data;struct node *next;};struct node * creatrightlink-_1(){struct node *head,*new,*tail; int n;head=NULL; scanf(“%d”,&n);while(n!=-1){new=(struct node *)malloc(sizeof(struct node));new->data=n;new->next=NULL;if(head==NULL)head=new;elsetail->next=new;tail=new;scanf(“%d”,&n);} return (head);} 建立链表建立链表(尾插法建表）尾插法建表）#include #include struct node{int data;struct node *next;};int creatrightlink_2(struct node **phead){struct node *new,*tail; int n,k=0;*phead=NULL; scanf(“%d”,&n);while(n!=-1){new=(struct node *)malloc(sizeof(struct node));new->data=n;new->next=NULL;if(*phead==NULL)*phead=new;elsetail->next=new;tail=new;scanf(“%d”,&n); k++;} return (k);} (1)头指针置空头指针置空head=NULL;(2)创建新结点创建新结点new=(struct child*)malloc(sizeof(struct child)); (3)新结点连入链表新结点连入链表 new->next=head; head=new;重复（重复（2）、（）、（3）步直到链表创建完成。
步直到链表创建完成 headnewNULLhead后进先出链表后进先出链表建立链表建立链表(头插法建表）头插法建表） 建立链表建立链表(头插法建表）头插法建表）#include #include struct node{int data;struct node *next;};struct node * creatleftlink_1(){struct node *head,*new; int n;head=NULL; scanf(“%d”,&n);while(n!=-1){new=(struct node *)malloc(sizeof(struct node));new->data=n;new->next=head;head=new;scanf(“%d”,&n);} return (head);} 建立链表建立链表(头插法建表）头插法建表）#include #include struct node{int data;struct node *next;};int creatleftlink_2(struct node **phead){struct node *new; int n,k=0;*phead=NULL; scanf(“%d”,&n);while(n!=-1){new=(struct node *)malloc(sizeof(struct node));new->data=n;new->next=head;*phead=new;scanf(“%d”,&n);k++;} return (k);} (1)head=NULL;(2)创建新结点创建新结点new=(struct child*)malloc(sizeof(struct child));(3)找到标记结点找到标记结点marker（新结点插入在标记结点的后面）（新结点插入在标记结点的后面）(4)新结点连入链表新结点连入链表 new->next=marker->next; marker->next=new;;重复（重复（2）、（）、（3）、（）、（4）步直到链表创建完成。
步直到链表创建完成 headnewNULLmarker在链表中间插入结点，一般用于建立有序链表在链表中间插入结点，一般用于建立有序链表建立链表建立链表 p=head; while(p!=NULL) {puts(p->name);/*输出当前结点数据输出当前结点数据*/p=p->next;/*p更新为下一个结点地址更新为下一个结点地址*/ } 功能：将整个链表的数据从头到尾扫描一遍功能：将整个链表的数据从头到尾扫描一遍遍历链表遍历链表#include #include struct node{int data;struct node *next;};void printlink(struct node *head){struct node *p;p=head;while(p!=NULL){printf(“%d\n”,p->data;p=p->next;} } （（1）找到要删除的结点，）找到要删除的结点，current指向该结点，指向该结点，p指向要删指向要删除结点的前趋结点。
除结点的前趋结点2）如果要删除的结点为头结点，则）如果要删除的结点为头结点，则 head=current->next;（（3）如果要删除的结点不是头结点，则）如果要删除的结点不是头结点，则 p->next=current->next（（4）释放已经删除的结点）释放已经删除的结点 free(current);NULLheadcurrent从链表中删除结点从链表中删除结点 从链表中删除结点从链表中删除结点#include #include struct node{int data;struct node *next;};struct node * deletelink_1(struct node *head,int n){struct node *p,*q;p=head;while(p->data!=n&&p->next!=NULL){q=p;p=p->next;}if(p->data==n) /*找到找到*/{if(p==head) /*被删除的结点是链头被删除的结点是链头*/head=p->next;else /*被删除的结点不是链头被删除的结点不是链头*/q->next=p->next;free(p);}return (head);} 从链表中删除结点从链表中删除结点#include #include struct node{int data;struct node *next;};int deletelink_2(struct node **phead,int n){struct node *p,*q;p=*phead;while(p->data!=n&&p->next!=NULL){q=p;p=p->next;}if(p->data==n) /*找到找到*/{if(p==*phead) /*被删除的结点是链头被删除的结点是链头*/*phead=p->next;else /*被删除的结点不是链头被删除的结点不是链头*/q->next=p->next;free(p);return (1);}elsereturn (0);} 向一个有序链表中插入新结点（向一个有序链表中插入新结点（new)。
1）找到要插入结点的位置，插入在）找到要插入结点的位置，插入在r指向的结点前面，指向的结点前面， p指向的结点后面指向的结点后面2）如果要插入在头结点前面，则）如果要插入在头结点前面，则new->next=head;head=new;（（3）如果要插入的位置不是头结点前面，则）如果要插入的位置不是头结点前面，则 new->next=r;p->next=new;将一个结点插入一个已经存在的链表中，例如插入在链将一个结点插入一个已经存在的链表中，例如插入在链表尾部、头部或者插入在一个有序链表中表尾部、头部或者插入在一个有序链表中插入结点插入结点 插入结点插入结点#include #include struct node{int data;struct node *next;};struct node * insertsort(struct node *head, int n){struct node *new,*p,*q; new=(struct node *)malloc(sizeof(struct node));new->data=n; p=head;while(p!=NULL &&p->datanext;}if(p==head){new->next=head;head=new;} else{q->next=new;new->next=p;}return (head);} 插入结点插入结点struct node * creatsortlink(struct node *head){int n;head=NULL; scanf(“%d”, &n); while(n!=-1){head=insertsort(head,n);scanf(“%d”, &n);}return head;} 结构类型定义与引用结构类型和指针结构数组链表联合类型本讲重点本讲重点本讲重点本讲重点 &构造数据类型构造数据类型,也叫共用体也叫共用体&用途：使几个不同类型的变量用途：使几个不同类型的变量共占一段内存共占一段内存(相互覆盖）相互覆盖）union 联合名联合名{ 类型标识符类型标识符 成员名；成员名； 类型标识符类型标识符 成员名；成员名； …………….}；；例 union data { int i; char ch; float f; };fchi类型定义不分配内存联合的定义联合的定义联合类型定义联合类型定义定义形式：定义形式： 形式一: union data { int i; char ch; float f; }a,b;形式二: union data { int i; char ch; float f; }; union data a,b,c,*p,d[3];形式三: union { int i; char ch; float f; }a,b,c;联合变量的定义联合变量的定义 fchifchiab联合变量定义分配内存,长度=最长成员所占字节数联合变量任何时刻只有一个成员存在联合变量的定义联合变量的定义 引用方式：引用方式：联合指针名联合指针名->成员名成员名联合变量名联合变量名.成员名成员名(*联合指针名联合指针名).成员名成员名union data { int i; char ch; float f; }; union data a,b,c,*p,d[3];a.i a.ch a.fp->i p->ch p->f(*p).i (*p).ch (*p).fd[0].i d[0].ch d[0].f联合变量引用联合变量引用 例 union { int i; char ch; float f; }a; a=1; () •引用规则引用规则–不能引用联合变量，只能不能引用联合变量，只能引用其成员引用其成员联合变量引用联合变量引用 例 a.i=1; a.ch=‘a’; a.f=1.5; printf(“%d”,a.i); (编译通过，运行结果不对) 联合变量引用联合变量引用•引用规则引用规则–联合变量中起作用的成员是联合变量中起作用的成员是最后一次存放的成员最后一次存放的成员 例 union { int i; char ch; float f; }a={1,’a’,1.5}; () 联合变量引用联合变量引用•引用规则引用规则–不能不能在定义联合变量时在定义联合变量时初始化初始化 例 float x; union { int i; char ch; float f; }a,b; a.i=1; a.ch=‘a’; a.f=1.5; b=a; () x=a.f; ()•引用规则引用规则–可以用一个联合变量为另一个变量赋值可以用一个联合变量为另一个变量赋值联合变量引用联合变量引用 例例 将一个整数按字节输出将一个整数按字节输出01100001 01000001低字节高字节0100000101100001ch[0]ch[1]i=60501ch0=101,ch1=141ch0=A,ch1=aint main(){ union int_char { int i; char ch[2]; }x; x.i=24897; printf("i=%o\n",x.i); printf("ch0=%o,ch1=%o\n ch0=%c,ch1=%c\n", x.ch[0],x.ch[1],x.ch[0],x.ch[1]); return 0;}运行结果：运行结果： struct node{ char ch[2]; int k;}a;union node{ char ch[2]; int k;}b;achkbch k变量的各成员同时存在任一时刻只有一个成员存在•区别区别：存储方式不同：存储方式不同•联系联系：两者可相互嵌套：两者可相互嵌套结构类型与联合结构类型与联合 例例 结构类型中嵌套联合结构类型中嵌套联合 name numsexjobclasspositionLiWang10112086FMST501prof循环循环n次次读入姓名、号码、性别、职务读入姓名、号码、性别、职务job==‘s’真真真真假假假假读入读入class读入读入position输出输出“输入错输入错”循环循环n次次job==‘s’真真假假输出输出:姓名姓名,号码号码,性别性别,职业职业,班级班级输出输出:姓名姓名,号码号码,性别性别,职业职业,职务职务job==‘t’struct{ int num; char name[10]; char sex; char job; union { int class; char position[10]; }category;}person[2]; 例联合中嵌套结构类型，机器字数据与字节数据的处理例联合中嵌套结构类型，机器字数据与字节数据的处理 00010010 00110100低字节高字节0011010000010010lowhigh0x123400010010 11111111低字节高字节1111111100010010lowhigh0x12ffstruct w_tag{ char low; char high;};union u_tag{ struct w_tag byte_acc; int word_acc;}u_acc;word_accbyte_acc.lowbyte_acc.highu_acc 例例 编程，输入一个长整型的整数，分别取出该数的各字节的值。
分析：分析：定义一个联合类型如下所示：union data{ char s[5]; long n; }; 例 编程，输入一个长整型的整数，分别取出该数的各字节的值include union data{char s[5]; long n; };int main(void ){union data x;int i;printf(“输入一个长整数：”);scanf(“%x”,&x.n);printf(“各字节取值如下：\n”); for (i=0;i
并输出指定姓名学生的当前住址struct off_school{int strnum; /*街道号*/char strname[20]; /*街道名*/char city[20]; /*城市名*/ };struct in_school{int roomnum; /*房间号*/ char dorm[20]; /*楼房名*/ };union address{struct off_school town;struct in_school gown; };struct student{int num; /*学号*/char name[20]; /*姓名*/char off_in; /*是否在学校住*/union address ad; /*当前住址*/ }; #include ＃include #define N 3struct off_school{int strnum; char strname[20]; char city[20]; };struct in_school{int roomnum; char dorm[20]; };union address{struct off_school town;struct in_school gown;};struct student{int num; char name[20]; char off_in; union address ad; }; int main( void){struct student s[N]; char name[20]; int i;for (i=0;i
