1 Java数据结构与算法基础

数据的逻辑结构可以采用两个方法来描述：二元组、图形。

数据结构的二元组形式为:

数据结构={D，S}

其中D是数据元素的集合；S是D中数据元素之间的关系集合，并且数据元素之间的关系使用序偶来表示。记作,x是它的第一个元素，y是它的第二个元素。

对于数据元素中，可以有多个直接前驱元素也可以有多个直接后驱元素。数据元素之间的关系是M对N的联系，我们把具有此种特点的数据结构称为图结构。

图 1-1 set、linearity、tree、graph的图形表示

由于是在Java这种高级语言中讨论数据结构，所以在讨论数据的存储结构的时候时不会在真正的物理地址的基础上去讨论顺序存储和链式存储，而是在Java提供的一维数组和对象的引用基础上讨论和实现数据的存储结构。

1.1 抽象数据类型ADT

数据类型：Java中提供了八种基本的数据类型，整数类型（byte、short、int、long）、字符类型（char）、浮点类型（float、double）和布尔类型（只占用一个比特）。定义数据类型有两个作用：①是隐藏计算机硬件的特性和差别，使的硬件对于用于而言是透明的，即用户不需要关心数据类型是怎么实现的而可以去使用它（就和Java中的封装一样）；②用于可以使用数据类型定义的操作，方便问题的求解。

抽象数据类型（abstract data type，简称ADT）由一种数据模型和在该数据模型上的一组操作组成。ADT包括定义和实现两个方面。

ADT可以使用一个三元组来表示：

ADT=(D,S,P)

其中D是数据对象，S是D上的关系集，P是加在D上的一组操作。在定义ADT时，我们使用以下的格式：

ADT 抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}

1.2 算法及性能分析

算法通常来说有五个特性：输入、输出、可行性、有穷性和确定性。

1.2.1 渐进时间复杂度

我们假设一些基本操作都可以在一个常数时间内完成。例如，逻辑运算、赋值运算等都是基本操作。这样算法执行的基本操作次数就可以反映算法的运行时间，在后面提到算法的运行时间都是指运行基本操作的次数。

一旦去掉表示算法运行时间中的低阶项和常数项，就称我们在度量算法的渐进时间复杂度。为了进一步说明，我们定义了如下符号Ο、Ω和Θ；

定义算法T(n)如下：

（其中c为某个常数）

也就是表示当时间复杂度为0(n²)。复杂度的定义如下：设T(n)的一个辅助函数，定义为当n大于等于某一个足够大的正整数n₀时，存在两个正的常数A和B（其中A<=B），使得A≤T(n)/g（n）≤B均成立。通俗的来说就是当时n趋近于无穷时，使得T(n)/g（n）= A。 

1. Ο符号

0(n2)解释为只有当排序元素的个数大于某个阈值N时，那么这个对于某个常量c＞0，运行时间最多为cn2。也就是说Ο符号提供了一个运行时间的上界。

1. Ω符号

可以解释为，如果输入大于等于某个阈值N，算法的运行时间的下界是f(n)的c倍，其中c是一个正常数，则称算法的时间复杂度时Ω(f(n))。

1. Θ符号

可以解释为算法的精确阶。

1.2.2 空间复杂度

空间频率：一个算法在执行过程中所占用的内存开销，称为空间频度。

空间复杂度是指在计算机内存中执行所占用的内存开销规模。

2 线性表

线性表是n个类型相同的数据元素的有限序列，通常记作(a₀,a₁,…a_n)。

线性表的ADT类型，定义如下

