1. 1、本文档共79页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加 2.1 线性表的类型定义 线性结构的特点: 在数据元素的非空有限集中, 1)有且仅有一个开始结点; 2)有且仅有一个终端结点; 3)除第一个结点外,集合中的每个数据元素均有且只有一个前驱; 4)除最后一个结点外,集合中的每个数据元素均有且只有一个后继。 线性序列:线性结构中的所有结点按其关系可以排成一个序列,记为(a1,…,ai,ai+1,…an) 2.1 线性表的类型定义 1. 线性表 1)线性表是n(n ≥0)个数据元素的有限序列。 2)线性表是一种最常用且最简单的数据结构。 含有n个数据元素的线性表是一个数据结构: List = (D,R) 其中:D = {ai | ai∈ElemSet, i=1,2,…n,n≥0} R = { ai-1 , ai | ai-1 , ai ∈D , i = 2,3,…n} 数据元素的具体含义? 特性:均匀性,有序性(线性序列关系) 2.1 线性表的类型定义 1. 线性表 3)线性表的长度及空表 线性表中数据元素的个数n(n≥0)定义为线性表的长度 当线性表的长度为0 时,称为空表。 ai 是第i个数据元素,称i为ai 在线性表中的位序。 2. 线性表的基本操作 p19~p20 线性表的基本操作(略介绍) (1)初始化线性表L InitList(L) (2)销毁线性表L DestoryList(L) (3)清空线性表L ClearList(L) (4)求线性表L的长度 ListLength(L) (5)判断线性表L是否为空 IsEmpty(L) (6)获取线性表L中的某个数据元素内容GetElem(L,i,e) 基本操作2 (7)检索值为e的数据元素 LocateELem(L,e) (8)返回线性表L中e的直接前驱元素 PriorElem(L,e) (9)返回线性表L中e的直接后继元素 NextElem(L,e) (10)在线性表L中插入一个数据元素 ListInsert(L,i,e) (11)删除线性表L中第i个数据元素 ListDelete(L,i,e) 其他操作? 参数合法性! 线性表的基本操作举例 例2-1 求A = A ∪ B P20算法2.1 基本思想:依次取B中每个元素赋值给变量e,若A中没有元素等于e,则在A的表尾插入。 ? 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); if(!locateelem(la,e,equal)) listinsert(la,++la-len,e) } } 线性表的基本操作举例 例2-2 合并递增有序表LA 和 LB 到LC中 P20-21算法2.2 LA=(1,3,5,7); LB=(2,3,6); 基本思想:依次比较LA和LB的元素,较小的放入LC中;LA或LB中剩余的元素直接放入LC中 2.2 线性表的顺序表示和实现 1.顺序表—线性表的顺序存储结构 1)用一组地址连续的存储单元依次存储线性表的数据元素。 2)假设:每个数据元素需占用L个存储单元, Loc(a1)-基地址,第一个单元的存储位置,线性表的 的起始存储位置, Loc(ai)-第i个数据元素的存储位置; Loc(ai) = Loc(a1) + (i-1)*L Loc(ai+1) = Loc(ai) + L 1.顺序表—线性表的顺序存储结构 3)线性表的顺序存储结构示意图——(p22图2.2) 用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。 根据线性表的顺序存储结构的特点,只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,所以,线性表的顺序存储结构是一种随机存取的存储结构。 typedef int ElemType; #define LIST_MAX_LENTH 100 typedef str

文档评论(0)

***** + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档