數(shù)據(jù)結(jié)構(gòu)(C語言版) 第5章 稀疏矩陣和廣義表

第5章 數(shù)組和廣義表3 廣義表3.1 邏輯結(jié)構(gòu)3.1.1 定義線性表的擴(kuò)展：每個(gè)子結(jié)構(gòu)或是一個(gè)基本元素，或是一個(gè)線性表。GList=a1,a2,an | aiAtomSet或aiGListaiAtomSet：ai為原子。aiGlist ：ai為子表。邏輯結(jié)構(gòu)圖A=( )B=(6,2)C=('a',(5,3,'x')D=(B,C,A)E=(B,D)F=(4,F)神奇之處：可以嵌套、可以共享、可以遞歸。數(shù)據(jù)關(guān)系：順序關(guān)系、層次關(guān)系。 a1為表頭(head)元素, 其余為表尾(tail)。3.1.2 典型應(yīng)用領(lǐng)域Lisp語言、前綴表達(dá)式。(setq x (+ 4 (- a b) y (+ 3 4) )表頭：函數(shù)名； 表尾：參數(shù)表3.1.3 基本概念與操作取表頭指針GListNode<T> *GetHead()取表尾指針GListNode<T> *GetTail()取某結(jié)點(diǎn)指針GListNode<T> *nth(int i)求表長(zhǎng)度int GetLength();求表深度int GetDepth();原子深度=0，表深度=maxGList_Depth(ai)+1 例：求長(zhǎng)度、深度：(a), (), (a),a)， (a),a),(a),a)遍歷void Traverse();復(fù)制GList<T> *Copy();3.2 存儲(chǔ)結(jié)構(gòu)3.2.1 不規(guī)范的結(jié)構(gòu)圖3.2.2 比較合理的結(jié)構(gòu)圖A=()B=(1,2,3)C=(1,(2,3,4),5)結(jié)構(gòu)約定：所有廣義表帶特殊頭結(jié)點(diǎn)(相當(dāng)于括號(hào))。意義：結(jié)構(gòu)規(guī)范、算法簡(jiǎn)化。3.2.3 類的定義/ 廣義表結(jié)點(diǎn)的結(jié)構(gòu)定義：表結(jié)點(diǎn)、原子結(jié)點(diǎn)typedef enum ATOM,LIST GListNodeType;template <class T>struct GListNode GListNodeType type;/ 結(jié)點(diǎn)類型 union / 聯(lián)合 T data; GListNode *child; ; GListNode * next;/ 廣義表類定義 template <class T>class GList GListNode<T> *m_Head; / 廣義表頭指針public: GList(); GList(char s); / 根據(jù)"(a (b c) d)"構(gòu)造 GList(GList<T> &gl); / 拷貝構(gòu)造 GList(); void Free(); / 釋放廣義表 void Traverse(); / 遍歷廣義表 int GetLength(); / 計(jì)算長(zhǎng)度 int GetDepth(); / 計(jì)算深度;3.3 存儲(chǔ)結(jié)構(gòu)的應(yīng)用：m元多項(xiàng)式typedef enum ATOM,LIST GListNodeType;struct MPNode GListNodeType type;/ 結(jié)點(diǎn)類型 int exp; / 指數(shù)域 union float coef; / 原子結(jié)點(diǎn)中的系數(shù)域 GListNode *child; ; GListNode * next;繪制存儲(chǔ)結(jié)構(gòu)： F(x,y,z)=(x12+2x6)y3+(3x15)y2)z20 + (x18+6x3)y4+2y)z10 + 15思考：求值算法、加法算法。4 廣義表的遞歸算法4.1 求廣義表長(zhǎng)度template <class T>int GList<T>:GetLength() int length=0; for(GListNode<T> *p=m_Head->child; p; p=p->next) length+; return length;4.2 遍歷廣義表template <class T>void GList<T>:Traverse() / 遍歷廣義表 DoTraverse(m_Head); cout<<endl;template <class T>void GList<T>:DoTraverse(GListNode<T> *p) for(; p; p=p->next) if(p->type=ATOM) cout << p->data << " " else / 輸出子表，格式： "()" cout << '(' DoTraverse(p->child); cout << ')' 4.3 求表深度template <class T>int GList<T>:GetDepth() return Depth(m_Head); template <class T>int GList<T>:Depth(GListNode<T> *first) int depth, maxdepth=0; GListNode<T> *p; if(first->type=ATOM) return 0; for(p=first->child; p; p=p->next) depth=Depth(p); if(depth>maxdepth) maxdepth=depth; return(maxdepth+1);4.4 拷貝構(gòu)造函數(shù)template <class T>GList<T>:GList(GList<T> &gl) m_Head = DoCopy(gl.m_Head); / 類似于“單向鏈表的構(gòu)造函數(shù)” template <class T>GListNode<T> *GList<T>:DoCopy(GListNode<T>* p) GListNode<T> *head=NULL, *tail; / 頭指針，尾指針 for(; p; p=p->next) GListNode<T> *newp=new GListNode<T> 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 析構(gòu)函數(shù)template <class T>void GList<T>:Free() / 釋放廣義表 DoFree(m_Head); m_Head=NULL; template <class T>void GList<T>:DoFree(GListNode<T> *p) while( p!=NULL ) GListNode<T> *q=p; / q指向?qū)h除的結(jié)點(diǎn) p=p->next; if(q->type=LIST) DoFree(q->child); delete q; 4.6 帶參構(gòu)造函數(shù)template <class T>GList<T>:GList(char s) / 根據(jù)"(a (b c) d)"構(gòu)造 m_ss=new charstrlen(s)+1; strcpy(m_ss,s); m_si=0; / 完成數(shù)據(jù)準(zhǔn)備 m_Head=DoCreate(); delete m_ss;/從m_ss中讀入下一個(gè)有效字符template <class T>char GList<T>:GetElem() while(m_ssm_si=' ') m_si+; / 濾掉空格 char e=m_ssm_si; m_si+; return e;template <class T>GListNode<T>* GList<T>:DoCreate() GListNode<T>* p; char e=GetElem(); if(e='(') p=new GListNode<T> p->type=LIST; p->child = DoCreate(); p->next = DoCreate(); return(p); if(e=')' | e='0') return(NULL); p=new GListNode<T> p->type=ATOM; p->data=e; p->next = DoCreate(); return(p);思考：設(shè)str="(a (b c) d)(e f)"，畫出結(jié)構(gòu)圖。4.7 參考閱讀：刪除廣義表中所有值為e的結(jié)點(diǎn)/ 單鏈表函數(shù)：遞歸刪除所有值為e的結(jié)點(diǎn)/ 設(shè)有特殊頭結(jié)點(diǎn)template<class T> void LinkList<T>:Delete(const T &e) Delete(m_Head,e); template<class T> void LinkList<T>:Delete(LinkNode<T> *first,const T &e) LinkNode<T> *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的結(jié)點(diǎn) / 遞歸刪除所有值為e的結(jié)點(diǎn)template<class T> void GList<T>:Delete(const T &e) Delete(m_Head,e); template<class T> void GList<T>:Delete(GListNode<T> *first,const T &e) GListNode<T> *p; if(!first) return; / 在*first的后繼表中刪除 if(first->next) p=first->next; if(p->data=e) first->next=p->next; free(p); Delete(first,e); else Delete(p, e); / 在*first的子表中刪除 if(first->type=LIST && first->child) p=first->child; if(p->data=e) first->child=p->next; free(p); Delete(first,e); else Delete(p, e); 5-19