网站大量收购闲置独家精品文档,联系QQ:2885784924

线性表(数据结构).ppt

  1. 1、本文档共50页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
线性表(数据结构)

问: 数据结构从逻辑层面和物理层面各有哪几种? 什么是 抽象数据类型? 算法有哪几个特点?有哪些设计要求? 什么是算法的时间复杂度? 线性结构 线性结构的特点: 数据元素的非空有限集中, (1)位置:每个元素都有一个位置 (3)起始结点:只有一个 (4)终端结点:只有一个 (5)前趋:第一个结点无前趋,其它结点有且只有一个 (6)后继:最后一个结点无后继,其它结点有且只有一个 所有结点按其线性结构关系排成一个序列,记为(a1,…,ai,ai+1,…an),称为“线性序列” 第2章、第3章、第4章均 讨论线性结构。 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示与实现 2.3 线性表的链式表示与实现 1. 单链表 2. 静态链表 2 循环链表 3 双向链表 2.4 线性表的应用 2.1 线性表的类型定义 结构相同的数据元素组成的线性序列称为线性表。 例如,学生表: (学生1,学生2,学生3,… ,学生n) 线性表的ADT定义: ADT List{ 数据对象:D = {ai | ai∈D0 ,i=1,2, … n,n≥0} //说明:n=0,表示空表 数据关系:R = {N}, N = { ai-1 , ai | ai-1 , ai ∈D0 , i = 2, … n} D0 为某类数据对象的集合 基本操作: 1)InitList(L) 操作结果:初始化为一个空的线性表 2)ListLength(L) //求长度,返回线性表中数据元素个数 3)GetElem(L,i, e) //取表L中第i个数据元素,用e返回 4)ListInsert(L,i,e) //在L中第i个位置前插入新的数据元素e,表长加1。 5)ListDelete(L,i,e) //删除表中第i个数据元素,e返回其值,表长减1。 6)LocateElem(L, e, compare() ) //定位(按值查找),返回第一个与e满足compare()关系(如:相等)的数据元素位置号;若找不到,返回0 。。。 } 基于以上基本操作,可以实现其它运算. 建立在ADT List上的高层算法—2-1 例2-1 求A = A ∪ B void unionList( List La, List Lb) { //将所有在线性表Lb中但不在La中的数据元素插入到La中 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) ) ListInsert(La,++La_len,e); //La中不存在和e相同的数据元素,则插入之 } }//union 2.2 线性表的顺序表示与实现 1. 顺序表 在计算机内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。 假设每个元素占用L个存储单元,则有以下关系: Loc(ai+1) = Loc(ai) + L Loc(ai) = Loc(a1) + (i-1)*L 所以,顺序存储结构是一种“随机存取”的存储结构。 线性表的这种机内表示称为线性表的顺序存储结构(或顺序映像)。通常,称这种存储结构的线性表为“顺序表”。 顺序表的特点: 逻辑上相邻的结点物理上仍相邻。 2. 顺序表的表示(1) C语言中的数组就是顺序表的存储表示(静态内存分配) 顺序表的表示(2) 因此,宜使用动态分配的一维数组来表示顺序表 3. 基本动态内存根本的基本运算的实现--①初始化 Status InitList (SqList L) { L.elem=(ElemType*) malloc(MAXSIZE * sizeof(ElemType) ); //此处应该检测是否分配成功! L.length = 0; L.listsize = MAXSIZE; return OK; } ②插入(按位插入) //基于动态分配 Status ListInsert (SqList L,int i,ElemType e) { //i位置插入新元素e。1≤i ≤表长+1 if (i1 || iL.length+1) return ERROR; if (L.length == L.listsize)

文档评论(0)

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

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

1亿VIP精品文档

相关文档