常見(jiàn)數(shù)據(jù)結(jié)構(gòu)
1 棧
棧（stack）又名堆棧，它是一種運(yùn)算受限的線(xiàn)性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算(先進(jìn)后出)。這一端被稱(chēng)為棧頂，把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱(chēng)作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
棧.jpg
public class Stack {
private int[] array = new int[5];// 棧
private int top = -1;// 指針
// 壓棧
public boolean push(int x) {
if(top<array.length-1){
array[++top] = x;
return true;
}else{
throw new RuntimeException("overFlow");//上溢
}
}
// 出棧
public int pop() {
if (!isEmpty()) {
return array[top--];
} else {
throw new RuntimeException("underflow");//下溢
}
}
// 是否為空
public boolean isEmpty() {
return top == -1 ? true : false;
}
}
2 隊(duì)列
隊(duì)列是一種特殊的線(xiàn)性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線(xiàn)性表。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。
隊(duì)列.jpg
public class Queue {
Object[] array = new Object[4]; // 對(duì)象數(shù)組，此時(shí)隊(duì)列最多存儲(chǔ)3個(gè)對(duì)象
int first = 0; // 隊(duì)首下標(biāo)
int last = 0; // 隊(duì)尾下標(biāo);指向指向即將添加的下一個(gè)元素位置
/**
* 將一個(gè)對(duì)象追加到隊(duì)列尾部
* @return 隊(duì)列滿(mǎn)時(shí)返回false,否則返回true
*/
public boolean add(Object obj) {
if ((last + 1) % array.length == first) {
return false;
}
array[last] = obj;
last = (last + 1) % array.length;
return true;
}
/**
* 隊(duì)列頭部的第一個(gè)對(duì)象出隊(duì)
* @return 出隊(duì)的對(duì)象，隊(duì)列空時(shí)返回null
*/
public Object remove() {
if (last == first) {
return null;
}
Object obj = array[first];
first = (first + 1) % array.length;
return obj;
}
}
單向鏈表
單鏈表有一個(gè)頭節(jié)點(diǎn)head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型為結(jié)構(gòu)體類(lèi)型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類(lèi)型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪(fǎng)問(wèn)需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無(wú)論在表中訪(fǎng)問(wèn)那一個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開(kāi)始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，?xiě)作為NULL。
單向鏈表.jpg
public class LinkedList {
public Node head = null;
public void add(int x) {
Node node = new Node(x, null);
Node p = head;
// 注意鏈表為空的時(shí)候的插入
if (head == null) {
head = node;
}
// 尾插法
else {
while (p.next != null) {
p = p.next;
}
p.next = node;
}
}
/**
* 遍歷打印
*/
public void travese(Node head) {
Node p = head;
while (p != null) {
System.out.println(p.item);
p = p.next;
}
}
/*
* 元素
*/
private static class Node {
int item;
Node next;
public Node(int item, Node next) {
this.item = item;
this.next = next;
}
}
}
算法
1 排序
/** 快速排序 遞歸 比較povit后，povit的左邊是小于它的數(shù)，povit右邊是大于它的數(shù) 下次遞歸 */
public void quickSort(int arr[], int low, int high) {
int l = low;
int h = high;
int povit = arr[low];
while (l < h) {
while (l < h && arr[h] >= povit)
h--;
if (l < h) {
int temp = arr[h];
arr[h] = arr[l];
arr[l] = temp;
l++;
}
while (l < h && arr[l] <= povit)
l++
if (l < h) {
int temp = arr[h];
arr[h] = arr[l];
arr[l] = temp;
h--;
}
}
System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
if (l > low) sort(arr, low, l - 1);
if (h < high) sort(arr, l + 1, high);
}
/** 冒泡排序 按照下標(biāo)向后相鄰數(shù)依次比較 大數(shù)向后走
第一次下標(biāo)0（j控制）與1比較 下一次下標(biāo)1與2比較 再下一次下標(biāo)2與3比較 大的放后面 每走完一圈最大數(shù)放置到了最后
*/
public static void bubbleSort(int[] ary) {
for (int i = 0; i < ary.length - 1; i++) {// length-1次,最后一個(gè)不用冒了.
for (int j = 0; j < ary.length - 1 - i; j++) {
if (ary[j] > ary[j + 1]) {
int t = ary[j]; ary[j] = ary[j + 1]; ary[j + 1] = t;
}
}
}
}
/**選擇排序 從下標(biāo)0（i控制）開(kāi)始與后面所有的數(shù)比較 ，第一輪下標(biāo)0與1，2，3...比較 下一輪 2與3，4，5...比較 大的放后面 */
public static void selectionSort(int[] ary) {
for(int i=0;i<ary.length-1;i++){
for(int j=i+1;j<ary.length;j++){
if(ary[i]>ary[j]){
int t = ary[i]; ary[i] = ary[j]; ary[j] = t;
}
}
}
}
/**插入排序 從下標(biāo)1開(kāi)始 ，與它前面所有的數(shù)比較，比它大移到后面，比較到比它小的數(shù)為止，就把它插到比他小的后面*/
public static void insertSort(int[] ary){
int t,i,j;
for(i=1;i<ary.length;i++){
System.out.println(Arrays.toString(ary));
t = ary[i];
for(j=i-1;j>=0&&ary[j]>t;j--){
ary[j+1] = ary[j];
}
ary[j+1] = t;
}
}
2 二分法查找法
/*
* 二分查找 假如數(shù)組是有序且按升序排列 取到中間的下標(biāo) 如果查找數(shù)大于左邊的數(shù)，則左邊的數(shù)無(wú)需再搜尋，直接搜尋右邊的數(shù)。
*/
public static int search(int[] nums, int num) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
// 與中間值比較確定在左邊還是右邊區(qū)間,以調(diào)整區(qū)域
if (num > nums[mid]) {
low = mid + 1;
} else if (num < nums[mid]) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
3 位移
java中有三種移位運(yùn)算符:
<< : 左移運(yùn)算符，num << 1,相當(dāng)于num乘以2
>> : 右移運(yùn)算符，num >> 1,相當(dāng)于num除以2
>>> : 無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
1010 十進(jìn)制：10 原始數(shù) number
10100 十進(jìn)制：20 左移一位 number = number << 1;
1010 十進(jìn)制：10 右移一位 number = number >> 1;
對(duì)于：>>>
無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
value >>> num -- num 指定要移位值value 移動(dòng)的位數(shù)。
無(wú)符號(hào)右移的規(guī)則只記住一點(diǎn)：忽略了符號(hào)位擴(kuò)展，0補(bǔ)最高位 無(wú)符號(hào)右移運(yùn)算符>>> 只是對(duì)32位和64位的值有意義
