【C/C++】实现数据结构广义表

1. 广义表的定义
     每个元素可以为Atom,原子,也可以为线性表。
     线性表的推广。线性表元素有唯一的前驱和后继,为线性表,而广义表是多层次的线性表
     表头:第一个元素,可能是原子,可能是广义表
     表尾:除了第一个元素,剩余的元素,所构成的广义表
     举例:
         A = (a,b,(c,d),e)
         head(A)  = a
         tail(A) = (b,(c,d),e)
     遍历操作:
     取表头,取表尾 ,取表头..
     长度:最外层的元素数,即最外层的','+1
     深度:括号层数
  2. 广义表的两种存储结构(子表法)
 
      2.1链式存储结构 - 每个数据元素可以用一个节点表示
         元素可以为原子或列表
         原子节点:标志域、值域
         列表节点:标志域、指示表头的指针域、指示表尾的指针域
         空表:A = NULL
         除了空表,表头指针指向一个表节点,表节点再分表头、表尾...
         最高层表节点(可能原子、子表)的个数就是表长度? A = (a,b,(c,d),e) 最高层表头是先a,表尾是(b,(c,d),e),表头是b,表尾((c,d),e)..就是第一层的表尾直到为空之前,有过的表尾指针+1
         判断是否在同一层次?
             是这样的: 最高层处于同一层,后继的tail指针指向的是同一层,否则,head指针,或者表头是Atom,都是下一层。
     2.2扩展线性表存储结构
         不是用表头表尾指针了,而是,每一个节点,不管是子表还是原子,都有一个指向本子表下一个元素的next指针
         A = (a,b,(c,d))
         A -> |1,HP,TP|
                 |    |
                 a -> b -> (c,d)
                             |
                             c -> d

下面,实现了广义表的两种定义,以及基于递归的一些操作。

 #include<bits/stdc++.h>
