這篇“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
算法步驟：
創(chuàng)建表長為m+n的空表LC。
指針pc初始化，指向LC的第一個元素。
指針pa和pb初始化，分別指向LA和LB的第一個元素。
當指針pa和pb均為到達相應表尾時，則依次比較pa和pb所指向的元素值，從LA或LB中摘取元素值較小的結點插入到LC的最后。
如果pb已到達LB的表尾，依次將LA的剩余元素查到LC的最后。
如果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++;
}
}算法步驟:
指針pa和pb初始化，分別指向LA和LB的第一個結點
LC的結點取值為LA的頭結點
指針pc初始化，指向LC的頭結點
當指針pa和pb均未到達相應表尾，則依次比較pa和pb所指向的元素值，從LA或LB中摘取元素值較小的結點插入到LC的最后
將非空表的剩余段插入到pc所指結點后。
釋放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的頭結點
}棧：限定僅在表尾進行插入和刪除操作的線性表。
允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又被稱為后進先出(Last In First Out)的線性表，簡稱LIFO結構。
棧的插入操作，叫做進棧，也稱壓棧、入棧。
棧的刪除操作，叫做出棧，有的也叫作彈棧。
單棧?？諚l件：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;
}棧的順序存儲還是很方便的，因為它只準棧頂進出元素，所以不存在線性表插入和刪除時需要移動元素的問題。不過它有一個很大的缺陷，就是必須事先確定數(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;對于共享棧的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ù)組元素賦值
}
}對于共享棧的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的棧頂元素出棧
}
}本內(nèi)容分成兩塊：
將中綴表達式轉化為后綴表達式（棧用來進出運算的符號）。
將后綴表達式進行運算得出結果（棧用來進出運算的數(shù)字）。
中綴表達式“9＋(3+1)×3＋10÷2”轉化為后綴表達式“9 3 1 - 3＊＋10 2 ／ ＋”
方法：從左到右遍歷中綴表達式的每個數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達式的—部分；若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或優(yōu)先級不高于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出，并將當前符號進棧，一直到最終輸出后綴表達式為止。
思路：
初始化一空棧，用來對符號進出棧使用。
第—個字符是數(shù)字9，輸出9，后面是符號‘‘＋’’ ，進棧。
第三個字符是”（ “ ，依然是符號，因其只是左括號，還未配對，故進棧。
第四個字符是數(shù)字3，輸出，總表達式為9 3，接著是“-”，進棧。
接下來是數(shù)字1，輸出，總表達式為9 3 1，后面是符號“）” ，此時，我們需要去匹配此前的“（ ”，所以棧頂依次出棧，并輸出，直到“（ ”出棧為止。此時左括號上方只有“-’’，因此輸出“-”。總的輸出表達式為9 3 1 -。
緊接著是符號”ד，因為此時的棧頂符號為“+”，優(yōu)先級低于“×”， 因此不輸出，“*”進棧。接著是數(shù)字3，輸出，總的表達式為9 3 1 - 3。
之后是符號“＋”，此時當前棧元素“*”，比這個“+”的優(yōu)先級高，因此棧中元素出棧并輸出（沒有比“+”更低的優(yōu)先級，所以全部出棧），總輸出表達式為9 3 1 - 3 * +。然后將當前這個符號“+”進棧。也就是說，前6張圖的棧底的“＋”是指中綴表達式中開頭的9后面那個‘‘＋” ，而左圖中的棧底（也是棧頂）的“＋”是指“9＋（3-1）×3＋”中的最后—個“＋”。
緊接著數(shù)字10，輸出，總表達式變?yōu)? 3 1 - 3 * + 10 2。后是符號“÷“，所以“／”進棧。
最后一個數(shù)字2，輸出，總的表達式為9 3 1 - 3 ＊＋10 2。
因為巳經(jīng)到最后，所以將棧中符號全部出棧并輸出。最終輸出的后綴表達式結果為9 3 1 - 3 ＊＋10 2 / +。
后綴表達式：9 3 1 - 3＊＋10 2 ／ ＋
初始化空棧，此棧用來對要運算的數(shù)字進出使用。
后綴表達式前三個都是數(shù)字，所以9、3、1進棧，如圖所示。
接下來是“-”，所以將棧中的1出棧作為減數(shù)，3出棧被減數(shù)，并運算3-1得到2，再將2進棧，如圖所示。
接著是數(shù)字3進棧，如圖所示。
后面是“*”，也就意味著棧中的3和2出棧，2與3相乘得到6，并將6進棧。
下面是‘‘＋” ，所以棧中6和9出棧，9與6相加，得到15，將15進棧。
接著是10與2兩數(shù)字進棧。
接下來是符號‘‘／”，因此，棧頂?shù)?與10出棧，10與2相除，得到5，將5進棧。
最后—個是符號“＋”，所以15與5出棧，并相加，得到20，將20進棧 。
結果是20出棧，棧變?yōu)榭铡?/p>
假設主串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算法：不回溯，從最長相等前后綴后面一個字符開始比較。
前綴：包含第一個字符，但不包含最后一個字符的子串。
后綴：包含最后一個字符，但不包含第一個字符的子串。
最長相等前后綴：前綴和后綴相等的最長子串。
例如字符串“abca”
前綴：{a,ab,abc}
后綴：{a,ca,bca}
最長相等前后綴：a
字符串“ababa”
前綴：{a,ab,aba,abab}
后綴：{a,ba,aba,baba}
最長相等前后綴：aba
當和發(fā)生失配時，i不回溯，下一趟讓j指向最長相等前后綴的后一個位置，用數(shù)組將這一位置記錄下來，即為next數(shù)組。
假設模式串T=“ababaaaba”，如圖所示。
當j=1時，第一位默認為0或-1，next[1]=0。
當j=2時，next[2]=1。
當j=3時，next[3]=1。
當j=4時，j由1到j-1的串是“aba”，next[4]=2。
前綴字符：{a,ab}
后綴字符：{a,ba}
最長相等前后綴：{a}
當j=5時，j由1到j-1的串是“abab”，next[5]=3。
前綴字符：{a,ab,aba}
后綴字符：{b,ab,bab}
最長相等前后綴：{ab}
當j=6時，j由1到j-1的串是“ababa”，next[6]=4。
前綴字符：{a,ab,aba,abab}
后綴字符：{a,ba,aba,baba}
最長相等前后綴：{aba}
當j=7時，j由1到j-1的串是“ababaa”，next[7]=2。
前綴字符：{a,ab,aba,abab,ababa}
后綴字符：{a,aa,baa,abaa,babaa}
最長相等前后綴：{a}
當j=8時，j由1到j-1的串是“ababaaa”，next[8]=2。
前綴字符：{a,ab,aba,abab,ababa,ababaa}
后綴字符：{a,aa,aaa,baaa,abaaa,babaaa}
最長相等前后綴：{a}
當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}
取表頭GetHead(LS)：取出的表頭為非空廣義表中的第一個元素，它可以是一個單原子，也可以是一個子表。
取表尾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ù)分解得到其表頭，表尾均為空表()。
**二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹的結點存儲二叉樹中的結點，并且結點的存儲位置，**也就是數(shù)組的下標要體現(xiàn)結點之間的邏輯關系，比如雙親與孩子的關系，左右兄弟的關系等。
一棵完全二叉樹如圖所示：
將這棵二叉樹存入數(shù)組中，相應的下標對應其同樣的位置，如圖所示。
完全二叉樹定義的嚴格用順序結構也可以體現(xiàn)出二叉樹的結構，對于一般的二叉樹，雖然層序編號不能反映邏輯關系，但完全可以按完全二叉樹的編號，把不存在的結點設置為“^”即可，如圖所示。
