Java數(shù)據(jù)結構重點知識有哪些

這篇“Java數(shù)據(jù)結構重點知識有哪些”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內(nèi)容，內(nèi)容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java數(shù)據(jù)結構重點知識有哪些”文章吧。

成都創(chuàng)新互聯(lián)公司是一家以網(wǎng)絡技術公司，為中小企業(yè)提供網(wǎng)站維護、成都網(wǎng)站制作、做網(wǎng)站、網(wǎng)站備案、服務器租用、域名注冊、軟件開發(fā)、微信小程序開發(fā)等企業(yè)互聯(lián)網(wǎng)相關業(yè)務，是一家有著豐富的互聯(lián)網(wǎng)運營推廣經(jīng)驗的科技公司，有著多年的網(wǎng)站建站經(jīng)驗，致力于幫助中小企業(yè)在互聯(lián)網(wǎng)讓打出自已的品牌和口碑，讓企業(yè)在互聯(lián)網(wǎng)上打開一個面向全國乃至全球的業(yè)務窗口：建站服務熱線：18980820575

1 線性表的合并（編程題）

1.1 有序表的合并

算法步驟：

  1. 創(chuàng)建表長為m+n的空表LC。

  2. 指針pc初始化，指向LC的第一個元素。

  3. 指針pa和pb初始化，分別指向LA和LB的第一個元素。

  4. 當指針pa和pb均為到達相應表尾時，則依次比較pa和pb所指向的元素值，從LA或LB中摘取元素值較小的結點插入到LC的最后。

  5. 如果pb已到達LB的表尾，依次將LA的剩余元素查到LC的最后。

  6. 如果pa已到達LA的表尾，依次將LB的剩余元素查到LC的最后。

算法代碼：

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
  LC.length = LA.length+LB.length;  // 新表長度為兩表長度之和
  LC.elem = new ElemType[LC.length];  // 為合并后的新表分配空間
  pc = LC.elem;  // 指針pc新表的第一個元素
  pa = LA.elem;  // 指針pa和pb的初值分別指向兩個表的第一個元素
  pb = LB.elem;
  pa_last = LA.elem+LA.length-1;  // 指針pa_last 指向LA的最后一個元素
  pb_last = LB.elem+LB.length-1;  // 指針pb_last 指向LB的最后一個元素
  while((pa<=pa_last)&&(pb<=pb_last){  // LA和LB均未達到表尾
    if(*pa<=*pb){
      *pc++ = *pa++;  // 依次摘取兩表中值較小的結點插入到LC的最后
    }else{
      *pc++ = *pb++;
    }
  }
  while(pa<=pa_last){  // LB到達表尾
    *pc++ = *pa++;
  }
  while(pb<=pb_last){  // LA到達表尾
    *pc++ = *pb++;
  }
}
1.2 鏈表的合并

算法步驟:

  1. 指針pa和pb初始化，分別指向LA和LB的第一個結點

  2. LC的結點取值為LA的頭結點

  3. 指針pc初始化，指向LC的頭結點

  4. 當指針pa和pb均未到達相應表尾，則依次比較pa和pb所指向的元素值，從LA或LB中摘取元素值較小的結點插入到LC的最后

  5. 將非空表的剩余段插入到pc所指結點后。

  6. 釋放LB的頭結點。

算法代碼：

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC){
  pa = LA->next;  pb=LB->next;  // pa和pb的初值分別指向兩個表的第一個結點
  LC=LA;  // 用LA的頭結點作為LC的頭結點
  pc=LC;  // pc的初值指向LC的頭結點
  while(pa&&pb){
    if(pa->data<=pb->data){
      pc->next = pa;  // 將pa所指結點鏈接到pc所指結點之后
      pc=pa;  // pc指向pa
      pa = pa->next;  // pa指向下一結點
    }else{
      pc->next = pb;  // 將pb所指結點鏈接到pc所指結點之后
      pc = pb;  // pc指向pb
      pb = pb->next;  // pb指向下一結點
    }
  }
  pc->next = pa?pa:pb;  // 將非空表的剩余段插入到pc所示結點之后
  delete LB;  // 釋放LB的頭結點
}

