第二章线性表共70页

发布时间:2021-07-31 13:11:34

主要内容: 1.线性表的类型定义 2.线性表的顺序表示和实现 3.线性表的链式表示和实现 学*提要: 1.了解线性表的逻辑结构和物理结构 2.掌握两种存储结构的描述方法以及在每种存 储结构上的基本操作的实现 3.理解两种存储结构的特点及其使用场合 重难点内容: 顺序表、链表及其操作实现 1 线性结构是一个数据元素的有序(次序)集 。 线性结构的基本特征: (1)存在唯一的一个被称作“第一个”的数据元素 (2)存在唯一的一个被称作“最后一个”的数据元 素 (3)除第一个外,集合中的每个数据元素均只有 一个前驱 (4)除最后一个外,集合中的每个数据元素均只有 一个后继 2 §2.1 线性表的类型定义 线性表:n个数据元素组成的有限序列。 表示为(a1,a2,…,ai,ai+1,…,an) 例:英文字母表(A,B,C,…..Z)是一个线性表 例: 学号 姓名 001 张三 002 李四 …… …… 年龄 数据元素 18 19 …… 3 §2.1 线性表的类型定义 逻辑特征: ?1<i<n时 ai的直接前驱是ai-1,a1无直接前驱 ai的直接后继是ai+1,an无直接后继 ?元素同构,且不能出现缺项 线性表的长度:表中元素的个数 n(n>=0),n=0 空表。 位序:元素ai在表中的位置数i 。 4 抽象数据类型线性表的定义如下: ADT List { 数据对象: D={ ai | ai ∈ElemSet,i=1,2,...,n, n≥0 } 数据关系: R1={ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } 基本操作: InitList( &L ) 操作结果:构造一个空的线性表L。 5 DestroyList( &L ) 初始条件:线性表L已存在。 操作结果:销毁线性表L。 ListEmpty( L ) 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE, 否则FALSE。 ListLength( L ) 初始条件:线性表L已存在。 操作结果:返回L中元素个数。 6 GetElem( L, i, &e ) 初始条件:线性表L已存在,1≤i≤ListLength (L) 操作结果:用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) ) 初始条件:线性表L已存在,compare( )是元素判定 函数。 操作结果:返回L中第i个与e满足关系compare( )的 元素的位序。若这样的元素不存在,则返回值为0。 7 PriorElem( L, cur_e, &pre_e ) 初始条件:线性表L已存在。 操作结果:若cur_e是L的元素,但不是第一个, 则用pre_e 返回它的前驱,否则操作失败,pre_e无 定义。 NextElem( L, cur_e, &next_e ) 初始条件:线性表L已存在。 引用型操作 操作结果:若cur_e是L的元素,但不是最后一个, 则用next_e返回它的后继,否则操作失败,next_e 无定义。 8 ListTraverse(L, visit( )) 初始条件:线性表L已存在。 加工型操作 操作结果:依次对L的每个元素调用函数visit( )。 一旦visit( )失败,则操作失败。 ClearList( &L ) 初始条件:线性表L已存在。 操作结果:将L重置为空表。 PutElem( L, i, &e ) 初始条件:线性表L已存在,1≤i≤ ListLength (L) 操作结果:L中第i个元素赋值同e的值。 9 ListInsert( &L, i, e ) 初 始 条 件 : 线 性 表 L 已 加存工在型操,作 1≤i≤ ListLength (L) +1 操作结果:在L的第i个元素之前插入新的 元素e,L的长度增1。 ListDelete(&L, i, &e) 初始条件:线性表L已存在且非空,1≤i≤ ListLength (L) 操作结果:删除L的第i个元素,并用e 返 *渲担琇的长度减1。 } ADT List 10 利用上述定义的线性表可以实现其 它更复杂的操作。 例2-1 假设:有两个集合A 和 B 分别用两个 线性表 LA 和 LB 表示,即:线性表中 的数据元素即为集合中的成员。 现要求一个新的集合A=A∪B。 11 算法思想: 要求对线性表作如下操作: 扩大线性表 LA,将存在于线 性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。 12 实现步骤: 1.从线性表LB中依次察看每个数据元素; GetElem(LB, i ,e ) 2.依值在线性表LA中进行查访; LocateElem(LA, e, equal( )) 3.若不存在,则插入之。 ListInsert(LA, n+1, e) 13 void union(List &La, List Lb) { La_len = ListLength(La); // 求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e); // La中不存在和 e 相同的数据元素,则插入之 } } // union O(ListLength(LA)×ListLength(LB)); 14 例2-2 已知线性表LA和LB是非递减的,将两表合 并成新的线性表LC,且LC也是非递减的。 算法思想: 将LA、LB两表中的元素逐一按序加入到一 个新表LC中。 设 La = (a1, …, ai, …, an), Lb = (b1,

相关文档

  • 第二章 线性表1
  • 第2章线性表2(单链表)
  • 第二章 线性表2.28
  • 900-第2章 线性表
  • (精品)第二章线性表答案
  • 第2章 线性表共92页文档
  • 工学第二章 线性表
  • 猜你喜欢

  • 2018年迎新年校长代表发言稿-推荐word版 (3页)
  • 【范文】国土资源局XX年工作总结_1
  • 将孝敬进行到底作文800字_叙事作文
  • MyGUI 3.2.0 出炉了
  • 新版2019年(秋)幼儿园学前班下学期开学测试试卷(附答案)
  • 杭州市建设工程评标专家推荐表填表说明
  • 中药食疗减肥美体的偏方是什么
  • 大红袍茶怎么泡最好喝
  • 概率统计第二章经典讲义
  • 【江苏省自然科学基金】_水文水资源_期刊发文热词逐年推荐_20140815
  • 幼儿园迎中秋节活动总结
  • 心罪
  • 2016-2017学年北京市东城区高一下学期期末考试历史试题
  • 江苏鹏步环保能源有限公司(企业信用报告)- 天眼查
  • 美好一天开始的早安句子
  • (娄底专版)人教版八年级英语上册课件:Unit 1 第四课
  • 关于圣诞节手抄报内容
  • 晋中万辰汽车销售服务有限公司企业信用报告-天眼查
  • 患者身份识别与腕带使用管理相关制度
  • 【四清导航】(华师版)七年级数学下册同步课件7.1二元一次方程组和它的解2
  • 2016-2021年中国极限运动用品市场深度调研及投资策略分析报告(目录)
  • 优传进口惊灰字行奶旖蚩?稻苹嵫?牒
  • 初中作文:是时候放弃了
  • seo优化推广个人简历范文
  • 信息技术与研究性学*课程的整合模式研究
  • 16、郑州市灵活就业人员社会保险申报表
  • 宁波利好纸业有限公司(企业信用报告)- 天眼查
  • 调节阀的原理及构造
  • 宁夏新天地投资有限公司(企业信用报告)- 天眼查
  • 小学二年级数学教案《课题7的乘法口诀》
  • OLTP与OLAP简介
  • 发挥党组织职能推进农村改革发展思考
  • 企业用气安全知识培训材料
  • 2016-2017高三物理粤教版选修3-5 第一章第五节自然界中的守恒定律 课堂练* Word版含解析
  • 发展观光休闲农业促进城郊新农村建设
  • 九年级下册“语文知识积累”教材梳理_图文.ppt
  • 2018年国土所工作总结
  • 肇东市安民乡立国蛋鸡养殖专业合作社企业信息报告-天眼查
  • 爱的教育读后感500字【精品文档】_0
  • 第6章 控制系统的校正及综合
  • 凯迪电力:发行股份及支付现金购买资产并募集配套资金暨关联交易公告
  • 社区三严三实学习心得
  • 电脑版