java数据结构和算法实现.zip

* [java-Data-structure-and-algorithm](#java-data-structure-and-algorithm) * [java数据结构和算法实现练习](#java数据结构和算法实现练习) * [list线性表](#list线性表) * [线性表接口](#线性表接口) * [数组型线性表实现](#数组型线性表实现) * [链表型线性表的实现](#链表型线性表的实现) * [头节点](#头节点) * [链表](#链表) * [静态链表的实现](#静态链表的实现) * [节点](#节点) * [静态链表](#静态链表) * [双向链表的实现](#双向链表的实现) * [头节点](#头节点-1) * [双向链表](#双向链表) * [循环链表的实现](#循环链表的实现) * [链表的应用之一元多项式相加](#链表的应用之一元多项式相加) * [stack栈](#stack栈) * [栈应用之行编辑器](#栈应用之行编辑器) * [迷宫求解](#迷宫求解) * [表达式求值](#表达式求值) * [汉诺塔问题](#汉诺塔问题) * [队列的接口和元素节点](#队列的接口和元素节点) * [java队列的链表实现](#java队列的链表实现) * [java数组队列的实现](#java数组队列的实现) * [java循环队列的实现](#java循环队列的实现) * [队列应用之离散事件模拟](#队列应用之离散事件模拟) * [String 串](#string-串) * [串的接口定义](#串的接口定义) * [串的数组实现](#串的数组实现) * [串的三种存储结构分析](#串的三种存储结构分析) * [定长顺序存储](#定长顺序存储) * [堆分配存储表示](#堆分配存储表示) * [串的块链存储表示](#串的块链存储表示) * [串的匹配算法](#串的匹配算法) * [遍历算法](#遍历算法) * [tree 树](#tree--树) * [diagram 图](#diagram-图) * [sorting 排序查找](#sorting-排序查找) # java-Data-structure-and-algorithm # java数据结构和算法实现练习 ## `list`线性表 ### 线性表接口 ``` package IntefaceList; public interface IList<T> { /** * 构造一个空的线性表 进行初始化 */ void InitList(); /** * 销毁线性表 */ IList DestroyList(); /** * 将线性表重置为空表 */ IList ClearList(); /** * 判断线性表是否为空 */ Boolean ListEmpty(); /** * 返回线性表中元素的个数 */ Integer ListLength(); /** * 获取线性表中第i个元素 */ T GetElem(Integer i); /** * 根据元素获取它的位序，如果有多个符合，则返回第一个，如果没有则返回0 */ Integer LocateElem(T e); /** * 获取该元素的上一个元素 */ T PriorElem(T e); /** *获取该元素的下一个元素 */ T NextElem(T e); /** * 在指定位置插入元素 */ IList ListInsert(Integer i, T e); /** *删除指定位置的元素 */ IList ListDelete(Integer i); /** * 遍历所有的元素 */ void ListTraverse(); /** * 合并两个线性表 合并不重复的元素 */ IList Union(IList list); /** * 按照递增顺序合并两个线性表 */ IList MergeList(IList list); /** * 在尾部新增元素 */ void add(T e); } ``` #### 数组型线性表实现 ```$xslt package Impl; import IntefaceList.IList; public class SequenceList<T> implements IList { private T[] arr; //数组当前容量(里面实际包含的元素个素) private Integer size = 0; //数组当前大小 private Integer Length = 4; @Override public void InitList() { this.arr = (T[]) new Object[Length]; } @Override public IList DestroyList() { arr = null; size=0; return this; //这里应该直接让list对象为null } @Override public IList ClearList() { this.arr = (T[]) new Object[Length]; size=0; return this; } @Override public Boolean ListEmpty() { if (size > 0) { return Boolean.TRUE; } else { return Boolean.FALSE; } } @Override public Integer ListLength() { return size; } @Override public Object GetElem(Integer i) { if (i > size) { return null; } return arr[i - 1]; } @Override public Integer LocateElem(Object e) { for (int i = 0; i < arr.length; i++) { if (e.equals(arr[i])) { return i + 1; } } return -1; } @Override public Object PriorElem(Object e) { for (int i = 0; i < arr.length; i++) { if (e.equals(arr[i])) { return arr[i - 1]; } } return -1; } @Override public Object NextElem(Object e) { for (int i = 0; i < arr.length; i++) { if (e.equals(arr[i])) { return arr[i + 1]; } } return -1; } @Override public IList ListInsert(Integer i, Object e) { if (i>size){ return null; } size++; addsize(); for (int j = i-1; j <this.size; j++) { arr[size-j]=arr[size-j-1]; } arr[i - 1] = (T) e; return this; } @Override public IList ListDelete(Integer i) { size--; for (int i1 = i - 1; i1 + 1 < arr.length; i1++) { arr[i1] = arr[i1 + 1]; } return this; } @Override public void ListTraverse() { for (int i = 0; i < arr.length; i++) { if (arr[i] != null) { System.out.print(arr[i]); System.out.print(","); } } System.out.println(); } /** * 合并不重复的元素 * * @param list * @return */ @Override public IList Union(IList list) { for (int i = 1; i <= list.ListLength(); i++) { if (this.LocateElem(list.GetElem(i)) == -1) { this.add(list.GetElem(i)); } } return this; } /** * 合并两个列表 从小到大 * * @param list * @return */ @Override public IList MergeList(IList list) { //已知两个表都是递增的顺序 //借助新的第三张表 T[] NewArr = (T[]) new Object[Length + list.ListLength()]; int pa = 1; int pb = 1; int pc = 0; while (pa <= list.ListLength() && pb <= this.ListLength()) { if ((int) list.GetElem(pa) <= (int) this.GetElem(pb)) { NewArr[pc] = (T) list.GetElem(pa); pc++; pa++; } else { NewArr[pc] = (T) this.GetElem(pb); pc++; pb++; } } while (pa<=list.ListLength()){ NewArr[pc] = (T) list.GetElem(pa); pc++; pa++; } while (pb<=this.ListLength()){ NewArr[pc] = (T) this.GetElem(pb); pc++; pb++; } this.arr=NewArr; size=size+ list.ListLength(); return this; } @Override public void add(Object e) { arr[size] = (T) e; size++; addsize(); } /** * 数组扩容 */ private void addsize() { if (size / (float) arr.length > 0.75) { Length = (int) (size * 1.5); T[] Newarr = (T[]) new Object[(Length)]; for (int a = 0; a < arr.length; a++) { Newarr[a] = arr[a];