#define AtomType int
typedef enum{ATOM,LIST}ElemTag; //ATOM = 0:原子;LIST = 1:子表
/*线性表存储之链式*/
typedef struct GLNode{
ElemTag tag; //枚举类型的标志域,只能取定义了的枚举值
union{ //union联合体,下面两部分只能取其一;要么取AtomType;要么取结构体ptr,ptr包括两个指针hp,tp
AtomType atom;
struct{
struct GLNode *hp,*tp;
}ptr;
};
}*GList; //定义广义表类型,GList为指针 /*线性表存储之扩展线性表 = 子表法*/
typedef struct GLNode2{
ElemTag tag;
union{
AtomType atom;
struct GLNode2 *hp; //对于原子,tp就是指向其相同层次的下一个元素
//对于列表,hp指向本列表内部第一个元素,而tp是指向本层次上的下一个元素
};
struct GLNode2 *tp;
} *GList2;
/*
* 讨论广义表的递归算法 : 分治法进行递归算法设计
* 1. 问题可拆解成子问题,与原问题性质相同,规模变小
* 2. 有递归终止条件
*/ /*求广义表的深度 - 采用链式存储结构时
* 广义表的深度:()的重数 空表() 深度为1.原子深度为0
*
*/
int GListDepth(GList L) {
if(!L) return ; //空表1
if(L->tag ==ATOM ) return ;
GList pp;
//遍历同一层,递归下一层,取表尾,取表头,第一步先去一个表头
int max;
for(max = , pp =L;pp!=NULL;pp = pp->ptr.tp){
int dep = GListDepth(pp->ptr.hp) ;
if(dep > max) max = dep; //这一步比较,是比较同一层的depth
}
return max+;
}
//练习
int depth_my(GList L) {
if(L == NULL){
return ;
}
if(L->tag == ATOM){
return ;
}
int max = ;
GList pp;
for(max = ,pp=L;pp!=NULL;pp = pp->ptr.tp){
int dep = depth_my(pp->ptr.hp);
if(dep >max) max = dep;
}
return max+;
} /*
求Depth2 == 子表法求dep
*/
int GListDepth_2(GList2 L){
if(L == NULL) return ;
if(L->tag == ATOM) return ;
int max = ;
GList2 pp;
for(max = ,pp=L->hp;pp!=NULL;pp = pp->tp){
int dep = GListDepth_2(pp);
if(dep >max) max = dep;
}
return max+;
}
/*********************分界*****************************/
/*
* 复制广义表:copy深复制 -- 链式存储
* 分别复制表头、表尾,然后合成即可==递归
*/
void CopyGList(GList &T,GList L) {
//头尾链表存储,将L赋值给T
if(!L) T = NULL; //空
else{
//创建一个节点 ,这个节点要么是ATOM,要么是广义表
T = (GList)malloc(sizeof(GLNode));
if(!T) exit();
T->tag = L->tag;
if(L->tag == ATOM) //是原子的话,复制原子
T->atom = L->atom;
//复制广义表
else{
//分别复制表头和表尾
CopyGList(T -> ptr.hp,L->ptr.hp);
CopyGList(T->ptr.tp,L->ptr.tp);
}
}
}
//练习
void copy_my(GList&T,GList L) {
if(L == NULL) T = NULL;
else{
T = (GList)malloc(sizeof(GLNode));
if(!T) exit();
T -> tag = L -> tag;
if(L->tag == ATOM){
T->atom = L->atom;
}else{
copy_my(T -> ptr.hp,L->ptr.hp);
copy_my(T ->ptr.tp,L->ptr.tp);
}
}
}
/**********************分割线*************************/
/*
* 创建一个广义表:必考内容
* 广义表的书写,看成一个字符串S
* 下面头尾链表法创建一个广义表
*/
using namespace std;
string emp = "()" ; void sever(string &str,string &hstr){
//将非空串str分割成两部分,hstr是表头
int n = str.size();
int i = -;
int k = ; //k记录尚未配对的“(” 数
char ch;
do{ //搜索最外层第一个(
++i;
ch = str[i];
if(ch == '(') ++k;
else if(ch == ')') --k;
}while(i<n&&(ch != ','||k!=));
if(i<n){
hstr =str.substr(,i);
//printf("in\n");
str = str.substr(i+,n-i-);
//printf("out\n");
}else{
hstr = str.substr(,str.size());
str.clear();
}
} void CreateGList(GList &L,string s){
//采用头尾链表存储结构,创建L
if(s.compare(emp) == ) L = NULL;
else{
L = (GList)malloc(sizeof(GLNode));
if(!L) exit();
if(s.size() == ){ //单个元素,建立原子节点
L->tag = ATOM;
L->atom = s[];
}else{ //表节点 ,表尾
L->tag = LIST;
GList p,q;
p = L; //p是指向当前子表(表尾节点)的指针
string sub;
sub = s.substr(,s.size()-); //去掉外层括号
string hsub;
do{ //重复建立n个子表
sever(sub,hsub); //sub中分理出表头串hsub ,同时,sub去除了hsub
CreateGList(p->ptr.hp,hsub);
q = p; //记录p,下面sub不为空,要再建立一个表尾节点,q记录上一层的p,用以连接q->ptr.tp = q
if(!sub.empty()) {
p = (GList)malloc(sizeof(GLNode));
if(!p)exit();
p -> tag = LIST;
q -> ptr.tp = p;
}//if
}while(!sub.empty());
q -> ptr.tp = NULL;
// printf("has complete\n");
}
}
} int main(){
// string s = "1232342342";
// if(s.compare("123") == 0){
// printf("13");
// }
// printf("\n");
// s = s.substr(1,s.size()-2);
// for(int i = 0;i<s.size();i++){
// printf("%c",s[i]);
// } string ss = "(2,3,4,(1,2))";
GList L;
CreateGList(L,ss);
printf("深度:");
printf("%d",GListDepth(L));
return ;
}
上一篇:TodoList开发笔记 – PartⅠ


下一篇:CozyRSS开发记录15-获取和显示RSS内容