第02章_线性表（I）.ppt

文档介绍：数据结构
李云清杨庆红揭安全
第2章线性表及其顺序存储
线性表是一种常用的数据结构,本章介绍线性表及其顺序存储,并对栈和队列及它们的顺序实现给出了详细的设计描述。

线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。

线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
如顺序表的每个结点占用len个内存单元,用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系
location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len

顺序表的存储结构如下图所示:
存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。
顺序表类型的描述如下:
ADT sequence_list{
数据集合K:K={k1, k2,…, kn},n≥0,K中的元素是datatype类型
数据关系R:R={r},r={ <ki, ki+1>| i=1,2,…,n-1}
操作集合:
(1) void init_sequence_list(sequence_list *slt) 顺序表的初始化------置空表
(2) void insert_sequence_list(sequence_list *slt,datatype x) 后部插入值为x结点
(3) void print_sequence_list(sequence_list slt) 打印顺序表的各结点值
(4) int is_empty_sequence_list(sequence_list slt) 判断顺序表是否为空
(5) int find_num_sequence_list(sequence_list slt,datatype x) 查找值为x结点位置
(6) int get_data_pos(sequence_list slt,int i) 取得顺序表中第i个结点的值
(7) void insert_pos_sequence_list(sequence_list *slt,int position,datatype x)
(8) void delete_pos_sequence_list(sequence_list *slt,int position)
} ADT sequence_list;

用C语言中的数组存储顺序表。C语言中数组的下标是从0开始的,即数组中下标为0的元素对应的是顺序表中的第1个结点,数组中下标为i的元素对应的是顺序表中的第i+1个结点。为了方便,将顺序表中各结点的序号改为和对应数组元素的下标序号一致,即将顺序表中各结点的序号从0开始编号。这样,一个长度为n的顺序表可以表示为
{k0, k1, k2, …, kn-1}
顺序表的存储结构的C语言描述如下:
/********************************/
/*顺序表的头文件,*/
/********************************/
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int size;
}sequence_list;
顺序表的几个基本操作的具体实现:
/********************************************/
/* 顺序表的初始化---置空表*/
/* , 函数名init_sequence_list() */
/*******************************************/
void init_sequence_list(sequence_list *slt)
{
slt->size=0;
}
---置空表
/**********************************************/
/* 在顺序表后部进行插入操作*/
/* , 函数名insert_sequenc