第十章 结构体与链表 西安工程大学

本章内容: 10.1 定义和使用结构体变量 10.2 结构体数组 10.3 结构体指针 10.4 链表 10.5 共用体 10.6 用typedef声明新类型名

10.1 定义和使用结构体变量 10.1.1 定义结构体类型 结构体是一种构造数据类型 用途：把不同类型的数据组合成一个整体 结构体类型定义的一般形式: 合法标识符 可省:无名结构体 struct [结构体名] { 类型标识符 成员名； ……………. }； struct是关键字, 不能省略 成员类型可以是 基本型或构造型

… ….. 例 struct student { int num; char name[20]; char sex; int age; score addr 2字节 20字节 1字节 4字节 30字节 … ….. 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }; 结构体类型定义描述结构 的组织形式,不分配内存 结构体类型定义的作用域

10.1.2定义结构体变量 1 先定义结构体类型，再定义结构体变量 一般形式： struct 结构体名 { 类型标识符 成员名； ……………. }； struct 结构体名 变量名表列； 例 #define STUDENT struct student STUDENT { int num; char name[20]; char sex; int age; float score; char addr[30]; }; STUDENT stu1,stu2; 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }; struct student stu1,stu2;

2 定义结构体类型的同时定义结构体变量 一般形式： 例 struct student { int num; char name[20]; 类型标识符 成员名； ……………. }变量名表列； 例 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2;

3 直接定义结构体变量 一般形式： 例 struct { int num; char name[20]; char sex; 类型标识符 成员名； ……………. }变量名表列； 例 struct { int num; char name[20]; char sex; int age; float score; char addr[30]; }stu1,stu2; 用无名结构体直接定义 变量只能一次

说明: 结构体类型与结构体变量概念不同 结构体可嵌套 结构体成员名与程序中变量名可相同，不会混淆 结构体类型及变量的作用域与生存期 类型:不分配内存； 变量:分配内存 类型:不能赋值、存取、运算; 变量:可以 结构体可嵌套 结构体成员名与程序中变量名可相同，不会混淆 结构体类型及变量的作用域与生存期 例 struct date { int month; int day; int year; }; struct student { int num; char name[20]; struct date birthday; }stu; num name birthday month day year 例 struct student { int num; char name[20]; struct date { int month; int day; int year; }birthday; }stu; num name birthday month day year

10.1.3 结构体变量的引用和初始化 结构体变量不能整体引用,只能引用变量成员 引用方式： 结构体变量名.成员名 引用方式： 结构体变量名.成员名 可以将一个结构体变量赋值给另一个结构体变量 结构体嵌套时逐级引用 例 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++; 例 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]; struct date { int month; int day; int year; }birthday; }stu1,stu2; num name birthday month day year stu1.birthday.month=12; 例 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]; char sex; 类型标识符 成员名； ……………. }； 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 结构体名 { 类型标识符 成员名； ……………. }结构体变量={初始数据}； 例 struct student 类型标识符 成员名； ……………. }结构体变量={初始数据}； 例 struct student { int num; char name[20]; char sex; int age; char addr[30]; }stu1={112,“Wang Lin”,‘M’,19, “200 Beijing Road”};

形式三： struct { 类型标识符 成员名； ……………. }结构体变量={初始数据}； 例 struct { int num; 类型标识符 成员名； ……………. }结构体变量={初始数据}； 例 struct { int num; char name[20]; char sex; int age; char addr[30]; }stu1={112,“Wang Lin”,‘M’,19, “200 Beijing Road”};

