VAL->VAL->LINK(->HEAD.....)->VAL->......&n..."/>
您好,登錄后才能下訂單哦!
廣義表是我第一次用遞歸接觸鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu),其結(jié)構(gòu)如下:
HEAD->VAL->VAL->LINK(->HEAD.....)->VAL->......
在這里,我們的頭結(jié)點(diǎn)與link節(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的,由此我們便可以定義出節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu):
typedef int DataType; enum NodeType//枚舉類型定義節(jié)點(diǎn)類型 { HEAD, VALUE, SUB, }; struct GeneralizedNode { public: GeneralizedNode() :_next(NULL) , _link(NULL) {} NodeType _type; GeneralizedNode* _next; union//因?yàn)閘ink與value是不可能同時(shí)存在的,故用共同體節(jié)省空間 { GeneralizedNode* _link; DataType _value; }; };
因?yàn)閺V義表是鏈?zhǔn)降那短捉Y(jié)構(gòu),所以我們必須用遞歸來(lái)進(jìn)行遍歷,這里面遞歸的方式有很多種,可以循環(huán)套遞歸,也可以遞歸套遞歸,也可以遞歸套循環(huán),根據(jù)我們不同的需求,可以吧這三種方法都運(yùn)用在合適的地方,這里,我簡(jiǎn)單的實(shí)現(xiàn)了,返回對(duì)象的層數(shù),數(shù)據(jù)個(gè)數(shù),以及一些常用的成員函數(shù),其代碼如下:
class Generalized { public: Generalized() :_head(NULL) {} Generalized(const char *str)//構(gòu)造函數(shù)是用字符串來(lái)體現(xiàn)廣義表如(1,2,(2,3)) { //這樣可以更好的體現(xiàn)出廣義表的結(jié)構(gòu) _head = _CreatList(str); } ~Generalized() { _Destory(_head); } void Print()//控制臺(tái)打印廣義表,也是打印出字符串類型 { _Print(_head); } Generalized(const Generalized &g) { _head = _Copy(g._head); } Generalized&operator = (Generalized g) { swap(_head, g._head); return *this; } size_t Depth() { return _Depth(_head); } size_t Size() { size_t size = 0; _Size(_head, size); return size; } protected: size_t _Depth(GeneralizedNode* head) { size_t depth = 1; GeneralizedNode* cur = head; while (cur) { if (cur->_type == SUB) { size_t newdepth = _Depth(cur->_link) + 1; depth = depth < newdepth ? newdepth : depth; } cur = cur->_next; } return depth; } void _Size(GeneralizedNode* head, size_t &size) { GeneralizedNode* cur = head; while (cur) { if (cur->_type == VALUE) ++size; else if (cur->_type == SUB) _Size(cur->_link, size); cur = cur->_next; } } GeneralizedNode* _Copy(GeneralizedNode *head) { GeneralizedNode* cur = head; GeneralizedNode* newHead = new GeneralizedNode; GeneralizedNode*tail = newHead; tail->_type = HEAD; while (cur) { if (cur->_type == SUB) { tail->_next = new GeneralizedNode; tail = tail->_next; tail->_type = SUB; tail->_link = _Copy(cur->_link); } else if (cur->_type == VALUE) { tail->_next = new GeneralizedNode; tail = tail->_next; tail->_type = VALUE; tail->_value = cur->_value; } cur = cur->_next; } return newHead; } void _Print(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << "("; } else if (cur->_type == VALUE) { cout << cur->_value; if (cur->_next!=NULL&& cur->_next->_type == VALUE) cout << ","; } else _Print(cur->_link); cur = cur->_next; } cout << ")"; } GeneralizedNode* _CreatList(const char* &str) { assert('(' == *str); GeneralizedNode* head = new GeneralizedNode; GeneralizedNode* cur = head; head->_type = HEAD; while (*++str) { if (IsValue(str)) { cur->_next = new GeneralizedNode; cur = cur->_next; cur->_type = VALUE; cur->_value = *str; str++; } else if (')' == *str) { return head; } else if ('(') { cur->_next = new GeneralizedNode; cur = cur->_next; cur->_type = SUB; cur->_link = _CreatList(str); } cur->_next = NULL; *str++; } return head; } bool IsValue(const char *str)//判斷表內(nèi)存儲(chǔ)數(shù)據(jù)是否為所需數(shù)據(jù)類型 { if (*str <= '9'&& *str >= '0') return true; return false; } void _Destory(GeneralizedNode*head) { GeneralizedNode*cur = head; if (cur->_value == SUB) _Destory(cur->_link); else if (cur->_next != NULL) _Destory(cur->_next); delete cur; } protected: GeneralizedNode* _head; };
如有什么不足或疑問(wèn)希望提出。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。