c语言数据结构.ppt

第二章线性表
本章主要内容:
•线性表的定义
•线性表的顺序存储结构及其基本操作
•线性表的链式存储结构及其基本操作
学****目的及要求:
•掌握线性表的定义
•掌握线性表的两种存储结构
第二章线性表
线性表的定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性表的定义
线性结构
线性表
栈
队列
串
数组
广义表
一个数据元素的有序(次序)集。
基本特征:
“第一元素”
“最后元素”
,均有唯一后继
,均有唯一前驱
一、定义
二、特点
三、抽象数据类型线性表的定义
线性表的定义
一、定义
线性表——是由n个具有相同特性的数据元素a1,a2,…,an组成的有限序列, 记为(a1,a2,…,an)。
。
。n=0时,称为空表;n>0时,线性表中每i个数据元素记为ai ,i为数据元素的位序。

线性表的定义
二、特点
。
(下标)确定的。
,每个数据元素有且仅有一个前驱元素;除最后一个元素an外,每个数据元素有且仅有一个后继元素。
a1 a2 a3 a4 ……an

线性表的定义
三、抽象数据类型线性表的定义
ADT List {
数据对象:D={ai| ai∈ElemSet,1≤i≤n,n≥0}
{n为表长,n=0为空表}
数据关系:R={<ai,ai+1>}| ai, ai+1∈D,1≤i≤n-1}
{i为序位。}

线性表的定义
基本操作:见书
}
线性表的顺序表示和实现
一、线性表的顺序存储结构
二、线性表顺序存储结构的实现
一、线性表的顺序存储结构

用一组地址连续的存储单元存储线性表的数据元素,此线性表又称顺序表。这种存储又称顺序映象。
a1
a2
ai
an
…
1
2
…
i
…
n
…
b
b+L
b+2L
b+(i-1)L
b+(n-1)L
两方面的内容:
(1)顺序表常用数组来描述
(2)设每个数据元素占用L个存储单元,则第i个数据元素的存储位置
记为LOC(ai),与其相邻元素ai-1 的存储位置LOC(ai-1)的关系满足:
LOC(ai)=LOC(ai-1)+L
第i数据元素ai 的存储位置为:
LOC(ai)=LOC(a1)+(i-1)*L

线性表的顺序表示和实现
b:线性表的
起始位置
与b相差一个与位序成正比的常量
一、线性表的顺序存储结构

逻辑相邻且物理相邻数据元素之间的逻辑关系
随机存取
(1) 优点
   。
。
(2)缺点
。
,较难确定所需的存储空间。

线性表的顺序表示和实现