网站服务器查询平台,高效网站推广设计,站长工具使用方法,网站域名列表目录
稀疏数组
顺序表
链表
单向顺序链表
双向链表
双向循环链表求解约瑟夫环#xff08;Joseph#xff09;
栈
顺序栈 队列 顺序队列
顺序循环队列 稀疏数组
当一个数组中大部分值为0,或者相同时#xff0c;可以采用稀疏数组的方式来保存#xff0c;从而节约存储…目录
稀疏数组
顺序表
链表
单向顺序链表
双向链表
双向循环链表求解约瑟夫环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[i1][0]][sparseArr[i1][1]] sparseArr[i1][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 front1; i rear1; 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]);
// }}
}