10.2 结构体数组 10.2.1 结构体数组的定义 形式一: struct student { int num; name sex age stu[0] stu[1] 25B 形式一: struct student { int num; char name[20]; char sex; int age; }; struct student stu[2]; 形式二: struct student { int num; char name[20]; char sex; int age; }stu[2]; 形式三: struct { int num; char name[20]; char sex; int age; }stu[2];

10.2.2 结构体数组初始化 分行初始化: 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 student { int num; char name[20]; char sex; int age; }stu[ ]={{……},{……},{……}}; 例 struct { int num; char name[20]; char sex; int age; }stu[ ]={{……},{……},{……}};

strcpy(stu[0].name,”ZhaoDa”); 10.2.3 结构体数组引用 引用方式：结构体数组名[下标].成员名 struct student { int num; char name[20]; char sex; int age; }str[3]; stu[1].age++; strcpy(stu[0].name,”ZhaoDa”);

}leader[3]={“Li”,0,“Zhang”,0,”Wang“,0}; main() struct person { char name[20]; int count; }leader[3]={“Li”,0,“Zhang”,0,”Wang“,0}; main() { 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); 例11.1 统计后选人选票，设有3个候选人，每次输入一个得票的候选人的名字，要求最后输出个人的得票结果。 name count Li Zhang Wang

10.3 结构体指针 10.3.1 指向结构体变量的指针 1 定义形式：struct 结构体名 *结构体指针名; 例 struct student *p; num name sex age stu p struct student { int num; char name[20]; char sex; int age; }stu; struct student *p=&stu; 2 使用结构体指针变量引用成员形式 存放结构体变量在内存的起始地址 (*结构体指针名).成员名 结构体指针名->成员名 结构体变量名.成员名 例 int n; int *p=&n; *p=10;  n=10 struct student stu1; struct student *p=&stu1; stu1.num=101;  (*p).num=101

main() { 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); } 例10.2 指向结构体的指针变量应用举例

10.3.2指向结构体数组的指针 例10.3 指向结构体数组的指针的应用 struct student { int num; 例10.3 指向结构体数组的指针的应用 num name sex age stu[0] p stu[1] stu[2] p+1 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}}; main() { struct student *p; for(p=stu;p<stu+3;p++) printf("%d%s%c%d\n",p->num,p->name,p->sex,p->age); }

10.3.3 用指向结构体的指针作函数参数 用结构体变量的成员作参数----值传递 用指向结构体变量或数组的指针作参数----地址传 递 用结构体变量作参数----多值传递，效率低

