線(xiàn)性表
順序存儲(chǔ)結(jié)構(gòu)
順序表：內(nèi)存地址是連續(xù)的
a1,a2,a3,a4.... ai,ai+1,an
a1是a2的前驅(qū)，ai+1 是ai的后繼，a1沒(méi)有前驅(qū)，an沒(méi)有后繼
n為線(xiàn)性表的長(zhǎng)度 ，若n==0時(shí)，線(xiàn)性表為空表優(yōu)點(diǎn)：
尾插效率高，支持隨機(jī)訪問(wèn)。
缺點(diǎn)：
中間插入或者刪除效率低。
應(yīng)用：
數(shù)組
ArrayList
蠻力法排序：
蠻力法（brute force method，也稱(chēng)為窮舉法或枚舉法）
是一種簡(jiǎn)單直接地解決問(wèn)題的方法，
常常直接基于問(wèn)題的描述，
所以，蠻力法也是最容易應(yīng)用的方法。（數(shù)據(jù)比較少的時(shí)候）
但是，用蠻力法設(shè)計(jì)的算法時(shí)間特性往往也是最低的，（數(shù)據(jù)過(guò)多的時(shí)候）
典型的指數(shù)時(shí)間算法一般都是通過(guò)蠻力搜索而得到的 。（即輸入資料的數(shù)量依線(xiàn)性成長(zhǎng)，所花的時(shí)間將會(huì)以指數(shù)成長(zhǎng)）
冒泡排序 適用于3-5個(gè)數(shù)據(jù)
/**
* 冒泡排序
* 相鄰的左邊比右邊大的就互相交換位置，一輪過(guò)后最大的數(shù)就到了順序表的末尾
* @param array
*/
public static void sort_bubble(int[] array){
if(array == null || array.length == 0){
return;
}
for(int i = array.length -1 ; i > 0 ; i--){
boolean flag = true;
for(int j = 0; j < i ; j++){
if(array[j] > array[j+1]){
array[j] = array[j]^array[j+1];
array[j+1] = array[j]^array[j+1];
array[j] = array[j]^array[j+1];
flag = false;
}
}
if(flag){
break;
}
}
}
選擇排序 適用于3-5個(gè)數(shù)據(jù)
/**
* 選擇排序 快速排序的基礎(chǔ)
*
* @param array
*/
public static void sort_select(int[] array){
if(array == null || array.length == 0){
return;
}
for(int i = 0 ; i < array.length - 1; i++){
int index = i;
for(int j = i + 1; j < array.length;j++){
if(array[j] < array[index]){
index = j;
}
}
if(index != i){
array[index] = array[i]^array[index];
array[i] = array[i]^array[index];
array[index] = array[i]^array[index];
}
}
}
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的
優(yōu)點(diǎn)：
插入或者刪除效率高。
缺點(diǎn)：
不支持隨機(jī)訪問(wèn)。分為：
1.單鏈表
2.單循環(huán)鏈表
3.雙鏈表
4.雙向循環(huán)鏈表
單鏈表
單鏈表的每一個(gè)數(shù)據(jù)可以看做是一個(gè)節(jié)點(diǎn)。
節(jié)點(diǎn)由 數(shù)據(jù)域+指針域組成
單循環(huán)鏈表
單鏈表的最后一個(gè)節(jié)點(diǎn)的指針域指向第一個(gè)數(shù)據(jù)
雙鏈表
前指針域+數(shù)據(jù)域+后 指針域組成。單鏈表查詢(xún)只能從前往后進(jìn)行查找，雙鏈表可以支持從后往前查找，所以?xún)?yōu)化了查詢(xún)效率。
雙向循環(huán)鏈表
參照 單循環(huán)鏈表
下面附上我自己寫(xiě)的自定義的雙向鏈表代碼，僅供大家參考:
package com.xx.lists;
/**
* 練習(xí)
* 自定義的雙向鏈表
* @author Lixin
*
* @param <E>
*/
public class MyLinkedList<E> {
private Node<E> first;
private Node<E> last;
public int size;
// 添加
public void add(E item){
addLast(item);
}
// 在最后添加一個(gè)數(shù)據(jù)
public void addLast(E item){
Node<E> node = new Node(last,item,null);
Node<E> l = last;
last=node;
if(l == null){
// 此前鏈表為空
first = node;
}else{
l.next = node;
}
size++;
}
// 在具體位置添加
public void add(int index, E item){
if(index < 0 || index > size){
return;
}
if(index == size){
addLast(item);
}else{
Node<E> oldNode = node(index);
if(oldNode == null){
throw new NullPointerException();
}
Node<E> preNode = oldNode.pre;
Node<E> newNode = new Node<E>(preNode,item,oldNode);
// old
oldNode.pre = newNode;
// pre
if(preNode != null){
preNode.next = newNode;
}else{
first = newNode;
}
size++;
}
}
// 根據(jù)下標(biāo)位置找到節(jié)點(diǎn)數(shù)據(jù) 可以看到鏈表的查找是比較麻煩的
public E get(int index){
Node<E> node = node(index);
if(node!=null){
return node.item;
}
return null;
}
// 刪除
public void remove(int index){
Node<E> node = node(index);
if(node == null){
return;
}
Node<E> nodePre = node.pre;
Node<E> nodeNext = node.next;
if(nodePre == null){
first = nodeNext;
}else{
nodePre.next = nodeNext;
}
node.pre = null;
if(nodeNext != null){
nodeNext.pre = nodePre;
}else{
last = nodePre;
}
node.next = null;
size--;
}
private Node<E> node(int index){
if(index<0 || index>(size - 1)){
throw new IndexOutOfBoundsException();
}
Node<E> node ;
// size >> 1 == size/2
if(index < (size>>1)){
node = first;
for(int i = 0;i<index;i++){
node = node.next;
}
}else{
node = last;
for(int i = size - 1;i > index;i--){
node = node.pre;
}
}
return node;
//如果index在整個(gè)鏈表的前半部分
// if(index<(size>>1)){ //1000 100 10
// Node<E> node=first;
// for (int i = 0; i < index; i++) {
// node=node.next;
// }
// return node;
// }else{
// Node<E> node=last;
// for (int i = size-1; i > index; i--) {
// node=node.pre;
// }
// return node;
// }
}
// 節(jié)點(diǎn)
private class Node<E>{
public E item;
// 前一個(gè)節(jié)點(diǎn)
public Node<E> pre;
// 下一個(gè)節(jié)點(diǎn)
public Node<E> next;
public Node(Node<E> pre,E item,Node<E> next){
this.item = item;
this.pre = pre;
this.next = next;
}
}
}
棧和遞歸
棧
棧是限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。
允許插入和刪除的一端稱(chēng)為棧頂（top），另一端稱(chēng)為棧底（bottom）,不含任何數(shù)據(jù)元素的棧稱(chēng)為空棧。
棧又稱(chēng)為后進(jìn)先出的線(xiàn)性表
棧的實(shí)現(xiàn)方式:
順序方式：Stack.java類(lèi)
鏈?zhǔn)椒绞剑簂ast = 棧頂
入棧方式
image.png
出棧方式
逆波蘭表達(dá)式: 高級(jí)語(yǔ)言中的運(yùn)算方法原理，比較麻煩，有時(shí)間再開(kāi)個(gè)專(zhuān)題講解吧，有興趣的同學(xué)也可以百度去查一下相關(guān)資料。
大概邏輯是：中綴表達(dá)式（如 1+1） （依照數(shù)字輸出，運(yùn)算符優(yōu)先級(jí)低出棧，運(yùn)算符高入棧的原則）轉(zhuǎn)成后綴表達(dá)式（1 1 + ）
計(jì)算時(shí)，數(shù)字入棧，遇到運(yùn)算符號(hào)就取棧內(nèi)的兩個(gè)數(shù)字進(jìn)行計(jì)算。
遞歸
程序調(diào)用自身的編程技巧稱(chēng)為遞歸（recursion）。
遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。 一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法，
它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，
遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。
遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。
一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。
當(dāng)邊界條件不滿(mǎn)足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿(mǎn)足時(shí)，遞歸返回。
執(zhí)行特點(diǎn)：每次遞歸調(diào)用的方法會(huì)放入方法棧中，然后從棧頂依次調(diào)用。
調(diào)用自己一次的情況:調(diào)用位置前面的代碼是正循環(huán)，調(diào)用位置后面的代碼是反循環(huán)
調(diào)用自己兩次的情況:一個(gè)二叉樹(shù)的中序遍歷過(guò)程
下面為大家介紹一個(gè)用遞歸算法實(shí)現(xiàn)的一個(gè)程序：
漢諾塔算法：有三根相鄰的柱子，標(biāo)號(hào)為A,B,C，A柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤(pán)，要把所有盤(pán)子一個(gè)一個(gè)移動(dòng)到柱子B上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤(pán)子在小盤(pán)子上方，請(qǐng)問(wèn)至少需要多少次移動(dòng)
public class RecursionTest {
public static void main(String[] arg0){
hanoi(3,1,2,3);
}
/**
* @param n 盤(pán)子的個(gè)數(shù)
* @param start 開(kāi)始的柱子
* @param middle 中介柱子
* @param end 結(jié)果柱子
*/
public static void hanoi(int n,int start,int middle,int end){
if(n<=1){
System.out.println(start+"----->"+end);
}else{
hanoi(n-1,start,end,middle);
System.out.println(start+"----->"+end);
hanoi(n-1,middle,start,end);
}
}
}
