数据结构 单链表讲授.ppt

数据结构
——第2章线性表
掌握线性表的顺序存储的实现及顺序表的存储类型定义。
掌握顺序表的创建、查找、插入和删除算法及算法的分析(时间复杂度)。
复习
本章内容
线性表的逻辑结构
线性表的顺序存储及运算实现
线性表的链式存储及运算实现
线性表的链式存储和运算实现
单链表
单链表上基本运算的实现
循环链表和双向链表
静态链表
单链表应用举例
单链表
线性表以链式存储方式存储时称为链表。
存储实现:
◆用一组任意的存储单元存储线性表的元素;
◆利用指针存放逻辑上相邻的元素间的关系。
结论:每个数据元素,除存储本身信息外,还需存储其直接后继的地址。
结点
数据域:元素本身信息
指针域:指示直接后继的存储位置
数据域指针域
单链表
相关术语
单链表头指针值域
指针域 NULL 头结点
结点类型定义:
typedef struct node
{ DataType data;
struct node *next;
} LNode,*LinkList;
举例:LNode *L; LinkList L;
单链表上基本运算的实现
1、单链表的创建(头插入法和尾插入法)
2、单链表的查找
3、单链表的插入
4、单链表的删除
单链表上基本运算的实现
1、单链表的创建
用头插入法建立单链表
◆创建一个新结点的语句
◆创建一个带头结点的单链表
◆创建单链表的过程
◆结点间的连接语句
单链表上基本运算的实现
1、单链表的创建
用头插入法建立单链表
◆创建一个新结点的语句
LNode *s;
s=new LNode; s->data=x;
◆创建一个带头结点的单链表
◆创建单链表的过程
◆结点间的连接语句
单链表上基本运算的实现
1、单链表的创建
用头插入法建立单链表
◆创建一个新结点的语句
◆创建一个带头结点的单链表
LinkList L;
L=new LNode; L->next=NULL;
◆创建单链表的过程
◆结点间的连接语句