广义表操作 (Java实现)——广义表深度、广义表长度、打印广义表信息

2021年6月19日 1点热度 0条评论 来源: sun_star1chen

广义表是对线性表的扩展——线性表存储的所有的数据都是原子的(一个数或者不可分割的结构),且所有的数据类型相同。而广义表是允许线性表容纳自身结构的数据结构。

广义表定义

      广义表是由n个元素组成的序列:LS = (a1,a2, ... an);其中 ai是一个原子项或者是一个广义表。n是广义表的长度。若ai是广义表,则称为LS的子表。

广义表表头和表尾:  若广义表LS不空,则a1,称为LS的表头,其余元素组成的子表称为表尾。

广义表的长度: 若广义表不空,则广义表所包含的元素的个数,叫广义表的长度。

广义表的深度: 广义表中括号的最大层数叫广义表的深度。

例如:

对广义表LS=((),a,b,(a,b,c),(a,(a,b),c))

表头为子表LSH = ();

表尾为子表LST = (a,b,(a,b,c),(a,(a,b),c));

广义表LS的长度:5

广义表LS的深度:3

对于广义表的操作都是建立在已经构建好的广义表上,那么如何通过一个广义表字符串构造一个广义表?

广义表的存储结构——广义表有多重存储结构,以下只讲代码中使用的存储结构,代码中采用以下存储结构:

tag data pH pT

tag    :tag == 0 ; 表示该节点为原子节点 。tag == 1 ; 表示该节点为表节点

data  :data是原子节点的数据,为表节点时该值域无效。

pH    :广义表的表头——是一个表节点或原子节点。

pT    :广义表的表尾——必定是一个表节点 或者 null。

表节点存储结构选择好了,那么如何来构造广义表呢?(比如:LS = ((),a,b,(a,b,c),(a,(a,b),c))), 根据以下规则,构造出来的广义表如下图:

header表示表头 , 带圈的指针表示由该符号创建的对应的节点(为了图片清晰有些节点没有画)。

对于一个广义表总有一个header节点指向该表的表节点,一个node表示当前正在操作的节点。

