- 1、本文档共86页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[教育]第五章 数组和广义表
若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp 复制求广义表的算法描述如下: Status CopyGList(Glist T, Glist L) { if (!L) T = NULL; // 复制空表 else { if ( !(T = (Glist)malloc(sizeof(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-ptr.hp); // 复制求得表头T-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); // 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp 语句 CopyGList(T-ptr.hp, L-ptr.hp); 等价于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp; 二、后置递归的设计思想为: 递归的终结状态是,当前的问题可以直接求解,对原问题而言,则是已走到了求解的最后一步。 链表是可以如此求解的一个典型例子。 例如:编写“删除单链表中所有值为x 的数据元素”的算法。 1) 单链表是一种顺序结构,必须从第一个结点起,逐个检查每个结点的数据元素; 分析: 2) 从另一角度看,链表又是一个递归结构,若 L 是线性链表 (a1, a2, ?, an) 的头指针,则 L-next是线性链表 (a2, ?, an)的头指针。 a1 a2 a3 an … ? L 例如: a1 a2 a3 an ? L a1 a2 a3 an ? L 已知下列链表 1) “a1=x”,则 L 仍为删除 x 后的链表头指针 2) “a1≠x”,则余下问题是考虑以 L-next 为头指针的链表 … … a1 L-next L-next=p-next p=L-next void delete(LinkList L, ElemType x) { // 删除以L为头指针的带头结点的单链表中 // 所有值为x的数据元素 if (L-next) { if (L-next-data==x) { p=L-next; L-next=p-next; free(p); delete(L, x); } else delete(L-next, x); } } // delete 算法:删除广义表中所有元素为x的原子结点 分析: 比较广义表和线性表的结构特点: 相似处:都是链表结构。 不同处:1)广义表的数据元素可能还是个 广义表; 2)删除时,不仅要删除原子结点, 还需要删除相应的表结点。 void Delete_GL(GlistL, AtomType x) { //删除广义表L中所有值为x的原子结点 if (L) { head = L-ptr.hp; // 考察第一个子表 if ((head-tag == Atom) (head-atom == x)) { } // 删除原子项 x的情况 else { }// 第一项没有被删除的情况 } } // Delete_GL … … … … p=L; L = L-ptr.tp; // 修改指针 free(head); // 释放原子结
文档评论(0)