第十一章
本章要点
结构体的定义 \引用和初始化( 1--5)
链表的概念和操作 \建立 \输出( 6-7)
§ 11.1 概述
有时要将具有内在联系的多个不同类型的数据组合成一个整体以便于引用。 如:
学生,stu1”的学号 /姓名 /性别 /年龄 /地址等
int num; char name[20]; char sex;
int age; int char addr[30];
若能用 stu1.num,student1.age… 访问图 11-1
100101 Li Fun M 18 87.5 Beijing
Num name sex age score addr
struct student
{
int num;
char name[20];
char sex;
int age; float score; char addr[30];
};/*分号不能丢,此处表类型定义完毕 */
struct student stu_1
结构体类型成员类型结构体成员结构体包含结构体类型与结构体变量两层含义,
前者只声明结构体在内存中的存储结构;后者是结构体类型的具体实例,编译系统只有定义了结构体变量后才为会根据结构体类型为结构体变量分配内存空间结构体变量
§ 11.2 结构体类型与结构体变量的定义
(1)先定义结构体类型,后定义结构体变量
struct student {…};
struct student student1,student2;
(2)定义结构体类型的同时定义结构体变量
struct date
{
int year; int month; int day;
}date1,date2;
(3) 直接定义结构体类型变量
struct
{ int num; char name[20]; char sex; float score;
struct date birthday;/*成员也可以是结构体类型 */
}student1,student2;
§ 11.3结构体变量的引用
(1)使用成员运算符引用结构体变量的成员:
结构体变量名,成员名
student1.num=10010;scanf(“%d”,&student1.num);
printf(“%d”,student1.num);
注,不能将结构体变量作为整体输入和输出,如
scanf(″% d″,& student1) 错 !
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 7
( 2)使用指针运算符和成员运算符引用结构体变量的成员。如
struct student stu,*p=&stu;
(*p).num=10001;scanf(“%s”,(*p).name);scanf(“%f”,&(*p).score);
( 3)使用指向运算符,->”引用结构体变量的成员。如
struct student stu,*p=&stu;
p->num=10001; scanf(“%s”,p->name);
scanf(“%f”,&p->score);printf(“age of %s is %d\n”,stu1.name,age);
( 4)将结构体变量作为一个整体进行操作。如
stu2=stu1;
printf(“the address of struct student variable stu2 is %x”,&stu2);
struct student stu1,stu2,*p=&stu1;
【 说明 】 (1),.”与,->” 优先级相同,都高于指针运算符,*”。
(2),(*p).成员名”,,p->成员名”与,stu.成员名” 等价思考:,(*p).成员名”中括号能省略吗?
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 8
11.4结构体变量的初始化:
定义结构体变量的同时为各成员赋值。如,
struct student stu1={1001,“lisi",'M',{1988,8,10},580};
struct student stu2={1002,"Li Ping",'F',1989,2,5,595};
struct student stu3={1002,"Li Ping",'F',1989};
【 说明 】 ( 1)不初始化则结构体变量各成员的取值是随机的。
( 2)花括号内初值的顺序、类型要与结构体成员的顺序和类型一致但不能用以下语句整体读入结构体变量,
例如:
scanf( ″%d,% s,% c,% d,% f,%
s″,& student1);
结构体变量的地址主要用作函数参数,
传递结构体变量的地址。
例 11.1 对结构体变量初始化,
#include <stdio.h>
void main()
{ struct student
{ long int num;
char name[20];
char sex;
char addr[20];
}a={10101,”LiLin”,’M’,″Beijing Road″
}; /* 对结构体变量 a赋初值 */
printf(“No.:%ld \nname:%s\nsex:%c\naddress:%s\n
”,a.num,a.name,a.sex,a.addr); }
运行结果:
No.,10101
name,LiLin
sex:M
address,Beijing Road
结构体程序举例
【 例 10.1’】 输入一个学生的信息并显示
#include<stdio.h>
void main()
{
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
printf("请输入学生出生日期,");
scanf("%d%d%d",&stu.birthday.year,&stu.birthday.month,&stu.birthday.day);
printf("学号,%d\n姓名,%s\n出生日期,%d年 %d月 %d日 \n",stu.num,stu.name,
stu.birthday.year,stu.birthday.month,stu.birthday.day,stu.score);
}
结构体在函数内部定义则只在本函数内部有效!
结构体变量作函数参数:
【 例 10.2’】 在函数 input中输入一个学生的信息,在函数 list中显示
#include<stdio.h>
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student input()
{
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
return(stu);
}
void list(struct student stu)
{ printf("学号,%d\n姓名,%s\n",stu.num,stu.name);}
void main()
{
struct student stu;
stu=input();list(stu);
}
void main()
{
struct person
{
char name[20];
int count;
}leader[N]={{"zhangsan",0},{"lisi",0},{"wangwu",0}};
int i,j;
char name[20];
for(i=0;i<M;i++)
{
printf("请输入候选人姓名,\n");
gets(name);
for(j=0;j<N;j++)
if(strcmp(leader[j].name,name)==0)leader[j].count++;
}
for(i=0;i<N;i++)
printf("%8s:%d\n",leader[i].name,leader[i].count);
}
结构体数组
【 例 10.4】 编程统计候选人的得票数。 N个候选人,M人投票初 始 化 各 候 选 人 得 票 数 为 0
对 每 个 投 票 人输 入 所 支 持 候 选 人 的 姓 名对 每 个 候 选 人得 票
Y
N
得 票 数 加 1
图 1 0,5 主 函 数 N - S 图输 出 各 候 选 人 得 票 结 果
【 例 10.3】 使用指向 结构体数组 元素的 指针 作函数参数输出学生相关信息
#include<stdio.h>
struct student{ int num; char name[20];float score; };
void main()
{
void print(struct student *);
struct student stu[3]={101,"li",583,102,"wu",590,103,"han",560};
print(stu);
}
void print(struct student *p)
{
int i;
printf(" 学号 姓名 成绩 \n");
for(i=0;i<3;i++,p++)
printf("%5d%10s%8.1f\n",p->num,p->name,p->score);
}
作业,11.5
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 15
回顾,
结构体 结构体类型 结构体变量 结构体成员变量 成员运算符 指向运算符
#include<stdio.h>
void main()
{
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
printf("请输入学生出生日期,");
scanf("%d%d%d",&stu.birthday.year,&stu.birthday.month,&stu.birthday.day);
printf("学号,%d\n姓名,%s\n出生日期,%d年 %d月 %d日 \n",stu.num,stu.name,
stu.birthday.year,stu.birthday.month,stu.birthday.day,stu.score);
}/*结构体成员变量完全类似一个普通变量 */
注意结构体类型与结构体变量定义的位置!
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 16
结构体变量,也类似一个普通变量,不过无法整体输入输出,但有些操作可以作为一个整体进行,如 struct student stu1,stu2,*p; stu1=stu2;p=&stu2
#include<stdio.h>
struct student{int num;char name[20];};
struct student input()
{
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
return(stu);
}
void list(struct student stu)
{ printf("学号,%d\n姓名,%s\n",stu.num,stu.name);}
void main()
{
struct student stu;
stu=input();list(stu);
}
void input(struct student stu)
{
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
}
…input(stu);…
/*调用语句可否实现对 stu的输入? */
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 17
结构体数组与基类型为结构体的指针
#include<stdio.h>
struct student{ int num; char name[20];float score; };
void main()
{
void print(struct student *);
struct student stus[3]={101,"li",583,102,"wu",590,103,"han",560};
print(stus);
}
void print(struct student *p)
{
int i;
printf(" 学号 姓名 成绩 \n");
for(i=0;i<3;i++,p++)
printf(“%5d%10s%8.1f\n”,p->num,p->name,p->score);/*相当于 (*p).num*/
}
【 说明 】,(*p).成员名”,,p->成员名”、,stu[i].成员名” 等价,
但,(*p).成员名”中括号不能省略
[思考 ] 学生数随时可能会增加或减少,如何编程实现?
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 18
引言,用数组存储数据有两方面问题:其一,个数不确定须定义一个最大长度;其二,需向数组增加或删除一个数据时,需要移动大量元素。
链表,一种动态地进行存储分配的数据结构,不需要事先确定最大长度,在插入或者删除一个元素时也不会引起大量数据的移动
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
11.7 链表
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 19
1、链表的结构:
一个“头”,一个“尾”,中间有若干结点,每个结点包括两部分:一部分是用户需要用的实际数据,称为数据域; 另一部分是下一个结点的地址,称为指针域图 10.8 链表结构示意图
1001
1001
2056
2056
3001
3001
3005
3005
11.7.1 链表结构
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
2、头指针与表尾,通常有一个头指针 head,它指向链表的第一个结点。最后一个结点称为“表尾”,该结点的地址部分存放空地址(用 NULL表示)。表尾不再有后继结点,链表到此结束
【 说明 】 ( 1)链表中各元素在内存中可以不连续存放
( 2)头指针和表尾至关重要,否则无法访问链
【 思考 】 画出空链表的结构示意图。
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 20
struct student
{
int num;
char name[20];
float score;
struct student *next;
};
11.7.2 链表的定义与创建链表创建,
静态链表:在程序中定义相应数量的结构体变量来充当结点;
动态链表:在程序执行过程中动态开辟结点 。
静态链表各结点所占用的存储空间在程序执行完毕后由系统释放;
动态链表可在程序执行过程中调用动态存储分配函数释放
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 21
#include<stdio.h>
struct student
{int num;char name[20]; float score;
struct student *next;
};
void main()
{
struct student a={10011,"zhangsan",592},
b={10012,"lisi",581},
c={10013,"wangwu",656};
struct student *head,*p;
head=&a;
a.next=&b;
b.next=&c;
c.next=NULL;
for(p=head;p!=NULL;p=p->next)
printf("%5d %8s %6.1f\n",p->num,p->name,p->score);
}/*头指针! */
11.7.3 静态链表
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例初始化各结构体变量令头指针指向第一个结点令第一个结点的指针域指向第二个结点令第二个结点的指针域指向第三个结点将第三个结点的指针域赋值为空图 10,10 例 10,6 主函数程序 N - S 图
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 22
1、动态存储分配函数 malloc.h
void *malloc(unsigned size);
void free(void *p);
void *calloc(unsigned n,unsigned size);
11.7.4 动态链表
2、动态链表的建立
struct student *create(int n)
{ struct student *localhead=NULL,*p1,*p2;
int i;
for(i=1;i<=n;i++)
{
p1=(struct student *)malloc(sizeof(struct student));
printf("请输入第 %d个学生的学号及考试成绩,\n",i);
scanf("%d%f",&p1->num,&p1->score);
p1->next=NULL;
if(i==1) head=p1;
else p2->next=p1;
p2=p1;
}
return(localhead);
}/*头文件莫忘,返回指针值的函数 */
fo r ( i = 1 ; i < = n ; i ++)
开辟新结点,令 p 1 指向它输入学生信息,指针域置空是否首结点
Y N
头指针指向首结点 新结点与前一结点链接
p 2 指向新结点返回 h e a d
图 10,14 动态链表的建立
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 23
11.7.4 动态链表 —输出 /输入
#include<stdio.h>
void print(struct student *localhead)
{
struct student *p=localhead;
while(p!=NULL)
{
printf("学号,%d 成绩,%3f\n",p->num,p->score);
p=p->next;
}
}/*用 p遍历所有结点,直到为 NULL*/
w h i l e ( p ! = N U L L )
输 出 p 所 指 向 结 点 的 信 息
p 后 移 一 个 结 点
p = h e a d
图 1 0,1 6 动 态 链 表 的 输 出图 10.15 链表输出示意图( p’代表指针 p后移一个结点后指向的位置,
p”代表后移两个结点后的位置)
P,
head
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 24
11.7.4 动态链表 —删除指定学号的结点
struct student *del(struct student *localhead,int num){……}
( 1)函数头写 void del(struct student *localhead,int num)不可,为什么?
( 2) p1->num!=num &&p1!=NULL错,但 p1!=NULL&& p1-
>num!=NULL正确,p1->num!=num &&p1->next!=NULL也对
( 3)临界情况要注意!空表、首结点、尾结点图 10.17 删除结点 C示意图图 10.18 删除指定学号的链表结点输出原表为空
Y N
Y N
NY
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 25
11.7.4 动态链表 —插入操作(按学号大小)
struct student *insert(struct student *localhead,struct student *stud) {…}
( 1)函数头写 void del(struct student *localhead,int num)不可,为什么?
( 2)循环结束条件与临界情况要注意!空表、首结点、尾结点图 10,19 插入结点示意图
a
b
c
Y N
Y
Y
N
N
图 10.20 在有序动态链表中插入结点
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 26
11.7.4 动态链表 —综合操作#include<stdio.h>
#include<malloc.h>
void main()
{
struct student *head,*stud;
int n,k;
printf("请输入学生个数,\n");
scanf("%d",&n);
printf("请按学号输入各学生的信息,\n");
head=create(n);
printf("原链表为,\n");
print(head);
printf("输入要删除学生的学号,\n");
scanf("%d",&k);
head=del(head,k);
printf("删除后链表为,\n");
print(head);
stud=(struct student*)malloc(sizeof(struct student));
printf("输入欲插入学生的学号及成绩 \n");
scanf("%d%f",&stud->num,&stud->score);
head=insert(head,stud);
printf("插入后链表为,\n");
print(head);
}
输入链表结点个数调用 c re a te () 函数创建链表并输入信息调用 p ri n t () 函数输出当前链表输入要删除学生结点的学号调用 d e l () 函数删除指定学号的结点调用 p ri n t () 函数输出当前链表输入要插入学生结点的信息调用 in se rt () 函数将新结点插入链表调用 p ri n t () 函数输出当前链表图 10,21 链表的综合操作
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 27
练习:
(1)实验报告下次上机重新改 (消字灵)
(2)综合实验电子版发
fm_lu@163.com,打印 装订 后第十七周周二交,不画 N-S图,评分考虑电子版提交早晚
(3)所有作业本和实验报告册以第十七周周五交,不能少!
本章要点
结构体的定义 \引用和初始化( 1--5)
链表的概念和操作 \建立 \输出( 6-7)
§ 11.1 概述
有时要将具有内在联系的多个不同类型的数据组合成一个整体以便于引用。 如:
学生,stu1”的学号 /姓名 /性别 /年龄 /地址等
int num; char name[20]; char sex;
int age; int char addr[30];
若能用 stu1.num,student1.age… 访问图 11-1
100101 Li Fun M 18 87.5 Beijing
Num name sex age score addr
struct student
{
int num;
char name[20];
char sex;
int age; float score; char addr[30];
};/*分号不能丢,此处表类型定义完毕 */
struct student stu_1
结构体类型成员类型结构体成员结构体包含结构体类型与结构体变量两层含义,
前者只声明结构体在内存中的存储结构;后者是结构体类型的具体实例,编译系统只有定义了结构体变量后才为会根据结构体类型为结构体变量分配内存空间结构体变量
§ 11.2 结构体类型与结构体变量的定义
(1)先定义结构体类型,后定义结构体变量
struct student {…};
struct student student1,student2;
(2)定义结构体类型的同时定义结构体变量
struct date
{
int year; int month; int day;
}date1,date2;
(3) 直接定义结构体类型变量
struct
{ int num; char name[20]; char sex; float score;
struct date birthday;/*成员也可以是结构体类型 */
}student1,student2;
§ 11.3结构体变量的引用
(1)使用成员运算符引用结构体变量的成员:
结构体变量名,成员名
student1.num=10010;scanf(“%d”,&student1.num);
printf(“%d”,student1.num);
注,不能将结构体变量作为整体输入和输出,如
scanf(″% d″,& student1) 错 !
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 7
( 2)使用指针运算符和成员运算符引用结构体变量的成员。如
struct student stu,*p=&stu;
(*p).num=10001;scanf(“%s”,(*p).name);scanf(“%f”,&(*p).score);
( 3)使用指向运算符,->”引用结构体变量的成员。如
struct student stu,*p=&stu;
p->num=10001; scanf(“%s”,p->name);
scanf(“%f”,&p->score);printf(“age of %s is %d\n”,stu1.name,age);
( 4)将结构体变量作为一个整体进行操作。如
stu2=stu1;
printf(“the address of struct student variable stu2 is %x”,&stu2);
struct student stu1,stu2,*p=&stu1;
【 说明 】 (1),.”与,->” 优先级相同,都高于指针运算符,*”。
(2),(*p).成员名”,,p->成员名”与,stu.成员名” 等价思考:,(*p).成员名”中括号能省略吗?
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 8
11.4结构体变量的初始化:
定义结构体变量的同时为各成员赋值。如,
struct student stu1={1001,“lisi",'M',{1988,8,10},580};
struct student stu2={1002,"Li Ping",'F',1989,2,5,595};
struct student stu3={1002,"Li Ping",'F',1989};
【 说明 】 ( 1)不初始化则结构体变量各成员的取值是随机的。
( 2)花括号内初值的顺序、类型要与结构体成员的顺序和类型一致但不能用以下语句整体读入结构体变量,
例如:
scanf( ″%d,% s,% c,% d,% f,%
s″,& student1);
结构体变量的地址主要用作函数参数,
传递结构体变量的地址。
例 11.1 对结构体变量初始化,
#include <stdio.h>
void main()
{ struct student
{ long int num;
char name[20];
char sex;
char addr[20];
}a={10101,”LiLin”,’M’,″Beijing Road″
}; /* 对结构体变量 a赋初值 */
printf(“No.:%ld \nname:%s\nsex:%c\naddress:%s\n
”,a.num,a.name,a.sex,a.addr); }
运行结果:
No.,10101
name,LiLin
sex:M
address,Beijing Road
结构体程序举例
【 例 10.1’】 输入一个学生的信息并显示
#include<stdio.h>
void main()
{
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
printf("请输入学生出生日期,");
scanf("%d%d%d",&stu.birthday.year,&stu.birthday.month,&stu.birthday.day);
printf("学号,%d\n姓名,%s\n出生日期,%d年 %d月 %d日 \n",stu.num,stu.name,
stu.birthday.year,stu.birthday.month,stu.birthday.day,stu.score);
}
结构体在函数内部定义则只在本函数内部有效!
结构体变量作函数参数:
【 例 10.2’】 在函数 input中输入一个学生的信息,在函数 list中显示
#include<stdio.h>
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student input()
{
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
return(stu);
}
void list(struct student stu)
{ printf("学号,%d\n姓名,%s\n",stu.num,stu.name);}
void main()
{
struct student stu;
stu=input();list(stu);
}
void main()
{
struct person
{
char name[20];
int count;
}leader[N]={{"zhangsan",0},{"lisi",0},{"wangwu",0}};
int i,j;
char name[20];
for(i=0;i<M;i++)
{
printf("请输入候选人姓名,\n");
gets(name);
for(j=0;j<N;j++)
if(strcmp(leader[j].name,name)==0)leader[j].count++;
}
for(i=0;i<N;i++)
printf("%8s:%d\n",leader[i].name,leader[i].count);
}
结构体数组
【 例 10.4】 编程统计候选人的得票数。 N个候选人,M人投票初 始 化 各 候 选 人 得 票 数 为 0
对 每 个 投 票 人输 入 所 支 持 候 选 人 的 姓 名对 每 个 候 选 人得 票
Y
N
得 票 数 加 1
图 1 0,5 主 函 数 N - S 图输 出 各 候 选 人 得 票 结 果
【 例 10.3】 使用指向 结构体数组 元素的 指针 作函数参数输出学生相关信息
#include<stdio.h>
struct student{ int num; char name[20];float score; };
void main()
{
void print(struct student *);
struct student stu[3]={101,"li",583,102,"wu",590,103,"han",560};
print(stu);
}
void print(struct student *p)
{
int i;
printf(" 学号 姓名 成绩 \n");
for(i=0;i<3;i++,p++)
printf("%5d%10s%8.1f\n",p->num,p->name,p->score);
}
作业,11.5
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 15
回顾,
结构体 结构体类型 结构体变量 结构体成员变量 成员运算符 指向运算符
#include<stdio.h>
void main()
{
struct date{int year;int month;int day;};
struct student{int num;char name[20];char sex;struct date birthday;float score;};
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
printf("请输入学生出生日期,");
scanf("%d%d%d",&stu.birthday.year,&stu.birthday.month,&stu.birthday.day);
printf("学号,%d\n姓名,%s\n出生日期,%d年 %d月 %d日 \n",stu.num,stu.name,
stu.birthday.year,stu.birthday.month,stu.birthday.day,stu.score);
}/*结构体成员变量完全类似一个普通变量 */
注意结构体类型与结构体变量定义的位置!
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 16
结构体变量,也类似一个普通变量,不过无法整体输入输出,但有些操作可以作为一个整体进行,如 struct student stu1,stu2,*p; stu1=stu2;p=&stu2
#include<stdio.h>
struct student{int num;char name[20];};
struct student input()
{
struct student stu;
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
return(stu);
}
void list(struct student stu)
{ printf("学号,%d\n姓名,%s\n",stu.num,stu.name);}
void main()
{
struct student stu;
stu=input();list(stu);
}
void input(struct student stu)
{
printf("请输入学生学号,");
scanf("%d",&stu.num);
printf("请输入学生姓名,");
scanf("%s",stu.name);
}
…input(stu);…
/*调用语句可否实现对 stu的输入? */
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 17
结构体数组与基类型为结构体的指针
#include<stdio.h>
struct student{ int num; char name[20];float score; };
void main()
{
void print(struct student *);
struct student stus[3]={101,"li",583,102,"wu",590,103,"han",560};
print(stus);
}
void print(struct student *p)
{
int i;
printf(" 学号 姓名 成绩 \n");
for(i=0;i<3;i++,p++)
printf(“%5d%10s%8.1f\n”,p->num,p->name,p->score);/*相当于 (*p).num*/
}
【 说明 】,(*p).成员名”,,p->成员名”、,stu[i].成员名” 等价,
但,(*p).成员名”中括号不能省略
[思考 ] 学生数随时可能会增加或减少,如何编程实现?
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 18
引言,用数组存储数据有两方面问题:其一,个数不确定须定义一个最大长度;其二,需向数组增加或删除一个数据时,需要移动大量元素。
链表,一种动态地进行存储分配的数据结构,不需要事先确定最大长度,在插入或者删除一个元素时也不会引起大量数据的移动
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
11.7 链表
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 19
1、链表的结构:
一个“头”,一个“尾”,中间有若干结点,每个结点包括两部分:一部分是用户需要用的实际数据,称为数据域; 另一部分是下一个结点的地址,称为指针域图 10.8 链表结构示意图
1001
1001
2056
2056
3001
3001
3005
3005
11.7.1 链表结构
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
2、头指针与表尾,通常有一个头指针 head,它指向链表的第一个结点。最后一个结点称为“表尾”,该结点的地址部分存放空地址(用 NULL表示)。表尾不再有后继结点,链表到此结束
【 说明 】 ( 1)链表中各元素在内存中可以不连续存放
( 2)头指针和表尾至关重要,否则无法访问链
【 思考 】 画出空链表的结构示意图。
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 20
struct student
{
int num;
char name[20];
float score;
struct student *next;
};
11.7.2 链表的定义与创建链表创建,
静态链表:在程序中定义相应数量的结构体变量来充当结点;
动态链表:在程序执行过程中动态开辟结点 。
静态链表各结点所占用的存储空间在程序执行完毕后由系统释放;
动态链表可在程序执行过程中调用动态存储分配函数释放
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 21
#include<stdio.h>
struct student
{int num;char name[20]; float score;
struct student *next;
};
void main()
{
struct student a={10011,"zhangsan",592},
b={10012,"lisi",581},
c={10013,"wangwu",656};
struct student *head,*p;
head=&a;
a.next=&b;
b.next=&c;
c.next=NULL;
for(p=head;p!=NULL;p=p->next)
printf("%5d %8s %6.1f\n",p->num,p->name,p->score);
}/*头指针! */
11.7.3 静态链表
10011num
n a m e z h a n g sa n
592sc o re
n e x t
10012
lisi
581
10013
w a n g w u
656
^
图 10,9 单链表示例初始化各结构体变量令头指针指向第一个结点令第一个结点的指针域指向第二个结点令第二个结点的指针域指向第三个结点将第三个结点的指针域赋值为空图 10,10 例 10,6 主函数程序 N - S 图
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 22
1、动态存储分配函数 malloc.h
void *malloc(unsigned size);
void free(void *p);
void *calloc(unsigned n,unsigned size);
11.7.4 动态链表
2、动态链表的建立
struct student *create(int n)
{ struct student *localhead=NULL,*p1,*p2;
int i;
for(i=1;i<=n;i++)
{
p1=(struct student *)malloc(sizeof(struct student));
printf("请输入第 %d个学生的学号及考试成绩,\n",i);
scanf("%d%f",&p1->num,&p1->score);
p1->next=NULL;
if(i==1) head=p1;
else p2->next=p1;
p2=p1;
}
return(localhead);
}/*头文件莫忘,返回指针值的函数 */
fo r ( i = 1 ; i < = n ; i ++)
开辟新结点,令 p 1 指向它输入学生信息,指针域置空是否首结点
Y N
头指针指向首结点 新结点与前一结点链接
p 2 指向新结点返回 h e a d
图 10,14 动态链表的建立
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 23
11.7.4 动态链表 —输出 /输入
#include<stdio.h>
void print(struct student *localhead)
{
struct student *p=localhead;
while(p!=NULL)
{
printf("学号,%d 成绩,%3f\n",p->num,p->score);
p=p->next;
}
}/*用 p遍历所有结点,直到为 NULL*/
w h i l e ( p ! = N U L L )
输 出 p 所 指 向 结 点 的 信 息
p 后 移 一 个 结 点
p = h e a d
图 1 0,1 6 动 态 链 表 的 输 出图 10.15 链表输出示意图( p’代表指针 p后移一个结点后指向的位置,
p”代表后移两个结点后的位置)
P,
head
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 24
11.7.4 动态链表 —删除指定学号的结点
struct student *del(struct student *localhead,int num){……}
( 1)函数头写 void del(struct student *localhead,int num)不可,为什么?
( 2) p1->num!=num &&p1!=NULL错,但 p1!=NULL&& p1-
>num!=NULL正确,p1->num!=num &&p1->next!=NULL也对
( 3)临界情况要注意!空表、首结点、尾结点图 10.17 删除结点 C示意图图 10.18 删除指定学号的链表结点输出原表为空
Y N
Y N
NY
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 25
11.7.4 动态链表 —插入操作(按学号大小)
struct student *insert(struct student *localhead,struct student *stud) {…}
( 1)函数头写 void del(struct student *localhead,int num)不可,为什么?
( 2)循环结束条件与临界情况要注意!空表、首结点、尾结点图 10,19 插入结点示意图
a
b
c
Y N
Y
Y
N
N
图 10.20 在有序动态链表中插入结点
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 26
11.7.4 动态链表 —综合操作#include<stdio.h>
#include<malloc.h>
void main()
{
struct student *head,*stud;
int n,k;
printf("请输入学生个数,\n");
scanf("%d",&n);
printf("请按学号输入各学生的信息,\n");
head=create(n);
printf("原链表为,\n");
print(head);
printf("输入要删除学生的学号,\n");
scanf("%d",&k);
head=del(head,k);
printf("删除后链表为,\n");
print(head);
stud=(struct student*)malloc(sizeof(struct student));
printf("输入欲插入学生的学号及成绩 \n");
scanf("%d%f",&stud->num,&stud->score);
head=insert(head,stud);
printf("插入后链表为,\n");
print(head);
}
输入链表结点个数调用 c re a te () 函数创建链表并输入信息调用 p ri n t () 函数输出当前链表输入要删除学生结点的学号调用 d e l () 函数删除指定学号的结点调用 p ri n t () 函数输出当前链表输入要插入学生结点的信息调用 in se rt () 函数将新结点插入链表调用 p ri n t () 函数输出当前链表图 10,21 链表的综合操作
C语言程序设计 (第三版) http://ccf.tsinghua.edu.cn 27
练习:
(1)实验报告下次上机重新改 (消字灵)
(2)综合实验电子版发
fm_lu@163.com,打印 装订 后第十七周周二交,不画 N-S图,评分考虑电子版提交早晚
(3)所有作业本和实验报告册以第十七周周五交,不能少!