中国铁道出版社：《C++面向对象程序设计》课程教学资源（PPT课件讲稿）第21讲 用指针处理链表

第二十一讲用指针处理链表 教学目的与要求 掌握链表的创建、插入、删除 教学内容提要: 1、链表的概述 2、链表的基本操作 教学重点:链表的创建、插入和删除 教学难点:链表的创建、插入和删除 教学进度: 教学过程: 2021/224

2021/2/24 1 第二十一讲 用指针处理链表 • 教学目的与要求： 掌握链表的创建、插入、删除 • 教学内容提要： 1、链表的概述 2、链表的基本操作 • 教学重点：链表的创建、插入和删除 • 教学难点：链表的创建、插入和删除 • 教学进度： • 教学过程：

、链表概述 1、链表:是指若干个数据项(每个数据项称为一个“结点”) 按一定的原则连接起来。每个数据项都包含有若干个数据和 个指向下一个数据项的指针,依靠这些指针将所有的数据 项连接成一个链表。下图表示了一个简单的链表。 数据项A 数据项B 数据项C 姓名1 姓名2 姓名3 头指针head学号1 学号2 学号3 成绩1 成绩2 成绩3 指针1 指针2 指针3 2021/224

2021/2/24 2 一、链表概述 1、链表：是指若干个数据项（每个数据项称为一个“结点”） 按一定的原则连接起来。每个数据项都包含有若干个数据和 一个指向下一个数据项的指针，依靠这些指针将所有的数据 项连接成一个链表。下图表示了一个简单的链表。 头指针head 姓 名1 学 号1 成 绩1 指 针1 数据项A 数据项C 姓 名2 学 号2 成 绩2 指 针2 数据项B 姓 名3 学 号3 成 绩3 指 针3

个简单链表示例 数据项A 数据项B 数据项C 1620 1620 李为1“536「刘娜1318「张 head 2004101 2004102 2004125 85 93 0586 3818 2021/224

2021/2/24 3 1620 head 李为 2004101 85 0586 数据项A 数据项C 刘娜 2004102 93 3818 数据项B 张三 2004125 95 0 1620 0586 3818 一个简单链表示例：

2、鲢痃与藪组的圭要区列 数组的元素个数是固定的,而组成链表的结点个 数可按需要增减 数组元素的存贮单元在数组定义时分配,链表结 点的存贮单元在程序执行时动态向系统申请; 数组中的元素顺序关系由元素在数组中的位置 (即下标)确定,链表中的结点顺序关系由结点所包含的 指针来体现。 对于不是固定长度的列表,用可能最大长度的数 组来描述,会浪费许多内存空间。另外,对于元素的插入、 删除操作非常频繁的列表处理场合,用数组表示列表也是 不适宜的。若用链表实现,会使程序结构清晰,处理的方 法也较为简便。 2021/224

2021/2/24 4 2、链表与数组的主要区别: 数组的元素个数是固定的，而组成链表的结点个 数可按需要增减； 数组元素的存贮单元在数组定义时分配，链表结 点的存贮单元在程序执行时动态向系统申请； 数组中的元素顺序关系由元素在数组中的位置 （即下标）确定，链表中的结点顺序关系由结点所包含的 指针来体现。 对于不是固定长度的列表，用可能最大长度的数 组来描述，会浪费许多内存空间。另外，对于元素的插入、 删除操作非常频繁的列表处理场合，用数组表示列表也是 不适宜的。若用链表实现，会使程序结构清晰，处理的方 法也较为简便

、链表的基本操作 链表的基本操作:建立链表、链表的插入、删除、输出和 查找等。 1.建立链表 所谓建立链表是指一个一个地输入各结点数据,并建立起 各结点前后相链的关系。下面通过一个例子来说明如何建 立一个链表。 两种方式: 链表尾 插表头 2021/224

2021/2/24 5 链表的基本操作：建立链表、链表的插入、删除、输出和 查找等。 1. 建立链表 所谓建立链表是指一个一个地输入各结点数据，并建立起 各结点前后相链的关系。下面通过一个例子来说明如何建 立一个链表。 两种方式： 链表尾 插表头 三、链表的基本操作

例建立链表,用链表存放学生数据表中每一个数据 项存放一个学生的数据。 链表建立程序如下: t include iostream. h tt define null o class student publIC char name [20] /*姓名*/ char id[10] /米学号米/ int score /*成绩米 student米next; /*指针米/ student ** head. *know. * last 2021/224

2021/2/24 6 链表建立程序如下： # include # define NULL 0 class student { public: char name[20]; /* 姓名 */ char id[10]; /* 学号 */ int score; /* 成绩 */ student *next; /* 指针 */ }; student *head,*now,*last; 例 建立链表，用链表存放学生数据,表中每一个数据 项存放一个学生的数据

maint ( int head s last= NUll for(i=0;;i++) know new student 分配节点存储空间* if(noW==NULL)/判断自由空间是否够用 {cout≤≤“ In Not enough memory! exit(1) 空间不够,返回 cout>now→name;/输入姓名至当前结点* if(now->name[o]==°0°) break; 2021/224

2021/2/24 7 main() { int i ; head = last = NULL ; for ( i=0 ; ; i ++ ) {now = new student ; /*分配节 点存储空间*/ if ( now == NULL ) /* 判断自由空间是否够用 */ { cout>now -> name ; /* 输入姓名至当前结点 */ if ( now-> name[0] == ‘\0' ) break ;

else cout>now ->id /*输入学号至当前接点*/ coutnow-> score;/*输入成绩至当前接点*/ now -> next NULL if ( head *判断是否第一节点head=NUL米/ head=now;/*头指针指向第一节点*/ else last->next=now;/*新节点添加在最后米/ last≡now; }/米 for end*/ 链表的建立有链表尾与插表头两种方式,上面程序使用的 是链表尾的方式 2021/224

2021/2/24 8 else {cout>now -> id ； /* 输入学号至当前接点 */ cout>now -> score ; /* 输入成绩至当前接点 */ now -> next = NULL ; if ( ! head ) /* 判断是否第一节点head=NULL*/ head = now ; /* 头指针指向第一节点 */ else last->next=now ; /* 新节点添加在最后 */ last=now; } } /* for end */ } 链表的建立有链表尾与插表头两种方式，上面程序使用的 是链表尾的方式

例用插表头法建立存放学生数据链表: 链表建立程序如下: t include< iostream.h t define null o class student Ipublic int num /*学号米/ char name 201 /*姓名*/ int score /*成绩* student米next; *指针*/ student*head,米noW; 2021/224

2021/2/24 9 链表建立程序如下： # include # define NULL 0 class student {public: int num; /* 学号 */ char name[20]; /* 姓名 */ int score; /* 成绩 */ student *next; /* 指针 */ }; student *head,*now; 例 用插表头法建立存放学生数据链表：

maino int i head E null for(i=0;;i++) know new student 分配节点存储空间* if(noW==NULL)/判断自由空间是否够用 {cout≤≤“ In Not enough memory! exit(1) 空间不够,返回 cout>now→name;/输入姓名至当前结点* if(now->name[o]==°0°) break; 2021/224

2021/2/24 10 main( ) { int i ; head = NULL ; for ( i=0 ; ; i ++ ) {now = new student ; /*分配节 点存储空间*/ if ( now == NULL ) /* 判断自由空间是否够用 */ { cout>now -> name ; /* 输入姓名至当前结点 */ if ( now-> name[0] == ‘\0' ) break ;