首页 > 代码库 > 广义表存储
广义表存储
节点形态：
存储结构：
每个节点都包含一个标志域，如果为0（即原子），那么仅含一个值域，如果是1（列表），那么说明该节点包含两个指针域。
需要注意的是求广义表长度的操作，其实计算的是根节点及其兄弟的个数，比如图2中广义表的长度为2，图3中广义表的长度为4。
深度的定义方式是递归式的，定义空表深度为1，原子深度为0，广义表的深度比其子表的深度的最大值大1.故图2的深度为3，图3的深度为2。
注意：任何一个非空列表其表头可能是原子，也可能是列表，但是其表尾必定是列表，也就是说不存在这样的广义表：
具体实现：
/************************************
广义表存储结构
by Rowandjj
2014/5/13
************************************/
#include<iostream>
using namespace std;
/*广义表的头尾链表存储表示*/
typedef enum{ATOM,LIST}ElemTag;//ATOM == 0,原子;LIST == 1,子表
typedef int AtomType;
typedef struct _BROADLIST_
{
ElemTag tag;/*标志域，用于区分是原子节点还是子表*/
union/*原子节点和表节点的联合部分*/
{
AtomType atom;/*原子节点的值域*/
struct/*子表的指针域,ptr.hp和ptr.tp分别指向表头和表尾*/
{
struct _BROADLIST_ *hp,*tp;
}ptr;
}Data;
}BroadList,*pBroadList,**ppBroadList;
//---------------------------------------------------
void InitBroadList(ppBroadList ppBroadListTemp);
void DestroyBroadList(ppBroadList ppBroadListTemp);
bool CopyBroadList(ppBroadList ppBroadListTemp,pBroadList pBroadListTemp);
void TravelBroadList(pBroadList pBroadListTemp);
int GetLength(pBroadList pBroadListTemp);//获取广义表长度,其实求的是根节点以及兄弟节点个总个数
int GetDepth(pBroadList pBroadListTemp);//求广义表深度
pBroadList GetHead(pBroadList pBroadListTemp);//获取头节点
pBroadList GetTail(pBroadList pBroadListTemp);//获取表尾
bool InsertFirst(ppBroadList ppBroadListTemp,pBroadList pBroadListTemp);//将pBroadListTemp插入广义表首位，该节点可能是原子也可能是表
bool DeleteFirst(ppBroadList ppBroadListTemp,ppBroadList pRet);//删除广义表的第一元素，并用pRet返回
//---------------------------------------------------
void InitBroadList(ppBroadList ppBroadListTemp)
{
if(ppBroadListTemp != NULL)
{
free(*ppBroadListTemp);
}
*ppBroadListTemp = NULL;
}
void DestroyBroadList(ppBroadList ppBroadListTemp)
{
if(*ppBroadListTemp == NULL)
{
return;
}
if((*ppBroadListTemp)->tag == ATOM)//原子类型
{
free(*ppBroadListTemp);
*ppBroadListTemp = NULL;
}
else
{
pBroadList pChild = NULL;
pBroadList pBrother = NULL;
pChild = (*ppBroadListTemp)->Data.ptr.hp;
pBrother = (*ppBroadListTemp)->Data.ptr.tp;
free(*ppBroadListTemp);
//递归调用
DestroyBroadList(&pChild);
DestroyBroadList(&pBrother);
}
}
bool CopyBroadList(ppBroadList ppBroadListTemp,pBroadList pBroadListTemp)
{
if(pBroadListTemp == NULL)
{
*ppBroadListTemp = NULL;
return false;
}
*ppBroadListTemp = (pBroadList)malloc(sizeof(BroadList));//动态创建新节点
memset(*ppBroadListTemp,0,sizeof(BroadList));//初始化内存
if(*ppBroadListTemp == NULL)
{
return false;
}
(*ppBroadListTemp)->tag = pBroadListTemp->tag;//复制标志位
if(pBroadListTemp->tag == ATOM)
{
(*ppBroadListTemp)->Data.atom = pBroadListTemp->Data.atom;//复制原子节点数据值
return true;
}
else//递归调用自己
{
CopyBroadList(&((*ppBroadListTemp)->Data.ptr.hp),pBroadListTemp->Data.ptr.hp);
CopyBroadList(&((*ppBroadListTemp)->Data.ptr.tp),pBroadListTemp->Data.ptr.tp);
}
return true;
}
void TravelBroadList(pBroadList pBroadListTemp)//遍历
{
if(pBroadListTemp == NULL)
{
return;
}
if(pBroadListTemp->tag == ATOM)
{
cout<<pBroadListTemp->Data.atom<<" ";
}
else
{
TravelBroadList(pBroadListTemp->Data.ptr.hp);
TravelBroadList(pBroadListTemp->Data.ptr.tp);
}
}
int GetLength(pBroadList pBroadListTemp)
{
if(pBroadListTemp == NULL)
{
return 0;
}
int len = 0;
if(pBroadListTemp->tag == ATOM)
{
return 1;
}
pBroadList pTravel = pBroadListTemp;
while(pTravel != NULL)
{
len++;
pTravel = pTravel->Data.ptr.tp;
}
return len;
}
int GetDepth(pBroadList pBroadListTemp)
{
if(pBroadListTemp == NULL)//空表的深度为1
{
return 1;
}
if(pBroadListTemp->tag == ATOM)//原子深度为0
{
return 0;
}
pBroadList pTemp = pBroadListTemp;
int max = 0,depth;
for(;pTemp!=NULL; pTemp = pTemp->Data.ptr.tp)//横向扫描
{
depth = GetDepth(pTemp->Data.ptr.hp);
if(depth>max)
{
max = depth;
}
}
return max+1;/*非空表的深度是各元素的深度的最大值加1*/
}
pBroadList GetHead(pBroadList pBroadListTemp)
{
/*仅仅获取头节点，并不包括头节点的兄弟节点,但是却包括头节点的孩子节点（如果有的话）*/
if(pBroadListTemp == NULL)
{
exit(0);
}
pBroadList h,p;
h = pBroadListTemp->Data.ptr.tp;
pBroadListTemp->Data.ptr.tp = NULL;//截断
CopyBroadList(&p,pBroadListTemp);
pBroadListTemp->Data.ptr.tp = h;//重新接回去
return p;
}
pBroadList GetTail(pBroadList pBroadListTemp)
{
pBroadList pTemp;
if(pBroadListTemp == NULL)
{
exit(0);
}
CopyBroadList(&pTemp,pBroadListTemp->Data.ptr.tp);
return pTemp;
}
bool InsertFirst(ppBroadList ppBroadListTemp,pBroadList pBroadListTemp)
{
//算法比较有趣，直接创建一个新的表，表头指针指向新节点，表尾指向旧表
pBroadList pNew = (pBroadList)malloc(sizeof(BroadList));
if(pNew == NULL)
{
return false;
}
memset(pNew,0,sizeof(BroadList));
pNew->tag = LIST;
pNew->Data.ptr.hp = pBroadListTemp;
pNew->Data.ptr.tp = *ppBroadListTemp;
*ppBroadListTemp = pNew;
return true;
}
bool DeleteFirst(ppBroadList ppBroadListTemp,ppBroadList pRet)
{
if(*ppBroadListTemp == NULL)
{
return false;
}
pBroadList pTemp;
*pRet = (*ppBroadListTemp)->Data.ptr.hp;
pTemp = *ppBroadListTemp;
*ppBroadListTemp = (*ppBroadListTemp)->Data.ptr.tp;
free(pTemp);
return true;
}部分测试代码：
int main()
{
pBroadList pBroadListTemp = (pBroadList)malloc(sizeof(BroadList));
//记得初始化，不然很讨厌..
memset(pBroadListTemp,0,sizeof(BroadList));
pBroadListTemp->tag = LIST;
pBroadListTemp->Data.ptr.hp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.hp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.hp->tag = ATOM;
pBroadListTemp->Data.ptr.hp->Data.atom = 1;
pBroadListTemp->Data.ptr.tp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.tp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.tp->tag = LIST;
pBroadListTemp->Data.ptr.tp->Data.ptr.tp = NULL;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.tp->Data.ptr.hp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->tag = LIST;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.hp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.hp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.hp->tag = ATOM;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.hp->Data.atom = 2;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->tag = LIST;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->Data.ptr.tp = NULL;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->Data.ptr.hp = (pBroadList)malloc(sizeof(BroadList));
memset(pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->Data.ptr.hp,0,sizeof(BroadList));
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->Data.ptr.hp->tag = ATOM;
pBroadListTemp->Data.ptr.tp->Data.ptr.hp->Data.ptr.tp->Data.ptr.hp->Data.atom = 3;
pBroadList p;
CopyBroadList(&p,pBroadListTemp);
TravelBroadList(p);
cout<<"\n------------------"<<endl;
cout<<"depth = "<<GetDepth(pBroadListTemp)<<endl;
TravelBroadList(pBroadListTemp);
cout<<endl;
cout<<"len = "<<GetLength(pBroadListTemp)<<endl;
cout<<"copy,len = "<<GetLength(p)<<endl;
cout<<"------------------------"<<endl;
cout<<"depth = "<<GetDepth(pBroadListTemp)<<endl;
cout<<"copy,depth = "<<GetDepth(p)<<endl;
cout<<"--------------"<<endl;
pBroadList temp = GetHead(pBroadListTemp->Data.ptr.tp);
TravelBroadList(temp);
cout<<"\n--------------"<<endl;
TravelBroadList(GetTail(pBroadListTemp));
cout<<"\n--------------"<<endl;
DestroyBroadList(&pBroadListTemp);
DestroyBroadList(&p);
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。