本文共 5111 字，大约阅读时间需要 17 分钟。

广义表的定义

带表名的广义表表示

广义表的特性

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

广义表抽象数据类型

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

广义表的存储结构

广义表的单链表示：

广义表的双链表示：

广义表双链表示的实现

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

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

转载地址：http://ffpqb.baihongyu.com/