2 棧和隊列

2.1 棧的基本操作

棧：限定僅在表尾進行插入和刪除操作的線性表。

允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又被稱為后進先出(Last In First Out)的線性表，簡稱LIFO結構。

棧的插入操作，叫做進棧，也稱壓棧、入棧。

棧的刪除操作，叫做出棧，有的也叫作彈棧。

2.1.1 入棧、進棧

單棧棧空條件：S->top==-1

單棧棧滿條件：S->top==MAXSIZE-1

對于棧的插入，即進棧操作，其實就是做了如下處理：

Status Push(SqStack *S.SElemType e){
    if(S -> top == MAXSIZE -1){ // 棧滿
        return ERROR;
    }
    S->top++; // 棧頂指針加一
    S->data[S->top] = e;  // 將新插入元素復制給棧頂空間
    return OK;
}

出棧操作pop，代碼如下：

Status Pop(SqStack *S,SElemType *e){
    if(S->top==-1){ // 棧為空
        return ERROR;
    }
    *e = S->data[S->top];  // 將要刪除的棧頂元素復制給e
    S->top--;  // 棧頂指針減一
    return OK;
}
2.1.2 共享棧(重要)

棧的順序存儲還是很方便的，因為它只準棧頂進出元素，所以不存在線性表插入和刪除時需要移動元素的問題。不過它有一個很大的缺陷，就是必須事先確定數(shù)組存儲空間大小，萬—不夠用了，就需要用編程手段來擴展數(shù)組的容量，非常麻煩。

共享棧就可以很好的解決這個問題。如果我們有兩個相同類型的棧，我們?yōu)樗鼈兏髯蚤_辟了數(shù)組空間，極有可能是第—個棧已經(jīng)滿了，再進棧就溢出了，而另一個棧還有很多存儲空間空閑，我們完全可以用—個數(shù)組來存儲兩個棧，充分利用這個數(shù)組占用的內(nèi)存空間。

設置數(shù)組有兩個端點，兩個棧有兩個棧底，讓一個棧的棧底為數(shù)組的始端，即下標為0處，另—個棧為數(shù)組的末端，即下標為數(shù)組長度n-1處。這樣兩個棧如果增加元素，就是兩端點向中間延伸。

?？諚l件：S->top=-1或top[i]=bot[i]

棧滿條件：S->top1+1=S->top2

共享棧的結構定義：

typedef struct{
    SElemType data[MAXSIZE];
    int top1; // 棧1棧頂指針
    int top2;  // 棧2棧頂指針
}SqDoubleStack;

2.1.2.1 共享棧進棧

對于共享棧的push方法，除了要插入元素值參數(shù)外，還需要有一個參數(shù)判斷是棧1還是棧2的棧號參數(shù)StackNumber。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
    if(S->top1+1=S->top2){  // 棧滿
        return ERROR;
    }
    if(stackNumber==1){ // 棧1元素進棧
        S->data[++S->top1]=e; // 若是棧1則先top1+1后給數(shù)組元素賦值
    }else if(stackNumber==2){ // 棧2元素進棧
        S->data[--S->top2]=e;  // 若是棧2則先top2-1后給數(shù)組元素賦值
    }
}

2.1.2.2 共享棧出棧

對于共享棧的pop方法，參數(shù)就只是判斷棧1棧2的參數(shù)stackNumber，代碼如下：

Status Pop(SqDoubleStack *S,SElemType *e.int stackNumber){
    if(stackNumber==1){
        if(S->top1==-1){  // 棧1是空棧
            return ERROR;
        }
        *e = S->data[S->top--];  // 將棧1的棧頂元素出棧
    }else if(stackNumber==2){
        if(S->top2==MAXSIZE){  // 棧2是空棧
            return ERROR;
        }
        *e = S->data[S->top2++] // 將棧2的棧頂元素出棧
    }
}
2.2 表達式求值——中綴表達式轉后綴表達式(編程題)