当遇到‘(’ 时构造一个表节点,并且将该符号压栈charStack,如果栈中的数据长度 > 1 , 表明广义表的深度加深一层 ,此时将该节点压入栈nodeStack,并且让node的pH节点指向新构造的节点。其代码如下:

if (ts.charAt(i) == mStartSymb) {
                tmpNode = new Node(null, null, TAG_TABLE, null);
                // tableNode = tableNode.mPt;
                symbStack.push(ts.charAt(i));
                if (symbStack.size() > 1) {
                    nodeStck.push(tableNode);
                    tableNode.mPh = tmpNode;
                    tableNode = tableNode.mPh;
                } else {
                    tableNode.mPt = tmpNode;
                    tableNode = tableNode.mPt;
                }
            } 

其中mStartSymb 表示广义表的 '表起始指示符' , 
symbStack.push(ts.charAt(i));将 '表起始指示符压栈' , 接下来判断symbStack栈的大小,代码:

nodeStck.push(tableNode);
tableNode.mPh = tmpNode;
tableNode = tableNode.mPh;

将当前的表节点压栈 , 接着表头指向新的node , 当前节点向前滑动一个位置。

当遇到原子节点符号(如:’a‘) 时,则创建一个原子节点,并且让表头指向该节点,其代码如下:

else {
                itemNode = new Node(null, null, TAG_ITEM, ts.charAt(i));
                tableNode.mPh = itemNode;
            }

当遇到符号 ’,‘ 时构造一个表节点,让当前节点的表尾指向新的节点,其代码如下:

else if (ts.charAt(i) == ',') {
                tableNode.mPt = new Node(null, null, TAG_TABLE, null);
                tableNode = tableNode.mPt;
            }

当遇到符号 ')' 时,做两件事

1、如果  symbStack 的长度 > 1 , 表明此时并没有回到表的最外层,肯定存在一个nodeStack中的节点需要出栈,接着让与之对应的 ’(‘ 符号出栈,其代码如下:

else if (ts.charAt(i) == mEndSymb) {
                if (symbStack.isEmpty()) {
                    throw new IllegalArgumentException(
                            "IllegalArgumentException in constructor GeneralizedTable!...");
                }
                if (symbStack.size() > 1) {
                    tableNode = nodeStck.pop();
                }
                symbStack.pop();
            }

当表字符串结束,切symStack的长度为0时,表明是一个格式正确的表字符串,否则说明该表字符串的格式错误,不予处理。

至此,一个广义表就构造OK了。根据上述原理,构造一个广义表的完整代码如下:

public GeneralizedTable(String genTable) {
        if (genTable == null) {
            throw new NullPointerException(
                    "genTable is null in constructor GeneralizedTable!...");
        }
        initTable(genTable);
    }

    private void initTable(String genTable) {
        String ts = genTable.replaceAll("\\s", "");
        int len = ts.length();
        Stack<Character> symbStack = new Stack<Character>();
        Stack<Node> nodeStck = new Stack<Node>();
        initSymbolicCharactor(ts);
        mGenTable = new Node(null, null, TAG_TABLE, null);
        Node itemNode, tableNode = mGenTable, tmpNode;
        for (int i = 0; i < len; i++) {
            if (ts.charAt(i) == mStartSymb) {
                tmpNode = new Node(null, null, TAG_TABLE, null);
                // tableNode = tableNode.mPt;
                symbStack.push(ts.charAt(i));
                if (symbStack.size() > 1) {
                    nodeStck.push(tableNode);
                    tableNode.mPh = tmpNode;
                    tableNode = tableNode.mPh;
                } else {
                    tableNode.mPt = tmpNode;
                    tableNode = tableNode.mPt;
                }
            } else if (ts.charAt(i) == mEndSymb) {
                if (symbStack.isEmpty()) {
                    throw new IllegalArgumentException(
                            "IllegalArgumentException in constructor GeneralizedTable!...");
                }
                if (symbStack.size() > 1) {
                    tableNode = nodeStck.pop();
                }
                symbStack.pop();
            } else if (ts.charAt(i) == ',') {
                tableNode.mPt = new Node(null, null, TAG_TABLE, null);
                tableNode = tableNode.mPt;
            } else {
                itemNode = new Node(null, null, TAG_ITEM, ts.charAt(i));
                tableNode.mPh = itemNode;
            }
        }

        if (!symbStack.isEmpty()) {
            throw new IllegalArgumentException(
                    "IllegalArgumentException in constructor GeneralizedTable!...");
        }
    }

    private void initSymbolicCharactor(String ts) {
        mStartSymb = ts.charAt(0);
        switch (mStartSymb) {
            case '(':
                mEndSymb = ')';
                break;
            case '{':
                mEndSymb = '}';
                break;
            case '[':
                mEndSymb = ']';
                break;
            default:
                throw new IllegalArgumentException(
                        "IllegalArgumentException ---> initSymbolicCharactor");
        }
    }

注释:本代码中支持 ( , )  , { , } ,  [ , ]  为"广义表标示符"的广义表字符串(默认是())。

求广义表的长度: 根据广义表长度的定义,该表的长度,等于原子节点或表节点的个数,即 header.pT != null 的个数 , 其代码如下:

public int length() { // 广义表的长度
        if (mGenTable == null || mGenTable.mPt == null) {
            return -1;
        }
        int tLen = 0;
        Node node = mGenTable;
        while (node.mPt != null) {
            node = node.mPt;
            if (node.mPh == null && node.mPt == null) {
                break;
            }
            tLen++;
        }
        return tLen;
    }

广义表的深度:因为广义表由
表头
表尾 组成 , 所以 , 广义表的深度是 表头、表尾中的最大深度。由此定义,得到如下代码:

public int depth() { // 广义表的深度
        if (mGenTable == null) {
            throw new NullPointerException("Generalized Table is null !.. ---> method depth");
        }
        return depth(mGenTable);
    }

    private int depth(Node node) {
        if (node == null || node.mTag == TAG_ITEM) {
            return 0;
        }
        int depHeader = 0, depTear = 0;
        depHeader = 1 + depth(node.mPh);
        depTear = depth(node.mPt);
        return depHeader > depTear ? depHeader : depTear;
    }

广义表的表头:广义表的第一项称为表头,表头可能是一个原子项和广义表。但是不管如何,他都是第一个的pH指向的内容:其代码如下:

public GeneralizedTable getHeader() {
        if (isEmpty())
            return null;
        Node node = mGenTable.mPt;
        GeneralizedTable gt = new GeneralizedTable();
        gt.mGenTable.mPt = node.mPh;
        return gt;
    }

广义表的表尾:广义表的表尾必定是一个广义表,但不管由什么子表组成,都是广义表的pT所指向的内容:求解广义表表尾的代码如下:

public GeneralizedTable getTear() {
        if (isEmpty())
            return null;
        Node node = mGenTable.mPt;
        GeneralizedTable gt = new GeneralizedTable();
        gt.mGenTable.mPt = node.mPt;
        return gt;
    }

打印广义表的内容:这里打印广义表内容是指,打印所有原子项中的数据,一个深度优先打印的代码如下:

public void print() {
        print(mGenTable);
    }

    private void print(Node node) {
        if (node == null) {
            return;
        }
        if (node.mTag == 0) {
            System.out.print(node.mData.toString() + " \t");
        }
        print(node.mPh);
        print(node.mPt);

    }

下面是整个广义表操作的代码:

import java.util.Stack;

/**
 * 广义表操作:
 *    1、广义表的构造  : 
 *        1.1 构造一个空的广义表
 *        1.2 根据现有的广义表,构造一个新的广义表
 *        1.3 根据广义表字符串构造一个广义表
 *    2、广义表的深度
 *    3、广义表的长度
 *    4、按照深度优先顺序打印广义表
 *    5、求广义表表头
 *    6、求广义表表尾
 *
 */
public class GeneralizedTable {

    public static final int TAG_ITEM = 0; // 原子节点
    public static final int TAG_TABLE = 1; // 表节点
    /*
     * 广义表支持的符号包括'(' , ')' , '{' , '}' , '[' , ']'
     * 广义表表示符号,使用字符串构造广义表时第一个字符必须是'(', '{' , '[' 之一 并以')' , '}' , ']' 之一结束,
     * 并且各符号相对应
     */
    private char mStartSymb = '(';
    private char mEndSymb = ')';
    private Node mGenTable;

    public GeneralizedTable() {
        mGenTable = new Node(null, null, TAG_TABLE, null);
    }

    // 使用广义表 src 构造一个新的广义表
    public GeneralizedTable(GeneralizedTable src) {
        if (src != null) {
            mGenTable = src.mGenTable;
        }

    }

    /**
     * @param genTable
     */
    public GeneralizedTable(String genTable) {
        if (genTable == null) {
            throw new NullPointerException(
                    "genTable is null in constructor GeneralizedTable!...");
        }
        initTable(genTable);
    }

    private void initTable(String genTable) {
        String ts = genTable.replaceAll("\\s", "");
        int len = ts.length();
        Stack<Character> symbStack = new Stack<Character>();
        Stack<Node> nodeStck = new Stack<Node>();
        initSymbolicCharactor(ts);
        mGenTable = new Node(null, null, TAG_TABLE, null);
        Node itemNode, tableNode = mGenTable, tmpNode;
        for (int i = 0; i < len; i++) {
            if (ts.charAt(i) == mStartSymb) {
                tmpNode = new Node(null, null, TAG_TABLE, null);
                // tableNode = tableNode.mPt;
                symbStack.push(ts.charAt(i));
                if (symbStack.size() > 1) {
                    nodeStck.push(tableNode);
                    tableNode.mPh = tmpNode;
                    tableNode = tableNode.mPh;
                } else {
                    tableNode.mPt = tmpNode;
                    tableNode = tableNode.mPt;
                }
            } else if (ts.charAt(i) == mEndSymb) {
                if (symbStack.isEmpty()) {
                    throw new IllegalArgumentException(
                            "IllegalArgumentException in constructor GeneralizedTable!...");
                }
                if (symbStack.size() > 1) {
                    tableNode = nodeStck.pop();
                }
                symbStack.pop();
            } else if (ts.charAt(i) == ',') {
                tableNode.mPt = new Node(null, null, TAG_TABLE, null);
                tableNode = tableNode.mPt;
            } else {
                itemNode = new Node(null, null, TAG_ITEM, ts.charAt(i));
                tableNode.mPh = itemNode;
            }
        }

        if (!symbStack.isEmpty()) {
            throw new IllegalArgumentException(
                    "IllegalArgumentException in constructor GeneralizedTable!...");
        }
    }

    private void initSymbolicCharactor(String ts) {
        mStartSymb = ts.charAt(0);
        switch (mStartSymb) {
            case '(':
                mEndSymb = ')';
                break;
            case '{':
                mEndSymb = '}';
                break;
            case '[':
                mEndSymb = ']';
                break;
            default:
                throw new IllegalArgumentException(
                        "IllegalArgumentException ---> initSymbolicCharactor");
        }
    }

    public void print() {
        print(mGenTable);
    }

    private void print(Node node) {
        if (node == null) {
            return;
        }
        if (node.mTag == 0) {
            System.out.print(node.mData.toString() + " \t");
        }
        print(node.mPh);
        print(node.mPt);

    }

    public int depth() { // 广义表的深度
        if (mGenTable == null) {
            throw new NullPointerException("Generalized Table is null !.. ---> method depth");
        }
        return depth(mGenTable);
    }

    private int depth(Node node) {
        if (node == null || node.mTag == TAG_ITEM) {
            return 0;
        }
        int depHeader = 0, depTear = 0;
        depHeader = 1 + depth(node.mPh);
        depTear = depth(node.mPt);
        return depHeader > depTear ? depHeader : depTear;
    }

    public int length() { // 广义表的长度
        if (mGenTable == null || mGenTable.mPt == null) {
            return -1;
        }
        int tLen = 0;
        Node node = mGenTable;
        while (node.mPt != null) {
            node = node.mPt;
            if (node.mPh == null && node.mPt == null) {
                break;
            }
            tLen++;
        }
        return tLen;
    }

    public GeneralizedTable getHeader() {
        if (isEmpty())
            return null;
        Node node = mGenTable.mPt;
        GeneralizedTable gt = new GeneralizedTable();
        gt.mGenTable.mPt = node.mPh;
        return gt;
    }

    public GeneralizedTable getTear() {
        if (isEmpty())
            return null;
        Node node = mGenTable.mPt;
        GeneralizedTable gt = new GeneralizedTable();
        gt.mGenTable.mPt = node.mPt;
        return gt;
    }

    public boolean isEmpty() {
        if (mGenTable == null) {
            return true;
        }
        Node node = mGenTable.mPt;
        return node == null || node.mPh == null;
    }

    public class Node {// 广义表节点
        Node mPh; // 广义表的表节点
        Node mPt; // 广义表表尾节点
        int mTag; // mTag == 0 , 院子节点 ; mTag == 1 , 表节点 。
        Object mData; // 广义表的数据值

        public Node(Node ph, Node pt, int tag, Object data) {
            mPh = ph;
            mPt = pt;
            mTag = tag;
            mData = data;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // String tStr = "((),(a,b,c),a,d,((d,g,(c))),(k,g),c)";
        String p = "((),a,b,(a,b,c),(a,(a,b),c))";
         String p2 = "((()),2)";
        // String space = "()";
         String big = "{
  {a,b},{
  {a,g},{h},{a,n,f,{a,b,c}}},c}";
         String middle = "[[p],[[d,f,[g]]],[h],[2]]";
        GeneralizedTable gTab = new GeneralizedTable(middle);
        // GeneralizedTable header, tear;
        // // gTab.print();
        // // System.out.println();
          System.out.println("length: " + gTab.length());
          System.out.println("depth: " + gTab.depth());
        //
        // header = gTab.getHeader();
        // if (header != null) {
        // System.out.println("header: ");
        // header.print();
        // }
        // tear = gTab.getTear();
        //
        // if (tear != null) {
        // System.out.println("tear: ");
        // tear.print();
        // }
//        gTab.print();
//        System.out.println();
//        GeneralizedTable gTab4 = null;
//        GeneralizedTable gTab2 = new GeneralizedTable(gTab4);
//        gTab2.print();
//        gTab2 = new GeneralizedTable(gTab);
//        gTab2.print();
    }

}

广义表的内容就先写到这里 , 后续有新内容再补充 。

    原文作者:sun_star1chen
    原文地址: https://blog.csdn.net/sun_star1chen/article/details/17882285
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。