《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第5章 稀疏矩陣和廣義表》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第5章 稀疏矩陣和廣義表（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第5章 數(shù)組和廣義表
3 廣義表
3.1 邏輯結(jié)構(gòu)
3.1.1 定義
線性表的擴展：每個子結(jié)構(gòu)或是一個基本元素，或是一個線性表。
GList={a1,a2,…,an | ai∈AtomSet或ai∈GList}
ai∈AtomSet：ai為原子。
ai∈Glist ：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)元素, 其余為表尾(t
2、ail)。
3.1.2 典型應(yīng)用領(lǐng)域
Lisp語言、前綴表達式。
(setq x (+ 4 (- a b)) y (+ 3 4) )
表頭：函數(shù)名； 表尾：參數(shù)表
3.1.3 基本概念與操作
取表頭指針
GListNode *GetHead()
取表尾指針
GListNode *GetTail()
取某結(jié)點指針
GListNode *nth(int i)
求表長度
int GetLength();
求表深度
int GetDepth();
原子深度=0，表深度=max{GList_Depth(ai)}+1
例：求長度、深度：
3、(a), (), ((a),a)， (((a),a),(a),a)
遍歷
void Traverse();
復(fù)制
GList *Copy();
3.2 存儲結(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é)點(相當(dāng)于括號)。
意義：結(jié)構(gòu)規(guī)范、算法簡化。
3.2.3 類的定義
// 廣義表結(jié)點的結(jié)構(gòu)定義：表結(jié)點、原子結(jié)點
typedef enum {ATOM,LIST} GListNodeType;
template
4、ss T>
struct GListNode
{ GListNodeType type; // 結(jié)點類型
union // 聯(lián)合
{ T data;
GListNode *child;
};
GListNode * next;
};
// 廣義表類定義
template
class GList
{
GListNode *m_Head; // 廣義表頭指針
public:
GList();
GList(char s[]); // 根據(jù)"(a (b c) d)"構(gòu)造
5、GList(GList &gl); // 拷貝構(gòu)造
~GList();
void Free(); // 釋放廣義表
void Traverse(); // 遍歷廣義表
int GetLength(); // 計算長度
int GetDepth(); // 計算深度
…………
};
3.3 存儲結(jié)構(gòu)的應(yīng)用：m元多項式
typedef enum {ATOM,LIST} GListNodeType;
struct MPNode
{ GListNodeType type; // 結(jié)點類型
int exp;
6、 // 指數(shù)域
union
{ float coef; // 原子結(jié)點中的系數(shù)域
GListNode *child;
};
GListNode * next;
};
繪制存儲結(jié)構(gòu)：
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=
7、0;
for(GListNode *p=m_Head->child; p; p=p->next)
length++;
return length;
}
4.2 遍歷廣義表
template
void GList::Traverse() // 遍歷廣義表
{ DoTraverse(m_Head);
cout<
void GList::DoTraverse(GListNode *p)
{ for(; p; p=p->next)
if
8、(p->type==ATOM)
cout << p->data << " ";
else // 輸出子表，格式： "(………)"
{ cout << '(';
DoTraverse(p->child);
cout << ')';
}
}
4.3 求表深度
template
int GList::GetDepth()
{ return Depth(m_Head); }
template
int GList::Depth(GL
9、istNode *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(depth>maxdepth) maxdepth=depth;
}
return(maxdepth+1);
}
4.4 拷貝構(gòu)造函數(shù)
template
GList::GList(GList &gl)
{
10、 m_Head = DoCopy(gl.m_Head); }
// 類似于“單向鏈表的構(gòu)造函數(shù)”
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->d
11、ata;
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
void GList::Free() // 釋放廣義表
{ DoFree(m_Head); m_Head=NULL; }
template
12、
void GList::DoFree(GListNode *p)
{ while( p!=NULL )
{ GListNode *q=p; // q指向?qū)h除的結(jié)點
p=p->next;
if(q->type==LIST) DoFree(q->child);
delete q;
}
}
4.6 帶參構(gòu)造函數(shù)
template
GList::GList(char s[]) // 根據(jù)"(a (b c) d)"構(gòu)造
{ m_ss=new char[strlen(s)+1
13、];
strcpy(m_ss,s); m_si=0; // 完成數(shù)據(jù)準(zhǔn)備
m_Head=DoCreate();
delete []m_ss;
}
//從m_ss[]中讀入下一個有效字符
template
char GList::GetElem()
{ while(m_ss[m_si]==' ') m_si++; // 濾掉空格
char e=m_ss[m_si]; m_si++;
return e;
}
template
GListNode* GList::DoCreate(
14、)
{ 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();
15、return(p);
}
思考：設(shè)str[]="(a (b c) d)(e f)"，畫出結(jié)構(gòu)圖。
4.7 參考閱讀：刪除廣義表中所有值為e的結(jié)點
// 單鏈表函數(shù)：遞歸刪除所有值為e的結(jié)點
// 設(shè)有特殊頭結(jié)點
template
void LinkList::Delete(const T &e)
{ Delete(m_Head,e); }
template
void LinkList::Delete(LinkNode *first,const T &e)
{ LinkNode *p;
if(
16、!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é)點
// 遞歸刪除所有值為e的結(jié)點
template
void GList::Delete(const T &e)
{ Delete(m_Head,e); }
template
void GList
17、>::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; 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
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第5章 稀疏矩陣和廣義表
