文档介绍：(第三讲)
绍兴文理学院
计算机系计算机应用教研室
数据结构
TKS
2
如何把一批数据“链”起来?
21:58
第2章线性表(2)
一、教学目的:明确线性表的链式存储结构;掌握单链表、循环链表和双向链表的结构定义和基本操作;算法设计训练。
二、教学重点:线性表的链式存储结构;单链表的结构定义和基本操作;算法设计。
三、教学难点:单链表的基本操作;算法设计。
四、教学过程:
n个结点链接成一个链表
数据元素(数据域)+指示后继元素存储位置(指针域(指针、链))
=数据元素的存储映象
-- 结点
-- 线性表的链式存储结构
链表的每个结点中只包含一个指针域
线性链表、单链表
▲顺序表的优缺点
◆无须为表示节点间的逻辑关系而增加额外的存储空间。
◆可以方便的随机存取表中的任一结点。
◆插入和删除运算不方便。
◆由于要求占用连续的存储空间,存储分配只能预先进行。
§ 单链表的定义和表示
(1) 概念
用一组地址任意的存储单元存放线性表中的数据元素。
§ 线性表的链式表示和实现
TKS
4
21:58
(2) 线性表及其链式存储结构
线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
链式存储结构为:
存储地址数据域指针域
头指针
31
1 LI 43
7 QIAN 13
13 SUN 1
19 WANG NULL
25 WU 37
31 ZHAO 7
37 ZHENG 19
43 ZHOU 25
TKS
5
21:58
线性链表可表示为:
ZHAO
QIAN
SUN
LI
ZHOU
WU
ZHENG
WANG ∧
H
(3) 单链表存储结构
typedef struct lnode
{ elemtype data;
struct lnode *next;
}lnode,*linklist;
data next
(4) 带头结点的单链表
a1
a2
an
…
∧
L
L
∧
TKS
6
21:58
§ 单链表基本操作的实现
1、动态链表的建立
(1) 算法思想
设:链表的结点结构为:
typedef struct node
{char data;
node *next;
}*linklist;
首先要建立一个只有头结点的空链表L,可调用算法initlist_l完成,为了使新结点能够插入到表尾,需要增加一个尾指针r指向链表的尾结点。
初始时,r与L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点r之后,然后使r指向新的尾结点。
当输入‘*’时结束,‘*’不是元素。
TKS
7
21:58
∧
(2) 后插法创建单链表及其演示
void createlist_l(linklist l)
{ // 输入若干个元素的值,后插
// 法建立带表头结点的单链表
TKS
8
21:58
int initlist_l(linklist &l)
{ // 生成新结点作为头结点,
// 用头指针l指向头结点
L
r
return 1;
}
l=new node;
l->next=NULL;
linklist p,r;char ch;
r=l;
p
p->next=NULL;
cin>>ch;
while(ch!='*')
{ p=new node;
p->data=ch;
a
}
∧
r->next=p;
r=p;
r
r
cin>>ch;
}
p=new node;
p
e
∧
b
p->data=ch;
∧
p->next=NULL;
r->next=p;
r=p;
r
cin>>ch;
p=new node;
p
p->data=ch;
c
p->next=NULL;
∧
r->next=p;
r
r=p;
cin>>ch;
p=new node;
p
p->data=ch;
d
p->next=NULL;
∧
r->next=p;
r=p;
r
cin>>ch;
p=new node;
p
p->data=ch;
p->next=NULL;
r->next=p;
r=p;
cin>>ch;
后插法创建单链表 S3_1
∧
(3) 前插法创建单链表及其演示
void createlist_l(linklist l)
{ // 输入若干个元素的值,后插
// 法建立带表头结点的单链表
TKS
9
21:58