MENU

复制广义表

• November 12, 2020 • 广义表

设广义表采用头链和尾链存储结构,编写把广义表la复制到另一个广义表的函数


广义表的存储结构分为:

  1. 头链和尾链存储结构
  2. 原子和子表存储结构

本文核心代码块:

注意:Glist为表的指针,GListNode,GLNode为实体
结构体如下:

//复制广义表,l1复制给l2
void copyGList(GList *l2, GList l1)
{
    if (!l1)
        *l2 = NULL;       //复制空表
    else
    {
        *l2 = (GList)malloc(sizeof(GListNode));
        (*l2)->tag = l1->tag;  //复制原子/子表标记位
        if (l1->tag == 0)
            (*l2)->val.atom = l1->val.atom;
        else
        {
            copyGList(&((*l2)->val.sublist.head), l1->val.sublist.head);
            copyGList(&((*l2)->val.sublist.tail), l1->val.sublist.tail);
        }
    }
}

实现过程:

首先我们创建一个广义表,采用头链和尾链存储结构,任何一个广义表都可以分解为表头和表尾,因此创建广义表的时候也可以分解为创建表头广义表和表尾广义表

在此之前我们得到一个字符串,即一个广义表,先把他分成表头(hstr)和表尾(str),分别用字符串表示,代码如下:

//得到字符串形式的表头和表尾
void decomposeStr(char str[], char hstr[])
{
    int n = strlen(str);
    int i, j;
    int tag = 0;  //标记左括号和右括号匹配信息,如果左括号数目等于右括号数目,则遍历到的左右括号数目相等
    for (i = 0; i < n; i++)           //搜索最外一层的第一个逗号
    {
        if (str[i] == ','&& tag == 1)  // ==1表示遍历到的左括号多一个,即最外层第一个逗号
            break;
        if (str[i] == '(')
            tag++;
        if (str[i] == ')')
            tag--;
    }//搜索到之后,i就是第一个逗号的下标值
    //如果表尾部分非空
    if (i < n&&str[i] == ',')
    {
        for (j = 0; j < i - 1; j++)    //表头字符串,在第一个逗号之前,即i-1
            hstr[j] = str[j + 1];
        hstr[j] = '\0';               //表头结束
        if (str[i] == ',')
        i++;                          //i越过第一个逗号
        str[0] = '(';
        for (j = 1; i < n - 1; j++, i++)
            str[j] = str[i];
        str[j] = ')';
        str[++j] = '\0';   //表尾结束
    }
    else            //表尾为空表
    {
        str++;      //略过最外层左括号
        strcpy_s(hstr, n+1, str);       //strcpy_s函数特性,中间参数是原字符串长度加一
        hstr[n - 2] = '\0';
        str--;
        strcpy(str,"()");     //表尾无论在那种情况下都是一种广义表,所以此处用空表
    }
    /*printf("表头:%s\n", hstr);
    printf("表尾:%s\n", str);*/
}

至此我们得到了广义表的表头与表尾,开始创建广义表,利用递归不断地将字符串分割成表头和表尾来创建子表,看代码:

//创建广义表
GListNode *createGList(char str[])
{
    GLNode *head;
    int len = strlen(str);
    if (strcmp(str, "()") == 0)      //是空广义表
        head = NULL;
    else if (len == 1)               //广义表只有一个原子
    {
        head = (GLNode*)malloc(sizeof(GLNode));
        head->tag = 0;
        head->val.atom = str[0];
    }
    else                             //广义表不止一个原子
    {
        head = (GLNode*)malloc(sizeof(GLNode));
        head->tag = 1;
        char hstr[200];
        decomposeStr(str, hstr);     //将广义表分解为表头和表尾
        head->val.sublist.head = createGList(hstr);  //创建表头广义表
        if (strcmp(str, "()") != 0)   //如果表尾广义表不为空,创建表尾广义表
            head->val.sublist.tail = createGList(str);
        else
            head->val.sublist.tail = NULL;
    }
    return head;
}

为了验证是否复制成功,在这里输出目的广义表的长度,深度

完整测试代码如下:

