《数据结构》教案(2)

　(3)删除操作


　　课程名称：数据结构任 课 教 师总课序授 课
时 间撰写（修改）讲 课 内 容2.3.1节课 型
（教法）多媒体讲授课 题 单链表存储及其运算教 具
准 备教 学
目 的　掌握单链表存储结构及运算的实现。教 学
重 点　建立单链表及实现结点的插入和删除等基本运算教 学
难 点
与关键　关键：单链表存储结构定义
　难点：基本运算的实现
教学内容纲要：
2.3 线性表的链式表示和实现
2.3.1 线性链表
1、线性表的链式存储结构的特点
相关概念：结点（Node）、数据域、指针域、指针、链、头指针
2、链式存储结构的优点：
插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。
链表的分类
单链表、循环链表和双向链表。
3.单链表：
(1)单链表概念：
链表中的每一个结点中只包含一个指针域的称为单链表或线性链表。


(2)单链表的存储结构定义
typedef struc LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
(3)单链表的操作：
* 访问：
算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。
* 插入操作：要在数据元素a和b 之间插入元素x。
算法思想：决定a和b之间的相邻关系是由a 的指针决定的。若要实现插入，生成x结点，然后让a 的指针指向x 且x 的指针指向b。实现三个元a、x和b的逻辑关系。
设p为指向结点a 的指针，s为指向结点x的指针，则修改s、a的指针：
s→next=p→next；p→next=s；
* 删除操作：在单链表数据元素a、b、c三个相邻的元素中删除b，算法思想：就是要让a 的指针直接指向c，使b从链表中脱离。
即，p→next=p→next→next
* 单链表的合并：

艺术的大道上荆棘丛生，这也是好事，常人望而却步，只有意志坚强的人例外。——雨果
例：将两个有序链表合并为一个有序链表。
设立三个指针pa、pb和pc 分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到合并表中，即，让合
并表的当前指针指向该元素，然后，修改指针。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。




　　课程名称：数据结构任 课 教 师总课序授 课
时 间撰写（修改）讲 课 内 容2.