本內(nèi)容分成兩塊：

  1. 將中綴表達式轉化為后綴表達式（棧用來進出運算的符號）。

  2. 將后綴表達式進行運算得出結果（棧用來進出運算的數(shù)字）。

2.2.1 中綴表達式轉后綴表達式

中綴表達式“9＋(3+1)×3＋10÷2”轉化為后綴表達式“9 3 1 - 3＊＋10 2 ／ ＋”

方法：從左到右遍歷中綴表達式的每個數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達式的—部分；若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或優(yōu)先級不高于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出，并將當前符號進棧，一直到最終輸出后綴表達式為止。

思路：

  1. 初始化一空棧，用來對符號進出棧使用。

  2. 第—個字符是數(shù)字9，輸出9，后面是符號‘‘＋’’ ，進棧。

  3. 第三個字符是”（ “ ，依然是符號，因其只是左括號，還未配對，故進棧。

  4. 第四個字符是數(shù)字3，輸出，總表達式為9  3，接著是“-”，進棧。

  5. 接下來是數(shù)字1，輸出，總表達式為9  3  1，后面是符號“）” ，此時，我們需要去匹配此前的“（ ”，所以棧頂依次出棧，并輸出，直到“（ ”出棧為止。此時左括號上方只有“-’’，因此輸出“-”?？偟妮敵霰磉_式為9  3  1  -。

  6. 緊接著是符號”ד，因為此時的棧頂符號為“+”，優(yōu)先級低于“×”， 因此不輸出，“*”進棧。接著是數(shù)字3，輸出，總的表達式為9  3  1  -  3。

  7. 之后是符號“＋”，此時當前棧元素“*”，比這個“+”的優(yōu)先級高，因此棧中元素出棧并輸出（沒有比“+”更低的優(yōu)先級，所以全部出棧），總輸出表達式為9  3  1  -  3  *  +。然后將當前這個符號“+”進棧。也就是說，前6張圖的棧底的“＋”是指中綴表達式中開頭的9后面那個‘‘＋” ，而左圖中的棧底（也是棧頂）的“＋”是指“9＋（3-1）×3＋”中的最后—個“＋”。

  8. 緊接著數(shù)字10，輸出，總表達式變?yōu)?  3  1  -  3  *  +  10  2。后是符號“÷“，所以“／”進棧。

  9. 最后一個數(shù)字2，輸出，總的表達式為9  3  1  -  3 ＊＋10  2。

  10. 因為巳經(jīng)到最后，所以將棧中符號全部出棧并輸出。最終輸出的后綴表達式結果為9  3  1  -  3 ＊＋10  2  /  +。

2.2.2 后綴表達式計算

后綴表達式：9 3 1 - 3＊＋10 2 ／ ＋

  1. 初始化空棧，此棧用來對要運算的數(shù)字進出使用。

  2. 后綴表達式前三個都是數(shù)字，所以9、3、1進棧，如圖所示。

  3. 接下來是“-”，所以將棧中的1出棧作為減數(shù)，3出棧被減數(shù)，并運算3-1得到2，再將2進棧，如圖所示。

  4. 接著是數(shù)字3進棧，如圖所示。

  5. 后面是“*”，也就意味著棧中的3和2出棧，2與3相乘得到6，并將6進棧。

  6. 下面是‘‘＋” ，所以棧中6和9出棧，9與6相加，得到15，將15進棧。

  7. 接著是10與2兩數(shù)字進棧。

  8. 接下來是符號‘‘／”，因此，棧頂?shù)?與10出棧，10與2相除，得到5，將5進棧。

  9. 最后—個是符號“＋”，所以15與5出棧，并相加，得到20，將20進棧 。

  10. 結果是20出棧，棧變?yōu)榭铡?/p>

3 串、數(shù)組和廣義表

3.1 KMP模式匹配算法
3.1.1 算法原理

假設主串S=“abcdefab”，我們要匹配的子串T=”abcdex“，如果用樸素模式匹配算法，前5個字母，兩個串完全相等，直到第6個字母，”f“與“x”不等，如圖所示。

