Java数据结构 —— 手写线性结构（稀疏数组、栈、队列、链表）

目录

稀疏数组

顺序表

链表

单向顺序链表

双向链表

双向循环链表求解约瑟夫环（Joseph）

栈

顺序栈

 队列

 顺序队列

顺序循环队列

---

稀疏数组

当一个数组中大部分值为0,或者相同时，可以采用稀疏数组的方式来保存，从而节约存储空间，提高存储效率。

稀疏数组的存储格式为：

• 记录数组一共有几行几列，有多少不同的值
• 把具有不同值的元素的行和列以及值保存在一个小规模的数组中，实现压缩存储的效果

如下：

public class SparseArray {public static void keepData(int[][] arr) {ObjectOutputStream oos = null;try {oos = new ObjectOutputStream(new FileOutputStream("src\\sparseData.dat"));oos.writeObject(arr);} catch (IOException e) {e.printStackTrace();} finally {if(oos != null) {try {oos.close();} catch (IOException e) {e.printStackTrace();}}}}public static int[][] returnSparseData() {ObjectInputStream ois = null;int[][] data = null;try {ois = new ObjectInputStream(new FileInputStream("src\\sparseData.dat"));data = (int[][])ois.readObject();} catch (IOException | ClassNotFoundException e) {e.printStackTrace();} finally {if(ois != null) {try {ois.close();} catch (IOException e) {e.printStackTrace();}}}return data;}public static void main(String[] args) {//已有的二维数组int row = 11;int col = 11;int[][] chessArr = new int[row][col];chessArr[1][2] = 1;chessArr[2][3] = 2;chessArr[5][5] = 5;//将以有的二维数组转换为稀疏数组节省存储空间int count = 0;  //用于统计二维数组中非零元素的个数for (int[] arr : chessArr) {for (int data : arr) {if (0 != data) {count++;}}}//创建稀疏数组int[][] sparseArr = new int[count + 1][3];sparseArr[0][0] = row;sparseArr[0][1] = col;sparseArr[0][2] = count;//将二维数组中非零元素的值保存在稀疏数组中int rowOfSparse = 0;for (int i = 0; i < chessArr.length; i++) {for (int j = 0; j < chessArr[i].length; j++) {if (chessArr[i][j] != 0) {sparseArr[++rowOfSparse][0] = i;sparseArr[rowOfSparse][1] = j;sparseArr[rowOfSparse][2] = chessArr[i][j];}}}//将稀疏数组还原成二维数组int[][] objArr = new int[sparseArr[0][0]][sparseArr[0][1]];for (int i = 0; i < count; i++) {objArr[sparseArr[i+1][0]][sparseArr[i+1][1]] = sparseArr[i+1][2];}for(int[] arr : objArr) {for (int data : arr) {System.out.printf("%d\t",data);}System.out.println();}//将稀疏数组的数据保存到磁盘中keepData(sparseArr);//将磁盘中的稀疏数组进行恢复int[][] arrOriginal = returnSparseData();for (int[] arr : arrOriginal) {for (int data : arr) {System.out.printf("%d\t",data);}System.out.println();}}
}

---

顺序表

Java描述的顺序表

public class SequenceList_ {private int[] elements; //存放顺序表中的元素private int length; //顺序表的长度private final int maxSize;public void listSequence() {if (isEmpty()) {System.out.println("顺序表为空，无法进行遍历");}for (int i = 0; i < length; i++) {System.out.print(elements[i] + " ");}}public SequenceList_(int maxSize) {this.elements = new int[maxSize];this.length = 0;this.maxSize = maxSize;}public void clear() {this.length = 0;}public boolean isFull() {return length == maxSize;}public boolean isEmpty() {return length == 0;}public int getLength() {return length;}public int get(int index) {//对输入的index的范围进行检验if (index < 0 || index > maxSize - 1) {throw new ArrayIndexOutOfBoundsException("输入的索引位置不正确");}if (index > length - 1) {throw new ArrayIndexOutOfBoundsException("输入的索引位置还未插入元素！");}return elements[index];}public void addElement(int val) {if (isFull()) {System.out.println("线性表已满，无法继续插入元素!");}elements[length++] = val;}public void addElement(int val, int index) {if (isFull()) {System.out.println("线性表已满，无法继续添加！");}if (index < 0 || index > maxSize - 1) {System.out.println("索引位置不正确");}for (int i = length - 1; i >= index; i--) {elements[i + 1] = elements[i];}elements[index] = val;if (index > length - 1) {length = index + 1;} else {length++;}}public int indexOf(int val) {for (int i = 0; i < this.length; i++) {if (val == elements[i]) {return i;}}return -1;}public int remove(int index) throws Exception {if (index < 0 || index > maxSize - 1) {throw new Exception("索引位置不正确");}if (index > length - 1) {throw new Exception("在该位置没有元素");}int value = elements[index];for (int i = index; i < length - 1; i++) {elements[i] = elements[i + 1];}length--;return value;}public void updateElement(int val, int index) throws Exception {if (index < 0 || index > maxSize - 1) {throw new Exception("索引位置不正确");}if (index > length - 1) {throw new Exception("索引位置为空，无法更新");}elements[index] = val;}
}

---

链表

单向顺序链表

Java实现的单向顺序链表：

public class SingleLinkedList {private ListNode head;//链表的头结点private ListNode foot;//始终指向链表的末尾结点private boolean sequence;//链表是否有序public class ListNode { //表示链表节点的内部类public int val;    //节点的数据域public ListNode next;   //节点的指针域public ListNode(int val) {this.val = val;}}public SingleLinkedList() {this.head = new ListNode(0);//初始化头结点this.foot = this.head;}public SingleLinkedList(boolean sequence) {this.head = new ListNode(0);this.foot = head;this.sequence = true;}public void listLinkedElement() {ListNode temp = head.next;while (temp != null) {System.out.printf("%d\t", temp.val);temp = temp.next;}System.out.println();}public boolean isEmpty() {return head.next == null;}public int getSize() {int count = 0;ListNode listNode = head.next;while (listNode != null) {count++;listNode = listNode.next;}return count;}/*** 头插法插入元素** @param val 待插入节点数据域的值*/public void addElementAtHead(int val) {ListNode listNode = new ListNode(val);listNode.next = head.next;head.next = listNode;System.out.println("添加成功");}/*** 尾插法插入元素*/public void addElementAtFoot(int val) {ListNode listNode = new ListNode(val);foot.next = listNode;foot = listNode;    //将foot指针指向尾结点System.out.println("添加成功");}public void addElementIndex(int index, int val) {//对插入位置进行检验if (index < 0 || index > getSize() + 1) {System.out.println("插入的位置不正确！");}ListNode listNode = new ListNode(val);//找到第index个元素前面的一个元素ListNode temp = head;for (int i = 0; i < index; i++) {temp = temp.next;}listNode.next = temp.next;temp.next = listNode;System.out.println("插入成功！");}public void deleteElementAtHead() {if (isEmpty()) {throw new RuntimeException("链表为空，无法继续删除!");}head.next = head.next.next; //删除链表的首个节点System.out.println("删除成功！");}public void deleteElementAtFoot() {if (isEmpty()) {throw new RuntimeException("链表为空，无法继续删除!");}ListNode temp = head;while (temp != null) {if (temp.next == foot) {foot = temp;foot.next = null;}temp = temp.next;}System.out.println("删除成功!");}/*** 按照索引删除元素** @param index*/public void deleteEmementIndex(int index) {//对index的值进行检验if (index < 0 || index > getSize()) {System.out.println("要删除元素的索引不正确！");}ListNode temp = head;for (int i = 0; i < index; i++) {temp = temp.next;}temp.next = temp.next.next;System.out.println("删除成功！");}public boolean contains(int value) {if (isEmpty()) {return false;}ListNode temp = head.next;while (temp != null) {if (temp.val == value) {return true;}temp = temp.next;}return false;}/*** 清空单链表中的数据*/public void clear() {head.next = null;foot = null;}public void addElementSequence(int val) {if (sequence) {ListNode listNode = new ListNode(val);ListNode temp = head;while (true) {if (temp.next == null) {temp.next = listNode;break;}if (temp.next.val > val) {listNode.next = temp.next;temp.next = listNode;break;}temp = temp.next;}System.out.println("添加成功！");} else {this.addElementAtFoot(val);}}
}

双向链表

Java描述的双向链表

public class DoubleLinkedList {public class ListNode_ {public int data;public ListNode_ next;public ListNode_ pre;public ListNode_() {}public ListNode_(int val) {this.data = val;}public ListNode_(int data, ListNode_ pre, ListNode_ next) {this.data = data;this.pre = pre;this.next = next;}}private ListNode_ head;private ListNode_ first;    //记录头结点private ListNode_ last;     //记录尾结点private int length;         //记录链表的长度public DoubleLinkedList() {this.head = new ListNode_();this.last = null;this.first = null;this.length = 0;}public boolean isEmpty() {return head.next == null;}public ListNode_ getFirst() {return first;}public ListNode_ getLast() {return last;}public void insertInto(int val) {ListNode_ newNode = new ListNode_(val);ListNode_ oldLast = this.last;if (isEmpty()) {newNode.pre = head;head.next = newNode;this.first = newNode;this.last = newNode;length++;return;}//链表不为空newNode.pre = oldLast;oldLast.next = newNode;last = newNode;length++;}public void insertInto(int index, int val) {if (index < 0 || index > length) {System.out.println("插入的index位置大于链表的长度");return;}ListNode_ newNode = new ListNode_(val);//判断是否为最后一个节点if (index == length - 1) {ListNode_ oldLast = last;oldLast.next = newNode;newNode.pre = oldLast;last = newNode;} else if (index == 0) {ListNode_ oldFirst = first;head.next.pre = newNode;newNode.next = head.next;newNode.pre = head;head.next = newNode;} else {ListNode_ cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}newNode.next = cur.next;newNode.pre = cur;cur.next.pre = newNode;cur.next = newNode;}length++;}public int get(int index) throws Exception {if (index < 0 || index > length - 1 || isEmpty()) {throw new Exception("index索引错误||链表为空");}ListNode_ cur = head.next;for (int i = 0; i < index; i++) {cur = cur.next;}return cur.data;}public int indexOf(int val) throws Exception {if (isEmpty()) {throw new Exception("链表为空");}ListNode_ cur = head.next;for (int i = 0; i < length; i++) {if (cur.data == val) {return i;}cur = cur.next;}return -1;}public int remove(int index) throws Exception {if (index < 0 || index > length - 1 || isEmpty()) {throw new Exception("链表中没有index索引||链表为空");}//最后一个节点if (index == length-- - 1) {ListNode_ oldLast = last;last = oldLast.pre;oldLast.pre.next = null;oldLast.pre = null;return oldLast.data;}//第一个节点if (index == 0) {ListNode_ oldFirst = first;oldFirst.next.pre = head;head.next = oldFirst.next;oldFirst.pre = oldFirst.next = null;first = head.next;return oldFirst.data;}ListNode_ cur = head.next;for (int i = 0; i < index; i++) {cur = cur.next;}cur.next.pre = cur.pre;cur.pre.next = cur.next;cur.next = cur.pre = null;return cur.data;}private void listDoubleLinkedList() {ListNode_ cur = head.next;while (cur != null) {System.out.print(cur.data + " ");cur = cur.next;}}public void listDoubleLinkedList(boolean reverse) {if (isEmpty()) {System.out.println("链表为空，无法遍历");return;}if (reverse) {ListNode_ cur = last;while (cur != head) {System.out.print(cur.data + " ");cur = cur.pre;}} else {listDoubleLinkedList();}System.out.println();}public int getLength() {return length;}
}

双向循环链表求解约瑟夫环（Joseph）

public class CircleSingleLinkedList {private BoyNode first;private int numOfBoy;public CircleSingleLinkedList(int num) {this.numOfBoy = num;this.addBoy(num);}private void addBoy(int num) {BoyNode last = null;for (int i = 1; i <= num; i++) {if (i == 1) {first = new BoyNode(i);last = first;last.setNext(first);continue;}BoyNode newNode = new BoyNode(i);last.setNext(newNode);newNode.setNext(first);last = newNode;}}public void showLinkedQueue() {BoyNode cur = first;while (true) {System.out.print(cur.getNo() + " ");cur = cur.getNext();if (cur == first) {break;}}}/*** @param k 从第几个人开始报数* @param m 报几个数*/public void removeFromLinkedList(int k, int m) {if (k < 1 || m < 0 || k > numOfBoy) {System.out.println("键入的数据不正确!");return;}//定义一个指针cur指向待出队的node节点,一个pre指针指向待出队节点的前一个节点BoyNode pre = first;BoyNode cur = first;while(pre.getNext() != first) {pre = pre.getNext();}//将pre和cur节点一项第k-1和第k个位置for (int i = 0; i < k - 1; i++) {pre = pre.getNext();}cur = pre.getNext();//循环出队System.out.print("出队序列： ");while (cur.getNext() != cur) {//将pre和cur分别指向待删除节点的前一个节点和待删除的节点for (int i = 0; i < m - 1; i++) {cur = cur.getNext();pre = pre.getNext();}//删除cur指向的节点System.out.print(cur.getNo() + " ");cur = cur.getNext();pre.setNext(cur);}System.out.print(cur.getNo());}
}class BoyNode {private int no;private BoyNode next;public BoyNode(int no) {this.no = no;}public BoyNode getNext() {return next;}public void setNext(BoyNode next) {this.next = next;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}
}
class Main {public static void main(String[] args) {CircleSingleLinkedList cll = new CircleSingleLinkedList(125);//环中总人数cll.showLinkedQueue();cll.removeFromLinkedList(10,20);}
}

