广义表,相对于链表较复杂,相对于树又较简单....用来过渡顺序表和树是非常好的选择.

　　废话不多说,一言不合就贴代码.

/*
*文件说明:广义表相关声明及定义
*作者:高小调
*日期:2016-12-12
*集成开发环境:Microsoft Visual Studio 2010 
*/
#ifndef __GENERALLIST_H__
#define __GENERALLIST_H__
#include<assert.h>
enum Type{
	HEAD,
	SUB,
	VALUE
};
struct GeneralListNode{
	Type type;
	union{
		char value;
		GeneralListNode *sublink;
	};
	GeneralListNode *next;
	GeneralListNode(Type t,const char v = 0)
		:type(t)
		,next(0){
			if(t == HEAD || t ==VALUE){
				value = http://www.mamicode.com/v;"(";
			}else if(cur->type == VALUE){	//值节点
				cout<<cur->value;
				if(cur->next!=NULL){		//不是最后一个元素
					cout<<",";				//以逗号分隔
				}
			}else if(cur->type == SUB){		//子表项
				_Print(cur->sublink);		//递归打印子表
				if(cur->next!=NULL){		//不是最后一项数据
					cout<<",";				//以逗号分隔
				}
			}else{
				assert(false);
			}
			cur = cur->next;
		}
		cout<<")";
	}
	//递归获取广义表数据个数
	size_t _Size(Node *head){
		Node *cur = head;
		size_t ret = 0;
		while(cur){
			if(cur->type ==VALUE){			//当前为值节点
				++ret;						//数据个数+1
			}else if(cur->type ==SUB){
				ret += _Size(cur->sublink);	//递归求取子表数据个数
			}else{
				//头节点
			}
			cur = cur->next;
		}
		return ret;
	}
	//递归求广义表深度
	size_t _Depth(Node *head){
		Node *cur = head;
		size_t MaxDepth = 1;						//当前深度为1
		while(cur){
			if(cur->type == SUB){					//遇到子表
				size_t Depth = _Depth(cur->sublink);//递归求子表深度
				if(MaxDepth<Depth+1){				//如果子表深入大于当前值
					MaxDepth = Depth+1;				//更新最大深入
				}
			}
			cur = cur->next;
		}
		return MaxDepth;							//返回最大深度
	}
private:
	Node * _head;
};
#endif

/*
*文件说明:测试文件
*作者:高小调
*日期:2016-12-12
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<iostream>
using namespace std;
#include"GeneralList.h"
void GeneralListTest(){
	const char * const str1 = "(a)"; 
	GeneralList g1(str1);
	g1.Print();
	cout<<"Size = "<<g1.Size()<<endl;
	cout<<"Depth = "<<g1.Depth()<<endl;

	const char * const str2 = "(a,b)"; 
	GeneralList g2(str2);
	g2.Print();
	cout<<"Size = "<<g2.Size()<<endl;
	cout<<"Depth = "<<g2.Depth()<<endl;

	const char * const str3 = "(a,b,(c,d))"; 
	GeneralList g3(str3);
	g3.Print();
	cout<<"Size = "<<g3.Size()<<endl;
	cout<<"Depth = "<<g3.Depth()<<endl;
	
	const char * const str4 = "((e,(f),h))"; 
	GeneralList g4(str4);
	g4.Print();
	cout<<"Size = "<<g4.Size()<<endl;
	cout<<"Depth = "<<g4.Depth()<<endl;

	const char * const str5 = "(((1,2)),((3,4)))";
	GeneralList g5(str5);
	g5.Print();
	cout<<"Size = "<<g5.Size()<<endl;
	cout<<"Depth = "<<g5.Depth()<<endl;

	cout<<"////////拷贝构造//////"<<endl<<endl;
	//(a)
	GeneralList g6(g1);
	g6.Print();
	cout<<"Size = "<<g6.Size()<<endl;
	cout<<"Depth = "<<g6.Depth()<<endl;
	//(a,b)
	GeneralList g7(g2);
	g7.Print();
	cout<<"Size = "<<g7.Size()<<endl;
	cout<<"Depth = "<<g7.Depth()<<endl;

	//(a,b,(c,d))
	GeneralList g8(g3);
	g8.Print();
	cout<<"Size = "<<g8.Size()<<endl;
	cout<<"Depth = "<<g8.Depth()<<endl;

	GeneralList g9(g4);
	g9.Print();
	cout<<"Size = "<<g9.Size()<<endl;
	cout<<"Depth = "<<g9.Depth()<<endl;

	GeneralList g10(g5);
	g10.Print();
	cout<<"Size = "<<g10.Size()<<endl;
	cout<<"Depth = "<<g10.Depth()<<endl;
}
int main(){
	GeneralListTest();
	return 0;
}

　　总结:

　　第一次接触这个,还确实有点难办,写得我脑袋都透支了,还专门打了几把LOL休息了一下....

　　这个东西并不是有多难,仅仅是因为递归程序,极其难于调试.当程序出问题时,调试比较让人抓狂!

　　还有一点就是,个人太钻牛角尖.有时候及时接受别人的知识,然后纳入自己的知识体系,比自己死磕要快得多....

数据结构之用C++实现广义表