- 1、本文档共113页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构 第2章 线性表 线性表是最简单、最基本、也是最常用的一种数据结构。 线性表的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在唯一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。 它有两种存储方法:顺序存储和链式存储。它的主要基本操作是插入、删除和检索等。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 1.线性表的定义 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列,通常记为: (a0, a1,a2,… ai-1,ai,ai+1,…an-1) 其中n为表长, n=0 时称为空表。 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 如学生情况信息表是一个线性表 . 在稍复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称文件。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 2.线性表的基本运算 ⑴ 线性表初始化:Init_List(L) 初始条件:表L不存在 操作结果:构造一个空的线性表 ⑵ 求线性表的长度:Length_List(L) 初始条件:表L存在 操作结果:返回线性表中的所含元素的个数 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 ⑶ 取表元:Get_List(L,i) 初始条件:表L存在且0≤i≤Length_List(L)-1 操作结果:返回线性表L中的第i个元素的值或地址 ⑷ 按值查找:Locate_List(L,x),x是给定的一个数据元素。 初始条件:线性表L存在 操作结果:在表L中查找值为x的数据元素,其结果返回在L中首次出现的值为x的那个元素的序号或地址,称为查找成功; 否则,在L中未找到值为x的数据元素,返回一特殊值(0)表示查找失败。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 ⑸ 插入操作:Insert_List(L,i,x) 初始条件:线性表L存在,插入位置正确 (0≤i≤n,n为插入前的表长)。 操作结果:在线性表L的第 i 个位置上插入一个值为 x 的新元素,这样使原序号为 i , i+1, ... , n-1 的数据元素的序号变为 i+1,i+2, ... , n,插入后表长=原表长+1。 ⑹ 删除操作:Delete_List(L,i) 初始条件:线性表L存在,0≤i≤n-1。 操作结果:在线性表L中删除序号为i的数据元素,删除后使序号为 i+1, i+2,..., n-1 的元素变为序号为 i, i+1,...,n-2,新表长=原表长-1。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 说明: 1.上面基本运算中的线性表L仅是一个抽象的线性表.由于不能确定其存储结构究竟是顺序的还是链接的,因此,还不能用某种程序语言写出其算法。 2.上述基本算法,可以成为组建其他一些复杂的算法的元素,而使复杂算法显得更简单。 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 例2.1 设有两个线性表LA和LB,现要求扩大线性表LA,将存在于线性表LB中而不存在于LA中的数据元素插入到线性表LA中去。 void union(List La, List Lb){ La_len= Length_List(La); Lb_len= Length_List(Lb); for (i=1;i=Lb_len;i++) { e= Get_List(Lb,i); if (!Locate_List(La,e)) Insert_List(La,++La_len,e);} } 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 例2.2 已知线性表LA和LB中的数据元素按值非减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非减有序排列。假设 LA=(3,5,8,11) LB=(2,6,8,9,11,15,30) 则 LC=(2,3,5,6,8,8,9,11,11,15,30) 数据结构 第2章 线性表 2.1 线性表的定义和基本运算 void MergeList(List La,List Lb,List Lc){ Init_Li
文档评论(0)