MENU

广义表的基本操作

• November 12, 2020 • 广义表

广义表的基本操作


在我刚刚接触数据结构这门课时,书上面就有示例代码,前两章线性表还好,因为都是学习C语言的时候接触过的内容,从书上过一遍内容自己试着可以把代码敲出来,但是从广义表这一章节开始,概念多了,代码就开始变得风骚起来了,只有先敲会书上的示例代码从第一步开始,才能更好的理解各种概念,把书上的理论知识和实际代码连接起来,能融会贯通,就可以旅行千里啦

在做题之前,我特别写了这一篇关于广义表的基础操作,注释帮助大家更好的理解书上的代码,跟着我敲一敲,不要只复制粘贴哦,有基础者请绕过此文,直接去搞题吧


注:本文以一个例子来演示广义表的基本操作,含有一个头文件《GList.h》和一个测试源文件《main.cpp》

  1. 根据广义表字符串(((a,b,c),(d)),e)分解表头字符串、表尾字符串
  2. 根据分解好的字符串创建广义表
  3. 求深度
  4. 求长度
  5. 查找原子个数
  6. 撤销广义表

《GList.h》:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char DataType;
//头链和尾链存储结构下的结点结构体
typedef struct GListNode
{
    int tag;    //当tag为0的时候,这个结点保存的是一个原子,当为1的时候,这个结点保存的是一个子广义表
    union {
        DataType atom; //原子域
        struct
        {
            struct GListNode *head;//头链
            struct GListNode *tail;//尾链
        }subList;
    }val;
}GLNode;
/*字符串复制函数,将str2的前n个字符复制到str1中*/
void strcpySelf(char str1[], char str2[], int n)
{
    if (strlen(str1) <= n || strlen(str2) <= n)       //防止出错
        return;
    int i;
    for (i = 0; i < n; i++)
        str1[i] = str2[i];
    str1[i] = '\0';            //添加字符串结束符
}
/*把表示广义表的字符串str分解成表头字符串hstr和表尾字符串str*/
void DecomposeStr(char str[], char hstr[])
{
    int i, j, tag, n = strlen(str);
    char ch;
    ch = str[0];
    tag = 0;
    /*搜索最外层的第一个逗号*/
    for (i = 0; i <= n - 1; i++)
    {
        if (str[i] == ','&&tag == 1)   //检测到第一个逗号,退出
            break;
        ch = str[i];
        if (ch == '(') //防止第一个逗号之前有多个层叠广义表,比如像这样的广义表((a,b,(c)),d,e),我们要找的是c后面的那个逗号,而不是a后面的
            tag++;
        if (ch == ')')
            tag--;
    }
    /*表尾部分非空*/
    if (i <= n - 1 && str[i] == ',')
    {
        /*取表头字符串*/
        for (j = 0; j < i - 1; j++)
            hstr[j] = str[j + 1];      //str[0]是'(',所以跳过
        hstr[j] = '\0';                //添加结束符
        if (str[i] == ',')
            i++;
        /*取表尾字符串*/
        str[0] = '(';                  //表尾一定是一个广义表,所以第一个字符是'('
        for (j = 1; i <= n - 2; i++,j++)
            str[j] = str[i];
        str[j] = ')';
        str[++j] = '\0';
    }
    else
    {
        str++;                        //跳过最左边的‘(’
        /*取表头部分*/
        strcpySelf(hstr, str,n-2);   //不复制最右边的')'
        hstr[n - 2] = '\0';
        str--;                        //恢复字符串指针位置
        /*取表尾部分*/
        strcpy(str,"()");
    }
}
/*创建广义表*/
GLNode *CreatGList(char str[])
{
    GLNode *h;
    char hstr[200];         //存放表头
    int len = strlen(str);
    if (strcmp(str, "()") == 0) //是空表
        h = NULL;
    else if(len==1)             //是原子
    {
        h = (GLNode *)malloc(sizeof(GLNode));
        h->tag = 0;
        h->val.atom = str[0];   //字符赋给原子域
    }
    else {                      //是子表
        h = (GLNode *)malloc(sizeof(GLNode));
        h->tag = 1;
        /*把字符串分解成表头和表尾*/
        DecomposeStr(str, hstr);
        h->val.subList.head = CreatGList(hstr);     //根据分解得到的表头创建广义表,循环调用自身,即递归
        if (strcmp(str, "()") != 0)                 //若表尾不是空表
            h->val.subList.tail = CreatGList(str);  //根据分解得到的表尾创建广义表,循环调用自身,即递归
        else
            h->val.subList.tail = NULL;
    }
    return h;
}
/*求广义表的深度,括号层数*/
int GListDepth(GLNode* h)
{
    int max, dep;
    GLNode *pre;
    if (h == NULL)             //递归出口1,递归直到空表
        return 1;
    if (h->tag == 0)           //递归出口2,原子没有深度
        return 0;
    pre = h;
    /*递归求广义表的深度*/
    /*广义表可分成表头和表尾,对表尾链循环,即一层一层的剥开括号*/
    for (max = 0; pre != NULL; pre = pre->val.subList.tail)
    {
        dep = GListDepth(pre->val.subList.head);           //用递归求表头的深度
        if (dep > max)
            max = dep;
    }
    return max + 1;
}
/*求广义表的长度*/
int GlistLength(GLNode* h)
{
    int number = 0;
    GLNode *p;
    for (p = h; p != NULL; p = p->val.subList.tail)
        number++;
    return number;
}
/*求广义表中的原子个数*/
int GListAtomNum(GLNode *h)
{
    if (h == NULL)
        return 0;
    else
    {
        if (h->tag == 0)
            return 1;
        else
            return GListAtomNum(h->val.subList.head) + GListAtomNum(h->val.subList.tail);
    }
}
/*查找原子--回溯*/
GLNode *GListSearch(GLNode *h, DataType x)
{
    GLNode *p;
    if (h == NULL)
        return NULL;
    if (h->tag == 0 && h->val.atom == x) //必须有h->tag == 0这个条件,否则h->val.atom为空的,直接访问会出错
        return h;                        //一层一层深入,直到剩下原子单位
    if (h->tag == 1 && h->val.subList.head != NULL)
    {
        p = GListSearch(h->val.subList.head, x);
        if (p != NULL)
            return p;
    }
    if (h->tag == 1 && h->val.subList.tail != NULL)
    {
        p = GListSearch(h->val.subList.tail, x);
        if (p != NULL)
            return p;
    }
    return NULL;       //原子、头链、尾链都没找到,只能返回NULL
}
/*撤销广义表*/
void DestroyList(GLNode *h)
{
    if (h == NULL)
        return;
    if (h->tag == 1 && h->val.subList.head != NULL)
        DestroyList(h->val.subList.head);
    if (h->tag == 1 && h->val.subList.tail != NULL)
        DestroyList(h->val.subList.tail);
    free(h);
}

《main.cpp》:

#include"GList.h"
int main()
{
    char str1[] = "(((a,b,c),(d)),e)";
    char str2[] = "(((a,b,c),(d)),e)";
    char hstr[100];
    GLNode *h, *p;
    int depth, length, number;//深度、长度、原子个数
    h = CreatGList(str1);     //根据str1创建以h为头指针的广义表
    printf("广义表str1 = %s\n", str2);
    DecomposeStr(str2, hstr); //获取表头和表尾
    printf("表头:= %s\n", hstr);
    printf("表尾:= %s\n", str2);
    depth = GListDepth(h); //求深度
    printf("深度depth = %d\n",depth);
    length = GlistLength(h); //求长度
    printf("长度depth = %d\n", length);
    number = GListAtomNum(h); //求原子个数
    printf("原子个数number = %d\n", number);
    p = GListSearch(h, 'd');  //查找广义表中是否有原子'd'
    if (p != NULL)
        printf("数据元素%c在广义表中\n", p->val.atom);
    else
        DestroyList(h);
    system("pause");
    return 0;
}

运行结果:



代码编译器:Visual Studio 2017
ok

Archives QR Code Tip
QR Code for this page
Tipping QR Code