首页 > 代码库 > 顺序存储结构模拟

顺序存储结构模拟

2024-07-18 00:37:05   218人阅读

我们过去介绍的数据结构都不是线性存储的结构,我们今天就来模拟一个最简单的数据结构基于数组构建存储连续的数据结构.


1.线性表顺序存储结构的接口



/**  
* 指的是用一段地址连续的存储单元一次存储线性表的数据元素  
* @ClassName: ISeqList   
*/  
public interface ISeqList<T> {
     /**  
      * 获得元素  
      * @param i 需要获得的第i个元素  
      * @return   
      */  
     public T getElem(int i);   
        
   
     /**  
      * 插入元素  
      * @param i 元素的插入位置  
      * @param t 需要插入的元素  
      * @return  是否成功插入  
      */  
     public boolean insertElem(int i, T t);   
        
     /**  
      * 删除元素  
      * @param i 需要删除元素的位置  
      * @return  
      */  
     public T deleteElem(int i);   
}
//实现类
public class SeqList<T>  implements  ISeqList<T> {
   
    public  static final  int MAXSIZE = 20;//存储空间的初始化配量   
    private T[] data;   //数组存储数据元素   
    private int length; //线性表当前长度  
    
    //构造函数
    public   SeqList()
    {
      data=http://www.mamicode.com/(T[]) new Object[this.MAXSIZE];
    }

    
public T deleteElem(int i) {
   if(length == 0) {   //"线性表为空"   
             System.out.println("线性表为空");   
             return null;    
         }   
   
         if(i < 1 || i > length) { //删除位置不在范围内   
             System.out.println("该位置不合法");   
             return null;   
         }   
             
         if(i<length)//正常的删除
         {
          T t=data[i-1];
          //移动后面的元素
          for(int j=i;j<length;j++)
          {
             data[j]=data[j+1];
          }
          length--;//线性表长度减少  
          return  t;
         }
         
  return null;
}
public T getElem(int i) {
  if(i<0 || i>MAXSIZE)
  {
   return  null;
  }
  else
  {   //返回i位置的数据
   T  t=data[i-1];
   return t;
  } 
}
    //插入数据
public boolean insertElem(int i, T t) {
      //空间已经满了,不好插入数据
     if(length == MAXSIZE) { //线性表已经满了   
             System.out.println("该线性表已经满了");   
             return false;   
         }    
         if(i < 1 || i > MAXSIZE) {//插入位置不在范围内   
             System.out.println("该位置不合法");   
             return false;   
         }
        if(i<length)//插入元素不在尾部 1,2,3,5
        {
         //i后元素，向后移动
         for(int  j=length;j>i;j--)
         {
            data[j]=data[j-1];
         }
          //然后插入新的值
         data[i-1]=t;
         //长度增加1 
         length++;
         return  true;
        }
  return false;
}

  public T[] getData() {   
         return data;   
     }   
   
     public void setData(T[] data) {   
         this.data = http://www.mamicode.com/data;
     }   
   
     public int getLength() {   
         return length;   
     }   
   
     public void setLength(int length) {   
         if(length < 0 || length > MAXSIZE) {  //删除位置不在范围内   
             System.out.println("长度不合法");   
         }   
         this.length = length;   
     }   

}
//测试
public class SeqListTest {
  final int MAX = 25;   
     Random r = new Random();   
     SeqList<Integer> seqList;   
        
     public SeqListTest() {   
         initSeqList();   
     }   
        
     //创建一个线性表顺序存储结构   
     public void initSeqList() {   
   
         seqList = new SeqList<Integer>();   
            //int length = (int) Math.random();   //只能产生0.0 - 1.0之间的double随机数   
         int length = Math.abs(r.nextInt(MAX));  //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值     
         System.out.println("产生的数组长度为 ：" + length);   
            
         if(length >SeqList.MAXSIZE) {   
             System.out.println("该长度不合法");   
         }   
            
         for (int i = 1; i <= length; i++) {  //为生成的数组赋值，同时也测试了插入值的方法   
             int j =r.nextInt(MAX);   
             System.out.print(j + " ");   
                
             if(!seqList.insertElem(i, j)) {   
                 System.exit(0);    
             }   
         }   
         System.out.println("\n原始数组是 ：");   
         display(seqList);   
     }   
        
     //测试删除方法   
     public void deleteElem() {   
         int i = r.nextInt(MAX);   
         System.out.println("\n\n删除的位置是：" + i);   
         Integer deleteNumber = seqList.deleteElem(i);   
            
         if( deleteNumber == null) {   
             System.exit(0);   
         } else {   
             System.out.println("删除的元素是 ： " + deleteNumber);   
             System.out.println("删除元素后数组是 ：");   
             display(seqList);   
         }   
     }   
        
     //测试随机插入方法   
     public void insertByRandom() {   
         int i = r.nextInt(MAX);   
         System.out.println("\n\n随机插入位置是 ：" + i);   
         int elem = r.nextInt(MAX);   
         System.out.println("随机插入数据是 ：" + elem);   
         seqList.insertElem(i, elem);   
         System.out.println("随机插入数据后数组是 ：");   
         display(seqList);   
     }   
        
     //数据展示   
     public  void display(SeqList seqList) {   
         for (int i = 1; i < seqList.getData().length; i++) {   
                
             if(seqList.getElem(i) != null) {   
                 System.out.print(seqList.getElem(i) + " ");   
             }   
                
         }   
         System.out.println("数组的长度为 ：" + seqList.getLength());   
     }   
        
     //获取元素   
     public void getElem() {   
         int i = r.nextInt(MAX);   
         System.out.println("\n获取位置为 ：" + i);   
         System.out.println("获取到的元素为 : " + seqList.getElem(i));   
            
     }   
        
     public static void main(String[] args) {   
         SeqListTest s = new SeqListTest();   
         s.insertByRandom();   
         s.deleteElem();   
         s.getElem();   
     }   

}

小结:目前此数据结构使用还是比较频繁,但是有个不好的地方就是需要一个连续的存储空间.


联系
我们