例10.4 用结构体变量作函数参数 struct data { int a, b, c; }; main() { void func(struct data); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf("arg.a=%d arg.b=%d arg.c=%d\n",arg.a,arg.b,arg.c); printf("Call Func()....\n"); func(arg); } void func(struct data parm) { printf("parm.a=%d parm.b=%d parm.c=%d\n",parm.a,parm.b,parm.c); printf("Process...\n"); parm.a=18; parm.b=5; parm.c=parm.a*parm.b; printf("parm.a=%d parm.b=%d parm.c=%d\n",parm.a,parm.b,parm.c); printf("Return...\n"); 例10.4 用结构体变量作函数参数

例10.5 用结构体指针变量作函数参数 arg a :18 b: 5 c :90 (main) (func) parm **** arg 例10.5 用结构体指针变量作函数参数 struct data { int a, b, c; }; main() { void func(struct data *parm); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf("arg.a=%d arg.b=%d arg.c=%d\n",arg.a,arg.b,arg.c); printf("Call Func()....\n"); func(&arg); } void func(struct data *parm) { printf("parm->a=%d parm->b=%d parm->c=%d\n",parm->a,parm->b,parm->c); printf("Process...\n"); parm->a=18; parm->b=5; parm->c=parm->a*parm->b; printf("parm->a=%d parm->b=%d parm->c=%d\n",parm->a,parm->b,parm->c); printf("Return...\n");

10.4 链表 10.4.1链表概述 1.链表的含义 当一个结构体中有一个成员是指向本结构体的指针时，通过这样的指针可以将若干个相同的结构体存储单元连接成一个新的数据结构，这种数据结构就称为链表。 head 2004 2100 1842 NULL

2. 单链表的结构 （1）头指针变量head──指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域──存储结点本身的信息。 2）指针域──指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志。 （4）链表数据结构的实现，必须利用指针变量。 （5）链表中的元素在内存中存放顺序不一定是连续的。

3 Ｃ语言对链表结点的结构描述 在Ｃ语言中，用结构体类型来描述结点链表结点的结构。 例如： struct student { int num; float score; struct student *next; /*指针域，由next指针来连接各节点*/ };

例10.6 建立一个简单的链表，它由3个学生数据的结点组成，输出各结点的数据。 10.4.2 简单链表 例10.6 建立一个简单的链表，它由3个学生数据的结点组成，输出各结点的数据。 #define NULL 0 struct student { long num; float score; struct student *next; };

main() {struct student a,b,c,*head,*p; a.num=99101; a.score=89.5; b.num=99103; b.score=90; c.num=99107; c.score=85; head=&a; a.next=&b; b.next=&c; c.next=NULL; p=head; do {printf("%ld %5.1f\n",p->num,p->score); p=p->next; }while(p!=NULL); }

10.4.3 处理动态链表所需的函数 1、malloc函数 （1）函数原型： void *malloc(unsigned int size); （2）作用：在内存中动态的分配一个长度为size的连续空间。 2、calloc函数 void *calloc(unsigned n,unsigned size); （2）作用：在内存中分配n个长度为size的连续空间。 3、free函数 void free(void *p); （2）作用：释放由指针p指向的内存区域。

例10.7 编写一个create()函数，创建一个有3名学生数据的单向动态链表。 1 建立动态链表 例10.7 编写一个create()函数，创建一个有3名学生数据的单向动态链表。 #include<malloc.h> #define NULL 0 #define LEN sizeof(struct student) struct student {long num; float score; struct student *next; };

int n; /*n变全局变量，本文件模块中各函数均可使用它*/ struct student *creat(void) /*此函数带回一个指向链表头的指针*/ {struct student *head; struct student *p1,*p2; n=0; p1=p2=(struct student *)malloc(LEN); /*开辟一个新单元*/ scanf("%ld,%f",&p1->num,&p1->score); head=NULL; while(p1->num!=0) {n=n+1; if(n==1)head=p1; else p2->next=p1; p2=p1; p1=(struct student *)malloc(LEN); } p2->next=NULL; return(head);

例10.8 编写一个print()函数，输出一个有3名学生数据的单向动态链表。 2 输出链表 例10.8 编写一个print()函数，输出一个有3名学生数据的单向动态链表。 void print(struct student *head) {struct student *p; printf("\nNow,These %d records are:\n",n); p=head; if(head!=NULL) do {printf("%ld %5.1f\n",p->num,p->score); p=p->next; }while(p!=NULL); }

例10.9 编写一个del()函数，用来删除单向动态链表的结点。 3 对链表的删除操作 例10.9 编写一个del()函数，用来删除单向动态链表的结点。 struct student *del(struct student *head,long num)/*定义del函数*/ {struct student *p1,*p2; if(head==NULL){printf("\nlist null!\n");goto end;} p1=head; while(num!=p1->num&&p1->next!=NULL) {p2=p1;p1=p1->next;} if(num==p1->num) { if(p1==head)head=p1->next; else p2->next=p1->next; printf("delete:%ld\n",num); n=n-1; } else printf("%ld not been found!\n",num); end: return(head);

例10.10 编写一个insert()函数，用来在单向动态链表中插入结点。 4 对链表的插入操作 例10.10 编写一个insert()函数，用来在单向动态链表中插入结点。 struct student *insert(struct student *head,struct student *stud) { struct student *p0,*p1,*p2; p1=head; p0=stud; if(head==NULL) {head=p0; p0->next=NULL;} else { while((p0->num>p1->num)&&(p1->next!=NULL)) {p2=p1; p1=p1->next; } if (p0->num<=p1->num) { if(head==p1) head=p0; else p2->next=p0; p0->next=p1; } else {p1->next=p0; p0->next=NULL;} n=n+1; return(head);

10.5 共用体 构造数据类型,也叫联合体 用途：使几个不同类型的变量共占一段内存(相互覆盖) 10.5.1 共用体类型定义形式 union 共用体名 { 类型标识符 成员名； ……………. }； 例 union data { int i; char ch; float f; }; f ch i 类型定义不分配内存

10.5.2共用体变量的定义 形式一: union data { int i; char ch; float f; }a,b; 形式二: }; union data a,b,c,*p,d[3]; 形式三: union { int i; char ch; float f; }a,b,c; f ch i a b 共用体变量任何时刻 只有一个成员存在 共用体变量定义分配内存, 长度=最长成员所占字节数

p->i p->ch p->f 10.5.3 共用体变量引用 共用体指针名->成员名 共用体变量名.成员名 (*共用体指针名).成员名 引用规则 不能引用共用体变量，只能引用其成员 union data { int i; char ch; float f; }; union data a,b,c,*p,d[3]; a.i a.ch a.f p->i p->ch p->f (*p).i (*p).ch (*p).f d[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; ()

例10.11 将一个整数按字节输出 main() { union int_char { int i; char ch[2]; }x; 例10.11 将一个整数按字节输出 01100001 01000001 低字节 高字节 01000001 01100001 ch[0] ch[1] 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]); } 运行结果： i=60501 ch0=101,ch1=141 ch0=A,ch1=a

10.5.4 结构体与共用体 区别: 存储方式不同 联系: 两者可相互嵌套 struct node { char ch[2]; ch int k; }a; union node }b; a ch k b 变量的各成员同时存在 任一时刻只有一个成员存在

例10.12 结构体中嵌套共用体 struct { int num; char name[10]; char sex; char job; 例10.12 结构体中嵌套共用体 循环n次 读入姓名、号码、性别、职务 job==‘s’ 真 假 读入class 读入 position 输出 “输入错” 输出:姓名,号码, 性别,职业,班级 性别,职业,职务 job==‘t’ struct { int num; char name[10]; char sex; char job; union { int class; char position[10]; }category; }person[2]; name num sex job class position Li Wang 1011 2086 F M S T 501 prof

例10.13共用体中嵌套结构体，机器字数据与字节数据的处理 00010010 00110100 低字节 高字节 00110100 00010010 low high 0x1234 struct w_tag { char low; char high; }; union u_tag { struct w_tag byte_acc; int word_acc; }u_acc; 00010010 11111111 低字节 高字节 11111111 00010010 low high 0x12ff word_acc byte_acc.low byte_acc.high u_acc

10.6 用typedef定义类型 功能：用自定义名字为已有数据类型命名 类型定义简单形式： typedef type name; 例 typedef int INTEGER; 类型定义语句关键字 已有数据类型名 例 INTEGER a,b,c; REAL f1,f2; 用户定义的类型名 例 typedef float REAL; int a,b,c; float f1,f2; 说明: 1.typedef 没有创造新数据类型 2.typedef 是定义类型,不能定义变量 3.typedef 与 define 不同 类型定义后,与已有类型一样使用 define typedef 预编译时处理 编译时处理 简单字符置换 为已有类型命名

typedef定义类型步骤 类型定义可嵌套 按定义变量方法先写出定义体 例如 int i; 将变量名换成新类型名 例如 int INTEGER; 最前面加typedef 例如 typedef int INTEGER; 用新类型名定义变量 例如 INTEGER i,j; 例 定义结构体类型 struct date { int month; int day; int year; }d; 例 定义函数指针类型 int (*p)(); int (*POWER)(); typedef int (*POWER)(); POWER p1,p2; 例 定义结构体类型 struct date { int month; int day; int year; }DATE; 例 定义数组类型 int a[100]; int ARRAY[100]; typedef int ARRAY[100]; ARRAY a,b,c; 例 定义指针类型 char *str; char *STRING; typedef char *STRING; STRING p,s[10]; 例 定义结构体类型 typedef struct date { int month; int day; int year; }DATE; 例 定义结构体类型 DATE birthday, *p; 类型定义可嵌套 例 typedef struct club { char name[20]; int size; int year; }GROUP; typedef GROUP *PG; PG pclub; GROUP为结构体类型 PG为指向GROUP的指针类型  struct date { int month; int day; int year; }birthday, *p;  int (*p1)(),(*p2)();  int a[100],b[100],c[100];  char *p; char *s[10];  GROUP *pclub;  struct club *pclub;