2.广义表

第一章 自测&关键词回顾

广义表概念: 青岛大学-数据结构
广义表实现: link
C语言基础联合体: 视频

第二章 手撕

①其实还有一种用类似”树形”的实现方式, 原理差不多; ②我实现的比较偏应试,没有具体操作广义表的节点的函数实现

• generalList.h
• generalList.c
• test.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef char DataType;

typedef struct GeneralListNode {
    int tag;  //  1表示字表节点; 0表示元素节点
    union {
        DataType data;
        struct GeneralListNode *subList;
    };
    struct GeneralListNode *next;
} GeneralListNode;

// 初始化
void initGeneralList(GeneralListNode **glist);
// 遍历
void traverseGeneralList(GeneralListNode *glist);

// 获取广义表长度(元素个数)
int getLength(GeneralListNode *glist);
// 获取广义表的深度
int getDepth(GeneralListNode *glist);
// 获取广义表的表头
GeneralListNode *getHead(GeneralListNode *glist);
// 获取广义表的表尾
GeneralListNode *getTail(GeneralListNode *glist);

#include "generalList.h"

// 初始化
void initGeneralList(GeneralListNode **glist) {
    char input;
    scanf("%c", &input);
    if (input == '(') {  // 说明是一个表节点
        GeneralListNode *newNode = (GeneralListNode *)malloc(sizeof(GeneralListNode));
        newNode->tag = 1;
        // TODO
        initGeneralList(&(newNode->subList));
        initGeneralList(&(newNode->next));
        *glist = newNode;
    } else if (input == ',') {
        initGeneralList(glist);
    } else if (input == ')' || input == '\n') {
        *glist = NULL;
    } else {  // 是元素(原子)
        GeneralListNode *newNode = (GeneralListNode *)malloc(sizeof(GeneralListNode));
        newNode->tag = 0;
        newNode->data = input;
        initGeneralList(&(newNode->next));
        *glist = newNode;
    }
}
// 遍历
void traverseGeneralList(GeneralListNode *glist) {
    if (glist == NULL) {
        printf("不存在该表");
        return;
    }
    if (glist->tag == 1) {
        printf("(");
        traverseGeneralList(glist->subList);
        printf(")");
    } else {
        if (glist->data == '#')
            printf("");
        else
            printf("%c", glist->data);
    }

    if (glist->next != NULL) {
        printf(",");
        traverseGeneralList(glist->next);
    }
}

// 获取广义表长度(元素个数)
int getLength(GeneralListNode *glist) {
    int len = 0;
    GeneralListNode *ghead = glist->subList;
    // 空表
    if (ghead->tag == 0 && ghead->data == '#')
        return len;
    // 长度至少为1 or 至少有一个元素
    else {
        while (ghead) {
            len++;
            ghead = ghead->next;
        }
        return len;
    }
}

/**
 * 获取广义表的深度
 * 广义表深度的定义: 空表的深度为1, 原子(元素)的深度为0
 * 考试就 数左括号, 数到第一个右括号为止
 */
int getDepth(GeneralListNode *glist) {
    if (glist->tag == 0 && glist->next == NULL)
        return 0;
    else {
        int p1 = glist->next != NULL ? getDepth(glist->next) : 0;
        // 只有tag为1才有子表; 不能判断这个glist->subList != NULL, 有坑哈
        int p2 = glist->tag == 1 ? getDepth(glist->subList) : 0;
        return glist->tag + MAX(p1, p2);  // 只有表才会多送1层; 节点是不能送1层(否则会凭空多一层)
    }
}
// 获取广义表的表头
GeneralListNode *getHead(GeneralListNode *glist) {
    GeneralListNode *ghead = glist->subList;
    // 空广义表,没有表头
    if (ghead->tag == 0 && ghead->data == '#')
        return NULL;
    GeneralListNode *resGHead = (GeneralListNode *)malloc(sizeof(GeneralListNode));
    resGHead->tag = ghead->tag;
    resGHead->next = NULL;
    if (resGHead->tag)
        resGHead->subList = ghead->subList;
    else
        resGHead->data = ghead->data;
    return resGHead;
}
// 获取广义表的表尾
GeneralListNode *getTail(GeneralListNode *glist) {
    GeneralListNode *ghead = glist->subList;
    // 空广义表,没有表头
    if (ghead->tag == 0 && ghead->data == '#')
        return NULL;

    // 表尾一定是一个表
    GeneralListNode *newGList = (GeneralListNode *)malloc(sizeof(GeneralListNode));
    newGList->tag = 1;
    newGList->next = NULL;

    GeneralListNode *tailGList = ghead->next;  // 假"表尾"
    // 说明是表尾是一个空表
    if (tailGList == NULL) {
        tailGList = (GeneralListNode *)malloc(sizeof(GeneralListNode));
        tailGList->tag = 0;
        tailGList->data = '#';  // #表示空表
        tailGList->next = NULL;
    }
    newGList->subList = tailGList;  // 封装为一个表
    return newGList;
}

#include "generalList.h"

void test01(void) {
    // A = (a,(b,c),y)
    // B = (((a,b,(#),c),d),e,((f),g))
    GeneralListNode *glist = (GeneralListNode *)malloc(sizeof(GeneralListNode));
    initGeneralList(&glist);

    traverseGeneralList(glist);
    printf("\n");
    printf("Length: %d\n", getLength(glist));
    printf("Depth: %d\n", getDepth(glist));
    GeneralListNode *ghead = getHead(glist);

    printf("Head: ");
    if (ghead == NULL)  // 不存在
        printf("不存在");
    else if (ghead->tag == 0)  //  是一个元素(原子)
        printf("%c", ghead->data);
    else  // 是一个字表
        traverseGeneralList(ghead);

    printf("\n");

    GeneralListNode *gtail = getTail(glist);
    printf("Tail: ");
    if (gtail == NULL)  // 不存在
        printf("不存在");
    else
        traverseGeneralList(gtail);
    printf("\n");
}

void linkModifyTest() {
    GeneralListNode *glist = (GeneralListNode *)malloc(sizeof(GeneralListNode));
    initGeneralList(&glist); // (((a,b,(#),c),d),e,((f),g))
    traverseGeneralList(glist);
    puts("");

    // ((a,b,(#),c),d)
    // (a,b,(#),c)
    // (b,(#),c)
    // ((#),c)
    // ()
    // GeneralListNode* ans = getTail(getTail(getHead(getHead(glist))));
    // 不存在该表
    GeneralListNode* ans = getHead(getHead(getTail(getTail(getHead(getHead(glist))))));
    traverseGeneralList(ans);
}

int main() {
    // test01();
    linkModifyTest();
    return 0;
}

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用