接下來按照樸素模式匹配算法，應該是按照上圖的步驟2、3、4、5、6，即主串S中當時，首字符與子串T的首字符均不等。

仔細觀察就會發(fā)現(xiàn)，對于要匹配的子串T來說，“abcdex”首字母“a”與后面串“bcdex”中任意一個字符都不相等。也就是說對于步驟1來說前五位字符分別相等，意味著子串T的首字符“a”不可能與S串的第2位到第5位字符相等。所以，在上圖中，步驟2、3、4、5的判斷都是多余的。

當我們知道T串中首字符“a”與T中后面的字符均不相等的前提下，T串后面的字符均不相等的前提下，T串的“a”與S串后面的“c”“d”“e”也都可以在步驟1之后就可以確定是不相等的，所以在樸素模式匹配算法中步驟2、3、4、5沒有必要，只保留步驟1、6即可，如圖所示。

保留步驟6中的判斷是因為在步驟1中，雖然我們已經(jīng)知道了，也不能斷定一定不等于，因此只需要保留步驟6這一步。

對于在子串中有與首字符相等的字符，也是可以省略一部分不必要的判斷步驟，如圖所示，省略T串前兩位“a”與“b”同S串中的4、5位置字符匹配操作。

在樸素的模式匹配算法中，主串的i值是不斷地回溯來完成的，而這種回溯其實是可以省略的，KMP模式匹配算法就是為了讓這沒必要的回溯不發(fā)生。

既然i值不回溯，也就是不可以變小，那要考慮的變化就是j值了，通過觀察可以發(fā)現(xiàn)，提到了T串的首字符與自身后面字符的比較，發(fā)現(xiàn)如果有相等字符，j值的變化就會不相同。也就是說，j值的變化與主串其實沒什么關系，關鍵取決于T串的結構中是否有重復問題，j值的大小取決于當前字符的串的前后綴的相似度。

在需要查找字符串前，先對要查找的字符串做一個分析，這樣可以大大減少我們查找的難度，提高查找的速度。

KMP算法：不回溯，從最長相等前后綴后面一個字符開始比較。

3.1.2 KMP算法字符串的前綴、后綴、最長相等前后綴

前綴：包含第一個字符，但不包含最后一個字符的子串。

后綴：包含最后一個字符，但不包含第一個字符的子串。

最長相等前后綴：前綴和后綴相等的最長子串。

例如字符串“abca”

  • 前綴：{a,ab,abc}

  • 后綴：{a,ca,bca}

  • 最長相等前后綴：a

字符串“ababa”

  • 前綴：{a,ab,aba,abab}

  • 后綴：{a,ba,aba,baba}

  • 最長相等前后綴：aba

3.1.2 next數(shù)組

當和發(fā)生失配時，i不回溯，下一趟讓j指向最長相等前后綴的后一個位置，用數(shù)組將這一位置記錄下來，即為next數(shù)組。

假設模式串T=“ababaaaba”，如圖所示。

  1. 當j=1時，第一位默認為0或-1，next[1]=0。

  2. 當j=2時，next[2]=1。

  3. 當j=3時，next[3]=1。

  4. 當j=4時，j由1到j-1的串是“aba”，next[4]=2。
    前綴字符：{a,ab}
    后綴字符：{a,ba}
    最長相等前后綴：{a}

  5. 當j=5時，j由1到j-1的串是“abab”，next[5]=3。
    前綴字符：{a,ab,aba}
    后綴字符：{b,ab,bab}
    最長相等前后綴：{ab}

  6. 當j=6時，j由1到j-1的串是“ababa”，next[6]=4。
    前綴字符：{a,ab,aba,abab}
    后綴字符：{a,ba,aba,baba}
    最長相等前后綴：{aba}

  7. 當j=7時，j由1到j-1的串是“ababaa”，next[7]=2。
    前綴字符：{a,ab,aba,abab,ababa}
    后綴字符：{a,aa,baa,abaa,babaa}
    最長相等前后綴：{a}

  8. 當j=8時，j由1到j-1的串是“ababaaa”，next[8]=2。
    前綴字符：{a,ab,aba,abab,ababa,ababaa}
    后綴字符：{a,aa,aaa,baaa,abaaa,babaaa}
    最長相等前后綴：{a}

  9. 當j=9時，j由1到j-1的串是“ababaaab”，next[9]=3。
    前綴字符：{a,ab,aba,abab,ababa,ababaa,ababaaa}
    后綴字符：{b,ab,aab,aaab,baaab,abaaab,babaaab}
    最長相等前后綴：{ab}

