没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
第 2 章 线性表 0
第 2 章 线 性 表
2.1 线性表的逻辑结构
2.1.1 线性表的定义
线性表简称表,是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数定义为线性表
的长度。长度等于零时称为空表,一个非空表通常记为:L=(a
1
,a
2
,……,a
n
)。
2.1.2 线性表的抽象数据类型定义
线性表的抽象数据类型定义为:
ADT List
Data
线性表中的数据元素具有相同类型,相邻元素具有前驱和后继关系
Operation
InitList
前置条件:线性表不存在
输入:无
功能:线性表的初始化
输出: 无
后置条件:一个空的线性表
DestroyList
前置条件:线性表已存在
输入:无
功能:销毁线性表
输出:无
后置条件:释放线性表所占用的存储空间
Length
前置条件:线性表已存在
输入:无
功能:求线性表的长度
输出: 线性表中数据元素的个数
后置条件:线性表不变
Get
前置条件:线性表已存在
输入:元素的序号 i
相同类型的含义:
序列的含义:
线性表的示意图:
将线性表抽象数据类型定义为抽象类:
1 数据结构电子笔记
功能:在线性表中取序号为 i 的数据元素
输出:若序号合法,返回序号为 i 的元素值,否则抛出异常
后置条件:线性表不变
Locate
前置条件:线性表已存在
输入:数据元素 x
功能:在线性表中查找值等于 x 的元素
输出:若查找成功,返回元素 x 在表中的序号,否则返回 0
后置条件:线性表不变
Insert
前置条件:线性表已存在
输入:插入位置 i;待插元素 x
功能:在线性表的第 i 个位置处插入一个新元素 x
输出:若插入不成功,抛出异常
后置条件:若插入成功,表中增加了一个新元素
Delete
前置条件:线性表已存在
输入:删除位置 i
功能:删除线性表中的第 i 个元素
输出:若删除成功,返回被删元素,否则抛出异常
后置条件:若删除成功,表中减少了一个元素
Empty
前置条件:线性表已存在
输入:无
功能:判断线性表是否为空表
输出:若是空表,返回 1,否则返回 0
后置条件:线性表不变
PrintList
前置条件:线性表已存在
输入:无
功能:按位置的先后次序依次输出线性表中的元素
输出:线性表的各个数据元素
后置条件:线性表不变
endADT
2.2 线性表的顺序存储结构及实现
2.2.1 线性表的顺序存储结构——顺序表
线性表的顺序存储结构称为顺序表。
说明:
1.顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。
2.通常用一维数组来实现顺序表,C++中数组的下标从 1 开始。
3.线性表中第 i 个元素存储在数组(C++)中下标为 i-1 的位置。
4.顺序表的存储示意图:
5.设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为:
LOC(a
i
)= LOC(a
1
)+(i-1)×c
第 2 章 线性表 2
2.2.1 顺序表的实现
将线性表的抽象数据类型定义在顺序表存储结构下用 C++的类实现。
const int MaxSize=100; //100 只是示例性的数据,可以根据实际问题具体定义
template <class T> //定义模板类 SeqList
class SeqList
{
public:
private:
};
1.构造函数
顺序表类提供了两个构造函数。
无参构造函数 SeqList( ):创建一个空的顺序表,即将顺序表的长度初始化为 0;
有参构造函数 SeqList(T a[ ], int n):创建一个长度为 n 的顺序表,其操作过程如图 2-3 所示。
下面给出具体的构造函数。
10 12 15 25 8 16 20
10 12 15 25 8 16 20
空 闲
7
数组 a
顺序表
图 2-3 有参构造函数操作示意图
线 性 表 的
长度为 7
template <class T> 札记
SeqList:: SeqList(T a[ ], int n)
{
}
顺序表有参构造函数 SeqList
3 数据结构电子笔记
2. 插入
算法用伪代码描述如下:
具体的顺序表插入算法。
插入 15
(b) 插入后
图 2-4 将元素 15 插入位置 3 顺序表前后状态的对
比
a
1
10
a
2
12
a
3
25
a
4
8
a
5
16
a
6
20
空 闲
6
插入前线性表
的长度为 6
a
1
10
a
2
12
a
3
15
a
4
25
a
5
8
a
6
16
a
7
20
空 闲
7
插入后线性表
的长度为 7
数组下标: 0 1 2 3 4 5 MaxSize-1
(a) 插入前
几点说明:
1.插入后,元素 a
i
-
1
和 a
i
之间的逻辑关系发生了变化并且存储位置要反映这个变化。
2.插入时,若在表尾插入,直接插入即可,否则元素必须是从最后一个元素开始移动,
直至将第 i 个元素后移为止,然后将新元素插入位置 i 处。(注意元素移动方向)
3.考虑插入时的边界条件:如果表满了,则引发上溢异常;如果元素的插入位置不合理 ,
则引发位置异常。
template <class T> 札记
void SeqList::Insert(int i, T x)
{
}
顺序表插入算法 Insert
剩余15页未读,继续阅读
资源评论
steven5210
- 粉丝: 5
- 资源: 13
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功