数据结构(C语言版) 第5章 稀疏矩阵和广义表.doc

第5章 数组和广义表3 广义表3.1 逻辑结构3.1.1 定义线性表的扩展：每个子结构或是一个基本元素，或是一个线性表。GList=a1,a2,an | aiAtomSet或aiGListaiAtomSet：ai为原子。aiGlist ：ai为子表。逻辑结构图A=( )B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)神奇之处：可以嵌套、可以共享、可以递归。数据关系：顺序关系、层次关系。 a1为表头(head)元素, 其余为表尾(tail)。3.1.2 典型应用领域Lisp语言、前缀表达式。(setq x (+ 4 (- a b) y (+ 3 4) )表头：函数名； 表尾：参数表3.1.3 基本概念与操作取表头指针GListNode *GetHead()取表尾指针GListNode *GetTail()取某结点指针GListNode *nth(int i)求表长度int GetLength();求表深度int GetDepth();原子深度=0，表深度=maxGList_Depth(ai)+1 例：求长度、深度：(a), (), (a),a)， (a),a),(a),a)遍历void Traverse();复制GList *Copy();3.2 存储结构3.2.1 不规范的结构图3.2.2 比较合理的结构图A=()B=(1,2,3)C=(1,(2,3,4),5)结构约定：所有广义表带特殊头结点(相当于括号)。意义：结构规范、算法简化。3.2.3 类的定义/ 广义表结点的结构定义：表结点、原子结点typedef enum ATOM,LIST GListNodeType;template struct GListNode GListNodeType type;/ 结点类型 union / 联合 T data; GListNode *child; ; GListNode * next;/ 广义表类定义 template class GList GListNode *m_Head; / 广义表头指针public: GList(); GList(char s); / 根据(a (b c) d)构造 GList(GList &gl); / 拷贝构造 GList(); void Free(); / 释放广义表 void Traverse(); / 遍历广义表 int GetLength(); / 计算长度 int GetDepth(); / 计算深度;3.3 存储结构的应用：m元多项式typedef enum ATOM,LIST GListNodeType;struct MPNode GListNodeType type;/ 结点类型 int exp; / 指数域 union float coef; / 原子结点中的系数域 GListNode *child; ; GListNode * next;绘制存储结构： F(x,y,z)=(x12+2x6)y3+(3x15)y2)z20 + (x18+6x3)y4+2y)z10 + 15思考：求值算法、加法算法。4 广义表的递归算法4.1 求广义表长度template int GList:GetLength() int length=0; for(GListNode *p=m_Head-child; p; p=p-next) length+; return length;4.2 遍历广义表template void GList:Traverse() / 遍历广义表 DoTraverse(m_Head); coutendl;template void GList:DoTraverse(GListNode *p) for(; p; p=p-next) if(p-type=ATOM) cout data ; else / 输出子表，格式： () cout child); cout ); 4.3 求表深度template int GList:GetDepth() return Depth(m_Head); template int GList:Depth(GListNode *first) int depth, maxdepth=0; GListNode *p; if(first-type=ATOM) return 0; for(p=first-child; p; p=p-next) depth=Depth(p); if(depthmaxdepth) maxdepth=depth; return(maxdepth+1);4.4 拷贝构造函数template GList:GList(GList &gl) m_Head = DoCopy(gl.m_Head); / 类似于“单向链表的构造函数” template GListNode *GList:DoCopy(GListNode* p) GListNode *head=NULL, *tail; / 头指针，尾指针 for(; p; p=p-next) GListNode *newp=new GListNode; newp-type = p-type; if(p-type=ATOM) newp-data =p-data; else newp-child=DoCopy(p-child); if(head=NULL) head=tail=newp; else tail-next=newp; tail=newp; tail-next=NULL; return head;4.5 析构函数template void GList:Free() / 释放广义表 DoFree(m_Head); m_Head=NULL; template void GList:DoFree(GListNode *p) while( p!=NULL ) GListNode *q=p; / q指向将删除的结点 p=p-next; if(q-type=LIST) DoFree(q-child); delete q; 4.6 带参构造函数template GList:GList(char s) / 根据(a (b c) d)构造 m_ss=new charstrlen(s)+1; strcpy(m_ss,s); m_si=0; / 完成数据准备 m_Head=DoCreate(); delete m_ss;/从m_ss中读入下一个有效字符template char GList:GetElem() while(m_ssm_si= ) m_si+; / 滤掉空格 char e=m_ssm_si; m_si+; return e;template GListNode* GList:DoCreate() GListNode* p; char e=GetElem(); if(e=() p=new GListNode; p-type=LIST; p-child = DoCreate(); p-next = DoCreate(); return(p); if(e=) | e=0) return(NULL); p=new GListNode; p-type=ATOM; p-data=e; p-next = DoCreate(); return(p);思考：设str=(a (b c) d)(e f)，画出结构图。4.7 参考阅读：删除广义表中所有值为e的结点/ 单链表函数：递归删除所有值为e的结点/ 设有特殊头结点template void LinkList:Delete(const T &e) Delete(m_Head,e); template void LinkList:Delete(LinkNode *first,const T &e) LinkNode *p; if(!first-next) return; p=first-next; if(p-data=e) first-next=p-next; free(p); Delete(first,e); else Delete(p, e); 2、删除广义表中所有元素为e的结点 / 递归删除所有值为e的结点template void GList:Delete(const T &e) Delete(m_Head,e); template void GList:Delete(GListNode *first,const T &e) GListNode *p; if(!first) return; / 在*first的后继表中删除 if(first-next) p=first-next; if(p-data=e) first-next=p-next; f