数据结构之链表.ppt

文档介绍：SCIE, University of Electronic Science and Technology of China
1

线性表不同的实现方式:

顺序表定义
顺序表基本操作:
遍历、插入、删除
顺序表算法分析



SCIE, University of Electronic Science and Technology of China
2

#include "“
struct list_seq {
int data[20];
int length;
};
int main(){
struct list_seq list;
int no, i;

=0;
for(i=0;i<10;i++){
scanf("%d",&no); if(no==0) break;
[i]=no;++;
}
no=30;
insert(list,no,5);
delete(list,8)
return 0;
}
SCIE, University of Electronic Science and Technology of China
3

一、链表的引入
数组结构的缺点:
1、在插入、删除时要移动大量的节点
2、表的大小固定。
预先在申明数组时指定,无法更改
原因:
存放的连续性
突破
离散存放
用指针来表示元素之间的关系。
SCIE, University of Electronic Science and Technology of China
4

用链表实现线性表(非连续存储)
线性表元素:a1、a2、a3、a4....
链表链点
线性关系:
a1
a2
a3
a4
指针域,指针关系
a1
a2
a3
a4
a1
a2
a3
a4
顺序存储
链式存储
SCIE, University of Electronic Science and Technology of China
5

二、链表的定义
链点
data
link
元素域
链接域
数据域(数据元素域):存放一个数据元素。
链接域(关系域):存放指向下一个元素的指针
——元素间的关系。
数据域+ 链接域= 结点(链点)
SCIE, University of Electronic Science and Technology of China
6

链表
a1
a2
an
……
由链点及链点相互间的链接构成
head
链表头
链表尾
链表长度(节点数目)
tail
length
^
SCIE, University of Electronic Science and Technology of China
7

定义
struct node_type{
elemtype data;
struct node_type * next;
} ;
struct list_type{
node_type *head;
node_type *tail;
int length;
};
链点的定义
链表的定义
data
next
8

SCIE, University of Electronic Science and Technology of China
8
带头节点的单链表
a1
an
……
head
^
带头节点链表的引入是为了使算法对空表和非空表的处理一致
普通单链表对链表尾的判断
(假定p是链表尾的指针)
空表: p==null;
非空表:p->next==null;
带头节点单链表对链表尾的判断
空表: p->next==null;
非空表:p->next==null;
SCIE, University of Electronic Science and Technology of China
9

初始化算法:
elemtype initlist(node * * h)
{
*h=(node *)malloc(sizeof(node));
(*h)->next=null;
}
三、链表的基本操作
访问
插入
删除
SCIE, University of Electronic Science and Technology of China
10