【实例】复制广义表

程序员文章站 2022-05-01 11:02:18

...

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

广义表的存储结构分为：

头链和尾链存储结构
原子和子表存储结构

本文核心代码块：

注意：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 &lt; n; i++)           //搜索最外一层的第一个逗号
{
    if (str[i] == ','&amp;&amp; tag == 1)  // ==1表示遍历到的左括号多一个，即最外层第一个逗号
        break;
    if (str[i] == '(')
        tag++;
    if (str[i] == ')')
        tag--;
}//搜索到之后，i就是第一个逗号的下标值

//如果表尾部分非空
if (i &lt; n&amp;&amp;str[i] == ',')
{
    for (j = 0; j &lt; i - 1; j++)    //表头字符串，在第一个逗号之前，即i-1
        hstr[j] = str[j + 1];
    hstr[j] = '\0';               //表头结束
    if (str[i] == ',')
    i++;                          //i越过第一个逗号
    str[0] = '(';
    for (j = 1; i &lt; 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

【实例】复制广义表

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

广义表的存储结构分为：

本文核心代码块：

实现过程：

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

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

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

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

完整测试代码如下：

测试结果：

mysql更新一个表里的字段等于另一个表某字段的值实例

利用Bootstrap实现漂亮简洁的CSS3价格表实例源码

SQLSERVER查询锁表，阻塞，使用表名查询存储过程，行数，表字段类型等常规查询实例讲解

SQL联结表实例讲解

Java 复制Excel工作表

MySQL单表查询操作实例详解【语法、约束、分组、聚合、过滤、排序等】

详解MySQL导出指定表中的数据的实例

C++类的相关问题、构造函数与析构函数、复制构造函数实例讲解

C#实现单链表(线性表)完整实例

C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)