数据结构C语言实现8.广义表

引言

数组是一个数据元素的集合,元素之间具有线性关系,但是,元素可以参与多个线性关系(前面讲的都是参与一个);
广义表是一个数据元素的集合,元素之间具有线性关系,但其前驱后继可以是一般元素,也可以是一个表。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
也可以说广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。但如果广义表的每个元素都是原子，它就变成了线性表。

一、广义表的定义

广义表一般记作 LS = (a1, a2, ···, an),

n是广义表的_ 长度 _。ai可以是单个元素(原子)，也可以是广义表(子表)，
LS是广义表的名字，通常广义表的_ 名字 _ 用大写字母表示。_ 单元素_一般用小写字母表示.
当广义表非空时，称第一个元素a1为LS的 _ 表头 ，称其余元素组成的表为LS的 表尾 _。注意：表头是元素(可以是原子，也可以是广表)，表尾一定是广义表。
例：
((a),a)的表头是(a)，表尾是(a)，
((a))的表头是(a)，表尾是( )。
_ 深度 _:简单说就是表的嵌套层次,定义为:

LS = ( dl , d2 ,... ,dn )
depth ( LS ) =max{depth(dl), depth(d2),... ,depth(dn) } + l
                   0 di 是单元素
depth ( di ) =  {  
                   l  di 是空表

5.举例说明：(长度、单元素、子表、表头、深度)
A = ( ) ; A空表,表长为0,深度1;
B = (e) ; B中只有一个元素e,表长为1,表头:e ,表尾 ( ),深度1;
C = (a,(b,c,d)); C的表长为2,两个元素分别为 a 和子表,表头:a, 表尾 ((b,c,d)),深度2;
D = (A,B,C) ; D 的表长为3,它的三个元素 A,B,C 广义表;表头:A 表尾 (B,C),深度3;
depth(D)=max{1,1,2}+1
E=(a, E); E是一个递归的表。
F=(( ),(e),(a,(b,c,d))); F是多层次的广义表，长度为3，深度为3。

二、广义表的数据结构定义

gen_list.h

#ifndef _GEN_LIST_H_
#define _GEN_LIST_H

#define  MATCH        (0)
#define  NOT_MATCH    (1)

#include "tools.h"

typedef enum
{
    HEAD = 0, //子表类型（头结点）
    INT,      //整型类型
    CHARACTER,//字符类型
    LIST      //子表类型
}Node_type;

//
typedef struct Gen_node
{
    //1.标志（类型） int, char, list, head
    Node_type n_type;
    //2.实际存储的值
    union {
        int         int_value;
        char       char_value;
        int         head_flag;
        struct Gen_node *head;
    }value;
    //3.next指针
    struct Gen_node     *next;
}Gen_node;

typedef struct Gen_node *Gen_list;

//接口：
//1.广义表的创建
Gen_list init_genlist(char *input_str);
//2.广义表的销毁
void destroy_genlist(Gen_list *gen_list);
//3.广义表元素个数
int get_genlist_count(Gen_list gen_list);
//4.广义表深度
int get_genlist_depth(Gen_list gen_list);
//5.广义表的拷贝
Gen_list copy_genlist(Gen_list gen_list);
//6.显示广义表信息
void show_genlist(Gen_list gen_list);

#endif

三、广义表的接口实现

gen_list.c

#include <stdio.h>
#include <strings.h>
#include <ctype.h>

#include "gen_list.h"
#include "tools.h"

//非使用者接口操作函数声明

Boolean is_input_empty(char *string);                         // 1. 判断输入串为空
Boolean is_braket_match(char *string);                        // 2. 检测括号是否匹配

char *delete_blank(char *string);                             // 3. 删除字符串中的空格
void delete_braket(char *src_str, char *des_str, int strlen); // 4. 删除字符串两边的括号
void get_item(char *sub_str, char *item_str);                 // 5. 获取当前条目

Gen_node *create_node(void);                                  // 6. 创建空节点
Gen_node *create_head_node(int head_flag);                    // 7. 创建头节点
Gen_node *create_int_node(int head_flag);                     // 8. 创建int型节点
Gen_node *create_char_node(const char character);             // 9. 创建字符节点
Gen_node *create_list_node(Gen_node *p_list);                 //10. 创建子表节点
Gen_list create_genlist(char *string);                        //11. 通过字符串构造广义表


void show_genlist_value(Gen_list gen_list);                   //12. 显示广义表

//非使用者接口函数实现

// 1. 判断输入串为空
Boolean is_input_empty(char *string)
{
    return strlen(string) == ZERO || strcmp(string, "()") == ZERO;
}

// 2. 检测括号是否匹配
Boolean is_braket_match(char *string)
{
    int flag = MATCH;
    int i = 1;

    if(string[0] != '(')
    {
         return NOT_MATCH;
    } 
    flag ++;

    while(string[i] != '\0')
    {
        if(string[i] == '(')
        {
            flag ++;
        }
        else if(string[i] == ')')
        {
            flag --;
        }
        if(flag == MATCH && string[i+1] != '\0')
        {
            return NOT_MATCH;
        }
        i ++;
    } 
 
    return flag == MATCH ? MATCH : NOT_MATCH ;
}

// 3. 删除字符串中的空格
char *delete_blank(char *string)
{
    int i = 0;
    int j = 0;

    if(string == NULL)
    {
        return string;
    }
    while(string[j] = string[i])
    {
        if(isblank(string[i]))
        {
            i++;
            continue;
        }
        i++;
        j++;
    }
    return string;
}


// 4. 删除字符串两边的括号
void delete_braket(char *src_str, char *des_str, int strlen)
{
    strncpy(des_str, src_str + 1, strlen -2 );
    des_str[strlen -2 ] = '\0';
}

// 5. 获取当前条目
void get_item(char *sub_str, char *item_str)
{
    int i = 0;
    int flag = 0;
    int sub_len = strlen(sub_str);

    while(i < sub_len)
    {
        if(sub_str[i] == '(')
        {
            flag++;
        }
        if(sub_str[i] == ')')
        {
            flag--;
        }
        if(flag == 0 && sub_str[i] == ',')
        {
            break;
        }
        i ++;
    }

    if(i == sub_len) //只有一个元素
    {
        strcpy(item_str, sub_str);
        sub_str[0]= '\0';
    }
    else              //把当前元素复制给item_str, 并在原列表删除所复制的元素
    {
        strncpy(item_str, sub_str, i);
        item_str[i] = '\0';
        strcpy(sub_str, sub_str + i +1);
    }
}


// 6. 创建空节点
Gen_node *create_node(void)
{
    Gen_node *result = (Gen_node *)Malloc(sizeof(Gen_node));
    bzero(result, sizeof(Gen_node));

    return result;
}

// 7. 创建头节点
Gen_node *create_head_node(int head_flag)
{
    Gen_node *node = create_node();
    node->n_type = HEAD;
    node->value.head_flag = head_flag;

    return node;
}

// 8. 创建int型节点
Gen_node *create_int_node(int int_value)
{
    Gen_node *node = create_node();
    node->n_type = INT;
    node->value.int_value = int_value;

    return node;
}
// 9. 创建字符节点
Gen_node *create_char_node(const char character)
{
    Gen_node *node = create_node();
    node->n_type = CHARACTER;
    node->value.char_value = character;

    return node;
}
//10. 创建子表节点
Gen_node *create_list_node(Gen_node *p_list)
{
    Gen_node *node = create_node();
    node->n_type = LIST;
    node->value.head = p_list;

    return node;
}

//11. 通过字符串构造广义表
Gen_list create_genlist(char *string)
{
    char *sub_str = NULL;
    char *item_str = NULL;
    int str_len = strlen(string);
    Gen_node *p_node = NULL;

    if(is_input_empty(string) == TRUE)
    {
        fprintf(stderr, "input illegal!\n");
        return NULL;
    }
    
    Gen_list start = create_head_node(1);
    p_node = start;

    sub_str = (char *)Malloc(sizeof(char) * str_len);
    item_str = (char *)Malloc(sizeof(char) * str_len);

    //1.去掉外层括号
    delete_braket(string, sub_str, str_len);
    //2.通过逗号分割广义表元素
    while(strlen(sub_str))
    {
        get_item(sub_str, item_str);
        //3.根据元素类型构造节点（遇到子表递归调用）
        if(item_str[0] != '(' && item_str[0] != '\'')
        {
            p_node->next = create_int_node(atoi(item_str));
        }      
        else if(item_str[0] != '(' && item_str[0] == '\'')
        {
            p_node->next = create_char_node(item_str[1]);
        }      
        else
        {
            p_node->next = create_list_node(create_genlist(item_str));
        }
        p_node = p_node->next;
    }

    free(sub_str);
    free(item_str);

    return start;
}
//12. 显示广义表
void show_genlist_value(Gen_list gen_list)
{
    Gen_node *p_node = NULL;

    if(gen_list == NULL)
    {
    //  printf("NULL\n");
        return ;
    }
    printf("(");
    p_node = gen_list->next;

    while(p_node != NULL)
    {
        if(p_node->n_type == INT)
        {
            printf("%d", p_node->value.int_value);
        }
        else if(p_node->n_type == CHARACTER)
        {
            printf("'%c'", p_node->value.char_value);
        }
        else
        {
            show_genlist_value(p_node->value.head);
        }
        if(p_node->next != NULL)
        {
            printf(",");
        }
        p_node = p_node->next;
    }
    printf(")");
}

//广义表接口实现：
//1.广义表的创建
Gen_list init_genlist(char *input_str)
{
    //判断字符串条件
    if(input_str == NULL || is_input_empty(input_str) == TRUE
    || is_braket_match(input_str) == NOT_MATCH)
    {
        return NULL;
    }
    //删除空格
    delete_blank(input_str);
    //
    //字符串构建广义表
    return create_genlist(input_str);
}

//2.广义表的销毁
void destroy_genlist(Gen_list *gen_list)
{
    Gen_node *p_node = NULL;
    if(gen_list == NULL || *gen_list == NULL)
    {
        return ;
    }

    p_node = *gen_list;
    while(p_node != NULL)
    {
        *gen_list = p_node->next;
        if(p_node->n_type == LIST)
        {
            destroy_genlist(&(p_node->value.head));
        }
        free(p_node);
        p_node = *gen_list;
    }
}
//3.广义表元素个数
int get_genlist_count(Gen_list gen_list)
{
    int count = 0;
    Gen_node *p_node = NULL;

    if(gen_list == NULL)
    {
        return -1;
    }
    p_node = gen_list->next;

    while(p_node != NULL)
    {
        if(p_node->n_type == INT)
        {
            count ++;
        }
        else if(p_node->n_type == CHARACTER)
        {
            count ++;
        }
        else
        {
            count += get_genlist_count(p_node->value.head);
        }
        p_node = p_node->next;
    }
    return count;
}
//4.广义表深度
int get_genlist_depth(Gen_list gen_list)
{
    int count = 0;
    Gen_node *p_node = NULL;

    if(gen_list == NULL)
    {
        return -1;
    }
    p_node = gen_list->next;

    while(p_node != NULL)
    {
        if(p_node->n_type == LIST)
        {
            count += get_genlist_depth(p_node->value.head);
        }
        p_node = p_node->next;
    }
    count++;
    return count;
}
//5.广义表的拷贝
Gen_list copy_genlist(Gen_list gen_list)
{
    Gen_node *p_node = NULL;
    Gen_node *q_node = NULL;
    Gen_list new_list = (Gen_list)Malloc(sizeof(gen_list));
    bzero(new_list, sizeof(gen_list));

    if(gen_list == NULL)
    {
      printf("NULL\n");
        return NULL;
    }
    p_node = gen_list->next;
    q_node = new_list;

    while(p_node != NULL)
    {
        if(p_node->n_type == INT)
        {
            q_node->next = create_int_node(p_node->value.int_value);
        }
        else if(p_node->n_type == CHARACTER)
        {
            q_node->next = create_char_node(p_node->value.char_value);
        }
        else
        {
            q_node->next = create_list_node(p_node->value.head);
        }
        p_node = p_node->next;
        q_node = q_node->next;
    }
    q_node = NULL;

    return new_list;
}
//6.显示广义表信息

void show_genlist(Gen_list gen_list)
{
    show_genlist_value(gen_list);
    printf("\n");
}

四、代码功能测试

目录结构：

.
├── gen_list
├── gen_list.c
├── gen_list.h
├── main.c
├── tools.c
└── tools.h

0 directories, 7 files

测试代码：

main.c

#include <stdio.h>
#include <stdlib.h>
#include "gen_list.h"

int main(int argc, char **argv)
{
    Gen_list list = NULL;
    Gen_list new_list = NULL;

    char str[] = "(15, 'c', (20, 'd', (30, 'f')), ('g', 'i'), 60)";

    list = init_genlist(str);
  
    show_genlist(list);    //显示广义表信息

    printf("%d\n",get_genlist_count(list));
    printf("%d\n",get_genlist_depth(list));

    new_list = copy_genlist(list);
    show_genlist(new_list);    //显示广义表信息
    destroy_genlist(&list);   //广义表的销毁
    return 0;
}

//(15, 'c', (20, 'd', (30, 'f')), ('g', 'i'), 60)

测试结果：

root@aemonair:~# cc.sh *.c
Compiling ...
-e CC      gen_list.c main.c tools.c -g -lpthread
-e         Completed .
-e         Sat Jun 25 00:55:16 CST 2016

root@aemonair:~# ./gen_list 
(15,'c',(20,'d',(30,'f')),('g','i'),60)
9
4
(15,'c',(20,'d',(30,'f')),('g','i'),60)

总结

至此，我们学习到了一种叫做广义表的数据结构，并且进行了操作接口的实现。
1.广义表是数据元素的有限序列，可以是单个元素，也可以是广义表。
2.一对表头和表尾可唯一确定广义表。
3.我们采用了链式存储结构，而且我们的节点可以是多种类型，或者是广义表节点。

文章作者: Air

文章链接: http://aemonair.github.io/2016/06/25/Data_Structure_08_General_List/

DataStruct