数据结构--广义表

刺骨的言语ヽ痛彻心扉 2021-08-13 21:27 669阅读 0赞

### 广义表的定义 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

### 带表名的广义表表示 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]

### 广义表的特性 ###

*  线性结构
 *  多层次结构，有深度
 *  可共享
 *  可递归

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]

### 广义表抽象数据类型 ###

package pers.zhang.genList;
    
    /** * @author zhang * @date 2020/1/20 - 10:57 * * 广义表抽象数据结构 */
    public interface GGenList<T> { 
        //判断广义表是否为空
        boolean isEmpty();
    
        //返回广义表长度
        int length();
    
        //返回广义表的深度
        int depth();
    
        //插入原子x作为第i个元素
        GenListNode<T> insert(int i, T x);
    
        //插入子表作为第i个元素
        GenListNode<T> insert(int i, GenList<T> glist);
    
    
    
    }

### 广义表的存储结构 ###

广义表的单链表示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]

广义表的双链表示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 5]

### 广义表双链表示的实现 ###

广义表双链表示的节点类：

package pers.zhang.genList;
    
    /** * @author zhang * @date 2020/1/20 - 11:03 * * 广义表双链表示的节点类 */
    public class GenListNode<T> { 
        //数据域
        public T data;
        
        //地址域，指向子表
        public GenList<T> child;
        
        //地址域，指向后继节点
        public GenListNode<T> next;
        
        //构造节点，data指定元素，child指向子表，next指向后继节点
        public GenListNode(T data, GenList<T> child, GenListNode<T> next){ 
            this.data = data;
            this.child = child;
            this.next = next;
        }
        
        public GenListNode(T data){ 
            this(data, null, null);
        }
        
        public GenListNode(){ 
            this(null, null, null);
        }
    }

package pers.zhang.genList;
    
    /** * @author zhang * @date 2020/1/20 - 11:07 * * 双链表表示的广义表类 */
    public class GenList<T> implements GGenList<T>{ 
    
        //头指针，指向（引用）头结点
        public GenListNode<T> head;
    
        //构造空广义表
        public GenList(){ 
            this.head = new GenListNode<T>();
        }
    
        //构造广义表，由数组提供原子初值，结点次序与数组元素次序相同，采用尾插入构造，算法同单链表
        public GenList(T[] atoms){ 
            this();//构造空广义表，只有头结点
            GenListNode<T> rear = this.head;
            for(int i = 0; i < atoms.length; i++){ 
                rear.next = new GenListNode<T>(atoms[i]);//尾插入
                rear = rear.next;
            }
        }
    
        //判断广义表是否为空
        @Override
        public boolean isEmpty() { 
            return head.next == null;
        }
    
        //返回广义表长度，算法同单链表
        @Override
        public int length() { 
            int i = 0;
            for(GenListNode<T> p = this.head.next; p != null; p = p.next)
                i++;
            return i;
        }
    
        //返回广义表深度，递归方式
        @Override
        public int depth() { 
            int max = 1;
            for(GenListNode<T> p = this.head.next; p != null; p = p.next){ 
                if(p.child != null){ 
                    int d = p.child.depth();//递归调用，返回子表深度
                    if(max <= d)//记住最大子表深度
                        max = d + 1;//当前广义表深度为子表深度
                }
            }
            return max;
        }
    
        //插入原子x作为第i个元素，算法同单链表
        @Override
        public GenListNode<T> insert(int i, T x) { 
            if(x == null)
                return null;
            GenListNode<T> p = this.head;
            for(int j = 0; p.next != null && j < i; j++)//寻找插入位置
                p = p.next;
            p.next = new GenListNode<T>(x, null, p.next);//插入在p结点之后，包括头插入、中间插入
            return p.next;
        }
    
        //插入子表作为第i个元素，算法同单链表插入结点
        @Override
        public GenListNode<T> insert(int i, GenList<T> glist) { 
            if(glist == null)
                return null;
            GenListNode<T> p = this.head;
            for(int j = 0; p.next != null && j < i; j++)
                p = p.next;
            p.next = new GenListNode<T>(null, glist, p.next);
            return p.next;
        }
        
    
        //在广义表最后添加原子结点，算法同单链表
        public void append(T x){ 
            insert(Integer.MAX_VALUE, x);
        }
    
        //在广义表最后添加子表
        public void append(GenList<T> glist){ 
            insert(Integer.MAX_VALUE, glist);
        }
    
        //返回广义表所有元素的描述字符串
        public String toString(){ 
            return this.toString("");
        }
    
        //返回广义表所有元素值对应的字符串，形式为“(,)”，广义表遍历算法，递归方法
        public String toString(String str){ 
            str += "(";
            for (GenListNode<T> p = this.head.next; p != null; p = p.next){ 
                if (p.child == null)
                    str += p.data.toString();
                else
                    str += p.child.toString();                 //递归调用，遍历子表添加子表描述字符串
                if (p.next != null)
                    str += ",";
            }
            return str+")";                                    //空表返回()
        }
    }

测试：

package pers.zhang.genList;
    
    /** * @author zhang * @date 2020/1/20 - 11:34 */
    public class GenList_ex { 
        public static void main(String args[])
        { 
            GenList<String> glist_empty = new GenList<String>();//构造空广义表
            System.out.print("glist_empty："+glist_empty.toString()+"， length="+glist_empty.length());
            System.out.println("，depth="+glist_empty.depth());
    
            glist_empty.insert(0, new GenList<String>());      //空表中插入空表
            glist_empty.append(new GenList<String>());
            System.out.print("glist："+glist_empty.toString()+"， length="+glist_empty.length());
            System.out.println("，depth="+glist_empty.depth());
    
            String[] gliststr_l = { "b","c","e"};
            GenList<String> glist_L = new GenList<String>(gliststr_l);//由原子数组构造广义表
            glist_L.insert(0, "a");                            //头插入原子
            glist_L.insert(3, "d");                            //中间插入原子
            glist_L.append("f");                               //尾插入原子
            System.out.print("glist_L："+glist_L.toString()+"， length="+glist_L.length());
            System.out.println("，depth="+glist_L.depth());
    
            String[] gliststr_t = { "o","p","q"};
            GenList<String> glist_T = new GenList<String>(gliststr_t);
            glist_T.append(glist_L);                           //尾插入子表
            System.out.print("glist_T："+glist_T.toString()+"， length="+glist_T.length());
            System.out.println("，depth="+glist_T.depth());
    
            String[] gliststr_g = { "x","y","z"};
            GenList<String> glist_G = new GenList<String>(gliststr_g);
            glist_G.append(glist_L);
            glist_G.append(glist_T);                           //尾插入子表，glist_L成为共享子表
            System.out.print("glist_G："+glist_G.toString()+"， length="+glist_G.length());
            System.out.println("，depth="+glist_G.depth());
        }
    }
    /* glist_empty：()， length=0，depth=1 glist：((),())， length=2，depth=2 glist_L：(a,b,c,d,e,f)， length=6，depth=1 glist_T：(o,p,q,(a,b,c,d,e,f))， length=4，depth=2 glist_G：(x,y,z,(a,b,c,d,e,f),(o,p,q,(a,b,c,d,e,f)))， length=5，depth=3 */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/4a1fad5a9e20435f9d4ede00c99f202a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/200dc00afbdc4633b362b0d82cc94904.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/e6f7266c24854c12a86e882de181d636.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/9a9492418fdc4c328a04cd41c000be69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]: /images/20210813/099b5f2295674626a0239482870be2f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 5]: /images/20210813/7ed8c569e7194583a0e166c18cd3611a.png