数据结构 广义表的c++实现(链表)[!注意!描述中有一个bug要修正]

/* 作者:臧旭 日期:2010/12/23 */ #include "GenList.h" #include "GenListNode.h" #include "Stack.h" GenList::~GenList() { Clear(); } GenList::GenList(char * exp) { if (exp && strlen(exp) > 0) { //利用一个栈来判断表达式的正确性 Stack<char> stack(10); first = Build(exp, stack); } else cout << "空字符串,不能创建广义表" << endl; } //所有的子表都可以表示成(...)的形式 GenListNode * GenList::Build(char *& ch, Stack<char> & stack) { GenListNode * q = 0; int dot = 0; while (*ch == ' ' || *ch == ',')//忽略' '和',' { if (*ch == ',') { dot++; if (dot > 1) //连续的两个逗号是错误的表达式 { cout << "广义表表达式语法错误!程序自动退出." << endl; exit(-1); } } ch++; } if (*ch == '\0') return q; //如果到达表达式的最后则返回 switch (*ch) { case '(': //找到新的表头 // stack.Add('('); ch++; q = new GenListNode; q->tag = true; q->dlink = Build(ch, stack); //首先构造下一层子表 //然后继续构造该层表头后面的部分 ch++; q->link = Build(ch, stack); return q; case ')': //找到一个表尾 //看是否有匹配的又括号 if (stack.IsEmpty()) { cout << "广义表表达式语法错误!程序自动退出." << endl; exit(-1); } char temp; stack.Delete(temp); return 0; default: //如果既不是'('也不是')',则表示该元素是一个原子 //原子直接入栈,不许判断正确性 stack.Add(*ch); q = new GenListNode; q->tag = false; q->data = *ch; ch++; q->link = Build(ch, stack); return q; } } ostream & operator<< (ostream & os, const GenList & pList) { if(!pList.first) { os << "空表"; return os; } pList.Print(os, pList.first); return os; } void GenList::Print(ostream & os, const GenListNode * node) const{ if (node == 0) //到子表的末尾 { os << ") "; return; } if (node->tag) //如果是子表头 { //首先打印该子表的'(' os << "( "; //打印子表 Print(os, node->dlink); //如果还有其他的表,则输出',' if (node->link) { os << ", "; } //打印其他的表 Print(os, node->link); } else //如果是原子 { //输出原子 os << node->data; if (node->link) os << ", "; //如果还有下一个元素 else os << " "; Print(os, node->link); //继续打印后面的元素 } } bool GenList::operator == (const GenList & pList) { GenListNode * p = this->first; GenListNode * q = pList.first; return Equal(p, q); } bool GenList::Equal(GenListNode * p, GenListNode * q) const { bool x; if (!p && !q) return true; if (p && q && (p->tag == q->tag)) { if (!p->tag) //原子 { if (p->data == q->data) x = true; else x = false; } else //有子表 { x = Equal(p->dlink, q->dlink); } if (x) return Equal(p->link, q->link); } return false; } int GenList::Depth() { return Depth(first); } //m用来保存当前的最深的深度 int GenList::Depth(GenListNode * p) { if(!p) return 1; //空表 else { GenListNode * q = p; int m = 0; while (q) //深度优先递归 { if (q->tag) //存在子表 { int n = Depth(q->dlink); if (m < n) m = n; } q = q->link; } return m + 1; } } //找到A里面第一层的最后一个元素, 然后把pList的第一层的第一个元素链在后面 void GenList::Merge(const GenList & pList) { if (first && pList.first) { GenList * tList = new GenList; tList->Copy(pList); GenListNode * q = first; for (; q->link != 0; q = q->link); q->link = tList->first; } } void GenList::Copy(const GenList & pList) { first = Copy(pList.first); } GenListNode * GenList::Copy(const GenListNode * p) { GenListNode * q = 0; if (p) { q = new GenListNode; q->tag = p->tag; if (q->tag) { q->dlink = Copy(p->dlink); } else { q->data = p->data; } q->link = Copy(p->link); } return q; } void GenList::Clear() { Clear(first); first = 0; } void GenList::Clear(GenListNode * p) { if (!p) return; if (p->tag) //子表 { Clear(p->dlink); Clear(p->link); delete p; //删除子表的首结点 } else //原子 { //如果不是最后一个原子 if (p->link) { Clear(p->link); delete p; } else //如果是最后一个原子,则开始删除 { delete p; } } }