第 5 章 数组和的广义表.ppt

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

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * A=( ) A 1 ^ ^ B=(e) B 1 ^ 0 e ^ 结点的链接 C 1 ^ 1 ^ 0 a 0 b 0 c 0 d ^ C=(a, (b, c, d)) D 1 ^ 1 D=(A, B, C) 1 ^ 1 ^ E=(a, E) E 1 ^ 1 ^ 0 a 表达式中的左括号 “(” 对应 存储表示中的 tag = 1 的结点 最高层结点 tp 域必为 NULL * * 5.7 广义表的递归算法 求广义表的深度 复制广义表 创建广义表存储结构 * * 5.7.1 求广义表的深度 深度:广义表中括弧的重数 算法: 设广义表LS= (a1, a2, … , an) 深度DEPTH(LS)递归定义: 基本项: DEPTH(LS) = 1, LS为空表; DEPTH(LS) = 0, LS为原子; 归纳项: DEPTH(LS) = * * int GlistDepth(Glist L) { // 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp){ dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; } return max + 1; } if (!L) return 1; //空表 if (L-tag == ATOM) return 0;//原子 * 5.7.2 复制广义表 想法: 分别复制表头和表尾,然后合成。 算法: 设把L复制到T, 复制操作的递归算法: 基本项: InitGList(T), 若L为空表 归纳项: 把GetHead(L)复制到GetHead(T), 把GetTail(L)复制到GetTail(T) * * Status CopyGList(Glist T, Glist L) { if (!L) T = NULL; // 复制空表 else { if ( !(T = new GLNode) ) exit(OVERFLOW); // 建表结点 T-tag = L-tag; if (L-tag == ATOM) T-atom = L-atom; // 复制单原子结点 else { } } // else return OK; } // CopyGList 分别复制表头和表尾 * CopyGList(T-ptr.hp, L-prt.hp); CopyGList(T-ptr.tp, L-prt.tp); * 假设以字符串 S = ?(?1, ?2, ???, ?n )? 的形式定义广义表 L,建立相应的存储结构。 由于S中的每个子串?i定义 L 的一个子表,从而产生 n 个子问题,即分别由这 n个子串 (递归)建立 n 个子表,再组合成一个广义表。 可以直接求解的两种简单情况为: 由串?( )?建立的广义表是空表; 由单字符建立的子表只是一个原子结点。 创建广义表存储结构 * 1、了解数组的两种存储表示方法,并掌握数组在 以行为主的存储结构中的地址计算方法; 2、掌握特殊矩阵压缩存储的下标变换公式; 3、了解稀疏矩阵的两种压缩存储方法的特点和适 用范围,理解以三元组表示稀疏矩阵时进行矩 阵运算采用的处理方法; 4、掌握广义表的结构特点及其存储表示方法,会 对非空广义表进行分解。 教学要求 * * * * * * * * * * * * * * * * * * * * * * * * * 三元组顺序表又称有序的双下标法。 三元组顺序表的优点:非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。 三元组顺序表的缺点:不能随机存取。若按行号存取某 一行中的非零元,则需从头开始进行查找。 * 2、行逻辑联接的顺序表(带行表的三元组) 在稀疏矩阵中若随机存取任

文档评论(0)

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

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

1亿VIP精品文档

相关文档