数据结构——线性表.ppt

20010年2月
第二章线性表
《数据结构》
制作者:叶洁
第二章线性表
线性表的基本概念

线性表的顺序存储及操作实现

线性表的链式存储及操作实现

线性表的应用



循环链表和双向链表
§
线性表的定义及表示
线性表的特点
线性表的基本运算
一、线性表的定义及表示
1、线性表的定义
由n(n≧)个数据元素(结点)a1,a2, …an组成的有限序列。
(a1,a2,…an)
其中:
n:数据元素的个数,也称表的长度。
空表:n=0,记为()
2、线性表的表示
a1
a2
a3
ai
an
…
…
二、线性结构的特点
1、存在唯一的一个被称为“第一个”的数据元素,称为首元素。
2、存在唯一的一个被称为“最后一个”的数据元素,称为尾元素
3、除第一个之外,集合中的每个元素均有且只有一个前驱除,最后一个之外,集合中每个数据元素有且只有一个后继。
三、线性表的基本运算
1、初始化,设置空的线性表
2、求线性表的长度
3、插入,在给定的线性表中,将数据元素插入到第任意的位置。
4、删除,在给定的线性表中,删除任意位置的元素。
5、获取线性表中任意位置结点的值。
6、查找定位。查找线性表中是否存在某值
7、取Item的后继结点
8、取Item的前驱结点  
9、清空线性表
§ -顺序表
顺序表的存储结构
顺序表的存储实现
基于顺序表的操作实现
一、顺序表存储结构
顺序表:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储格里。用这种方法存储的线性表简称顺序表。
思路:逻辑上相邻的数据元素存放在相邻的存储空间中,即物理相邻体现逻辑相邻。
线性表-有n个元素
(a1,a2……ai……an)
申请连续空间大小为maxsize
放入元素
内存
0
maxsize-1
考虑n和maxsize的关系
a1
a2
an
已用空间
备用空间
二、顺序表的存储实现
用C语言实现
struct List {
ElemType *elem;
int size;
int maxsize;
};
//存放线性表的动态存储空间的指针
//线性表的大小
//存储空间的大小
二、顺序表的存储实现
类型实例化
typedef int ElemType;
struct List {
ElemType *elem;
int size;
int maxsize;
};