java——線性表接口實作

 線性表是存儲順序牌類的資料時最常用的資料結構。

    實作線性表有兩種方式。第一種是使用數組存儲線性表的元素。數組是動态建立的。超過數組的容量時，建立一個

新的更大的數組，并且将目前數組中的元素複制到建立的數組中。另一種方法是用連結清單結構實作。連結清單由節點組成，每

個結點都是動态生成的，用來存儲一個元素。所有的結點連接配接成一個線性表。

    對于線性表的主要操作有：

    1、提取線性表的元素

    2、線上性表中插入一個新元素

    3、從線性表中删除一個元素

    4、擷取線性表中元素的個數

    5、查找線性表中是否包含某個元素

    6、判斷線性表是否為空

下面這個接口類定義了常用的操作。

1 package com.ezreal;
 2 
 3 
 4 public interface ListIntf {
 5     /**
 6      * 傳回表長度
 7      * @return
 8      */
 9     public int size();
10     
11     /**
12      * 增加元素
13      * @param obj
14      */
15     public void add(Object obj);
16     /**
17      * 重置為空表
18      */
19     public void clear();
20     /**
21      * 判斷是否為空
22      * @return
23      */
24     public boolean isEmpty();
25     /**
26      * 第i個資料元素的值
27      * @param i
28      * @return
29      */
30     public Object get(int i);
31     /**
32      * 傳回第一個這個元素的位置
33      * @param obj
34      * @return
35      */
36     public int indexOf(Object obj);
37     /**
38      * 傳回這個元素的前驅
39      * @param obj
40      * @return
41      */
42     public Object getPre(Object obj);
43     /**
44      * 傳回這個元素的後繼
45      * @param obj
46      * @return
47      */
48     public Object getNext(Object obj);
49     /**
50      * 第i個位置插入新的元素對象
51      * @param obj
52      * @param i
53      */
54     public void insertElementAt(Object obj ,int i);
55     /**
56      * 删除第i個元素
57      * @param i
58      * @return
59      */
60     public Object remove(int i);
61     /**
62      * 删除資料元素obj，并傳回這個元素的值
63      * @param obj
64      * @return
65      */
66     public Object remove(Object obj);
67 }      

接下來用數組實作線性表。數組的類型是Object類型，是以，數組中每個元素實際元素存儲的是對象的。

1 package com.ezreal;
  2 
  3 public class SqList implements ListIntf {
  4     final int maxlen = 1000;
  5     Object v[] = new Object[maxlen];
  6     int len = 0;
  7 
  8     public SqList() {
  9 
 10     }
 11 
 12     @Override
 13     public void add(Object obj) {
 14         if(len == maxlen){
 15             System.out.println("溢出");
 16         }else{
 17             v[len] = obj;
 18             len++;
 19         }
 20     }
 21 
 22     @Override
 23     public int size() {
 24         return len;
 25     }
 26 
 27     @Override
 28     public void clear() {
 29         
 30         len =0;
 31     }
 32 
 33     @Override
 34     public boolean isEmpty() {
 35         
 36         if(len == 0){
 37             return true;
 38         }
 39         return false;
 40     }
 41 
 42     @Override
 43     public Object get(int i) {
 44         if(i<1 || i>len){
 45             System.out.println("擷取元素位置不正确");
 46         }else{
 47             return v[i-1];
 48         }
 49         return null;
 50         
 51     }
 52 
 53     @Override
 54     public int indexOf(Object obj) {
 55         for(int i=0;i<len;i++){
 56             if(v[i].equals(obj)){
 57                 return i;
 58             }
 59         }
 60         return -1;
 61     }
 62 
 63     @Override
 64     public Object getPre(Object obj) {
 65         int i = indexOf(obj);
 66         if(i==-1){
 67             System.out.println("無該元素");
 68         }else if(i == 0){
 69             System.out.println("無前驅");
 70         }else{
 71             return v[i-1];
 72         }
 73         
 74         return null;
 75     }
 76 
 77     @Override
 78     public Object getNext(Object obj) {
 79         int i = indexOf(obj);
 80         if(i==-1){
 81             System.out.println("無該元素");
 82         }else if(i == len){
 83             System.out.println("無前驅");
 84         }else{
 85             return v[i+1];
 86         }
 87         
 88         return null;
 89     }
 90 
 91     @Override
 92     public void insertElementAt(Object obj, int i) {
 93         if(len == maxlen){
 94             System.out.println("溢出");
 95             return;
 96         }else {
 97             if(i < 0 || i >len){
 98                 System.out.println("插入位置不正确");
 99                 return;
100             }else{
101                 for(int j=len-1;j>=i-1;j--){
102                     v[j+1]=v[j];//第i個元素和他後面的所有元素均後移一個位置
103                 }
104                 v[i-1]=obj;
105                 len++;
106                 return;
107             }
108             
109         }
110 
111     }
112 
113     @Override
114     public Object remove(int i) {
115         Object obj;
116         if(i<1 || i>len){
117             System.out.println("删除位置不正确");
118         }else{
119             obj = v[i-1];
120             for(int j=i;j<len;j++){
121                 v[j-1]=v[j];
122             }
123             len--;
124             return obj;
125         }
126         return null;
127         
128     }
129 
130     @Override
131     public Object remove(Object obj) {
132         int i=indexOf(obj);
133         if(i==-1){
134             System.out.println("無該元素");
135         }else {
136             remove(i+1);
137         }
138         
139         return null;
140     }
141 
142 }      

 如有不對的地方，請各位看官指出。

轉載于:https://www.cnblogs.com/ezreal2016/p/5813304.html