数据结构数据结构课件
需积分: 0 49 浏览量
2010-03-21
20:56:18
上传
评论
收藏 360KB PDF 举报
1
1
第二章 线性表
2.1 线性表的概念
2.2 顺序表示
2.3 链接表示
2.4 应用举例-Josephus问题
另外介绍“动态顺序表”
2
程序里常需要保存一批某种类型的元素，这些元素的
数目可能变化（可以加入或删除元素）
有时需要把这组元素看成一个序列，元素的顺序可能
表示实际应用中的某种有意义的关系
这样一组元素可以抽象为元素的一个线性表。线性表
是元素的集合，同时记录了元素的顺序关系
线性表是一种最基本的数据结构，在各种程序里应用
广泛，还常作为实现更复杂的数据结构的基础
本章讨论线性表的概念，它的两种基本实现方式，它
们的一些变形，以及若干应用实例
3
2.1 线性表的概念
¾ 元素:{e
0
，…，e
N-1
} 是一个元素集合
¾ 线性表：简称表，元素的有穷序列，可包含0个或多
个元素，表示为 (e
0
，e
1
, …，e
n-1
)，n≥0
¾ 元素位置称为下标，下标从0开始（一种选择）
¾ 表中元素个数称为表的长度，长度为0的表是空表
¾ 关系：<e
0
, e
1
>,<e
1
,e
2
>,…,<e
n-2
, e
n-1
>。是一种顺序关
系（线性关系）
¾ 例：整数的表，字符串的表，某种结构的表
4
线性表是一种线性结构
非空线性表中：
1. 存在唯一的称为“第一个”的元素；
2. 存在唯一的称为“最后一个”的元素；
3. 除第一个元素之外，表中的每个元素都有且只有
一个前驱元素；
4. 除最后一个元素之外，表中的每个元素都有且只
有一 个后继元素。
可以把线性表作为一种数学对象，为它建立抽象模型
5
抽象模型
元素集合：
线性表集合：
基本操作
组合：
取头部：
取尾部：
判空表：
6
操作的基调（Signature，原型，类型特征）
组合：
取头部：
取尾部：
判空表：
其他操作可类似定义
定义操作，例如表的长度操作
基调：
定义：
剩余11页未读，继续阅读
评论0
最新资源