 思路：

• 创建两个引用pre和cur，初始状态下分别指向链表的最后一个节点和链表的首节点
• 得到k值后，将cur引用指向开始报数的节点，pre引用指向开始报数节点的前一个节点
• 报数m-1次，将pre和cur指针依次向后移动m-1次，删除cur指向的节点。(循环进行)

---

栈

顺序栈

Java描述的顺序栈：

public class ArrayStack {private int[] stack;private int top;private int maxSize;public ArrayStack(int maxSize) {this.maxSize = maxSize;stack = new int[maxSize];top = -1;}public boolean isFull() {return top == maxSize - 1;}public boolean isEmpty() {return top == -1;}public void push(int val) {if (isFull()) {System.out.println("栈满！无法添加");return;}stack[++top] = val;}public int pop() {if (isEmpty()) {throw new RuntimeException("栈空，无法取出元素！");}return stack[top--];}public void listStack() {if (isEmpty()) {System.out.println("栈为空，无法遍历！");}for (int i = top; i >= 0; i--) {System.out.printf("stack[%d] = %d\t", i, stack[i]);}}
}

链栈

---

 队列

 顺序队列

Java描述的顺序队列：

public class ArrayQueue {private int maxSize;private int front;   //队列头部private int rear;   //队列尾部private int[] arr; //队列数组public ArrayQueue(int maxSize) {this.maxSize = maxSize;arr = new int[maxSize];front = rear = -1;}/*** 判断队列是否满** @return 返回值*/public boolean isFull() {return rear == maxSize - 1;}/*** 判断队列是否为空** @return 返回值*/public boolean isEmpty() {return rear == front;}/*** 向队列中添加元素** @param val 待添加元素的值*/public void addElement(int val) {if (isFull()) {System.out.println("队列已满，无法继续添加！");}arr[++rear] = val;}/*** 获得队列中的数据** @return 返回队头元素*/public int getElement() {if (isEmpty()) {throw new RuntimeException("队列为空,无法取出数据");}return arr[++front];}/*** 显示当前队列的所有元素*/public void listQueue() {if (isEmpty()) {System.out.println("队列为空！");return;}for (int i = front+1; i < rear+1; i++) {System.out.printf(arr[i] + "\t");}}/*** 查询队列的队头元素** @return 返回查询元素*/public int headElement() {if (isEmpty()) {throw new RuntimeException("队列为空,无法取出数据");}return arr[front + 1];}
}

顺序循环队列

 Java描述的顺序循环队列：

public class CircleArrayQueue {private int maxSize;private int front;private int rear;private int[] arr;public CircleArrayQueue(int maxSize) {this.maxSize = maxSize;front = 0;rear = 0;arr = new int[maxSize];}public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear + 1) % maxSize == front;}public void addElement(int val) {if (isFull()) {System.out.println("队列已满，无法添加!");return;}arr[rear] = val;rear = (rear + 1) % maxSize;System.out.println("元素添加成功!");}public int getElement() {if (isEmpty()) {throw new RuntimeException("队列为空，无法获取元素!");} else {int val = arr[front];front = (front + 1) % maxSize;return val;}}public int getElementSize() {return (rear + maxSize - front) % maxSize;}public void listQueue() {if (isEmpty()) {System.out.println("队列为空！");return;}for (int i = front; i < getElementSize() + front; i++) {System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);}
//        int temp = front;
//        while ((temp + 1) % maxSize != rear + 1) {
//            System.out.printf("%d\t", arr[temp++]);
//        }}
}