头文件:《GLNode》

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char DataType;
typedef struct GListNode
{
    int tag;     //为1表示原子,0表示子表
    union
    {
        DataType atom;
        struct {
            struct GListNode *head;
            struct GListNode *tail;
        }sublist;
    }val;
}GLNode,*GList;
//得到字符串形式的表头和表尾
void decomposeStr(char str[], char hstr[])
{
    int n = strlen(str);
    int i, j;
    int tag = 0;  //标记左括号和右括号匹配信息,如果左括号数目等于右括号数目,则遍历到的左右括号数目相等
    for (i = 0; i < n; i++)           //搜索最外一层的第一个逗号
    {
        if (str[i] == ','&& tag == 1)  // ==1表示遍历到的左括号多一个,即最外层第一个逗号
            break;
        if (str[i] == '(')
            tag++;
        if (str[i] == ')')
            tag--;
    }//搜索到之后,i就是第一个逗号的下标值
    //如果表尾部分非空
    if (i < n&&str[i] == ',')
    {
        for (j = 0; j < i - 1; j++)    //表头字符串,在第一个逗号之前,即i-1
            hstr[j] = str[j + 1];
        hstr[j] = '\0';               //表头结束
        if (str[i] == ',')
        i++;                          //i越过第一个逗号
        str[0] = '(';
        for (j = 1; i < n - 1; j++, i++)
            str[j] = str[i];
        str[j] = ')';
        str[++j] = '\0';   //表尾结束
    }
    else            //表尾为空表
    {
        str++;      //略过最外层左括号
        strcpy_s(hstr, n+1, str);       //strcpy函数特性,中间参数是原字符串长度加一
        hstr[n - 2] = '\0';
        str--;
        strcpy(str,"()");     //表尾无论在那种情况下都是一种广义表,所以此处用空表
    }
    /*printf("表头:%s\n", hstr);
    printf("表尾:%s\n", str);*/
}
//创建广义表
GListNode *createGList(char str[])
{
    GLNode *head;
    int len = strlen(str);
    if (strcmp(str, "()") == 0)      //是空广义表
        head = NULL;
    else if (len == 1)               //广义表只有一个原子
    {
        head = (GLNode*)malloc(sizeof(GLNode));
        head->tag = 0;
        head->val.atom = str[0];
    }
    else                             //广义表不止一个原子
    {
        head = (GLNode*)malloc(sizeof(GLNode));
        head->tag = 1;
        char hstr[200];
        decomposeStr(str, hstr);     //将广义表分解为表头和表尾
        head->val.sublist.head = createGList(hstr);  //创建表头广义表
        if (strcmp(str, "()") != 0)   //如果表尾广义表不为空,创建表尾广义表
            head->val.sublist.tail = createGList(str);
        else
            head->val.sublist.tail = NULL;
    }
    return head;
}
//复制广义表,l1复制给l2
void copyGList(GList *l2, GList l1)
{
    if (!l1)
        *l2 = NULL;       //复制空表
    else
    {
        *l2 = (GList)malloc(sizeof(GListNode));
        (*l2)->tag = l1->tag;  //复制原子/子表标记位
        if (l1->tag == 0)
            (*l2)->val.atom = l1->val.atom;
        else
        {
            copyGList(&((*l2)->val.sublist.head), l1->val.sublist.head);
            copyGList(&((*l2)->val.sublist.tail), l1->val.sublist.tail);
        }
    }
}
//广义表的深度——对表尾循环,一层一层拆开
int GListDepth(GListNode *head)
{
    GListNode *p = head;
    //两个递归出口
    if (head == NULL)      //空表深度为1
        return 1;
    if (head->tag == 0)    //原子深度
        return 0;
    int max;
    for (max = 0; p != NULL;p = p->val.sublist.tail)
    {
        int dep = GListDepth(p->val.sublist.head);
        if (dep > max)
            max = dep;
    }
    return max + 1;
}
//广义表的长度
int GListLength(GListNode *head)
{
    if (head == NULL)
        return 0;
    int number = 0;
    GLNode *p = head;
    while (p != NULL)
    {
        number++;
        p = p->val.sublist.tail;   //一层一层剥开表尾
    }
    return number;
}

主函数:《main.c》

int main()
{
    char str[200];
    gets_s(str);
    char brr[200];
    printf("原广义表:%s\n", str);
    GListNode *h1;
    h1 = createGList(str);
    GListNode *h2 = (GListNode*)malloc(sizeof(GListNode));
    copyGList(&h2,h1);
    printf("\nh2 的深度为:%d\n", GListDepth(h2));
    printf("h2 的长度为:%d\n", GListLength(h2));
    system("pause");
    return 0;
}

代码结束



测试结果:

测试一


测试二


代码编译器:Visual Studio 2017
ok

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