1 Java数据结构与算法基础
数据的逻辑结构可以采用两个方法来描述：二元组、图形。
数据结构的二元组形式为:
数据结构={D，S}
其中D是数据元素的集合；S是D中数据元素之间的关系集合，并且数据元素之间的关系使用序偶来表示。记作<x,y>,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(n2)。复杂度的定义如下：设T(n)的一个辅助函数，定义为当n大于等于某一个足够大的正整数n0时，存在两个正的常数A和B（其中A<=B），使得A≤T(n)/g（n）≤B均成立。通俗的来说就是当时n趋近于无穷时，使得T(n)/g（n）= A。
- Ο符号
0(n2)解释为只有当排序元素的个数大于某个阈值N时，那么这个对于某个常量c＞0，运行时间最多为cn2。也就是说Ο符号提供了一个运行时间的上界。
- Ω符号
可以解释为，如果输入大于等于某个阈值N，算法的运行时间的下界是f(n)的c倍，其中c是一个正常数，则称算法的时间复杂度时Ω(f(n))。
- Θ符号
可以解释为算法的精确阶。
1.2.2 空间复杂度
空间频率：一个算法在执行过程中所占用的内存开销，称为空间频度。
空间复杂度是指在计算机内存中执行所占用的内存开销规模。
2 线性表
线性表是n个类型相同的数据元素的有限序列，通常记作(a0,a1,…an)。
线性表的ADT类型，定义如下
ADT List {
数据对象：D={ai|ai∈D0，i=0,1,2…n-1，D0为某一数据对象}
数据关系：R={<ai,ai+1>|ai,ai+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<size; 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<size; 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 }