1、线性表实现:顺序存储

抽象数据模型ADT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package ren.laughing.datastructure.base;
 
import ren.laughing.datastructure.exception.OutOfBoundaryException;
/**
* 线性表ADT(抽象数据模型)
* ADT包括数据数据元素,数据关系以及相关的操作。
* 即ADT
* {
* 数据对象:(数据元素集合)
* 数据关系:(数据关系二元组结合)
* 基本操作:(操作函数的罗列)
* }
* @author Laughing
* @time 2016年4月5日
*/
public interface List {
//返回线性表的大小,即数据元素的个数。
public int getSize();
//如果线性表为空返回 true,否则返回 false。
public boolean isEmpty();
//判断线性表是否包含数据元素 e
public boolean contains(Object e);
//返回数据元素 e 在线性表中的序号
public int indexOf(Object e);
//将数据元素 e 插入到线性表中 i 号位置
public void insert(int i, Object e) throws OutOfBoundaryException;
//将数据元素 e 插入到元素 obj 之前
public boolean insertBefore(Object obj, Object e);
//将数据元素 e 插入到元素 obj 之后
public boolean insertAfter(Object obj, Object e);
//删除线性表中序号为 i 的元素,并返回之
public Object remove(int i) throws OutOfBoundaryException;
//删除线性表中第一个与 e 相同的元素
public boolean remove(Object e);
//替换线性表中序号为 i 的数据元素为 e,返回原数据元素
public Object replace(int i, Object e) throws OutOfBoundaryException;
//返回线性表中序号为 i 的数据元素
public Object get(int i) throws OutOfBoundaryException;
}

数据元素的比较策略:

1
2
3
4
5
6
7
8
9
10
11
12
package ren.laughing.datastructure.base;
/**
 * 数据元素的比较策略
 * @author Laughing
 * @time 2016年4月5日
 */
public interface Strategy {
 //判断两个数据是否相等
 public boolean equal(Object obj1,Object obj2);
 //判断两个数据大小,返回-1|0|1
 public int compare(Object obj1,Object obj2);
}

线性表的实现:顺序存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package ren.laughing.datastructure.baseImpl;
 
import ren.laughing.datastructure.base.List;
import ren.laughing.datastructure.base.Strategy;
import ren.laughing.datastructure.exception.OutOfBoundaryException;
/**
 * 线性表的实现
 * @author Laughing
 * @time 2016年4月5日
 */
public class ArrayList implements List{
 private final int LEN = 8; //默认数组大小8
 private Strategy strategy; //数据元素的比较策略
 private int size; //线性表中数据元素的个数
 private Object[] elements; //数据元素数组
 //构造器
 public ArrayList() {
 this(new DefaultStrategy());
 }
 public ArrayList(Strategy strategy) {
 this.strategy = strategy;
 size = 0;
 elements = new Object[LEN];//默认数组大小
 }
 
 
 @Override
 public int getSize() {
 return size;
 }
 
 @Override
 public boolean isEmpty() {
 if(size == 0){
 return true;
 }else{
 return false;
 }
 }
 
 @Override
 public boolean contains(Object e) {
 for(int i=0;i<size;i++){
 if(strategy.equal(e, elements[i])){
 return true;
 }
 }
 return false;
 }
 
 @Override
 public int indexOf(Object e) {
 for(int i=0;i<size;i++){
 if(strategy.equal(e, elements[i])){
 return i;
 }
 }
 return -1;
 }
 
 @Override
 public void insert(int i, Object e) throws OutOfBoundaryException {
 if (i < 0 || i > size) {
 throw new OutOfBoundaryException("错误,指定的插入序号越界。");
 }
 //若数据元素个数大于数据元素数组长度
 if (size >= elements.length) {
 expandSpace();// 扩充数组长度
 }
 for (int j = size; j > i; j--) {
 elements[j] = elements[j - 1];
 }
 elements[i] = e;
 size++;
 
 }
 //将数据元素 e 插入到元素 obj之前
 @Override
 public boolean insertBefore(Object obj, Object e) {
 int index = this.indexOf(obj);
 if(index < 0){
 return false;
 }else{
 this.insert(index, e);
 return true;
 }
 }
 //将数据元素 e 插入到元素 obj之后
 @Override
 public boolean insertAfter(Object obj, Object e) {
 int index = this.indexOf(obj);
 if(index < 0){
 return false;
 }else{
 this.insert(index+1, e);
 return true;
 }
 }
 //删除线性表中序号为 i 的元素,并返回之
 @Override
 public Object remove(int i) throws OutOfBoundaryException {
 if(i>=size||i<0){
 throw new OutOfBoundaryException("指定的删除序号越界");
 }
 Object obj = elements[i];
 for(int j=i;j<size;j++){
 elements[j]=elements[j+1];
 }
 elements[size--]=null;//释放数组最后一个位置的元素
 return obj;
 }
 //删除线性表中第一个与 e 相同的元素
 @Override
 public boolean remove(Object e) {
 int index = indexOf(e);
 if(index<0){
 return false;
 }else{
 this.remove(index);
 return true;
 }
 }
 //替换线性表中序号为 i 的数据元素为 e,返回原数据元素
 @Override
 public Object replace(int i, Object e) throws OutOfBoundaryException {
 if(i<0||i>=size){
 throw new OutOfBoundaryException("要替换元素的序号越界");
 }
 Object obj = elements[i];
 elements[i] = e;
 return obj;
 }
 //返回线性表中序号为 i 的数据元素
 @Override
 public Object get(int i) throws OutOfBoundaryException {
 if(i<0||i>=size){
 throw new OutOfBoundaryException("要获取元素的序号越界");
 }
 Object obj = elements[i];
 return obj;
 }
 /**
 * 扩充数组长度
 */
 private void expandSpace() {
 Object[] a = new Object[elements.length * 2];
 for (int i = 0; i < elements.length; i++)
 a[i] = elements[i];
 elements = a;
 }
 
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注