您好,登錄后才能下訂單哦!
廣義表的定義:
廣義表是非線性的結(jié)構(gòu),是n個(gè)元素的有限序列。
舉例:A=(a,b,(c,d))
我們先定義它的結(jié)構(gòu):
(1)它有三種節(jié)點(diǎn),頭節(jié)點(diǎn)、值節(jié)點(diǎn)、子表節(jié)點(diǎn)。
(2)兩種指向下一節(jié)點(diǎn)的指針:指向下一值值節(jié)點(diǎn)的指針_next,指向子表節(jié)點(diǎn)的指針_sublink.
enum Type//用枚舉形式來定義廣義表中三種節(jié)點(diǎn)類型 { HEAD, //頭類型 VALUE,//值類型 SUB,//子表類型 }; struct GeneralizedNode { Type _type;//類型 GeneralizedNode* _next;//指向下一節(jié)點(diǎn)的指針 union { int _value;//一個(gè)節(jié)點(diǎn)下一節(jié)點(diǎn)可能是值節(jié)點(diǎn),也可能是子表節(jié)點(diǎn) GeneralizedNode* _sublink; }; GeneralizedNode(Type type) :_next(NULL) , _type(type) {} GeneralizedNode(Type type,int value) :_next(NULL) , _type(type) , _value(value) {} };
下面,我們來看下實(shí)現(xiàn)的代碼:
class Generalized { public: Generalized() :_head(NULL) {} Generalized(const char* str) { _head = _CreateList(str);//調(diào)用函數(shù)創(chuàng)建節(jié)點(diǎn) } Generalized(const Generalized& gr) { _head = _Copy(gr._head);//調(diào)用函數(shù)拷貝節(jié)點(diǎn) } Generalized& operator=(const Generalized& gr) { if (&gr != this) { _Copy(gr._head); _Destroy(_head); } return *this; } ~Generalized() { _Destroy(_head); } void Print() { _Print(_head); } size_t Size() { return _Size(_head); } size_t Depth() { return _Depth(_head); } protected: //拷貝廣義表 GeneralizedNode* _Copy(GeneralizedNode* grhead) { GeneralizedNode* grcur = grhead; GeneralizedNode* newHead = new GeneralizedNode(HEAD); GeneralizedNode* newcur = newHead; while (grcur) { if (grcur->_type == VALUE) { GeneralizedNode* tmp = new GeneralizedNode(VALUE); newcur->_next = tmp; newcur = newcur->_next; newcur->_value = grcur->_value; } else if (grcur->_type == SUB) { GeneralizedNode* tmp = new GeneralizedNode(SUB); newcur->_next = tmp; newcur = newcur->_next; newcur->_sublink = _Copy(grcur->_sublink); } grcur = grcur->_next; } newcur = NULL; return newHead; } //釋放廣義表 void _Destroy(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; cur = cur->_next; if (del->_type == SUB) { _Destroy(del->_sublink); } else { delete del; del = NULL; } } } //打印 void _Print(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << "("; } else if (cur->_type == VALUE) { cout << (char)(cur->_value); if (cur->_next) { cout << ","; } } else if (cur->_type == SUB) { _Print(cur->_sublink); if (cur->_next) { cout << ","; } } cur = cur->_next; } cout << ")"; } //判斷是否是值 bool _IsValue(const char* str) { if (*str > 0 && *str<9 || *str>'a' && *str<'z' || *str>'A' && *str < 'Z') { return true; } else { return false; } } //創(chuàng)建節(jié)點(diǎn) GeneralizedNode* _CreateList(const char* str) { assert(*str=='('); ++str; GeneralizedNode* head = new GeneralizedNode(HEAD); GeneralizedNode* cur = head; while (cur) { if (_IsValue(str)) { cur->_next = new GeneralizedNode(VALUE,*str); cur = cur->_next; str++; } else if (*str == '(') { GeneralizedNode* SubNode = new GeneralizedNode(SUB); cur->_next = SubNode; cur = cur->_next; SubNode->_sublink = _CreateList(str); str++; } else if (*str == ')') { str++; return head; } else { str++; } } cout << "廣義表出錯(cuò)!" << endl; assert(false); return head; } //大?。ㄖ倒?jié)點(diǎn)數(shù)) size_t _Size(GeneralizedNode* head) { GeneralizedNode* cur = head; size_t size = 0; while (cur) { if (cur->_type == VALUE) { size++; } else if (cur->_type == SUB) { size += _Size(cur->_sublink); } cur = cur->_next; } return size; } //深度 size_t _Depth(GeneralizedNode* head) { size_t depth = 1; GeneralizedNode* cur = head; while (cur) { if (cur->_type == SUB) { size_t curdepth = _Depth(cur->_sublink); if (curdepth + 1 > depth) { depth = curdepth + 1; } } cur = cur->_next; } return depth; } private: GeneralizedNode* _head; }; void Test() { Generalized gr1("()"); Generalized gr2("(a,b,(c,d))"); Generalized gr3("(a,b,(c,(d),e))"); Generalized gr4(gr3); gr1.Print(); cout << endl; gr2.Print(); cout << endl; gr3.Print(); cout << endl; gr4.Print(); cout << endl; size_t size = gr4.Size(); cout << "gr4大?。?<<size << endl; int depth = gr4.Depth(); cout << "gr4深度:" << depth << endl; } int main() { Test(); system("pause"); return 0; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。