细讲线性结构
数组
操作
增：索引增(头部增，尾部增)
删：索引删(头部删，尾部删)
改：索引改(头部改，尾部改)
查：索引查(头部查，尾部查)，遍历查
整体操作：顺序遍历，逆序遍历，排序，反转，截取，合并
查找数值：排序+二分查找，遍历查找
代码
//选择排序
public static void choiceSort(int[] arr){for(int circlenum=0;circlenum<arr.length-1;circlenum++){int lastIndex=arr.length-1-circlenum;int maxIndex=0;for(int i=0;i<arr.length-circlenum;i++){if(arr[i]>arr[maxIndex]){maxIndex=i;}}int temp=arr[maxIndex];arr[maxIndex]=arr[lastIndex];arr[lastIndex]=temp;}
}//冒泡排序
public static void bubbleSort(int[] arr){for(int num=0;num<arr.length-1;num++){for(int i=0;i<arr.length-num-1;i++){if(arr[i]>arr[i+1]){int temp=arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}}}
}//快速排序
public static void fastSort(int[] arr,int begin,int end){int length=end-begin+1;if(length<=1){return;}if(length==2){if(arr[begin]>arr[end]){int temp=arr[begin];arr[begin]=arr[end];arr[end]=temp;}return;}int beginPoint=begin+1;int endPoint=end;while(beginPoint<endPoint){while(arr[beginPoint]<=arr[begin]){beginPoint++;if(beginPoint>endPoint){break;}}while(arr[endPoint]>arr[begin]){endPoint--;if(beginPoint>endPoint){break;}}if(beginPoint>endPoint){break;}int temp=arr[beginPoint];arr[beginPoint]=arr[endPoint];arr[endPoint]=temp;}int temp=arr[begin];arr[begin]=arr[endPoint];arr[endPoint]=temp;fastSort(arr,begin,endPoint-1);fastSort(arr,beginPoint,end);
}//插入排序
public static void insertSort(int[] arr){for(int num=0;num<arr.length-1;num++){int insertNum=arr[num+1];for(int i=num;i>=0;i--){if(arr[i]>insertNum){arr[i+1]=arr[i];if(i==0){arr[0]=insertNum;}}else{arr[i+1]=insertNum;break;}}}
}//归并排序
public static void combineSort(int[] arr,int begin,int end){int length=end-begin+1;System.out.println(123);if(length<=1){return;}int middle=(begin+end)/2;combineSort(arr,begin,middle);combineSort(arr,middle+1,end);int firstPoint=begin;int secondPoint=middle+1;int[] tempArr=new int[length];int i=0;while(firstPoint<=middle&&secondPoint<=end){if(arr[firstPoint]<arr[secondPoint]){tempArr[i]=arr[firstPoint];firstPoint++;}else{tempArr[i]=arr[secondPoint];secondPoint++;}i++;}while(firstPoint<=middle){tempArr[i]=arr[firstPoint];firstPoint++;}while(secondPoint<=end){tempArr[i]=arr[secondPoint];secondPoint++;}for(int index=0;index<tempArr.length;index++){arr[begin]=tempArr[index];begin++;}
}//堆排序
public static void heapSort(int[] arr){int endIndex=arr.length-1;while(endIndex>0){toBigHeap(arr,endIndex);int temp=arr[endIndex];arr[endIndex]=arr[0];arr[0]=temp;endIndex--;}
}public static void toBigHeap(int[] arr,int endIndex){int leafIndex=(endIndex+1)/2-1;while(leafIndex>-1){int maxChild;if(leafIndex*2+2>endIndex){maxChild=leafIndex*2+1;}else{maxChild=arr[leafIndex*2+1]>arr[leafIndex*2+2]?leafIndex*2+1:leafIndex*2+2;}if(arr[maxChild]>arr[leafIndex]){int temp=arr[maxChild];arr[maxChild]=arr[leafIndex];arr[leafIndex]=temp;}leafIndex--;}
}//二分查找
public static int binarySearch(int[] arr,int left,int right,int value){int lenght=right-left+1;if(lenght==1){if(arr[left]==value){return left;}else{return -1;}}int middle=(left+right)/2;if(arr[middle]==value){return middle;}else if(arr[middle]>value){return binarySearch(arr,left,middle-1,value);}else{return binarySearch(arr,middle+1,right,value);}
}排序的图示
排序的功能
无序数组变成有序数组
实现排序遇到的难点
①循环时，不好确定终止条件，多一次或少一次，都有可能造成错误。
②递归、循环的最后一步，有时需要额外处理。
我的建议
①多重循环，先实现内层一次循环，再逐步加码。
链表
单链表
操作
增：遍历增(头增，尾增)
删：遍历删(头删，尾删)
改：遍历改
查：遍历查
整体操作：顺序遍历，反转
代码
class HeadNode{String symbo1;Node nextNode=null;HeadNode(String symbol){this.symbo1=symbol;}//链表长度public int getLength(){int num=0;Node node=this.nextNode;while(node!=null){node=node.nextNode;num++;}return num;}//增public void insert(Node insertNode,int position){if(position>getLength()-1){System.out.println("可以插入的索引:"+0+"~"+(getLength()-1));return;}if(position==0){unshift(insertNode);}Node node=this.nextNode;for(int i=0;i<position-1;i++){node=node.nextNode;}insertNode.nextNode=node.nextNode;node.nextNode=insertNode;}//删public Node remove(int position){if(position>getLength()-1){System.out.println("可以删除的索引:"+0+"~"+(getLength()-1));return null;}if(position==0){return shift();}Node node=this.nextNode;for(int i=0;i<position-1;i++){node=node.nextNode;}Node removeNode=node.nextNode;node.nextNode=removeNode.nextNode;return removeNode;}//改public void update(int position,int num){if(position>getLength()-1){System.out.println("可以更新的索引:"+0+"~"+(getLength()-1));return;}Node node=this.nextNode;for(int i=0;i<position;i++){node=node.nextNode;}node.num=num;}//查public Node find(int position){Node node=this.nextNode;for(int i=0;i<position;i++){if(node!=null){node=node.nextNode;}}return node;}public void push(Node pushNode){if(this.nextNode==null){this.nextNode=pushNode;return;}Node node=this.nextNode;while(node.nextNode!=null){node=node.nextNode;}node.nextNode=pushNode;}public Node pop(){Node node=this.nextNode;if(node==null){return node;}if(node.nextNode==null){this.nextNode=null;return node;}while(node.nextNode.nextNode!=null){node=node.nextNode;}Node popNode=node.nextNode;node.nextNode=null;return popNode;}public void unshift(Node unshiftNode){unshiftNode.nextNode=this.nextNode;this.nextNode=unshiftNode;}public Node shift(){if(this.nextNode==null){return null;}Node shiftNode=this.nextNode;this.nextNode=shiftNode.nextNode;return shiftNode;}//遍历public void traverse(){if(this.nextNode==null){System.out.println("链表已空");}Node node=this.nextNode;while(node!=null){System.out.print(node.num+" ");node=node.nextNode;}}//反转public void reverseLink(){Node head=this.nextNode;Node middle=head.nextNode;Node tail=middle.nextNode;head.nextNode=null;while(tail!=null){middle.nextNode=head;head=middle;middle=tail;tail=tail.nextNode;}middle.nextNode=head;this.nextNode=middle;}
}
class Node{int num;Node nextNode=null;Node(int num){this.num=num;}
}
三指针反转图示
p2=p1.nextNode;
p3=p2.nextNode;
p2.nextNode=p1;p1=p2;
p2=p3;
p3=p3.nextNode;栈
数组栈
操作
尾增，尾删
代码
class ArrayStack{private int maxSize;private String[] stack;public int top=-1;public ArrayStack(int maxSize){this.maxSize=maxSize;stack=new String[this.maxSize];}public boolean isFull(){return this.top==this.maxSize-1;}public boolean isEmpty(){return this.top==-1;}public void push(String num){if(this.top==this.maxSize-1){System.out.println("栈已满");return;}top++;stack[top]=num;}public String pop(){if(this.top==-1){return "empty";}String value=stack[this.top];this.top--;return value;}public String getLast(){if(this.top==-1){return "empty";}String value=stack[this.top];return value;}public void showStack(){for(int i=0;i<=this.top;i++){System.out.print(this.stack[i]+" ");}System.out.println();}
}
链表栈
略
队列
线性数组队列
描述
①列头head固定为0；列尾tail在变化
②队列长度length=tail-head+1=tail+1
③元素入列，列尾后移一位(tail++)，元素放到列尾的位置。
④元素出列，列头元素出列，其余元素向前移动一位。
图示
举例
①head=0，tail=5，length=6。有6个元素
②head=0，tail=0，length=1。有1个元素
③head=0，tail=9，length=9。有10个元素，已满
④head=0，tail=-1，length=0,。为空
缺点
列头head固定。元素出列，数组整体需要移动，十分消耗性能。
环形数组队列
描述
①列头head、列尾tail都在变化。
②长度length=tail-head+1
③元素入列，列尾后移一位(tail++)，元素放到列尾位置。
④元素出列，列头元素出列，列头后移一位(head++)。
图示
举例
①head=2，tail=5，length=4，有4个元素
②head=5，tail=12，length=8，有8个元素
④head=0，tail=-1，length=0，为空。
⑤head=0，tail=9，length=10，已满。
⑥head=10，tail=9，length=0，为空。
代码
class ArrayQueue {private int head;private int tail;private TreeNode[] arr;private int maxSize;public ArrayQueue(int maxSize) {this.maxSize=maxSize;arr = new TreeNode[this.maxSize];head = 0;tail = -1;}public int getLength() {int length=tail-head+1;return length;}public void push(TreeNode treeNode) {if(getLength()==10){System.out.println("队列已满");return;}tail++;arr[tail%10]=treeNode;}public TreeNode shift(){if(getLength()==0){System.out.println("队列已空");return null;}TreeNode treeNode=arr[head%10];head++;return treeNode;}public void showQueue() {int start=head;int end=tail;while(start>end){System.out.print(arr[start%10]);start++;}}
}class TreeNode{public int num;public TreeNode leftNode;public TreeNode rightNode;
}链表队列
描述
我推荐链表使用头结点，可以把方法全部放到头结点中，一般节点只需存储指针和数据。
图示
代码
public class singleLinkDemo {public static void main(String[] args){HeadNode myQueue=new HeadNode("001");Node node;for(int i=0;i<10;i++){myQueue.push(i);}myQueue.showQueue();for(int i=0;i<5;i++){if((node=myQueue.shift())!=null){System.out.println(node.num+"出列");}}myQueue.showQueue();for(int i=0;i<10;i++){myQueue.push(i);}myQueue.showQueue();}
}class HeadNode{String symbo1;Node nextNode=null;Node lastNode=null;HeadNode(String symbol){this.symbo1=symbol;}public int getLength(){int length=0;Node node=this.nextNode;while(node!=null){length++;node=node.nextNode;}return length;}public void push(int num){Node pushNode=new Node(num);if(this.nextNode==null){this.nextNode=pushNode;return;}Node node=this.nextNode;while(node.nextNode!=null){node=node.nextNode;}node.nextNode=pushNode;}public Node shift(){if(this.nextNode==null){return null;}Node shiftNode=this.nextNode;this.nextNode=shiftNode.nextNode;return shiftNode;}public void showQueue(){if(this.nextNode==null){System.out.println("队列已空");return;}Node node=this.nextNode;System.out.println("队列内容");while(node!=null){System.out.print(node.num+" ");node=node.nextNode;}System.out.println();}
}
class Node{int num;Node nextNode=null;Node(int num){this.num=num;}
}
运行结果
队列内容
0 1 2 3 4 5 6 7 8 9
0出列
1出列
2出列
3出列
4出列
队列内容
5 6 7 8 9
队列内容
5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 
