1.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
1.什么是數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)炮沐、組織數(shù)據(jù)的方式。
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合回怜。
通常情況下大年，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。
數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。
可以使用邏輯結(jié)構(gòu)描述數(shù)據(jù)結(jié)構(gòu)
2. 邏輯結(jié)構(gòu)(描述數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系)
- 集合結(jié)構(gòu)image
- 線性結(jié)構(gòu)image
- 樹(shù)形結(jié)構(gòu)image
- 圖形結(jié)構(gòu)image
邏輯結(jié)構(gòu)需要保存在加算計(jì)中,稱為存儲(chǔ)結(jié)構(gòu)
3.存儲(chǔ)結(jié)構(gòu)(重點(diǎn))
- 表
- 堆棧
- 隊(duì)列
- 數(shù)組
- 樹(shù)
- 二叉樹(shù)
- 圖
4.什么是算法
用來(lái)解決問(wèn)題的方法,一個(gè)算法的好壞可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量
程序好壞=空間復(fù)雜度+時(shí)間復(fù)雜度+應(yīng)用場(chǎng)景
1.空間復(fù)雜度
算法運(yùn)行占用多少運(yùn)行內(nèi)存
2.時(shí)間復(fù)雜度(主要考慮對(duì)象)
算法的效率O(n),關(guān)鍵代碼的執(zhí)行次數(shù)
- 時(shí)間復(fù)雜度O(n) = n*n+n+1
function1() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j ++) {
// dosomething;
}
}
for(int i = 0; i < n; i++) {
//dosomething
}
// dosomething
}
2.O(n) = n*n
function2() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j ++) {
// dosomething;
}
}
上面?zhèn)z中算法的時(shí)間復(fù)雜度是相等的(n=>無(wú)窮大),考慮n的幾次方
3.使用數(shù)據(jù)交換看程序好壞(考慮場(chǎng)景)
倆個(gè)數(shù)據(jù)交換的幾種方式
1.可讀性最好(不影響用戶體驗(yàn)情況下翔试，優(yōu)先選擇可讀性最好的情況下)
int a = 5;
int b = 6;
int t = a;
a = b;
b = t;
2.相比于1節(jié)省了一個(gè)空間復(fù)雜度,但無(wú)法做對(duì)象的交換
a = a + b;
b = a - b;
a = a - b;
3.性能最優(yōu),任何情況下都能用,但可讀性低,主要應(yīng)用在無(wú)人機(jī),車載等空間占用少,性能要求高的情況下
a = a ^ b;
b = a ^ b;
a = a ^ b;
2.線性表
1.順序存儲(chǔ)結(jié)構(gòu)(順序表)
- 存儲(chǔ)是連續(xù)的,ArrayList就是順序表
image
image
a1是a2的前驅(qū),ai+1是ai的后繼,a1沒(méi)有前驅(qū),a2沒(méi)有后繼,n是線性表長(zhǎng)度,n=0時(shí)線性表是空表
- 判斷圖中班級(jí)是不是順序表image
圖中的班級(jí)表是順序表,數(shù)組都是連續(xù)的存儲(chǔ)空間 - 向數(shù)組指定位置添加數(shù)據(jù)
int index = 1;
int data = 2;
int array[] = {1, 3, 4, 5, 6, 7};
array[array.length] = 0;
for (int i = array.length - 1; i > index; i++) {
array[i] = array[i - 1];
}
array[index]=data;
這種插入的優(yōu)點(diǎn)是尾插入效率高,支持隨機(jī)訪問(wèn),缺點(diǎn)是中間插入或者刪除效率低
紙牌排序問(wèn)題
- 定義紙牌類
public int pokerColors;//花色
public int cardPoints;//點(diǎn)數(shù)
public Cards(int pokerColors, int cardPoints) {
this.pokerColors = pokerColors;
this.cardPoints = cardPoints;
}
//提供一個(gè)方法轻要，用來(lái)比較對(duì)象的大小
@Override
public int compareTo(@NonNull Object o) {
Cards c=(Cards)o;
if(this.cardPoints>c.cardPoints){
return 1;
}else if(this.cardPoints<c.cardPoints){
return -1;
}
if(this.pokerColors>c.pokerColors){
return 1;
}else if(this.pokerColors<c.pokerColors){
return -1;
}
return 0;
}
- 使用sort排序
Cards[] cards = {
new Cards(3, 9),
new Cards(2, 7),
new Cards(1, 1),
new Cards(3, 3),
new Cards(4, 4),
new Cards(2, 5),
new Cards(3, 6),
new Cards(3, 7),
};
//效率很低，執(zhí)行代碼至少在一百行以上
// Arrays.sort(cards);
- 蠻力法進(jìn)行排序(也稱為窮舉法或枚舉法)
在數(shù)據(jù)量足夠少的情況下是所有算法里效率最高的
在數(shù)據(jù)量趨于無(wú)窮大的時(shí)候效率是最低的 - 冒泡排序(蠻力法的一種)
應(yīng)用于數(shù)據(jù)量足夠小,如炸金花,斗牛游戲中的牌排序(個(gè)位數(shù)內(nèi)排序)
時(shí)間復(fù)雜度O(n)=n*(n-1)/2
public static int[] bubbleSort(int[] array) {
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]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
return array;
}
- 選擇排序
學(xué)習(xí)快速排序的基礎(chǔ)
//選擇排序
public static void selectSort(int[] array) {
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) {//如果已經(jīng)是最小的垦缅，不需要交換
int temp = array[index];
array[index] = array[i];
array[i] = temp;
System.out.println(index);
}
}
}
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
1.ArrayList分析
- 創(chuàng)建ArrayList會(huì)創(chuàng)建一個(gè)空數(shù)組和一個(gè)size大小
- 調(diào)用add添加元素時(shí)
public boolean add(E e) {
ensureCapacityInternal(size + 1);//檢測(cè)數(shù)組容量,如果滿足繼續(xù)添加,不滿足就擴(kuò)展容量
Increments modCount!!
elementData[size++] = e;
return true;
}
- 擴(kuò)展容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//右移1:用之前的容量加上之前容量的一半
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//把原來(lái)的數(shù)據(jù)拷貝一下
}
- 向指定位置添加元素
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//index后面的數(shù)據(jù)copy一份添加到index+1的位置,在把element添加到index的位置
elementData[index] = element;
size++;
}
2.鏈表
定義:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素,這組存儲(chǔ)單元是可以連續(xù)的,也是可以不連續(xù)的
單鏈表是由很多的節(jié)點(diǎn)組織起來(lái)的,MessageQueue就是單鏈表
- 節(jié)點(diǎn)
- 每個(gè)節(jié)點(diǎn)分成倆塊,數(shù)據(jù)域和指針域,數(shù)據(jù)域是可以有很多數(shù)據(jù)的
- 數(shù)據(jù)域都有對(duì)自己的引用,例如Message中有Message引用(Message消息就是一個(gè)節(jié)點(diǎn))
image
刪除102只需要把101中的指向改成103
插入也是改響應(yīng)的指向
Handler中的死循環(huán),p=p.next就是取下一個(gè)message - MessageQueue插入enqueueMessage(Message msg,long when),刪除next()
- 鏈表排序麻將(適合數(shù)據(jù)量在二三十個(gè)左右,空間占用少)
使用鏈表先對(duì)點(diǎn)數(shù)進(jìn)行排序,再使用鏈表對(duì)花色進(jìn)行排序image
@Test
public void testMj(){
LinkedList<Majiang> linkedList = new LinkedList<>();
linkedList.add(new Majiang(3,1));
linkedList.add(new Majiang(1,1));
linkedList.add(new Majiang(2,1));
linkedList.add(new Majiang(3,3));
linkedList.add(new Majiang(4,1));
linkedList.add(new Majiang(3,6));
linkedList.add(new Majiang(3,1));
linkedList.add(new Majiang(2,2));
linkedList.add(new Majiang(1,3));
linkedList.add(new Majiang(2,4));
linkedList.add(new Majiang(3,5));
linkedList.add(new Majiang(4,6));
linkedList.add(new Majiang(3,9));
linkedList.add(new Majiang(2,8));
linkedList.add(new Majiang(1,7));
linkedList.add(new Majiang(3,6));
raidxSort(linkedList);
}
/**
* 麻將排序冲泥，參數(shù)可以是任意的鏈表
*
* @param list
*/
public static void raidxSort(LinkedList<Majiang> list) {
//先對(duì)點(diǎn)數(shù)進(jìn)行分組
LinkedList[] rankList = new LinkedList[9];
for (int i = 0; i < rankList.length; i++) {
rankList[i] = new LinkedList<>();
}
while (list.size() > 0) {
//取一個(gè)
Majiang majiang = list.remove();
//放到組中，下表=點(diǎn)數(shù)-1的
rankList[majiang.rank - 1].add(majiang);
}
//把九組合并在一起
for (int i = 0; i < rankList.length; i++) {
list.addAll(rankList[i]);
}
//花色進(jìn)行分組
LinkedList[] suitList = new LinkedList[4];
for (int i = 0; i < suitList.length; i++) {
suitList[i] = new LinkedList();
}
//把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的花色鏈表中
while (list.size() > 0) {
Majiang majiang = list.remove();
//下表=點(diǎn)數(shù)-1
suitList[majiang.suit - 1].add(majiang);
}
for (int i = 0; i < suitList.length; i++) {
list.addAll(suitList[i]);
}
for (Majiang majiang : list) {
System.out.print(majiang.toString());
}
}
3. 單循環(huán)鏈表
圍成一個(gè)圈,末尾一個(gè)指向第一個(gè)
3.雙鏈表
解釋:一個(gè)節(jié)點(diǎn)帶倆個(gè)指針
應(yīng)用:LinkedList
image
優(yōu)點(diǎn):不僅可以向后查,還可以向前查,增加查詢效率
5.雙向循環(huán)鏈表
最后一個(gè)循環(huán)指向第一個(gè)
3.手寫(xiě)LinkedList
public class LinkedList<E> {
/**
* 節(jié)點(diǎn)
*
* @param <E>
*/
private static class Node<E> {
//數(shù)據(jù)
E item;
//前一個(gè)節(jié)點(diǎn)
Node<E> prev;
//后一個(gè)節(jié)點(diǎn)
Node<E> next;
public Node(Node<E> prev, E item, Node<E> next) {
this.item = item;
this.prev = prev;
this.next = next;
}
}
//頭節(jié)點(diǎn)
Node<E> first;
//尾節(jié)點(diǎn)
Node<E> last;
//節(jié)點(diǎn)個(gè)數(shù)
int size;
/**
* 添加數(shù)據(jù)
*
* @param e
*/
public void add(E e) {
linkLast(e);
}
/**
* 添加數(shù)據(jù)在index位置
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
return;
}
if (index == size) {
linkLast(e);
} else {
Node<E> target = node(index);
Node<E> prevNode = target.prev;
Node<E> newNode = new Node<E>(prevNode, e, target);
if (prevNode == null) {
first = newNode;
target.prev = newNode;
} else {
prevNode.next = newNode;
target.prev = newNode;
}
size++;
}
}
/**
* 添加到最后
*
* @param e
*/
public void linkLast(E e) {
Node<E> newNode = new Node<E>(last, e, null);
Node<E> l = last;
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
/**
* 查找位置
*/
public E get(int index) {
if (index < 0 || index > size) {
return null;
}
return node(index).item;
}
/**
* 獲取index位置上的節(jié)點(diǎn)
*/
private Node<E> node(int index) {
//如果index在整個(gè)鏈表的前半部分
if (index < size >> 1) {
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.prev;
}
return node;
}
}
/**
* 刪除元素
*/
public void remove(int index) {
Node<E> target = node(index);
unLinkNode(target);
}
private void unLinkNode(Node<E> node) {
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) {
first = node.next;
} else {
prev.next = node.next;
}
if (next == null) {
last = next.prev;
} else {
next.prev = node.prev;
}
size--;
}
}
測(cè)試
public class test {
private static final String TAG = "test";
@Test
public void test() {
LinkedList<Object> list = new LinkedList<>();
list.add("3");
list.add("2");
list.add("4");
list.add("6");
list.add("1");
for (int i = 0; i < list.size; i++) {
System.out.print(" "+list.get(i).toString());
}
System.out.println();
list.add(1, "10");
for (int i = 0; i < list.size; i++) {
System.out.print(" "+list.get(i).toString());
}
System.out.println();
list.add(0, "9");
for (int i = 0; i < list.size; i++) {
System.out.print(" "+list.get(i).toString());
}
System.out.println();
list.remove(3);
for (int i = 0; i < list.size; i++) {
System.out.print(" "+list.get(i).toString());
}
}
}
輸出結(jié)果
3 2 4 6 1
3 10 2 4 6 1
9 3 10 2 4 6 1
9 3 10 4 6 1
