理解线性表的逻辑结构特性.ppt

理解线性表的逻辑结构特性.ppt

ID:52329654

大小:586.56 KB

页数:89页

时间:2020-04-04

理解线性表的逻辑结构特性.ppt_第1页
理解线性表的逻辑结构特性.ppt_第2页
理解线性表的逻辑结构特性.ppt_第3页
理解线性表的逻辑结构特性.ppt_第4页
理解线性表的逻辑结构特性.ppt_第5页
资源描述:

《理解线性表的逻辑结构特性.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第二章线性表重点:理解线性表的逻辑结构特性熟练掌握线性表的顺序存储结构的描述方法,以及在该存储结构下的基本操作熟练掌握线性表的链式存储结构的描述方法,灵活使用单链表、双链表、循环链表,学会在相应存储结构下实现其各种基本算法及相关的时间性能分析一元多项式的表示和相加1第二章线性表难点:能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用场合使用本章所学的基本知识设计有效算法,解决与线性表相关的应用问题2第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.

2、1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加3第二章线性表线性结构的特点:在数据元素的非空有限集中,1)存在唯一的一个被称为“第一个”的数据元素2)存在唯一的一个被称为“最后一个”的数据元素3)除第一个之外,集合中的每个数据元素均只有一个前驱4)除最后一个之外,集合中的每个数据元素均只有一个后继41.线性表:定义:简称为表,是零个或多个元素的有穷序列,通常可以表示成(a1,a2,…,an)(n0)表的长度:表中所含元素的个数n空表:长度为零的表表项:表中的元素ai位序:数据元素ai在线

3、性表中的位置2.1线性表的类型定义51.线性表:线性表中的数据元素在不同的情况下可以有不同的具体含义,它可以是一个数、一个符号,也可是其它更复杂的信息例1.26个字母(A,B,…,Z)例2.班级人数(33,32,35,30)例3.学生情况登记表:数据元数为记录,有若干个数据项组成(如姓名,学号,性别,年龄…)2.1线性表的类型定义62.线性表的特点:线性表中的数据元素是各种各样的,但同一线性表中的元素必定具有相同特性,即属于同一数据对象相邻数据元素之间存在序偶关系(a1,a2,…,ai-1,ai,ai+1,…,an)

4、ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素相当灵活,长度可以增长或缩短2.1线性表的类型定义73.线性表的基本运算在线性表中插入一个元素;在线性表中删除某个元素;在线性表中查找某个特定元素;在线性表中查找某个元素的后继元素;在线性表中查找某个元素的前驱元素;创建空线性表;判别一个线性表是否为空表。……由基本运算可以构成其它较为复杂的运算2.1线性表的类型定义84.抽象数据类型线性表的定义(P19)ADTList{数据对象:D={ai

5、aiElemSet,i=1,2,…,n,n0}数据关系:R1={

6、

7、ai-1,aiD,i=1,2,…,n}基本操作:InitList(&L)操作结果:构造一个空的线性表LDestroyList(&L)初始条件:线性表L已存在操作结果:销毁线性表…2.1线性表的类型定义94.抽象数据类型线性表的定义(P19)…ClearList(&L)初始条件:线性表L已存在操作结果:将线性表L重置为空表ListEmpty(L)初始条件:线性表L已存在操作结果:若L为空表,则返回TRUE,否则返回FALSEListLength(L)初始条件:线性表L已存在操作结果:返回L中数据元

8、素个数2.1线性表的类型定义104.抽象数据类型线性表的定义(P19)GetElem(L,i,&e)初始条件:线性表L已存在,1≤i≤LengthList(L)操作结果:用e返回L中第i个元素的值LocateElem(L,e,compare())初始条件:线性表L已存在,compare()是元素判定函数操作结果:返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在,则返回值为0PriorElem(L,cur_e,&pre_e)初始条件:线性表L已存在操作结果:若cur_e是L的元素,但不是第一

9、个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义2.1线性表的类型定义114.抽象数据类型线性表的定义(P19)NextElem(L,cur_e,&next_e)初始条件:线性表L已存在操作结果:若cur_e是L的元素,但不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义ListTraverse(L,visit())初始条件:线性表L已存在操作结果:依次对L的每个元素调用函数visit()。一旦visit()失败,则操作失败PutElem(L,i,&e)初始条件:线性表L已存在

10、,1≤i≤LengthList(L)操作结果:L中第i个元素赋值同e的值2.1线性表的类型定义124.抽象数据类型线性表的定义(P19)ListInsert(&L,i,e)初始条件:线性表L已存在,1≤i≤LengthList(L)+1操作结果:在L的第i个元素之前插入新的元素e,L的长度增1ListDelete(&L,i,&e)初始条件:线性

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。