3.1.2 時間復雜度
3.2 廣義表

  1. 取表頭GetHead(LS)：取出的表頭為非空廣義表中的第一個元素，它可以是一個單原子，也可以是一個子表。

  2. 取表尾GetTail(LS)：**取出的表尾為除去表頭之外，由其他元素構成的表。**即表尾一定是一個廣義表。

例如：

GetHead(B)=e GetTail(B)=()

GetHead(D)=A GetTail(D)=(B,C)，

由于B,C是廣義表，則可繼續(xù)分解得到：

GetHead(B,C)=B GetTail(B,C)=C

廣義表()和(())不同，前者為空表，長度n=0；后者長度n=1，可繼續(xù)分解得到其表頭，表尾均為空表()。

4 樹和二叉樹

4.1 二叉樹的存儲結構
4.1.1 二叉樹的順序存儲結構

**二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹的結點存儲二叉樹中的結點，并且結點的存儲位置，**也就是數(shù)組的下標要體現(xiàn)結點之間的邏輯關系，比如雙親與孩子的關系，左右兄弟的關系等。

一棵完全二叉樹如圖所示：

將這棵二叉樹存入數(shù)組中，相應的下標對應其同樣的位置，如圖所示。

完全二叉樹定義的嚴格用順序結構也可以體現(xiàn)出二叉樹的結構，對于一般的二叉樹，雖然層序編號不能反映邏輯關系，但完全可以按完全二叉樹的編號，把不存在的結點設置為“^”即可，如圖所示。

但是對于一種極端情況，一棵深度為k的右斜樹，只有k個結點，卻需要分配6%252046%2520152%252046T177%252047T193%252050T201%252052T207%252057T213%252061V578Z%2522%253E%253C%252Fpath%253E%250A%253C%252Fdefs%253E%250A%253Cg%2520stroke%253D%2522currentColor%2522%2520fill%253D%2522currentColor%2522%2520stroke-width%253D%25220%2522%2520transform%253D%2522matrix(1%25200%25200%2520-1%25200%25200)%2522%2520aria-hidden%253D%2522true%2522%253E%250A%2520%253Cuse%2520xlink%253Ahref%253D%2522%2523E1-MJMAIN-32%2522%2520x%253D%25220%2522%2520y%253D%25220%2522%253E%253C%252Fuse%253E%250A%2520%253Cuse%2520transform%253D%2522scale(0.707)%2522%2520xlink%253Ahref%253D%2522%2523E1-MJMATHI-6B%2522%2520x%253D%2522707%2522%2520y%253D%2522583%2522%253E%253C%252Fuse%253E%250A%2520%253Cuse%2520xlink%253Ahref%253D%2522%2523E1-MJMAIN-2212%2522%2520x%253D%25221191%2522%2520y%253D%25220%2522%253E%253C%252Fuse%253E%250A%2520%253Cuse%2520xlink%253Ahref%253D%2522%2523E1-MJMAIN-31%2522%2520x%253D%25222192%2522%2520y%253D%25220%2522%253E%253C%252

本文題目：Java數(shù)據(jù)結構重點知識有哪些
網(wǎng)頁網(wǎng)址：http://bm7419.com/article12/igccgc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、App設計、網(wǎng)站營銷、微信小程序、企業(yè)網(wǎng)站制作、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

成都seo排名網(wǎng)站優(yōu)化