2009/7/28
1
第二十一讲 用指针处理链表
教学目的与要求：
掌握链表的创建,插入,删除
教学内容提要：
1,链表的概述
2,链表的基本操作
教学重点：链表的创建,插入和删除
教学难点,链表的创建,插入和删除
教学进度：
教学过程：
2009/7/28
2
一、链表概述
1,链表：是指若干个数据项 （ 每个数据项称为一个,结点,）
按一定的原则连接起来 。 每个数据项都包含有若干个数据和一个指向下一个数据项的指针,依靠这些指针将所有的数据项连接成一个链表 。 下图表示了一个简单的链表 。
头指针 head
姓 名 1
学 号 1
成 绩 1
指 针 1
数据项 A 数据项 C
姓 名 2
学 号 2
成 绩 2
指 针 2
数据项 B
姓 名 3
学 号 3
成 绩 3
指 针 3
2009/7/28
3
1620
head
李为
2004101
85
0586
数据项 A 数据项 C
刘娜
2004102
93
3818
数据项 B
张三
2004125
95
0
1620 0586 3818
一个简单链表示例：
2009/7/28
4
2、链表与数组的主要区别,
数组的元素个数是固定的，而组成链表的结点个数可按需要增减；
数组元素的存贮单元在数组定义时分配，链表结点的存贮单元在程序执行时动态向系统申请；
数组中的元素顺序关系由元素在数组中的位置
（即下标）确定，链表中的结点顺序关系由结点所包含的指针来体现。
对于不是固定长度的列表，用可能最大长度的数组来描述，会浪费许多内存空间。另外，对于元素的插入、
删除操作非常频繁的列表处理场合，用数组表示列表也是不适宜的。若用链表实现，会使程序结构清晰，处理的方法也较为简便。
2009/7/28
5
链表的基本操作：建立链表,链表的插入,删除,输出和查找等 。
1,建立链表所谓建立链表是指一个一个地输入各结点数据,并建立起各结点前后相链的关系 。 下面通过一个例子来说明如何建立一个链表 。
两种方式：
链表尾插表头三、链表的基本操作
2009/7/28
6
链表建立程序如下：
# include < iostream.h >
# define NULL 0
class student
{ public:
char name[20]; /* 姓名 */
char id[10]; /* 学号 */
int score; /* 成绩 */
student *next; /* 指针 */
};
student *head,*now,*last;
例 建立链表，用链表存放学生数据,表中每一个数据项存放一个学生的数据。
2009/7/28
7
main()
{
int i ;
head = last = NULL ;
for ( i=0 ; ; i ++ )
{now = new student ;
/*分配节 点存储空间 */
if ( now == NULL ) /* 判断自由空间是否够用 */
{ cout<<,\n Not enough memory!”;
exit(1) ； /* 空间不够，返回 */
}
cout<<,\n enter name:,;
cin>>now -> name ; /* 输入姓名至当前结点 */
if ( now-> name[0] ==?\0' ) break ;
2009/7/28
8
else
{cout<<"\n enter id:" ;
cin>>now -> id ； /* 输入学号至当前接点 */
cout<<"\n enter score";
cin>>now -> score ; /* 输入成绩至当前接点 */
now -> next = NULL ;
if ( ! head ) /* 判断是否第一节点 head=NULL*/
head = now ; /* 头指针指向第一节点 */
else last->next=now ; /* 新节点添加在最后 */
last=now;
}
} /* for end */
}
链表的建立有链表尾与插表头两种方式，上面程序使用的是链表尾的方式。
2009/7/28
9
链表建立程序如下：
# include < iostream.h >
# define NULL 0
class student
{public:
int num; /* 学号 */
char name[20]; /* 姓名 */
int score; /* 成绩 */
student *next; /* 指针 */
};
student *head,*now;
例 用插表头法建立存放学生数据链表：
2009/7/28
10
main( )
{
int i ;
head = NULL ;
for ( i=0 ; ; i ++ )
{now = new student ;
/*分配节 点存储空间 */
if ( now == NULL ) /* 判断自由空间是否够用 */
{ cout<<,\n Not enough memory!”;
exit(1) ； /* 空间不够，返回 */
}
cout<<,\n enter name:,;
cin>>now -> name ; /* 输入姓名至当前结点 */
if ( now-> name[0] ==?\0' ) break ;
2009/7/28
11
else
{cout<<"\n enter num:" ;
cin>>now -> num ； /* 输入学号至当前接点 */
cout<<"\n enter score";
cin>>now -> score ; /* 输入成绩至当前接点 */
now -> next = NULL ;
if ( ! head ) /* 判断是否第一节点 head=NULL*/
head = now ; /* 头指针指向第一节点 */
else {now->next=head;/* 新节点添加在最后 */
head=now;
}
}
} /* for end */
}
2009/7/28
12
2,链表的插入操作将一个结点插入到一个已有的链表中 。
分两步：找到插入点插入结点如果插入的位置为第一结点之前,要修改头结点 （ head） 指针 。 如果要插到表尾之后,应将插入结点的指针域赋 NULL值 。
如果插入的位置既不在第一个结点之前,又不在表尾结点之后,则将相关指针域修改即可 。
2009/7/28
13
将指针 q所指结点插入第 n个结点之后
(b) 插入到第 2个结点之后
Head
p
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
70
(a) head指示已有链表，
q指示待插入结点
q 104
Zhao
70
Head
r
101
Zhang
90
q 104
Zhao
60
103
Wang
80
p
N
U
L
L
105
Li
70
2009/7/28
14
插入结点的函数 insert如下：
student *insert ( student *head)
{
student *p0,*p1,*p2;
p1=head; /*p1指向第一个结点 */
p0=new student; /*p0指向要插入的结点 */
cout<<“input all message\n”;
cin>>p0->name>>p0->num>>p0->score;
p0->next=NULL;
if (head==NULL) /*原来是空表 */
head=p0; /*使 p0指向的结点作为链表第一个结点 */
2009/7/28
15
else
{
while((p0->num>p1->num)&&(p1->next!=NULL))
{ p2=p1; p1=p1->next; }
/*p2指向刚才 p1指向的结点,p1后移一个结点 */
if (head==p1) {p0->next=head;
head=p0; /* 插到原来第一个结点之前 */
else {p0->next=p1; p2->next=p0; }
/*插到 p2指向的结点之后 */
return(head);
}
2009/7/28
16
3,链表的删除操作
要从链表中删除一个结点，不一定从内存中真正把它删除掉（当然也可使用 free函数真正释放），只要把它从链表中分离开来，即改变链表中的链接关系即可。
下面是从链表中删除指定结点的函数 del。
2009/7/28
17
删除第 n个结点
(a) head指示已有链表
Head
p
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
60
101
Zhao
70
(b) 删除第 3个结点
q p
Head
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
60
101
Zhao
70
2009/7/28
18
写一函数从链表中删除学号为指定值 num的结点
– 解题思路：首先让 p指向第一个结点，然后从 p开始检查该结点中的 num值是否等于指定值 num。如果相等，
则删除该结点；如果不等，则 p后移一个结点，再如此进行下去，直到遇到表尾为止。
– 注意：
首先要考虑链表是否为空
要设置两个指针变量分别指向待比较的结点和其前一结点
如果找到要删除的结点，要区分是否为第一个结点
2009/7/28
19
student *del( student *head;long num)
{ student *p1,*p2;;
if (head==NULL)
{cout<<"\nlist null!\n";return head}
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;
delete p1;
}
else cout<<num<<,not been found!\n";
return(head);
}
2009/7/28
20
4,输出链表
将链表中各结点的数据依次输出。这个问题比较简单。
首先要知道链表头元素的地址 head，然后设置一个指针变量 p，让它指向第一个结点，输出 p所指向的结点的值后使 p向后移动一个结点的位置，再输出之，直到
p移动到尾结点并输出尾结点的值,p再次移动则为空指针值，即可结束链表的输出。
下面是链表输出的函数 print。
2009/7/28
21
输出链表函数：
void print( student *head)
{ student *p;
cout<<"\nNow,These records are:\n";
p=head;
if (head!=NULL)
do
{cout<<p->num<<“\t”<<p->name
<<“\t”<<p->score;
p=p->next;
}while (p!=NULL);
}
2009/7/28
22
5,统计链表中结点个数只需将上述输出结点改成计数即可。
int count（ student *head） /*统计链表中结点个数 */
{int n=0；
student *p；
p=head；
while（ p！ =NULL
{n++； p=p->next； }
return（ n）；
}
2009/7/28
23
1
第二十一讲 用指针处理链表
教学目的与要求：
掌握链表的创建,插入,删除
教学内容提要：
1,链表的概述
2,链表的基本操作
教学重点：链表的创建,插入和删除
教学难点,链表的创建,插入和删除
教学进度：
教学过程：
2009/7/28
2
一、链表概述
1,链表：是指若干个数据项 （ 每个数据项称为一个,结点,）
按一定的原则连接起来 。 每个数据项都包含有若干个数据和一个指向下一个数据项的指针,依靠这些指针将所有的数据项连接成一个链表 。 下图表示了一个简单的链表 。
头指针 head
姓 名 1
学 号 1
成 绩 1
指 针 1
数据项 A 数据项 C
姓 名 2
学 号 2
成 绩 2
指 针 2
数据项 B
姓 名 3
学 号 3
成 绩 3
指 针 3
2009/7/28
3
1620
head
李为
2004101
85
0586
数据项 A 数据项 C
刘娜
2004102
93
3818
数据项 B
张三
2004125
95
0
1620 0586 3818
一个简单链表示例：
2009/7/28
4
2、链表与数组的主要区别,
数组的元素个数是固定的，而组成链表的结点个数可按需要增减；
数组元素的存贮单元在数组定义时分配，链表结点的存贮单元在程序执行时动态向系统申请；
数组中的元素顺序关系由元素在数组中的位置
（即下标）确定，链表中的结点顺序关系由结点所包含的指针来体现。
对于不是固定长度的列表，用可能最大长度的数组来描述，会浪费许多内存空间。另外，对于元素的插入、
删除操作非常频繁的列表处理场合，用数组表示列表也是不适宜的。若用链表实现，会使程序结构清晰，处理的方法也较为简便。
2009/7/28
5
链表的基本操作：建立链表,链表的插入,删除,输出和查找等 。
1,建立链表所谓建立链表是指一个一个地输入各结点数据,并建立起各结点前后相链的关系 。 下面通过一个例子来说明如何建立一个链表 。
两种方式：
链表尾插表头三、链表的基本操作
2009/7/28
6
链表建立程序如下：
# include < iostream.h >
# define NULL 0
class student
{ public:
char name[20]; /* 姓名 */
char id[10]; /* 学号 */
int score; /* 成绩 */
student *next; /* 指针 */
};
student *head,*now,*last;
例 建立链表，用链表存放学生数据,表中每一个数据项存放一个学生的数据。
2009/7/28
7
main()
{
int i ;
head = last = NULL ;
for ( i=0 ; ; i ++ )
{now = new student ;
/*分配节 点存储空间 */
if ( now == NULL ) /* 判断自由空间是否够用 */
{ cout<<,\n Not enough memory!”;
exit(1) ； /* 空间不够，返回 */
}
cout<<,\n enter name:,;
cin>>now -> name ; /* 输入姓名至当前结点 */
if ( now-> name[0] ==?\0' ) break ;
2009/7/28
8
else
{cout<<"\n enter id:" ;
cin>>now -> id ； /* 输入学号至当前接点 */
cout<<"\n enter score";
cin>>now -> score ; /* 输入成绩至当前接点 */
now -> next = NULL ;
if ( ! head ) /* 判断是否第一节点 head=NULL*/
head = now ; /* 头指针指向第一节点 */
else last->next=now ; /* 新节点添加在最后 */
last=now;
}
} /* for end */
}
链表的建立有链表尾与插表头两种方式，上面程序使用的是链表尾的方式。
2009/7/28
9
链表建立程序如下：
# include < iostream.h >
# define NULL 0
class student
{public:
int num; /* 学号 */
char name[20]; /* 姓名 */
int score; /* 成绩 */
student *next; /* 指针 */
};
student *head,*now;
例 用插表头法建立存放学生数据链表：
2009/7/28
10
main( )
{
int i ;
head = NULL ;
for ( i=0 ; ; i ++ )
{now = new student ;
/*分配节 点存储空间 */
if ( now == NULL ) /* 判断自由空间是否够用 */
{ cout<<,\n Not enough memory!”;
exit(1) ； /* 空间不够，返回 */
}
cout<<,\n enter name:,;
cin>>now -> name ; /* 输入姓名至当前结点 */
if ( now-> name[0] ==?\0' ) break ;
2009/7/28
11
else
{cout<<"\n enter num:" ;
cin>>now -> num ； /* 输入学号至当前接点 */
cout<<"\n enter score";
cin>>now -> score ; /* 输入成绩至当前接点 */
now -> next = NULL ;
if ( ! head ) /* 判断是否第一节点 head=NULL*/
head = now ; /* 头指针指向第一节点 */
else {now->next=head;/* 新节点添加在最后 */
head=now;
}
}
} /* for end */
}
2009/7/28
12
2,链表的插入操作将一个结点插入到一个已有的链表中 。
分两步：找到插入点插入结点如果插入的位置为第一结点之前,要修改头结点 （ head） 指针 。 如果要插到表尾之后,应将插入结点的指针域赋 NULL值 。
如果插入的位置既不在第一个结点之前,又不在表尾结点之后,则将相关指针域修改即可 。
2009/7/28
13
将指针 q所指结点插入第 n个结点之后
(b) 插入到第 2个结点之后
Head
p
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
70
(a) head指示已有链表，
q指示待插入结点
q 104
Zhao
70
Head
r
101
Zhang
90
q 104
Zhao
60
103
Wang
80
p
N
U
L
L
105
Li
70
2009/7/28
14
插入结点的函数 insert如下：
student *insert ( student *head)
{
student *p0,*p1,*p2;
p1=head; /*p1指向第一个结点 */
p0=new student; /*p0指向要插入的结点 */
cout<<“input all message\n”;
cin>>p0->name>>p0->num>>p0->score;
p0->next=NULL;
if (head==NULL) /*原来是空表 */
head=p0; /*使 p0指向的结点作为链表第一个结点 */
2009/7/28
15
else
{
while((p0->num>p1->num)&&(p1->next!=NULL))
{ p2=p1; p1=p1->next; }
/*p2指向刚才 p1指向的结点,p1后移一个结点 */
if (head==p1) {p0->next=head;
head=p0; /* 插到原来第一个结点之前 */
else {p0->next=p1; p2->next=p0; }
/*插到 p2指向的结点之后 */
return(head);
}
2009/7/28
16
3,链表的删除操作
要从链表中删除一个结点，不一定从内存中真正把它删除掉（当然也可使用 free函数真正释放），只要把它从链表中分离开来，即改变链表中的链接关系即可。
下面是从链表中删除指定结点的函数 del。
2009/7/28
17
删除第 n个结点
(a) head指示已有链表
Head
p
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
60
101
Zhao
70
(b) 删除第 3个结点
q p
Head
101
Zhang
90
103
Wang
80
N
U
L
L
105
Li
60
101
Zhao
70
2009/7/28
18
写一函数从链表中删除学号为指定值 num的结点
– 解题思路：首先让 p指向第一个结点，然后从 p开始检查该结点中的 num值是否等于指定值 num。如果相等，
则删除该结点；如果不等，则 p后移一个结点，再如此进行下去，直到遇到表尾为止。
– 注意：
首先要考虑链表是否为空
要设置两个指针变量分别指向待比较的结点和其前一结点
如果找到要删除的结点，要区分是否为第一个结点
2009/7/28
19
student *del( student *head;long num)
{ student *p1,*p2;;
if (head==NULL)
{cout<<"\nlist null!\n";return head}
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;
delete p1;
}
else cout<<num<<,not been found!\n";
return(head);
}
2009/7/28
20
4,输出链表
将链表中各结点的数据依次输出。这个问题比较简单。
首先要知道链表头元素的地址 head，然后设置一个指针变量 p，让它指向第一个结点，输出 p所指向的结点的值后使 p向后移动一个结点的位置，再输出之，直到
p移动到尾结点并输出尾结点的值,p再次移动则为空指针值，即可结束链表的输出。
下面是链表输出的函数 print。
2009/7/28
21
输出链表函数：
void print( student *head)
{ student *p;
cout<<"\nNow,These records are:\n";
p=head;
if (head!=NULL)
do
{cout<<p->num<<“\t”<<p->name
<<“\t”<<p->score;
p=p->next;
}while (p!=NULL);
}
2009/7/28
22
5,统计链表中结点个数只需将上述输出结点改成计数即可。
int count（ student *head） /*统计链表中结点个数 */
{int n=0；
student *p；
p=head；
while（ p！ =NULL
{n++； p=p->next； }
return（ n）；
}
2009/7/28
23
