数据结构算法C语言实现（十九）--- 5.5&5.6&5.7广义表
2024-10-14 20:24:48
一.简述
传说Lisp的基本数据结构就是广义表，广义表也是具有典型递归属性的数据结构，此外，由于建表要处理字符串，用C语言处理起来也是一脸懵逼.....最后自己还想写一个将广义表还原成字符串的函数，一是使其可视化，而是验证算法5.6。花了不少功夫才写出来（强烈建议自己动手写一写），最后是借助树形结构的角度才找到一个不错的解决办法。按照《数据结构编程实验》的分类，数据结构无非线性结构、树状结构、图结构，可以说树是特殊的图（图的最小生成树），线性表示特殊的树。。。。。扯远了！
二.头文件
补充版字符串处理头文件
//4_2_part1.h
/**
author:zhaoyu
*/
//2016-6-10
//----串的定长顺序存储表示----
#ifndef _4_2_PART1_H_
#define _4_2_PART1_H_
#include "head.h"
#define MAXSTRLEN 255//用户可以在255以内定义最大串长
//这语法还不是很熟悉
typedef unsigned char SString[MAXSTRLEN+];//0 号单元存放串的长度
int StrLength(SString T)
{
for (int i = ; i <= MAXSTRLEN; ++i)
{
if ('\0' == T[i])
{
return i-;
}
}
return MAXSTRLEN;
} /**
algorithm 4.2
*/
Status Concat(SString &T, SString S1, SString S2)
{
//用 T 返回由 S1 和 S2 连接而成的新串。
//若未截断，则返回 TRUE，否则返回 FALSE
Status uncut;
if (S1[] + S2[] < MAXSTRLEN)
{//未截断
int i = ;
for (i = ; i <= S1[]; ++i)
{
T[i] = S1[i];
}
for (i = ; i <= S2[]; ++i)
{
T[S1[]+i] = S2[i];
}
T[] = S1[] + S2[];
uncut = TRUE;
}
else if (S1[] < MAXSTRLEN)
{
int i = ;
for (i = ; i <= S1[]; i++)
{
T[i] = S1[i];
}
for (i = S1[]+; i <= MAXSTRLEN; i++)
{
T[i] = S2[i-S1[]];
}
T[] = MAXSTRLEN;
uncut = FALSE;
}
else
{
for (int i = ; i <= MAXSTRLEN; i++)
{
T[i] = S1[i];
}
T[] = S1[] = MAXSTRLEN;
uncut = FALSE;
}
return uncut;
}
/**
algorithm 4.3
*/
Status SubString(SString &Sub, SString S, int pos, int len)
{
//用 Sub 返回串 S 的第 pos 个字符起长度为 len 的字串
//其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
if (pos < || pos > S[] || len < || len > S[]-pos+)
{
return ERROR;
}
for (int i = ; i <= len; i++)
{
Sub[i] = S[i+pos-];
}
Sub[len+] = '\0';
Sub[] = len;
return OK;
}
/**
add for chapter 5 / page 116.117
*/
Status StrCompare(SString S, SString T)
{
for (int i = ; i <= S[] && i <=T[]; i++)
{
if (S[i]-T[i] > ){
return ;
}
if (S[i]-T[i] < )
{
return -;
}
}
if (S[] == T[])
{
return ;
}
return S[]>T[]?:-;
}
Status StrEmpty(SString S)
{
if ( == StrLength(S))
{
return TRUE;
}
else
{
return FALSE;
}
}
Status StrCopy(SString &T, SString S)
{//健壮性并不够
for (int i = ; i <= S[]+; i++)
{
T[i] = S[i];
}
return OK;
}
Status ClearString(SString S)
{
S[] = ;
S[] = '\0';
return OK;
}
void PrintSString(SString T)
{
//if(T[])
for (int i = ; i <= T[]; ++i)
{
printf("%c", *(T+i));
}
printf("\n");
}
#endif
4_2_part1.h
//5_5.h
/**
author:zhaoyu
date；2016-6-16
*/
//----广义表的头尾链表存储表示----
#include "4_2_part1.h"
#define AtomType char
typedef enum {ATOM, LIST} ElemTag;//ATOM==0：原子，LIST==1子表
typedef struct GLNode
{
ElemTag tag;//公共部分，用于区分原子结点和表节点
union{//原子结点和表节点的公共部分
AtomType atom;//atom 是原子结点的值域，AtomType由用户定义
struct {struct GLNode *hp, *tp;}ptr;//ptr 是表结点
//的指针域，ptr.hp 和 ptr.tp 分别指向表头和表尾
};
}*GList;//广义表类型
/**
algorithm 5.5
*/
int GListDepth(GList L)
{//采用头尾链表存储结构，求广义表 L 深度
if (!L)
{
return ;//空表深度为 1
}
if (L->tag == ATOM)
{
return ;//原子深度为 0
}
int MAX = ;
for (GList pp = L; pp; pp = pp->ptr.tp)
{
int t = GListDepth(pp->ptr.hp);//求以 ptr.hp 为头指针的子表深度
MAX = MAX>t?MAX:t;
}
return MAX+;
}
/**
algorithm 5.8
*/
Status sever(SString &str, SString &hstr)
{//将非空串 str 分割成两部分：hsub为第一个','之前的字串，str 为之后的子串
int n = StrLength(str);
int i = , k = ;//k 记尚未配对的左括号的个数
char ch;
SString CH;
do{
++i;
SubString(CH, str, i, );
ch = CH[];
if ('(' == ch)
{
++k;
}
else if (')' == ch){
--k;
}
}while (i < n && (',' != ch || != k));
if (i < n)
{
SubString(hstr, str, , i-);
SubString(str, str, i+, n-i);
}
else
{
StrCopy(hstr, str);
ClearString(str);
}
} /**
algorithm 5.7
*/
Status CreateGList(GList &L, SString S)
{//采用头尾链表存储结构，由广义表的书写形式串 S 创建广义表 L,设emp="()"
GList q = NULL, p = NULL;
SString emp = { , '(', ')', '\0'};
SString sub, hsub;
if ( == StrCompare(S, emp))
{//创建空表
L = NULL;
}
else
{
if (!(L = (GList)malloc(sizeof(GLNode))))
{
exit(OVERFLOW);//建表结点
}
if ( == StrLength(S))
{//创建单原子广义表
L->tag = ATOM;
L->atom = S[];
}
else
{
L->tag = LIST;
p = L;
SubString(sub, S, , StrLength(S)-);
do{//重复建 n 个子表
sever(sub, hsub);//从 sub 中分离出表头串 hsub
CreateGList(p->ptr.hp, hsub);
q = p;
if (!StrEmpty(sub))
{//表尾不空
if (!(p = (GList)malloc(sizeof(GLNode))))
{
exit(OVERFLOW);
}
p->tag = LIST;
q->ptr.tp = p;
}//if
}while (!StrEmpty(sub));
q->ptr.tp = NULL;
}//else
}
}
/**
algorithm 5.6
*/
Status CopyGList(GList &T, GList L)
{//采用头尾链表存储结构，由广义表 L 复制得到广义表 T
if (!L)
{
T = NULL;
}
else
{
if (!(T = (GList)malloc(sizeof(GLNode))))
{
exit(OVERFLOW);
}
T->tag = L->tag;
if (ATOM == L->tag)
{
T->atom = L->atom;
}
else
{
CopyGList(T->ptr.hp, L->ptr.hp);
CopyGList(T->ptr.tp, L->ptr.tp);
}
}
return OK;
} /**
my code
*/
int cnt = ;
void PrintGList(GList L)
{
if (NULL == L)
{
printf("()");
}
else
{
if (ATOM == L->tag)
{
printf("%c", L->atom);
}
else
{
if (NULL == L->ptr.hp)
{
printf("(");
}
if (NULL != L->ptr.hp && LIST == L->ptr.hp->tag)
{
printf("(");
}
PrintGList(L->ptr.hp);
if (NULL != L->ptr.tp && LIST == L->ptr.tp->tag)
{
printf(",");
}
if (NULL == L->ptr.tp)
{
printf(")");
}
else
{
PrintGList(L->ptr.tp);
} }
}
}
5_5.h
三.CPP文件
#include "5_5.h"
int main(int argc, char const *argv[])
{
// freopen("out.txt", "w", stdout);
//test function sever SString s, t;
scanf("%s", s+);
s[] = StrLength(s);
sever(s, t);
printf("t:%s\n", t+);
printf("s:%s\n", s+); GList L = NULL, T = NULL;
SString S;
scanf("%s", S+);
S[] = StrLength(S);
printf("len: %d\n", S[]);
CreateGList(L, S);
printf("\nL--Depth\t%d\n", GListDepth(L));
CopyGList(T, L);
printf("\nT--Depth\t%d\n", GListDepth(T));
printf("T:\t");
PrintGList(T);
printf("\n");
return ;
}
5_5.cpp
四.测试
测试用例是书上的一个例子，其结构图及对应二叉树如下
最新文章
- Data组件的JSON数据格式
- cookie导读，理解什么是cookie
- AngularJS - 路由入门
- poj2763 树链剖分（线段树）
- JS-面向对象-封装
- 常见的appbug（转）
- android:clipToPadding和android:clipChildren
- Flex4/Flash开发在线音乐播放器 , 含演示地址
- jquery简单的图片切换效果，支持pc端、移动端的banner图片切换开发
- Android--------使用gson解析json文件
- Android Framework------之PowerManagerService的功能
- UVA 11090 - Going in Cycle!!（Bellman-Ford）
- Codeforces Round #434 (Div. 2, based on Technocup 2018 Elimination Round 1)&&Codeforces 861C Did you mean...【字符串枚举，暴力】
- 提示让IE8以下版本的浏览器去更新浏览器
- Dynamics AX 2012 性能优化之 SQL Server 复制
- js实现鼠标拖动框选元素小狗
- Android 高级 Jackson Marshalling（serialize）/Unmarshalling（deserialize）
- 用深度学习LSTM炒股：对冲基金案例分析
- Android制作曲线、柱状图、饼形等图表——使用AChartEngine
- C++设计模式实现--模板(Template)模式