计算机软件技术基础课件-2(线性表).ppt

计算机软件技术基础课件-2(线性表).ppt1、基本概念、术语及类型定义 2、线性表的顺序表示和实现 3、线性表的链式表示和实现  4、线性表的实例应用
§2 线性表
1、基本概念、术语及类型定义
线性表:
n个数据元素的有限序列。
线性表中数据元素在不同的环境下可以有不同的具体含义,但在同一数据表中数据元素性质必须相同。
表长:
线性表中数据元素的个数n(n≧0)。
空表:
n=0时的线性表。
一般表示形式:
L=(a1,a2,… ai, …,an)
其中:a i(i=1‥n)是属于某数据对象的元素。
线性表的特点:
在线性表中存在唯一的“第一个”元素。
在线性表中存在唯一的“最后一个”元素。
除第一个元素以外,每个元素有且只有一个直接前驱
除最后一个元素以外,每个元素有且只有一个直接后继
线性表的抽象定义:
L=(D,R,P)
D=( a1,a2,… ai, …,an ) 数据对象
1、基本概念、术语及类型定义
P: 基本操作,包括有:
建立一个线性表;
在线性表中插入元素;
删除线性表中的元素;
查找线性表中的元素;
对线性表中的元素进行排序;
留到后面专门讨论
R= { <ai-1,ai>︳ai-1,ai∈D, 2≦i≦n ) 数据关系
2、线性表的顺序表示和实现
顺序表:
是指用一组地址连续的存储单元依次存放线性表中数据元素。
线性表的顺序表示称为顺序存储线性表,简称顺序表。
顺序表的存储结构示意
Adr(a1)=b
Adr(a2)=b+k
Adr(ai)=b+(i-1)k
a1
a2
ai
an
…
…
顺序表的存储特点
存储单元地址连续,即需要一段连续空间;
逻辑上相邻的元素,其物理地址也相邻;
随机存取;
存储密度最大(达100%),不需要额外的空间来管理数据;
b—线性表在内存中的首地址
k—元素占用存储单元的大小
k
顺序表的数据类型描述
在具体实现时,可以用高级语言中的一维数组类型来描述。
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+1 n n+1 m
a2
…
ai-1
an
a1
ai
…
…
ai+1
插入运算
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+1 n n+1 m
a2
…
ai-1
an+1
a1
ai
…
…
ai+1
插入运算
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+1 n+1 m
a2
…
ai-1
an+1
a1
ai
…
…
ai+1
插入运算
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+2 n+1 m
a2
…
ai-1
an+1
a1
ai
…
…
ai+2
插入运算
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+1 i+2 n+1 m
a2
…
ai-1
an+1
a1
…
…
ai+2
ai+1
插入运算
2、线性表的顺序表示和实现
顺序表的插入和删除算法
要求:在长度为n的线性表中第i个元素之前插入元素x。
1 2 i-1 i i+1 n+1 m
a2
…
ai-1
an+1
a1
ai+1
…
x
算法描述如下:
InsertList(V,n,I,x)
If (i<1) or (i>n+1) then {参数错误!}
for j=n to I step(-1)
V[j+1] ←v[j]
endfor
V[i] ←x
n←n+1
return
初始条件:V存在且插入位置有效!
插入前的准备工作:为待插入的元素腾出位置。
插入元素x
表长加1
插入运算