本次课内容：动态存储分配、链表
教学目的：掌握相关概念、函数和链表的基本操作。
重点：动态存储分配方法，链表的基本操作（建、插、
删）。
难点：链表的基本操作（建、插、删）。
预习,
结构体类型定义，变量定义和成员引用；
指向结构体类型变量的指针；
结构体类型的嵌套定义。
简单单向链表举例,
num
score
*next
学号
成绩
下一学生数据地址
3010
head 3010
3028
4016
4048
89101
89102
89105
89018
89.5
90.5
91
94.5
3028
4016
4048
NULL
结点
头指针
数据域
指针域
结点
结点构成
结点结构定义,
struct stud_score
{
long num;
float score;
struct stud_score *next;
};
一、动态存储分配和链表概念
1、动态存储分配
根据需要临时分配存储单元用于存放数据，当数据
不用时，又可随时释放存储单元。
2、链表
若干数据按一定的原则连接起来。
原则：前一个结点指向下一个结点，通过前一个结
点找到下一个结点。
结点构成：数据域和指针域。
结点：一组数据或一个记录。
头指针：用 head（一般情况下）表示的首结点地
址。
NULL（尾结点指针域值）：符号常量，值为 0
一般表示不指向任何一个数据。
基本操作,
(1)建立链表
(2)插入结点
(3)删除结点
插入结点,
删除结点,
1340
89103
92.5
4016
3028
89102
90.5
1340
4016
89105
91
4048
3028
89102
90.5
4016 1340
89103
92.5
4016
4016
89105
91
4048
原 4016
原 1340 结点虽仍指向下一结点,
但此结点已无法访问 。
4016
结点构成,
数据域：若干不同类型变量
指针域：一个或多个指针类型变量
结点定义方法：定义包含指针项的结构体变量，结构
体成员中至少有一个指向该结构体类型的指针成员。
如,
struct stud_score
{
long num;
float score;
struct stud_score *next;
};
其中,*next是指向该类型的指针成员。用于存放该结
构体类型数据的首地址。
struct stud_score *next; 是嵌套定义。
例：简单的单向链表
struct stud_score
{ long num;
float score;
struct stud_score *next;
};
struct stud_score stud1,stud2,stud3,*head;
stud1.num=89101;stud1.score=89.5;
stud2.num=89102;stud2.score=90.5;
stud3.num=89103;stud3.score=94.5;
head=&stud1;
stud1.next=&stud2;
stud2.next=&stud3;
stud3.next=NULL;
定义结点结构
各结点赋有用值
形成“链”
&stud1
head 89101 89102 89103
89.5 90.5 94.5
&stud1 &stud2
&stud2
&stud3
&stud3 NULL
三、动态存储分配函数
1、分配一个动态存储空间
Void *malloc(unsigned int size)
功能：函数分配了一个指定大小的存储空间，返回值为
起始地址，指针是不指向任何具体的类型。
如,long p;
p=(long*)malloc( 4 );
或,p=(long*)malloc(sizeof(long))
注 (1)函数值为指针（地址）；
(2)若指向某一类型时，需强制类型转换；
(3)内容若无足够的空间，返回值为 0。
2、分配多个动态存储空间
Void *calloc(unsigned int num,unsigned int size)
空间个数 空间大小
如,calloc(10,20);
分配了 10个，每个大小为 20个字节的空间。
引用地址时，类型要强制转换。
如,struct stud
{ char name[10];
int age;
char sex;
struct stud *next;
}new;
new=(struct stud*)calloc(1,15);
3、释放存储空间
void free(void *ptr)
功能：将指针变量 ptr指向的存储空间释放。
注,ptr值不能是任意的地址，而只能是由在程序中执行
过的 malloc或 calloc函数所返回 的地址。
如,p=(long*)malloc(4);
,
free(p);
或,p=(long*)calloc(1,4); free(p);
注：函数无返回值，函数会自动将指针变量类型转换为
void类型。
四、举例 P260_例 7.13
#include,stdio.h”
#include,stdlib.h”
struct stud
{ char name[20];
long num;
int age;
char sex;
float score;
struct stud *next;
};
struct stud *head,*this,*new;
main()
{ char ch;
int flag=1;
head=NULL;
while (flag)
{ ch=getchar( );getchar( );
switch( ch )
{ case ?e?,
case ?E?:new_record( );
case ?l?,
case ?L?:listall( );break;
default:flag=0;
} /*end switch*/
} /*end while*/
}
Void new_record(void)
{ char numstr[20];
new=(struct stud *)malloc(sizeof(struct stud));
if (head==NULL)
head=new;
else
{ this=head;
while(this->next !=NULL)
this=this->next;
this->next = new;
}
gets(this->name);
gets(numstr);this->num=atol(numstr);
gets(numstr);this->age=atoi(numstr);
this->sex=getchar( );getchar( );
gets(numstr);this->score=atof(numstr);
this->next=NULL;
}
void listall(void)
{ int i=0;
if(head==NULL)
return;
this=head;
do
{ printf(“name:%s \n”,this->name);
printf(“num:%ld \n”,this->num);
printf(“age:%d \n”,this->age);
printf(“sex:%c \n”,this->sex);
printf(“score:%f \n”,this->score);
}while(this != NULL);
}
NULL
head
(a)
new
(b)
new
(c)
1384
head 1384
new
(d)
1384
head 1384
this
89101
89.5
NULL (e)
1384
head 1384
this
89101
89.5
NULL
new 2150
1384
(f)
1384
head 1384
this
89101
89.5
2150
new 2150
(g)
1384
89101
89.5
2150
new 2150
this
1384
head
89102
90.5
NULL
分配结点
初始为空
头指向首结点
地址赋给 this并给成员赋值 再分配一个新结点
新结点地址赋上结点指针成员中，两结点链接 通过 this对成员赋值
小结,
1、动态分配和链表概念
2、结点构成
3、动态分配函数
4、链接应用方法，基本操作（建、插、删）。
作业,P274_7.4, 7.8
教学目的：掌握相关概念、函数和链表的基本操作。
重点：动态存储分配方法，链表的基本操作（建、插、
删）。
难点：链表的基本操作（建、插、删）。
预习,
结构体类型定义，变量定义和成员引用；
指向结构体类型变量的指针；
结构体类型的嵌套定义。
简单单向链表举例,
num
score
*next
学号
成绩
下一学生数据地址
3010
head 3010
3028
4016
4048
89101
89102
89105
89018
89.5
90.5
91
94.5
3028
4016
4048
NULL
结点
头指针
数据域
指针域
结点
结点构成
结点结构定义,
struct stud_score
{
long num;
float score;
struct stud_score *next;
};
一、动态存储分配和链表概念
1、动态存储分配
根据需要临时分配存储单元用于存放数据，当数据
不用时，又可随时释放存储单元。
2、链表
若干数据按一定的原则连接起来。
原则：前一个结点指向下一个结点，通过前一个结
点找到下一个结点。
结点构成：数据域和指针域。
结点：一组数据或一个记录。
头指针：用 head（一般情况下）表示的首结点地
址。
NULL（尾结点指针域值）：符号常量，值为 0
一般表示不指向任何一个数据。
基本操作,
(1)建立链表
(2)插入结点
(3)删除结点
插入结点,
删除结点,
1340
89103
92.5
4016
3028
89102
90.5
1340
4016
89105
91
4048
3028
89102
90.5
4016 1340
89103
92.5
4016
4016
89105
91
4048
原 4016
原 1340 结点虽仍指向下一结点,
但此结点已无法访问 。
4016
结点构成,
数据域：若干不同类型变量
指针域：一个或多个指针类型变量
结点定义方法：定义包含指针项的结构体变量，结构
体成员中至少有一个指向该结构体类型的指针成员。
如,
struct stud_score
{
long num;
float score;
struct stud_score *next;
};
其中,*next是指向该类型的指针成员。用于存放该结
构体类型数据的首地址。
struct stud_score *next; 是嵌套定义。
例：简单的单向链表
struct stud_score
{ long num;
float score;
struct stud_score *next;
};
struct stud_score stud1,stud2,stud3,*head;
stud1.num=89101;stud1.score=89.5;
stud2.num=89102;stud2.score=90.5;
stud3.num=89103;stud3.score=94.5;
head=&stud1;
stud1.next=&stud2;
stud2.next=&stud3;
stud3.next=NULL;
定义结点结构
各结点赋有用值
形成“链”
&stud1
head 89101 89102 89103
89.5 90.5 94.5
&stud1 &stud2
&stud2
&stud3
&stud3 NULL
三、动态存储分配函数
1、分配一个动态存储空间
Void *malloc(unsigned int size)
功能：函数分配了一个指定大小的存储空间，返回值为
起始地址，指针是不指向任何具体的类型。
如,long p;
p=(long*)malloc( 4 );
或,p=(long*)malloc(sizeof(long))
注 (1)函数值为指针（地址）；
(2)若指向某一类型时，需强制类型转换；
(3)内容若无足够的空间，返回值为 0。
2、分配多个动态存储空间
Void *calloc(unsigned int num,unsigned int size)
空间个数 空间大小
如,calloc(10,20);
分配了 10个，每个大小为 20个字节的空间。
引用地址时，类型要强制转换。
如,struct stud
{ char name[10];
int age;
char sex;
struct stud *next;
}new;
new=(struct stud*)calloc(1,15);
3、释放存储空间
void free(void *ptr)
功能：将指针变量 ptr指向的存储空间释放。
注,ptr值不能是任意的地址，而只能是由在程序中执行
过的 malloc或 calloc函数所返回 的地址。
如,p=(long*)malloc(4);
,
free(p);
或,p=(long*)calloc(1,4); free(p);
注：函数无返回值，函数会自动将指针变量类型转换为
void类型。
四、举例 P260_例 7.13
#include,stdio.h”
#include,stdlib.h”
struct stud
{ char name[20];
long num;
int age;
char sex;
float score;
struct stud *next;
};
struct stud *head,*this,*new;
main()
{ char ch;
int flag=1;
head=NULL;
while (flag)
{ ch=getchar( );getchar( );
switch( ch )
{ case ?e?,
case ?E?:new_record( );
case ?l?,
case ?L?:listall( );break;
default:flag=0;
} /*end switch*/
} /*end while*/
}
Void new_record(void)
{ char numstr[20];
new=(struct stud *)malloc(sizeof(struct stud));
if (head==NULL)
head=new;
else
{ this=head;
while(this->next !=NULL)
this=this->next;
this->next = new;
}
gets(this->name);
gets(numstr);this->num=atol(numstr);
gets(numstr);this->age=atoi(numstr);
this->sex=getchar( );getchar( );
gets(numstr);this->score=atof(numstr);
this->next=NULL;
}
void listall(void)
{ int i=0;
if(head==NULL)
return;
this=head;
do
{ printf(“name:%s \n”,this->name);
printf(“num:%ld \n”,this->num);
printf(“age:%d \n”,this->age);
printf(“sex:%c \n”,this->sex);
printf(“score:%f \n”,this->score);
}while(this != NULL);
}
NULL
head
(a)
new
(b)
new
(c)
1384
head 1384
new
(d)
1384
head 1384
this
89101
89.5
NULL (e)
1384
head 1384
this
89101
89.5
NULL
new 2150
1384
(f)
1384
head 1384
this
89101
89.5
2150
new 2150
(g)
1384
89101
89.5
2150
new 2150
this
1384
head
89102
90.5
NULL
分配结点
初始为空
头指向首结点
地址赋给 this并给成员赋值 再分配一个新结点
新结点地址赋上结点指针成员中，两结点链接 通过 this对成员赋值
小结,
1、动态分配和链表概念
2、结点构成
3、动态分配函数
4、链接应用方法，基本操作（建、插、删）。
作业,P274_7.4, 7.8
