文档介绍：数据结构
李云清杨庆红揭安全
第3章线性表的链式存储
线性表的存储方式除了常用的顺序存储外,采用链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式,如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表------栈和队列的链式存储实现。
数据结构的存储方式必须体现它的逻辑关系。在链式存储方式下,实现中除存放一个结点的信息外,还需附设指针,用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱,那么可以附设相应个数的指针,一个结点附设的指针指向的是这个结点的某个前驱或后继。
线性结构中,每个结点最多只有一个前驱和一个后继,这里暂且设定更关心它的后继,这样在存储时除了存放该结点的信息外,只要附设一个指针即可,该指针指向它的后继结点的存放位置。每个结点的存储形式是:
info
next
例,数据的逻辑结构B=(K,R)
其中 K={k1,k2,k3,k4,k5}
R={r}
R={< k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}
是一个线性结构,它的链式存储如图所示
为了清晰,左图可以更简洁地用下图表示。
单链表
单链表是线性表链式存储的一种形式,其中的结点一般含有两个域,一个是存放数据信息的info域,另一个是指向该结点的后继结点的存放地址的指针域next。一个单链表必须有一个首指针指向单链表中的第一个结点。。
单链表类型的描述如下:
ADT link_list{
数据集合K:K={k1, k2,…, kn},n≥0,K中的元素是datatype类型
数据关系R:R={r}
r={ <ki, ki+1>| i=1,2,…,n-1}
操作集合:
(1) node *init_link_list() 建立一个空的单链表
(2) void print_link_list(node *head) 输出单链表中各个结点的值
(3) node *insert_in_front_link_list(node *head,datatype x)
插入一个值为x的结点作为单链表的第一个结点
(4) node *find_num_link_list(node *head,datatype x) 在单链表中查找一个值为x的结点
(5) node *find_pos_link_list(node *head,int i) 在单链表中查找第i个结点
(6) node *insert_x_after_y(node *head,datatype x,datatype y)
在单链表中值为y的结点后插入一个值为x的新结点
(7) node *insert_x_after_i(node *head,datatype x,int i)
在单链表中第i个结点后插入一个值为x的新结点
(8) node *delete_num_link_list(node *head,datatype x) 在单链表中删除一个值为x的结点
(9) node *delete_pos_link_list(node *head,int i) 在单链表中删除第i个结点
} ADT link_list;
单链表结构的C语言描述如下:
/**********************************/
/*链表实现的头文件, */
/**********************************/
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
单链表几个基本操作的具体实现:
/*****************************************************/
/* 建立一个空的单链表*/
/* ,函数名init_link_list() */
/*****************************************************/
node *init_link_list() /*建立一个空的单链表*/
{
return NULL;
}
/*****************************************************/
/* 输出单链表中各个结点的值*/
/* ,函数名print_link_list() */
/**********************