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