文档介绍：第十三章软件技术基础
主讲:张明旺
数据结构
1、基本概念
数据
所有能被计算机处理的符号的集合
包括:常数、字母、程序、图形、语言等。
数据元素
给定数据集合中的个体
设给定数据集合为:
D={d1,d2,...,dn}则di属于D,并称di为数据元素。
例如
给定数据集合
班级A={学生a,学生b………学生n}
则班级中的每一个学生称为数据元素。
数据项
数据元素常常还可分为若干个数据项,数据项是数据具有意义的最小单位。
例如:学生a的姓名、性别、年龄等都是数据项
数据之间的逻辑结构
反映数据元素之间的关系
线性结构:
仅有一个开始和结束数据元素,每个数据元素最多只有一个直接前驱和直接后继。(数组)
非线性结构:
数据元素可能有多个直接前驱和直接后继(树、图)
线性表及其基本运算
1、线性表(linear_list)
线性表是n个数据元素的有限序列,记为:
L=(a1,a2, …,an)
数据元素之间的关系是:
ai-1领先于ai,ai领先于ai+1。
称ai-1是ai的直接前驱元素;ai+1是ai的直接后继元素。
除a1外,每个元素有且仅有一个直接前驱元素;
除an外,每个元素有且仅有一个直接后继元素;
线性表中数据元素的个数n(n>=0)称为线性表的长度;
当n=0时,称为空表。
2、基本运算
INITIATE(L) 初始化操作设定一个空的线性表L
LENGTH(L) 求长度函数值为L中数据元素的个数
GET(L,i) 取元素函数 1<=i<=LENGTH(L)时返回L中第i个数据元素,否则为空元素NULL。 i称为该数据元素在L中的位序
LOCATE(L,x) 定位函数给定值x,若x不在表中,则返回-1,否则,返回x在表中第一次出现时的位序
INSERT(L, i , b)前插操作在第i个元素之前插入新元素b,i 的取值范围为:1<=i<=n+1;i =n+1表示在表尾插入, n为表长
DELETE(L,i) 删除操作删除线性表L中的第i个元素, 1<=i<=n
EMPTY(L) 判空表函数 若L为空表,则返回布尔值“true”,否则返回布尔值“false”
CLEAR(L) 表置空操作将L置为空表
a1
a2
ai
an
b
b+k
b+(i-1)k
b+(n-1)k
3、线性表的顺序存储结构
1)顺序存储结构
用一组地址连续的存储单元依次存储线性表的元素。设每个元素占用k个存储单元, Loc(a1)为线性表的起址,则第i个元素ai 的存储位置为:Loc(ai)=Loc(a1)+(i-1)*k
2)插入运算 INSERT(L, i, b)
插入前:L=(a1, ... , ai-1, ai, ... ,an)
插入后:L=(a1, ... , ai-1, b, ai, ... ,an )
算法思想:
①进行合法性检查,1<=i<=n+1;
②判断线性表是否已满;
③将第n个至第i个元素逐一后移一个单元;
④在第i个位置处插入新元素;
⑤将表的长度加1。
3)删除运算DELETE(L,i)
删除前:L=(a1,...,ai-1,ai,ai+1,...,an)
删除后:L=(a1,...,ai-1,ai+1,...,an)
算法思想:
①进行合法性检查,i是否满足1<=i<=n;
②判线性表是否已空,length(L)=0;
③将第i+1至第n个元素逐一向前移一个位置;
④将表的长度减1。
4、线性表顺序存储结构的特点
(1) 逻辑上相邻的元素,其物理位置也相邻;
(2) 可随机存取表中任一元素;
(3) 必须按最大可能长度预分存储空间,存储空间利用率低,表的容量难以扩充,是一种静态存储结构;
(4) 插入删除时,需移动大量元素,平均移动元素为n/2。