ADT List {

数据对象：D={a_i|a_i∈D₀，i=0,1,2…n-1，D₀为某一数据对象}

数据关系：R={i,a_i+1>|a_i,a_i+1∈D，i=0,1,2…n-2}

基本操作：

• getSize()返回线性表的大小；
• isEmpty()返回线性表是否为空；
• Contains(e)判断线性表是否含有元素e；
• indexOf(e)返回元素e在线性表中的索引，如果不存在则返回-1；
• insert(i,e)将元素e插入到线性表i中的位置，如果i越界，则报错；
• insertBefore(p,e)将元素e插入到p之前，成功返回true；
• remove(i)删错线性表中索引为i的元素，并返回值；
• remove(e)删错线性表中e元素，成功返回true；
• replace(i,e)替换线性表中索引为i的数据元素为e，返回原数据元素，如果i越界则报错；
• get(i)返回线性表中索引为i的元素，如果i越界则报错。

其中这部分可以翻译成Java代码，就是定义一个List接口，List接口代码如下：

 1 package dataStruct;
 2 
 3 /**
 4  * 如何将抽象数据类型所提供的操作利用Java语言来明确的定义。
 5  * ADT的操作就是在Java中就可以认为是定义一个接口
 6  *
 7  */
 8 
 9 public interface List {
10     
11     /**
12      * 返回线性表的大小，即元素的个数
13      */
14     public int getSize();
15     /**
16      * @return 判断数据元素是否为空
17      */
18     public boolean isEmpty();
19     /**
20      * 判断线性表中是否包含了数据元素e
21      * @param e 
22      * @return 
23      */
24     public boolean contain(Object e);
25     /**
26      * 返回将数据元素e在链表中的序号
27      * @param e
28      * @return
29      */
30     public int indexOf(Object e);
31     /**
32      * 将数据元素e插入到线性表中i号位置
33      * @param i
34      * @param e
35      * @throws OutOfBoundaryException 插入越界异常
36      */
37     public void insert(int i, Object e)throws OutOfBoundaryException;
38     /**
39      * 将数据元素e插入到元素obj之前
40      * @param obj
41      * @param e
42      * @return
43      */
44     public boolean insertBefore(Object obj, Object e);
45     /**
46      * 将数据元素e插入到元素obj之后
47      * @param obj
48      * @param e
49      * @return
50      */
51     public boolean insertAfter(Object obj, Object e);
52     /**
53      * 删除线性表中索引为i的元素，并且返回之
54      * @param i
55      * @return
56      * @throws OutOfBoundaryException
57      */
58     public Object remove(int i)throws OutOfBoundaryException;
59     /**
60      * 删除线性表中第一个元素为e的元素
61      * @param e
62      * @return
63      */
64     public boolean remove(Object e);
65     /**
66      * 替换线性表中索引为i的元素为e
67      * @param i
68      * @param e
69      * @return
70      * @throws OutOfBoundaryException
71      */
72     public Object replace(int i, Object e)throws OutOfBoundaryException;
73     /**
74      * 返回线性表中需要为i的元素
75      * @param i
76      * @return
77      * @throws OutOfBoundaryException
78      */
79     public Object get(int i)throws OutOfBoundaryException;
80  
81 }

 Java中不支持运算符的重载，所以需要使用Strategy接口来实现不同数据元素之间的独立的比较策略。重写类的equal()。我们编写线性表中使用Object来指定数据域，虽然具有很好地通用性，但是不同的数据类型元素互相之间不好比较，需要实现Strategy类来实现不同类之间的比较。Strategy类的接口定义如下：

2.1 Java中的Strategy接口 

 1 package dataStruct;
 2 
 3 /**
 4  * 在List定义的方法中，我们将所有的数据元素都用了Object来代替
 5  * ，具有通用性，但同时不同元素之间的比较策略也需要考虑。
 6  * Strategy策略用来比较两个不同的对象
 7  *
 8  */
 9 public interface Strategy {
10     /**
11      * 判断两个数据元素是否相等
12      * @param obj1
13      * @param obj2
14      * @return
15      */
16     public boolean equal(Object obj1, Object obj2);
17     /**
18      * 比较两个元素之间的大小
19      * if obj1 < obj2 return -1;
20      * if obj1 = obj2 return 1;
21      * if obj1 > obj2 return 1;
22      * @param obj1
23      * @param obj2
24      * @return
25      */
26     public int compare(Object obj1, Object obj2);
27 }

2.2 线性表中的顺序存储和实现

线性表中的顺序存储

 图 2-1 线性表的顺序存储

如果线性表中存放的是对象时，数组存放的是对象的引用，即线性表中所有数据元素的对象引用是存放在一组连续的地址空间中。

图 2-2 数组存储对象的引用

基于线性表的数组实现，编写成ListArray

  1 package dataStruct;
  2 
  3 /**
  4  * 线性表的数组实现 *
  5  */
  6 public class ListArray implements List {
  7     private final int LEN = 8; // 数组的默认大小
  8     private Strategy strategy; // 数据元素的比较策略
  9     private Object[] elements; // 线性表中数据元素的个数
 10     private int size; // 线性表中数据元素的个数
 11     public ListArray() {
 12         this(new DefaultStrategy());
 13     }
 14 
 15     public ListArray(Strategy strategy) {
 16         this.strategy = strategy;
 17         size = 0;
 18         elements = new Object[LEN];
 19     }
 20 
 21     @Override
 22     public int getSize() {
 23         return this.size;
 24     }
 25 
 26     @Override
 27     public boolean isEmpty() {
 28         return size ==0;
 29     }
 30 
 31     @Override
 32     public boolean contain(Object e) {
 33         for(int i=0; i){
 34 //            return strategy.equal(e, elements[i]);
 35             if (strategy.equal(e, elements[i])) {
 36                 return true;
 37             }
 38         }
 39         return false;
 40     }
 41 
 42     @Override
 43     public int indexOf(Object e) {
 44         for(int i=0; i){
 45             if (strategy.equal(e, elements[i])) {
 46                 return i;
 47             }
 48         }
 49         return -1;
 50     }
 51 
 52     @Override
 53     public void insert(int i, Object e) throws OutOfBoundaryException {
 54         if (i<0||i>size) {
 55             throw new OutOfBoundaryException("错误，指定插入索引越界");
 56         }
 57         if(size>=elements.length)
 58             expendSpace(); // 扩展数组
 59         for (int j = size; j>i ; j-- ) {
 60             elements[j] = elements[j-1];
 61         }
 62         elements[i] = e;
 63         size++;
 64     }
 65     /**
 66      * 扩展数组，新数组大小为旧数组的2倍
 67      */
 68     private void expendSpace(){
 69         Object[] a = new Object[elements.length*2];
 70         for (int i = 0; i < elements.length ; i++) {
 71             a[i] = elements[i];
 72         }
 73         elements = a;
 74     }
 75 
 76     @Override
 77     public boolean insertBefore(Object obj, Object e) {
 78         int i = indexOf(obj);
 79         if (i<0) {
 80             return false;
 81         }
 82         insert(i, e);
 83         return true;
 84     }
 85 
 86     @Override
 87     public boolean insertAfter(Object obj, Object e) {
 88         int i = indexOf(obj);
 89         if (i<0) {
 90             return false;
 91         }
 92         insert(i+1, e);
 93         return true;
 94     }
 95 
 96     @Override
 97     public Object remove(int i) throws OutOfBoundaryException {
 98         if (i<0||i>=size) {
 99             throw new OutOfBoundaryException("错误，删除指定索引越界");
100         }
101         Object obj = elements[i];
102         for (int j = i; j < size-1; j++) {
103             elements[j] = elements[j+1]; 
104         }
105         elements[--size] = null;
106         return obj;
107     }
108 
109     @Override
110     public boolean remove(Object e) {
111         int i = indexOf(e);
112         if(i<0) return false;
113         remove(i);
114         return true;
115     }
116 
117     @Override
118     public Object replace(int i, Object e) throws OutOfBoundaryException {
119         if (i<0||i>=size) {
120             throw new OutOfBoundaryException("错误，指定索引越界");
121         }
122         Object obj = elements[i];
123         elements[i] = e;
124         return obj;
125     }
126 
127     @Override
128     public Object get(int i) throws OutOfBoundaryException {
129         if (i<0||i>=size) {
130             throw new OutOfBoundaryException("错误，指定索引越界");
131         }
132         return elements[i];
133     }
134     public void display(){
135         for(int i = 0; i < size; i++){
136             System.out.print(elements[i]+" ");
137         }
138         System.out.println();
139     }
140 
141     public static void main(String[] args) {
142         // 测试的代码的运行
143         ListArray listArray = new ListArray();        
144         for(int i=0; i<10; i++){
145             listArray.insert(i,i);
146         }
147         System.out.println("顺序表的大小:"+listArray.getSize());
148         System.out.println("顺序表是否为空:"+listArray.isEmpty());
149         System.out.println("顺序表是否含有元素1:"+listArray.contain(1));
150         System.out.println("元素1在顺序表中的位置:"+listArray.contain(1));        
151         listArray.display();
152         System.out.println("在索引为10的位置上插入888:");
153         listArray.insert(10, 888);
154         listArray.display();
155         listArray.insertBefore(888, 777);
156         listArray.display();
157         listArray.insertAfter(888, 999);
158         listArray.display();
159         System.out.println("移除索引为8的元素:"+listArray.remove(8));
160         listArray.display();
161         System.out.println("移除元素888:"+listArray.remove((Object)888));
162         listArray.display();
163         System.out.println("替换在索引10处的元素为520:"+listArray.replace(10, (Object)520));
164         listArray.display();
165     }
166 }

2.3.1 单链表2.3 线性表中链式存储和实现

单链表的结构：一个域用于数据元素的存储，一个域用于指向其他单元的指针

图 2-3 单链表结点的结构

Java中没有显示的使用指针，实际上，对象的引用就是使用指针来实现的。也就是在Java中使用对象的引用来替代指针。结点的数据域data可以使用一个Object类型的对象来实现，用于存储任何类型的数据元素，并通过对象的引用指向该元素；而指针域next可以通过结点对象的引用来实现。我们先定义一个Node接口，用来规范所有线性表中结点的特性。

 1 /**
 2  * 单链表中的结点是结点的最简单的一种形式，在Node接口中
 3  * 定义所有结点均支持的操作，即对结点中存储数据的存取
 4  *
 5  */
 6 public interface Node {
 7     /**
 8      * @return 返回结点的数据域
 9      */
10     public Object getData();
11     /**
12      * 设置结点数据域
13      */
14     public void setData(Object obj);
15 }

给出了结点接口定义之后，单链表的结点定义就可以实现结点的接口来完成。 

 1 /**
 2  * 单链表中结点的定义 
 3  */
 4 public class SLNode implements Node {
 5     protected Object element; // 定义数据域
 6     protected SLNode next; // 定义的指针域
 7     public SLNode(){
 8         this(null,null);
 9     }
10     
11     public SLNode(Object obj, SLNode next){
12         this.element = obj;
13         this.next = next;
14     }
15     
16     @Override
17     public Object getData() {
18         return this.element;
19     }
20 
21     @Override
22     public void setData(Object obj) {
23         this.element = obj;
24     }
25 
26 }

 一个单链表（single linked list）的结构如下： 

图 2-4 单链表的结构

在单链表中的查询操作只能从链表的首节点开始，通过每个结点的next引用来一次访问链表中的每个结点以完成相应的查找操作。

图 2-5 在单链表中实现查找操作

图 2-6在单链表中插入结点

单链表的实现代码如下：

  1 package dataStruct;
  2 
  3 /**
  4  * 带头结点的单链表
  5  *
  6  */
  7 public class ListSLinked implements List {
  8     private Strategy strategy; // 数据元素的比较策略
  9     private SLNode head; // 单链表中的头结点
 10     private int size; // 线性表中数据元素的个数
 11     public ListSLinked(){
 12         this(new DefaultStrategy());
 13     }
 14     public ListSLinked(Strategy strategy){
 15         this.strategy = strategy;
 16         head = new SLNode();
 17         size = 0;
 18     }
 19     
 20     /**
 21      * 辅助方法：获取数据元素e所在结点的前驱结点
 22      * @param e
 23      * @return
 24      */
 25     public SLNode getPreNode(Object e){
 26         SLNode p = head;
 27         while (p.next !=null) {
 28             if(strategy.equal(p.next.getData(), e)){
 29                 return p;
 30             }
 31             else {
 32                 p = p.next;
 33             }
 34         }
 35         return null;
 36     }
 37     /**
 38      * 辅助方法：获取序号为0<=i<=size的元素所在的前驱结点
 39      * @param e
 40      * @return
 41      */
 42     public SLNode getPreNode(int i){
 43         SLNode p = head;
 44         for (; i>0 ;i-- ) {
 45             p = p.next;
 46         }
 47         return p;
 48     }
 49     /**
 50      * 辅助方法：获取序号为0<=i<=size的元素所在的结点
 51      * @param e
 52      * @return
 53      */
 54     public SLNode getNode(int i){
 55         SLNode p = head.next;
 56         for (; i>0 ;i-- ) {
 57             p = p.next;
 58         }
 59         return p;
 60     }
 61 
 62     @Override
 63     public int getSize() {
 64         return size;
 65     }
 66 
 67     @Override
 68     public boolean isEmpty() {
 69         return size==0;
 70     }
 71 
 72     @Override
 73     public boolean contain(Object e) {
 74         SLNode p = head.next;
 75         while(p!=null){
 76             if (strategy.equal(p.getData(), e)) {
 77                 return true;
 78             }
 79             else{
 80                 p = p.next;
 81             }
 82         }
 83         return false;
 84     }
 85 
 86     @Override
 87     public int indexOf(Object e) {
 88         SLNode p = head.next;
 89         int index = 0;
 90         while(p!=null){
 91             if (strategy.equal(p.getData(), e)) {
 92                 return index;
 93             }
 94             else{
 95                 index++;
 96                 p = p.next;
 97             }
 98         }
 99         return -1;
100     }
101 
102     @Override
103     public void insert(int i, Object e) throws OutOfBoundaryException {
104         if(i<0||i>size)
105             throw new OutOfBoundaryException("错误，指定插入索引越界");
106         SLNode p = getPreNode(i);
107         SLNode q = new SLNode(e, p.next);
108         p.next = q;
109         size++;
110     }
111 
112     @Override
113     public boolean insertBefore(Object obj, Object e) {
114         SLNode p = getPreNode(obj);            
115         if (p!=null) {
116             SLNode q = new SLNode(e, p.next);
117             p.next = q;
118             size++;
119 //            display();
120             return true;
121         }
122         return false;
123     }
124 
125     @Override
126     public boolean insertAfter(Object obj, Object e) {
127         SLNode p = head.next;
128         while(p!=null){
129             if (strategy.equal(p.getData(), obj)) {
130                 SLNode q = new SLNode(e, p.next);
131                 p.next = q;
132                 size++;
133                 return true;
134             }
135             else
136                 p = p.next;
137         }
138         return false;
139     }
140 
141     @Override
142     public Object remove(int i) throws OutOfBoundaryException {
143         if (i<0||i>=size) {
144             throw new OutOfBoundaryException("错误，删除指定索引越界");
145         }
146         SLNode p = getPreNode(i);
147         Object obj = p.next.getData();
148         p.next = p.next.next;
149         size--;
150         return obj;
151     }
152 
153     @Override
154     public boolean remove(Object e) {
155         SLNode p = getPreNode(e);
156         if (p!=null) {
157             p.next = p.next.next;
158             size--;
159             return true;
160         }
161         return false;
162     }
163 
164     @Override
165     public Object replace(int i, Object e) throws OutOfBoundaryException {
166         if (i<0||i>=size) {
167             throw new OutOfBoundaryException("错误，指定索引越界");
168         }
169         SLNode p = getNode(i);
170         Object obj = p.getData();
171         p.setData(e);
172         return obj;
173     }
174 
175     @Override
176     public Object get(int i) throws OutOfBoundaryException {
177         if (i<0||i>=size) {
178             throw new OutOfBoundaryException("错误，指定索引越界");
179         }
180         SLNode p = getNode(i);
181         return p.getData();
182     }
183     public void display(){
184         SLNode p = head.next;
185         while(p!=null){
186             System.out.print(p.getData()+" ");
187             p = p.next;
188         }
189         System.out.println();
190     }
191 
192     public static void main(String[] args) {
193         ListSLinked LSL1 = new ListSLinked();
194         for(int i = 0; i<10 ; i++){
195             LSL1.insert(i, 2*i-1);
196         }
197         System.out.println("顺序表的大小:"+LSL1.getSize());
198         System.out.println("顺序表是否为空:"+LSL1.isEmpty());
199         System.out.println("顺序表是否含有元素1:"+LSL1.contain(1));
200         System.out.println("元素2在顺序表中的位置:"+LSL1.indexOf(2));        
201         LSL1.display();
202         System.out.println("在索引为10的位置上插入888:");
203         LSL1.insert(10, 888);
204         LSL1.display();
205         System.out.println("测试几个辅助函数：1、获取索引为10的前结点"+LSL1.getPreNode(10).getData()+"--"+LSL1.getPreNode(10).next);
206         System.out.println("测试几个辅助函数：2、获取元素为5的前结点"+LSL1.getPreNode((Object)5).getData()+"--"+LSL1.getPreNode((Object)5).next);
207         System.out.println("测试几个辅助函数：3、获取索引为5的结点"+LSL1.getNode(5).getData()+"--"+LSL1.getPreNode(5).next);
208         LSL1.insertBefore((Object)888, (Object)777);
209         LSL1.display();
210         LSL1.insertAfter(888, 999);
211         LSL1.display();
212         System.out.println("移除索引为8的元素:"+LSL1.remove(8));
213         LSL1.display();
214         System.out.println("移除元素888:"+LSL1.remove((Object)888));
215         LSL1.display();
216         System.out.println("替换在索引10处的元素为520:"+LSL1.replace(10, (Object)520));
217         LSL1.display();
218     }
219 
220 }