Java造轮子-数据结构-线性表
2017-02-18 本文已影响0人
Rayhaha
数据结构-线性表
@(数据结构)
线性表是数据结构中的逻辑结构。可以存储在数组上，也可以存储在链表上。
顺序表（数组）
简述
用数组来存储的线性表就是顺序表。
优点
- 查找速度快，因为本身是数组的查找
缺点
- 插入和删除都会伴随着大量的元素操作和移动
Java代码造轮子
- 基本方法架构如图:
- 这里我们实现的是大小固定的，当然我们也可以去详细写一个大小根据插入而拓展的就像我们常使用的ArrayList一样。
线性表 顺序表（数组）
*
* MyList(int size) 构造函数指定大小
* void destory() 销毁顺序表对象
* void clear() 清空顺序表内元素
* boolean isEmpty() 判空
* boolean isFull() 判满
* int getLength() 获取当前顺序表长度
* T get(intposition) 根据位置获取顺序表内元素对象
* int getPosition(T t) 根据 元素对象获取顺序表位置
* T prior(T t)获取对象前驱
* T next(T t) 获取对象后继
*
* boolean insert(T t) / insert(int position, T t)
* 向顺序表插入对象，不传位置就默认在最后插入，这里!不是!内部调用insert(int position, T t)
*
* boolean delete(T t) / delete(int position)
* 根据对象或者位置删除顺序表 内元素
*
* void traverse(int position)
* 遍历顺序表
*
* abstract void onTraverse()
* 遍历顺序表得到对象的具体操作
* @author Rayhahah
*
* @param <T> 当前顺序表中的元素对象类型
- 代码实现部分
public abstract class MyList<T> {
private int mCapacity;
private Object[] mList;
private int mLength;
/**
* 构造函数
*
* @param size
* 指定顺序表容量
*/
public MyList(int size) {
mCapacity = size;
mList = new Object[mCapacity];
}
/**
* 摧毁当前顺序表
*/
public void destory() {
clear();
mCapacity = 0;
mList = null;
System.gc();
}
/**
* 清空顺序表 只需要将长度置为0就可以了
* 因为获取表中内容的时候，都需要和length做判断
*/
public void clear() {
mLength = 0;
}
/**
* 判断当前顺序表是否为空
*
* @return 空：true， 非空：false
*/
public boolean isEmpty() {
return mLength == 0;
}
/**
* 判断当前顺序表是否为满
*
* @return 满：true， 未满：false
*/
public boolean isFull() {
return mLength == mCapacity;
}
/**
* 获取当前 顺序表的长度 注意不是容量
*
* @return
*/
public int getLength() {
return mLength;
}
/**
* 根据坐标获取顺序表的元素
*
* @param position
* 坐标
* @return 顺序表元素
*/
public T get(int position) {
// 不满足都返回null
if (position < 0 || position >= mLength || mList == null) {
return null;
}
return (T) mList[position];
}
/**
* 根据传入元素返回元素在顺序表中的坐标
* 判断依据是 元素的地址
*
* @param t
* @return 元素所在坐标
*/
public int getPosition(T t) {
if (isEmpty()) {
return -1;
}
for (int i = 0; i < mLength; i++) {
if (t == mList[i]) {
return i;
}
}
return -1;
}
/**
* 获取传入元素的前驱 判断依据元素的地址
*
* @param t
* @return
*/
public T prior(T t) {
if (isEmpty()) {
return null;
}
for (int i = 1; i < mLength; i++) {
if (t == mList[i]) {
return (T) mList[i - 1];
}
}
return null;
}
/**
* 获取传入元素的后继 判断依据 元素的地址
*
* @param t
* @return
*/
public T next(T t) {
if (isEmpty()) {
return null;
}
for (int i = 0; i < mLength; i++) {
if (t == mList[i]) {
return (T) mList[i + 1];
}
}
return null;
}
/**
* 插入元素，不指定位置默认插入在顺序表的最后
* 如果顺序表已经满了，就返回false 插入成功返回true
*
* @param t
* @return
*/
public boolean insert(T t) {
if (isFull()) {
return false;
}
mList[mLength] = t;
mLength++;
return true;
}
/**
* 向指定位置插入元素，其他元素向后退一位
*
* @param position
* @param t
* @return
*/
public boolean insert(int position, T t) {
T tar = t;
T temp = null;
// 满了以后长度不再变化
if (!isFull()) {
mLength++;
}
for (int i = position; i < mLength; i++) {
if (temp != null) {
tar = temp;
}
temp = (T) mList[i];
mList[i] = tar;
}
return true;
}
/**
* 删除顺序表中的指定元素
*
* @param t
* @return
*/
public boolean delete(T t) {
if (isEmpty()) {
return false;
}
T temp = null;
boolean flag = false;
for (int i = 0; i < mLength; i++) {
//找到删除元素以后就开始将后面元素前移
if (t == mList[i]) {
mLength--;
if (i == mLength) {
return true;
}
flag = true;
}
if (i != mLength) {
temp = (T) mList[i + 1];
}
if (flag) {
mList[i] = temp;
if (i == mLength) {
return true;
}
}
}
return false;
}
/**
* 删除顺序表中的指定位置的元素
*
* @param position
* @return
*/
public boolean delete(int position) {
if (isEmpty() || position >= mLength || position < 0) {
return false;
}
for (int i = position; i < mLength; i++) {
System.out.println(i);
if (i + 1 >= mLength) {
mLength--;
return true;
}
mList[i] = mList[i + 1];
System.out.println(mList[i]);
}
return true;
}
/**
* 默认遍历为遍历整个顺序表
*/
public void traverse() {
traverse(0);
}
/**
* 指定开始遍历的位置
*
* @param position
*/
public void traverse(int position) {
for (int i = position; i < mLength; i++) {
onTraverse((T) mList[i]);
}
}
/**
* 遍历得到元素所需要的具体操作
* 交回给用户自己确定
*
* @param t
*/
public abstract void onTraverse(T t);
}
链表
单链表
- 单向性：链表中的节点只会指向另一个节点，最后的节点指向null
单链表.png
循环链表
- 形成回路：与单链表最大的区别就是尾节点指向头结点
循环链表.png
双向链表
- 每个节点都会指向它的"前节点"和"后节点"
- 头结点的"前节点"指向为null，尾节点的"后节点"指向为null
双向链表.png
静态链表
- 对于没有指针的语言，就要使用静态链表
- 使用数组，每个节点的指向就是保存它指向节点的数组中的坐标
静态链表.png
代码造轮子
- 在这里我只做了单链表的代码实现，其他的链表其实也是触类旁通
- 这里的功能我只做了基本的方法，想要深入研究的朋友可以参考一下Java源码的LinkedList相信一定可以有所收获
- 基本结构：
* MyLinkedList() 构造函数
* void clearList() 清空链表数据
*
* boolean isEmpty() 链表判空
* int getLength() 链表的当前长度
*
* T get(int position) 根据坐标获取链表中的元素
* int getPosition(T t) 根据数据对象获取在链表中的位置坐标
*
* boolean insert(T t) / insert(int position,T t)
* 向链表末尾插入数据对象 / 向指定位置插入数据对象
*
* boolean delete(T t) / delete (int position)
* 删除在链表中的传入数据对象 / 删除指定位置的节点
*
* void traverse(int position)
* 启动遍历链表
* abstract void onTraverse()
* 遍历顺序表得到对象的具体操作
*
* @author Rayhahah
*
* @param <T>
* 链表储存的数据对象类型
- 具体代码实现：
public abstract class MyLinkedList<T> {
private MyNode<T> first;
private int mLength;
public MyLinkedList() {
first = new MyNode<T>(null, null);
mLength = 0;
}
/**
* 判空
*
* @return
*/
public boolean isEmpty() {
return mLength == 0;
}
/**
* 清空链表
*/
public void clear() {
for (MyNode<T> temp = first; temp != null;) {
MyNode<T> next = temp.next;
temp.next = null;
temp.t = null;
temp = next;
}
mLength = 0;
}
/**
* 节点是否为空
*
* @param myNode
* @return
*/
private boolean isNodeNull(MyNode<T> myNode) {
if (myNode.next == null && myNode.t == null) {
return true;
}
return false;
}
/**
* 向链表最后插入节点
*
* @param t
* @return
*/
public boolean insert(T t) {
return insert(mLength, t);
}
/**
* 向指定位置插入及节点
*
* @param position
* @param t
* @return
*/
public boolean insert(int position, T t) {
if (position < 0 || position > mLength) {
return false;
}
mLength++;
MyNode<T> currentNode = first;
MyNode<T> currentNodeBefore = null;
//插入位置是头节点的情况
if (position == 0) {
MyNode<T> newNode = new MyNode<T>(t, first);
first = newNode;
return true;
}
for (int i = 0; i < position; i++) {
currentNodeBefore = currentNode;
currentNode = currentNode.next;
}
//指向后节点
MyNode<T> newNode = new MyNode<>(t, currentNode);
//前节点指向新节点就等于插入
currentNodeBefore.next = newNode;
return true;
}
/**
* 根据坐标删除节点
*
* @param position
* @return
*/
public boolean delete(int position) {
if (position < 0 || position >= mLength) {
return false;
}
mLength--;
if (position == 0) {
return deleteFirst(first.next);
}
MyNode<T> currentNode = first;
MyNode<T> currentNodeBefore = null;
for (int i = 0; i < position; i++) {
currentNodeBefore = currentNode;
currentNode = currentNode.next;
}
//将要删除的节点的前节点指向 要删除的节点的后节点
//失去了联系节点就等于被删除了
currentNodeBefore.next = currentNode.next;
return true;
}
/**
* 清楚头节点数据
*
* @param node
* @return
*/
private boolean deleteFirst(MyNode<T> node) {
first = node;
return true;
}
/**
* 删除包含有该数据对象的节点数据
*
* @param t
* @return
*/
public boolean delete(T t) {
if (isEmpty()) {
return false;
}
mLength--;
// 现在节点
MyNode<T> currentNode = first;
// 前节点
MyNode<T> currentNodeBefore = null;
while (currentNode.t != null) {
if (currentNode.t == t) {
// 头节点
if (currentNodeBefore == null) {
first = currentNode.next;
} else {
currentNodeBefore.next = currentNode.next;
}
return false;
}
currentNodeBefore = currentNode;
currentNode = currentNode.next;
}
return false;
}
/**
* 根据坐标返回数据对象
*
* @param position
* 坐标
* @return 数据对象
*/
public T get(int position) {
if (position < 0 || position >= mLength) {
return null;
}
MyNode<T> currentNode = first;
// 移动至position就可以找到需要的数据对象了
for (int i = 0; i < position; i++) {
currentNode = currentNode.next;
}
return currentNode.t;
}
/**
* 根据传入元素获取在链表中的坐标
*
* @param t
* 需要查找坐标的对象
* @return 坐标
*/
public int getPosition(T t) {
if (isEmpty()) {
return -1;
}
int count = 0;// 获取当前查找到的坐标
MyNode<T> currentNode = first;
while (currentNode != null) {
// 找到元素就返回
if (currentNode.t == t) {
return count;
}
count++;
currentNode = currentNode.next;
}
return -1;
}
/**
* 遍历整个链表
*/
public void traverse() {
MyNode<T> currentNode = first;
while (currentNode.t != null) {
onTraverse(currentNode.t);
currentNode = currentNode.next;
}
}
/**
* 遍历时对每个元素具体的操作
*
* @param t
*/
public abstract void onTraverse(T t);
}
最后
线性表是平常我们会用到非常多的一个数据结构，虽然自己造轮子并没有什么卵用
不过对于我们思维联想的提升，我相信还是有点帮助的
附上 数据结构项目的GitHub:
https://github.com/Rayhahah/DataStructure
