首页 > 代码库 > 数据结构和算法(Java版)
数据结构和算法(Java版)
主要内容：（内容来自互联网以及李刚著作的《突破程序员基本功的16课》）
1.数据结构：线性表、栈、队列、树&二叉树
2.算法：常用内部排序（选择、插入、交换、归并）
目录：
1. 线性表（顺序存储、链式存储单链表、双向链表）-------------2014/10/15
2. 栈(顺序栈、链栈) -------------2014/10/15
线性表（顺序存储、链式存储）：一对一松耦合关系。（List就是线性表的意思）
基本特征(非空、有限的线性表)
1. 首位元素唯一
2. 除最后一个元素外，每个元素只有一个后继元素
3. 除第一个元素外，每个元素只有一个前驱元素
基本操作：
1. 初始化（构造器、创建空的线性表）
2. 返回长度（元素个数）
3. 获取指定索引处的元素
4. 查找数据元素的索引 （仅仅返回找到的第一个，没找到则返回-1）
5. 指定位置插入元素（长度+1）
6. 尾部插入元素（长度+1）
7. 删除指定位置的元素（长度-1）
8. 删除尾部的元素（长度-1）
顺序结构：SequenceList
1. 逻辑地址和物理地址一致（逻辑上连续表现为物理地址上的连续）
2. 地址的计算 : an=a0+nb; （b表示每个元素的存储单元大小）
3. 从2的公式看的出访问表中任意一个元素不存在时间上时间上的差异，即顺序结构可以实现随机访问(查找快)
4. 增删比较麻烦（操作决定它要腾挪和变化容量）
------------------------------------------------------------------------------------------------------------------------
链式结构：LinkList
1. 不能随机访问
2. 插入删除效率比较高
顺序结构实现
import java.util.Arrays;public class SequenceList<T> { private final int DEFAULT_SIZE = 16; //定义一个常量 private int capacity = DEFAULT_SIZE; //保存数组的容量 private Object[] elementData; //用数组实现 private int size=0; //数组当前元素个数 public SequenceList() //1.创建一个链表并且初始化 { elementData = new Object[capacity]; } public SequenceList(T element)//以一个元素为基础创建链表 { this(); elementData[0]=element; size++; } public SequenceList(int initSize) //指定初始容量 { //最好要先判断一个传进来的参数 //指定的容量是2的n次方 capacity = 1; while(capacity<initSize) { capacity<<=1; } elementData = new Object[capacity]; } public int Length() //2.获取list的大小 { return size; } public T get(int index) //3.获取指定索引处的元素 { //传进来的参数一定要判断其合法性 if(index<0 || index>size-1) { throw new IndexOutOfBoundsException("数组下标越界"); } return (T)elementData[index]; } public int indexOf(T element) //4.查找指定元素的索引 { for(int i=0;i<capacity;i++) { if(element.equals(elementData[i])) { return i; } } return -1; } public void insert(T element,int index) //5.在指定位置插入一个元素 { if(index<0 || index>size) { throw new IndexOutOfBoundsException("数组下标越界"); } //先处理数组长度问题,保证数组长度增加后仍然安全 if((size+1)>capacity) { //容量不够了,扩容，把原数组copy到新数组 while(capacity<(size+1)) { capacity <<=1; } elementData = Arrays.copyOf(elementData, capacity); //效率不好 } //把index处的数组元素后移 System.arraycopy(elementData,index,elementData,index+1,size-index); elementData[index]=element; size++; } public void insertLast(T element) //6.在尾部新增一个元素 { insert(element,size); //注意尾部是size而不是capacity } public T remove(int index) //7.删除指定位置的元素 { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException("线性表索引越界"); } T oldValue = (T)elementData[index]; int numMoved = size - index - 1; //index后面多少个元素都要前移 if(numMoved>0) { System.arraycopy(elementData, index+1, elementData, index, numMoved); } elementData[--size] = null; return oldValue; } public T removeLast() //8.删除尾部的元素 { return remove(size-1); } public boolean empty() //判断表是否为空 { return size==0; } public void clear() //清空线性表 { Arrays.fill(elementData, null); size=0; } public String toString() //以字符串输出 { if(size==0) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(int i=0;i<size;i++) { //取出一个元素加上一个逗号 sb.append(elementData[i].toString()+", ");//逗号+空格 } //删除最后一个“逗号和空格”，加上"]" [3,4,5, int length = sb.length(); return sb.replace(length-2, length, "]").toString(); } } }
单链表
public class LinkList<T> { //内部类Node代表节点 private class Node { private T data; //保存节点的数据 private Node next; //指向下一个节点 public Node(){} public Node(T data, LinkList<T>.Node next) { super(); this.data =http://www.mamicode.com/ data; this.next = next; } } private Node header; //保存该链表的头结点 private Node tail; //保存该链表的尾节点 private int size; //保存该链表的节点数 public LinkList() //创建空链表 { header = null; tail = null; } public LinkList(T element) //以一个元素来初始化链表 { header = new Node(element,null); //只有一个节点 tail = header; size++; } public int length() //获取链表的长度 { return size; } public T get(int index) //根据索引获取某元素的数据 { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException("链表越界"); } Node current = header; for(int i=0;current!=null && i<size;i++) { if(i == index) { return current.data; } } current = current.next; return null; } public int indexOf(T element) //获取链表中指定元素的索引 { Node current = header; for(int i=0;i<size && current!=null;i++ , current=current.next ) //要返回索引所以必须在循环里也写上i { if(current.data.equals(element)) { return i; } } return -1; } public void insert(T element,int index) //向线性表的指定索引后新增一个元素 { if(index <0 || index>size) //可以向链表的最后添加一个元素 { throw new IndexOutOfBoundsException("线性表下标越界"); } if(header == null) //如果还是空链表 { addAtLast(element);//尾插法 } else { //获取插入的前一个节点 Node pre = header; for(int i=0;i<index-1;i++) { pre=pre.next; } pre.next = new Node(element,pre.next); //让新节点只想原来pre.next节点 size++; } } private void addAtLast(T element) //尾插法--被insert(T，int)调用 { header = new Node(element,null); tail = header; //只有一个节点，header和tail都指向它 size++; } public void addAtHeader(T element)//头插法 { //总是以新节点作为头结点 header = new Node(element,header); //不管原来的头结点是否为空 size++; } public T delete(int index) //删除链式表指定处的元素 { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException("链表索引错误"); } //删除头节点有点特殊 Node del = header; if(index == 0) { header = header.next; del.next=null; //让原来的头结点的下一个指向null //del = null; //让原来的头结点失去引用 } else { Node pre = header; for(int i =0;i<index-1;i++) //让pre指向index-1节点 { pre = pre.next; } del = pre.next; //del指向了index pre.next = pre.next.next; del.next=null; //让需要删除的节点的下一指向指向null } size--; return del.data; } public T deleteLast() //删除最后一个元素 { return delete(size-1); } public boolean empty() //判断链表是否为空 { return size ==0; } public void clear() //清空链表 { // Node pre =header; Node current = pre.next; for(;current!=null;current =current.next) { pre.next = null; pre = current; } //pre.next = null; tail = null; size = 0; } public String toString() { if(empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(Node current = header;current !=null;current=current.next) { sb.append(current.data.toString()+", "); } int len = sb.length(); return sb.replace(len-2, len, "]").toString(); } }}
循环链表(circular linked list)---无头无尾链表 （从链表中任一节点出发均可以找到表中其他所有节点）
（算法实现更容易，让tail.next = header即可）
（头插法和尾插法均可）
（当使用单链表比较麻烦的时候，可以考虑这种实现）
双向链表(double linked list------DbLinkedList)
保存前驱引用和后继引用，所以维护成本略大
public class DbLinkedList<T> { private class Node //内部节点类 { private T data; private Node prev; private Node next; public Node(){} public Node(T data, Node prev, DbLinkedList<T>.Node next) { super(); this.data =http://www.mamicode.com/ data; this.prev = prev; this.next = next; } } private Node header; //保存该链表的头结点 private Node tail; //保存链表的尾节点 private int size; //包含链表中已包含的节点数 public DbLinkedList() { //空链表的header 和 tail都是null header = null; tail = null; } public DbLinkedList(T element) //以特定的元素构建链表 { header = new Node(element,null,null); //只有一个节点,header,tail都指向该节点 tail = header; size++; } public int length()//返回链表的长度 { return size; } public T get(int index)//获取链式线性表中索引为index处的元素 { return getNodeByIndex(index).data; } private Node getNodeByIndex(int index) //根据索引获取 { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException("线性表下标越界"); } if(index<=size/2) { //header节点开始 Node current = header; for(int i=0;i<size/2&¤t!=null; i++,current=current.next)//索引靠前就用 { if(i==index) { return current; } } } else { //从tail节点开始搜索 Node current = tail; for(int i=size-1;i>size/2&¤t!=null; i--,current=current.prev) { if(i == index) { return current; } } } return null; } public int indexOf(T element) //获取指定元素的下标 { Node current = header; for(int i=0;i<size && current!=null;i++,current=current.next) { if(current.data.equals(element)) { return i; } } return -1; } public void insert(T element,int index)//向指定位置插入一个元素 { if(index<0 || index> size) //可向链表的最后一个元素后面插入元素 { throw new IndexOutOfBoundsException("下标越界"); } if(header==null) { addLast(element); //尾插法 } else { //当index为0的时候，也就是在表头插入 if(index==0) { addAtHeader(element); } else //中间插入 { Node prev = getNodeByIndex(index-1); //获取插入节点的前一个节点 Node next = prev.next; //获取插入节点 Node newNode = new Node(element,prev,next); prev.next = newNode; next.prev = newNode; size++; } } } public void addLast(T element) //尾插法实现 { if(header == null) { header = new Node(element,null,null); tail = header; } else { //找到尾节点 Node newNode = new Node(element,tail,null); tail.next = newNode; tail = newNode; } size++; } public void addAtHeader(T element) //采用头插法 { //创建新节点的next指向header,并把它作为新的list头 header = new Node(element,null,header); if(tail == null) { tail = header; } size++; } public T delete(int index) //删除指定索引的元素 { if(index<0 || index>size -1) { throw new IndexOutOfBoundsException("线性表索引越界"); } Node del = null; //用于返回要删除元素的值 if(index==0) //删除头结点 { del = header; header = header.next; //让head指向原来的header的next header.prev = null; //新header的prev指向null } else { Node prev = getNodeByIndex(index-1); //获取要删除的前一个节点 del = prev.next; //获取要删除的元素 //开始处理互相引用 prev.next = del.next; if(del.next!=null) { del.next.prev = prev; } del.prev = null; del.next = null; } size--; return del.data; } public T deleteLast() //删除链式线性表中的最后一个元素 { return delete(size-1); } public boolean empty() //判断是否为空 { return size==0; } public void clear() { //前向和后项全部要置为null } public String toString() { if(empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(Node current = header;current !=null;current=current.next) { sb.append(current.data.toString()+", "); } int len = sb.length(); return sb.replace(len-2, len, "]").toString(); } } public String reverseToString() { if(empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(Node current = tail;current!=null;current = current.prev) { sb.append(current.data.toString()+", "); } int len=sb.length(); return sb.replace(len-2,len, "]").toString(); } }}
小结：线性表就是加强操作的动态数组，充当容器的工具类。
Java中的实现（ArrayList，LinkedList，其中LinkedList还是双向链表）
----------------------------------------------------------------------------------------------------------------------------
栈和队列----功能弱化的线性表(功能受到限制，比方说增删只能在首尾)
(广度优先遍历的时候用到队列 保存节点)
(实现递归---栈)
---------------------------------------------------------------------------------------------------------------------------
Stack(栈--栈顶插入删除)
1. pop出栈、push入栈、LIFO
2. 常用操作：
a. 初始化：构造器中，创建空栈
b. 返回栈的长度：返回栈中元素的个数
c. 入栈：栈顶插入一个元素，长度+1
d. 出栈：栈顶删除一个元素，长度-1
e. 访问栈顶元素：返回栈顶元素但是不删除元素
f. 判断栈是否为空
g. 清空栈
3. 顺序栈(当插入元素满了之后，要考虑数组容量重新定义)
import java.util.Arrays;public class SequenceStack<T> //顺序栈{ private int DEFAULT_SIZE=10; private int capacity; //数组容量 private int capacityIncrement = 0; //程序每次增加的数组长度 private Object[] elementData; private int size=0; //当前元素的个数 public SequenceStack() //创建一个空栈 { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } public SequenceStack(T element) //用一个元素来初始化栈 { this(); elementData[0] = element; size++; } public SequenceStack(T element,int initSize, int capacityIncrement) //指定增长容量 { this.capacity = initSize; this.capacityIncrement = capacityIncrement; elementData = new Object[capacity]; elementData[0] = element; size++; } public int length() //获取顺序栈的大小 { return size; } public void push(T element) //入栈 { ensureCapacity(size+1); //size+1即当前所需要的容量 elementData[size++] = element; } private void ensureCapacity(int minCapacity) //性能不是很好 { if(minCapacity>capacity) //供不应求 { if(capacityIncrement >0) //增量为正数 { while(capacity<minCapacity) { capacity += capacityIncrement; } } else //没有指定增长容量的时候，就直接采用翻倍的方法 { while(capacity<minCapacity) { capacity <<=1; } } elementData = Arrays.copyOf(elementData, capacity); // } } public T pop() //出栈:1.获取栈顶元素 2.栈元素的数量-1 3.原来栈顶引用为空 { T oldValue = (T) elementData[size-1]; elementData[--size] = null;//这1步可写成2步:--size; elementData[size]=null return oldValue; } public T peek() //取出栈顶元素 { return (T)elementData[size-1]; } public boolean isEmpty() //判断栈是否为空 { return size==0; } public void clear() //清空栈 :数组元素的引用置为空;元素个数为空 { Arrays.fill(elementData, null); size = 0; } public String toString() { if(size==0) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(int i=size-1;i>-1;i--) //需要倒序输出 { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.replace(len-2, len, "]").toString(); } }}
4. 链栈（top保存栈顶元素的引用，size记录当前栈中保存元素的个数）
入栈---头插法,size+1
出栈---释放引用,size-1
(头插法实现了FILO)
public class LinkStack<T> { private class Node { private T data; private Node next; //指向下一个节点 public Node(){} public Node(T data, LinkStack<T>.Node next) { super(); this.data =http://www.mamicode.com/ data; this.next = next; } } private Node top; //保存该栈的栈顶元素 private int size; //保存节点个数 public LinkStack()//空栈 { top = null; } public LinkStack(T element) //只有一个元素的栈 { top = new Node(element,null); size++; } public int length() //获取栈的长度 { return size; } public void push(T element) //入栈 { top = new Node(element,top); size++; } public T pop() { Node oldTop = top; top = top.next; //原来top的指向改变 oldTop.next = null; size--; return oldTop.data; } public T peek() //取栈顶元素 { return top.data; } public boolean isEmpty() //判断是否为空 { return size==0; } public void clear() { top = null; size = 0; } public String toString() { if(isEmpty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for(Node current = top; current!=null; current = current.next) { sb.append(current.data.toString()+", "); } int len = sb.length(); return sb.replace(len - 2, len, "] ").toString(); } } }
（整体而言，栈基本用不到顺序结构的随机访问功能，所以一般采用链栈）
（Java中Vector实现了List接口，Stack继承了Vector，所以Stack是线程安全的）
（Java.util.LinkedList提供了pop()、push()、peek()，所以它可以当做栈来使用）
-----------------------------------------------------------------未完待续----------------------------------------------------
数据结构和算法(Java版)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。