溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“Java數據結構重點知識有哪些”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java數據結構重點知識有哪些”文章吧。
算法步驟：
創建表長為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)，不含任何數據元素的棧稱為空棧。棧又被稱為后進先出(Last In First Out)的線性表，簡稱LIFO結構。
棧的插入操作，叫做進棧，也稱壓棧、入棧。
棧的刪除操作，叫做出棧，有的也叫作彈棧。
單棧棧空條件：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;
}棧的順序存儲還是很方便的，因為它只準棧頂進出元素，所以不存在線性表插入和刪除時需要移動元素的問題。不過它有一個很大的缺陷，就是必須事先確定數組存儲空間大小，萬—不夠用了，就需要用編程手段來擴展數組的容量，非常麻煩。
共享棧就可以很好的解決這個問題。如果我們有兩個相同類型的棧，我們為它們各自開辟了數組空間，極有可能是第—個棧已經滿了，再進棧就溢出了，而另一個棧還有很多存儲空間空閑，我們完全可以用—個數組來存儲兩個棧，充分利用這個數組占用的內存空間。
設置數組有兩個端點，兩個棧有兩個棧底，讓一個棧的棧底為數組的始端，即下標為0處，另—個棧為數組的末端，即下標為數組長度n-1處。這樣兩個棧如果增加元素，就是兩端點向中間延伸。
棧空條件：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方法，除了要插入元素值參數外，還需要有一個參數判斷是棧1還是棧2的棧號參數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后給數組元素賦值
}else if(stackNumber==2){ // 棧2元素進棧
S->data[--S->top2]=e; // 若是棧2則先top2-1后給數組元素賦值
}
}對于共享棧的pop方法，參數就只是判斷棧1棧2的參數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的棧頂元素出棧
}
}本內容分成兩塊：
將中綴表達式轉化為后綴表達式（棧用來進出運算的符號）。
將后綴表達式進行運算得出結果（棧用來進出運算的數字）。
中綴表達式“9＋(3+1)×3＋10÷2”轉化為后綴表達式“9 3 1 - 3＊＋10 2 ／ ＋”
方法：從左到右遍歷中綴表達式的每個數字和符號，若是數字就輸出，即成為后綴表達式的—部分；若是符號，則判斷其與棧頂符號的優先級，是右括號或優先級不高于棧頂符號（乘除優先加減）則棧頂元素依次出棧并輸出，并將當前符號進棧，一直到最終輸出后綴表達式為止。
思路：
初始化一空棧，用來對符號進出棧使用。
第—個字符是數字9，輸出9，后面是符號‘‘＋’’ ，進棧。
第三個字符是”（ “ ，依然是符號，因其只是左括號，還未配對，故進棧。
第四個字符是數字3，輸出，總表達式為9 3，接著是“-”，進棧。
接下來是數字1，輸出，總表達式為9 3 1，后面是符號“）” ，此時，我們需要去匹配此前的“（ ”，所以棧頂依次出棧，并輸出，直到“（ ”出棧為止。此時左括號上方只有“-’’，因此輸出“-”。總的輸出表達式為9 3 1 -。
緊接著是符號”ד，因為此時的棧頂符號為“+”，優先級低于“×”， 因此不輸出，“*”進棧。接著是數字3，輸出，總的表達式為9 3 1 - 3。
之后是符號“＋”，此時當前棧元素“*”，比這個“+”的優先級高，因此棧中元素出棧并輸出（沒有比“+”更低的優先級，所以全部出棧），總輸出表達式為9 3 1 - 3 * +。然后將當前這個符號“+”進棧。也就是說，前6張圖的棧底的“＋”是指中綴表達式中開頭的9后面那個‘‘＋” ，而左圖中的棧底（也是棧頂）的“＋”是指“9＋（3-1）×3＋”中的最后—個“＋”。
緊接著數字10，輸出，總表達式變為9 3 1 - 3 * + 10 2。后是符號“÷“，所以“／”進棧。
最后一個數字2，輸出，總的表達式為9 3 1 - 3 ＊＋10 2。
因為巳經到最后，所以將棧中符號全部出棧并輸出。最終輸出的后綴表達式結果為9 3 1 - 3 ＊＋10 2 / +。
后綴表達式：9 3 1 - 3＊＋10 2 ／ ＋
初始化空棧，此棧用來對要運算的數字進出使用。
后綴表達式前三個都是數字，所以9、3、1進棧，如圖所示。
接下來是“-”，所以將棧中的1出棧作為減數，3出棧被減數，并運算3-1得到2，再將2進棧，如圖所示。
接著是數字3進棧，如圖所示。
后面是“*”，也就意味著棧中的3和2出棧，2與3相乘得到6，并將6進棧。
下面是‘‘＋” ，所以棧中6和9出棧，9與6相加，得到15，將15進棧。
接著是10與2兩數字進棧。
接下來是符號‘‘／”，因此，棧頂的2與10出棧，10與2相除，得到5，將5進棧。
最后—個是符號“＋”，所以15與5出棧，并相加，得到20，將20進棧 。
結果是20出棧，棧變為空。
假設主串S=“abcdefab”，我們要匹配的子串T=”abcdex“，如果用樸素模式匹配算法，前5個字母，兩個串完全相等，直到第6個字母，”f“與“x”不等，如圖所示。
接下來按照樸素模式匹配算法，應該是按照上圖的步驟2、3、4、5、6，即主串S中當時，首字符與子串T的首字符均不等。
仔細觀察就會發現，對于要匹配的子串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中，雖然我們已經知道了，也不能斷定一定不等于，因此只需要保留步驟6這一步。
對于在子串中有與首字符相等的字符，也是可以省略一部分不必要的判斷步驟，如圖所示，省略T串前兩位“a”與“b”同S串中的4、5位置字符匹配操作。
在樸素的模式匹配算法中，主串的i值是不斷地回溯來完成的，而這種回溯其實是可以省略的，KMP模式匹配算法就是為了讓這沒必要的回溯不發生。
既然i值不回溯，也就是不可以變小，那要考慮的變化就是j值了，通過觀察可以發現，提到了T串的首字符與自身后面字符的比較，發現如果有相等字符，j值的變化就會不相同。也就是說，j值的變化與主串其實沒什么關系，關鍵取決于T串的結構中是否有重復問題，j值的大小取決于當前字符的串的前后綴的相似度。
在需要查找字符串前，先對要查找的字符串做一個分析，這樣可以大大減少我們查找的難度，提高查找的速度。
KMP算法：不回溯，從最長相等前后綴后面一個字符開始比較。
前綴：包含第一個字符，但不包含最后一個字符的子串。
后綴：包含最后一個字符，但不包含第一個字符的子串。
最長相等前后綴：前綴和后綴相等的最長子串。
例如字符串“abca”
前綴：{a,ab,abc}
后綴：{a,ca,bca}
最長相等前后綴：a
字符串“ababa”
前綴：{a,ab,aba,abab}
后綴：{a,ba,aba,baba}
最長相等前后綴：aba
當和發生失配時，i不回溯，下一趟讓j指向最長相等前后綴的后一個位置，用數組將這一位置記錄下來，即為next數組。
假設模式串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是廣義表，則可繼續分解得到：
GetHead(B,C)=B GetTail(B,C)=C
廣義表()和(())不同，前者為空表，長度n=0；后者長度n=1，可繼續分解得到其表頭，表尾均為空表()。
**二叉樹的順序存儲結構就是用一維數組存儲二叉樹的結點存儲二叉樹中的結點，并且結點的存儲位置，**也就是數組的下標要體現結點之間的邏輯關系，比如雙親與孩子的關系，左右兄弟的關系等。
一棵完全二叉樹如圖所示：
將這棵二叉樹存入數組中，相應的下標對應其同樣的位置，如圖所示。
完全二叉樹定義的嚴格用順序結構也可以體現出二叉樹的結構，對于一般的二叉樹，雖然層序編號不能反映邏輯關系，但完全可以按完全二叉樹的編號，把不存在的結點設置為“^”即可，如圖所示。
但是對于一種極端情況，一棵深度為k的右斜樹，只有k個結點，卻需要分配個存儲單元，對存儲空間有著極大的浪費，如圖所示。所以，順序存儲結構一般只用于完全二叉樹。
**二叉樹每個結點最多有兩個孩子，所以為它涉及一個數據域和兩個指針域，稱這樣的鏈表為二叉鏈表。**結點結構涉及如圖所示。
其中，data是數據域；lchild和rchild都是指針域，分別存放指向左孩子和右孩子的指針。
二叉鏈表的結點結構定義代碼如下：
typedef struct BiTNode{ // 結點結構
TElemType data; // 結點數據
struct BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;結構示意圖如圖所示：
建議自己畫兩棵樹試試
兩個二叉樹遍歷的性質：
已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。
已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。
已知前序和后序遍歷，是不能確定一棵二叉樹的。
二叉樹的定義是使用遞歸的方式，實現遍歷算法也可以采用遞歸，二叉樹的前序遍歷算法如下：
void PreOrderTraverse(BiTree T){
if(T==NULL){ // 樹為空
return;
}
printf("%c",T-data); // 對數據進行輸出操作
PreOrderTraverse(T->lchild); // 先序遍歷左子樹
PreOrderTraverse(T->rchild); // 先序遍歷右子樹
}二叉樹的中序遍歷算法和前序遍歷算法僅僅是代碼順序上的差，實現代碼如下：
// 初始條件：二叉樹T存在
// 操作結果：中序遞歸遍歷T，依次輸出值
void InOrderTraverse(BiTree T){
if(T==null){
return;
}
InOrderTraverse(T->lchild); // 中序遍歷左子樹
printf("%c",T->data); // 進行輸出結點數據的操作
InOrderTraverse(T->rchild); // 中序遍歷右子樹
}后序遍歷算法與前序、中序遍歷算法類似，只是執行步驟有些差異，算法代碼如下：
// 初始條件：二叉樹T存在
// 操作結果：后續遞歸遍歷T
void PostOrderTraverse(BiTree T){
if(T==null){
return;
}
PostOrderTraverse(T->lchild); // 后序遍歷左子樹
PostOrderTraverse(T->rchild); // 后序遍歷右子樹
print("%c",T->data); // 進行結點數據輸出操作
}int NodeCount(BiTree T){
if(T==null){
return 0;
}else{
return NodeCount(T->lchild)+NodeCount(l->rchild)+1;
}
}int NodeCount_Leaf(BiTree T){
if(T==null){
return 0;
}else if(T>lchild==null&&T->rchild==null){
return 1;
}else {
return NodeCount_Leaf(T->lchild)+NodeCount_Leaf(T->rchild);
}
}int NodeCount_D1( BiTree T){
if(T==NULL) {
return 0;
}
if(T->lchild==NULL&&T->rchild!=NULL||T->rchild==NULL&&T->lchild!=NULL){
return 1 + NodeCount_D1(T->lchild) + NodeCount_D1(T->rchild);
}
return NodeCount_D1(T->lchild)+NodeCount_D1(T->rchild);
}int NodeCount_D2(BiTree T){
if(T==NULL) {
return 0;
}else if(T->lchild&&T->rchild){
return NodeCount_D2(T->lchild)+NodeCount_D2(T->rchild)+1;
}else{
return NodeCount_D2(T->lchild)+NodeCount_D2(T->rchild);
}
}/* 初始條件: 二叉樹T存在。操作結果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}核心思想、Prim算法和Kruskal算法的區別：歸并點和歸并邊
**構造連通網的最小代價生成樹稱為最小生成樹（Mininum Cost Spanning Tree）。**找連通網的最小生成樹，經典的有兩種算法，普里姆算法和克魯斯卡爾算法。
我們先構造鄰接矩陣，如圖所示：
從開始，旁有兩條邊, 10與11比, 10更小一些些。所以選至的邊為最小生成樹的第—條邊，如左下圖所示。然后我們看和兩個頂點的其他邊，有11、16、12、18，這里面最小的是11，所以到的邊為最小生成樹的第二條邊，如中下圖所示。然后我們看、和三個頂點的其他邊，有18、12、16、17、26，這里面最小的是12，所以到的邊為最小生成樹的第三條邊，如右下圖所示。
類似的方法，我們可以得到下面的六張圖：
Prim算法實現代碼如下：
/* Prim算法生成最小生成樹 */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; /* 保存相關頂點下標 */
int lowcost[MAXVEX]; /* 保存相關頂點間邊的權值 */
lowcost[0] = 0;/* 初始化第一個權值為0，即v0加入生成樹 */
/* lowcost的值為0，在這里就是此下標的頂點已經加入生成樹 */
adjvex[0] = 0; /* 初始化第一個頂點下標為0 */
for(i = 1; i < G.numVertexes; i++) /* 循環除下標為0外的全部頂點 */
{
lowcost[i] = G.arc[0][i]; /* 將v0頂點與之有邊的權值存入數組 */
adjvex[i] = 0; /* 初始化都為v0的下標 */
}
for(i = 1; i < G.numVertexes; i++)
{
min = GRAPH_INFINITY; /* 初始化最小權值為∞， */
/* 通常設置為不可能的大數字如32767、65535等 */
j = 1;k = 0;
while(j < G.numVertexes) /* 循環全部頂點 */
{
if(lowcost[j]!=0 && lowcost[j] < min)/* 如果權值不為0且權值小于min */
{
min = lowcost[j]; /* 則讓當前權值成為最小值 */
k = j; /* 將當前最小值的下標存入k */
}
j++;
}
printf("(%d, %d)\n", adjvex[k], k);/* 打印當前頂點邊中權值最小的邊 */
lowcost[k] = 0;/* 將當前頂點的權值設置為0,表示此頂點已經完成任務 */
for(j = 1; j < G.numVertexes; j++) /* 循環所有頂點 */
{
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{/* 如果下標為k頂點各邊權值小于此前這些頂點未被加入生成樹權值 */
lowcost[j] = G.arc[k][j];/* 將較小的權值存入lowcost相應位置 */
adjvex[j] = k; /* 將下標為k的頂點存入adjvex */
}
}
}
}普里姆算法是以某頂點為起點，逐步找各頂點上最小權值的邊來構建最小生成樹。同樣的思路’我們也可以直接就以邊為目標去構建，因為權值是在邊上，直接去找最小權值的邊來構建生成，只不過構建時要考慮是否會形成環路而已。
我們將同樣的圖的鄰接矩陣通過程序轉化為右下圖的邊集數組，并旦對它們按權值從小到大排序。
克魯斯卡爾算法的思想就是站在了上帝視角，先把權值最短的邊—個個挑出來。左圖找到了權值最短邊和，中下圖找到了權值第二短邊和，右下圖找到了權值第三短邊和。
我們找到了大量的權值短邊后’發現了—個問題。比如當完成到左下圖的情況時，我們接下來去找權值最小的邊應該是和，這條邊的權值是17，但是這會帶來一個結果, 和已經通過中轉的頂點和連通了，它們并不需要繼續再關聯否則就是重復。而和兩個頂點更應該與頂點、和進行連接。檢查了它們的權值，22、21、24、19、26，最終選擇了19作為最小的權值邊。如右下圖，完成最小生成樹的構建。
克魯斯卡爾算法實現代碼如下：
/* 查找連線頂點的尾部下標 */
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
/* 生成最小生成樹 */
void MiniSpanTree_Kruskal(MGraph G)
{
int i, j, n, m;
int k = 0;
int parent[MAXVEX];/* 定義一數組用來判斷邊與邊是否形成環路 */
Edge edges[MAXEDGE];/* 定義邊集數組,edge的結構為begin,end,weight,均為整型 */
/* 用來構建邊集數組并排序********************* */
for ( i = 0; i < G.numVertexes-1; i++)
{
for (j = i + 1; j < G.numVertexes; j++)
{
if (G.arc[i][j]<GRAPH_INFINITY)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
sort(edges, &G);
/* ******************************************* */
for (i = 0; i < G.numVertexes; i++)
parent[i] = 0; /* 初始化數組值為0 */
printf("打印最小生成樹：\n");
for (i = 0; i < G.numEdges; i++) /* 循環每一條邊 */
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if (n != m) /* 假如n與m不等，說明此邊沒有與現有的生成樹形成環路 */
{
parent[n] = m; /* 將此邊的結尾頂點放入下標為起點的parent中。 */
/* 表示此頂點已經在生成樹集合中 */
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}順序查找的算法實現如下：
/* 無哨兵順序查找，a為數組，n為要查找的數組個數，key為要查找的關鍵字 */
int Sequential_Search(int *a,int n,int key)
{
int i;
for(i=1;i<=n;i++)
{
if (a[i]==key)
return i;
}
return 0;
}這種算法在每次循環時都需要對i是否越界，即是否小于等于n作判斷。優化此算法可以設置一個哨兵，可以解決不需要每次讓i與n作比較。
/* 有哨兵順序查找 */
int Sequential_Search3(int *a,int n,int key)
{
int i;
a[0]=key;
i=n;
while(a[i]!=key)
{
i--;
}
return i;
}此時代碼是從尾部開始查找, 由于a[0]=key，也就是說，如果在a[j]中有key則返回值，查找成功。否則—定在最終的a[0]處等于key，此時返回的是0，即說明a[1]-a[n]中沒有關鍵字key，查找失敗。
折半查找（Binary Search）技術，又稱為二分查找。
它的前提是線性表中的記錄必須是關鍵碼有序（通常從小到大有序），線性表必須采用順序存儲。
折半查找的基本思想是：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續童找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，直到查找成功，或所有查找區域無記錄，查找失敗為止。
折半查找算法代碼如下：
/* 折半查找 */
int Binary_Search(int *a,int n,int key)
{
int low,high,mid;
low=1; /* 定義最低下標為記錄首位 */
high=n; /* 定義最高下標為記錄末位 */
while(low<=high)
{
mid=(low+high)/2; /* 折半 */
if (key<a[mid]) /* 若查找值比中值小 */
high=mid-1; /* 最高下標調整到中位下標小一位 */
else if (key>a[mid])/* 若查找值比中值大 */
low=mid+1; /* 最低下標調整到中位下標大一位 */
else
{
return mid; /* 若相等則說明mid即為查找到的位置 */
}
}
return 0;
}算法執行流程如下：
假設我們傳入的參數，我們要查找的數值為62，初始化n=10，key=62，第3-5行，此時low=1，high=10，如圖所示。
第6-15行循環，進行查找。
第8行，mid計算出得5，由于a[5]=47<key，所以執行第12行，low=5+1=6，如圖所示。
再次循環，mid=(6+10)/2=8，此時a[8]=73>key，所以執行第10行，high=8-1=7，如圖所示。
再次循環，mid=(6+7)/2=6，此時a[6]=59<key，所以執行第12行，low=6+1=7，如圖所示。
再次循環，mid=(7+7)/2=7，a[7]=62=key，查找成功，返回7。
折半查找時間復雜度：
散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系，使得每個關鍵字key對應一個存儲位置。
存儲位置=f(關鍵字)
對應關系稱為散列函數，又稱為哈希（Hash）函數。
采用散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散列表或哈希表。散列技術既是一種存儲方法，也是一種查找方法。
散列函數可能會把兩個或兩個以上的不同關鍵字映射到同一地址，稱這些情況為沖突，這些發生碰撞的不同關鍵字稱為同義詞。
對于下圖所示的0-100歲的人口數字統計表，對年齡這個關鍵字就可以直接用年齡的數字作為地址，此時f(key)=key。
如果我們要統計的是1980年后出生年份的人口數，如下圖所示，我們對出生年份這個關鍵字可以用年份減去1980來作為地址。此時f(key)=key-1980。
直接去關鍵字的某個線性函數值為散列地址，散列函數為：
直接定址法的散列函數的優點是簡單、均勻，也不會產生沖突，但是需要提前知道關鍵字的分布情況，適合查找表較小且連續的情況。
除留余數法是最常用的構造散列函數的方法，假設散列表表長為m，取一個不大于m但最接近或等于m的質數p，散列函數為：
假設我們有12個記錄的關鍵字構造散列表時，就用了的方法，比如，所以它存儲在下標為5的位置。
根據經驗，若散列表表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20質因子的合數。
開放地址法
線性探測法
開放定址法就是一旦發生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
公式是：
一個簡單的案例，我們的關鍵字集合為，表長為12.我們用散列函數。
當計算前5個數，都是沒有沖突的散列地址，直接存入，如下圖所示。
計算key=37時，發現，此時就與25所在的位置沖突，于是再次進行計算，于是將37存入下標為2的位置，如圖所示。
到了key=48，我們計算得到，與12所在的0位置沖突了，繼續計算，與25所在的位置沖突，于是一直到，才有空位，如圖所示。
這種解決沖突的開放定址法稱為線性探測法。
二次探測
當時，稱為二次探測法。增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域。
公式如下：
偽隨機探測
在沖突時，對于位移量 采用隨機函數計算得到，我們稱為隨機探測法。
冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，指導沒有反序的記錄為止。
冒泡排序算法：,
void BubbliSort(SqList *L){
int i,j;
Status flag= TRUE;
for (i=1;i<L->length && flag;i++){ // 如果flag發生數據交換，則退出循環
flag = FALSE;
for(j=L->length-1;j>=i;j--){ // j從后往前循環
if(L->r[j]>L->r[j+1]){ // 若前者大于后者
swap(L,j,j+1); // 交換L->r[j]與L->r[j+1]的值
flag = TRUE; // 如果有數據交換，則flag為TRUE
}
}
}
/* 交換L中數組r的下標為i和j的值 */
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}算法步驟：
設待排序的記錄存在在數組r[1····n]中，首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序(L->r[j]>L->r[j+1])，則交換兩個記錄。然后比較第二個記錄和第三個記錄的關鍵字。依次類推，直到第n-1個記錄和第n個記錄的關鍵字進行過比較為止，上述過程稱為冒泡排序的第一個趟，其結果是使得關鍵字最大的記錄被安置到最后一個記錄的位置上。
然后進行第二趟冒泡排序，對前n-1個記錄進行同樣操作，其結果是使關鍵字次大的記錄被安置到第n-1個記錄的位置上。
重復上述比較和交換過程，第i趟是從L-r[1]到L->r[L->length-i+1]依次比較相鄰兩個記錄的關鍵字，并在“逆序”時交換相鄰記錄，其結果是這L->length-i+1個記錄中關鍵字最大的記錄被交換到第L->length-i+1的位置上。指導在某一趟排序過程中沒有進行過交換記錄的操作，說明序列已全部達到排序要求，則完成排序。
若待排序記錄的關鍵字序列為
{49,38,65,97,76,13,27,49}，請給出用冒泡排序法進行排序的過程。
時間復雜度：，總的時間復雜度
快速排序的基本思想是：:通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另—部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
快速排序算法的實現：
/* 交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置 */
/* 此時在它之前(后)的記錄均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; /* 用子表的第一個記錄作樞軸記錄 */
while(low<high) /* 從表的兩端交替地向中間掃描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* 將比樞軸記錄小的記錄交換到低端 */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* 將比樞軸記錄大的記錄交換到高端 */
}
return low; /* 返回樞軸所在位置 */
}
/* 對順序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /* 將L->r[low..high]一分為二，算出樞軸值pivot */
QSort(L,low,pivot-1); /* 對低子表遞歸排序 */
QSort(L,pivot+1,high); /* 對高子表遞歸排序 */
}
}
/* 對順序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}Partiotion()函數要做的，就是先選取一個當中的一個關鍵字，想盡辦法將它放到一個位置，使得左邊的值都比它小，右邊的值比它大，稱這樣的關鍵字稱為樞軸(pivot)。
快速排序算法執行流程：
假設我們要排序的序列為{50,10,90,30,70,40,80,60,20}，執行流程如下：
程序開始執行，此時low=1，high=L->length=9。第4行，我們將L.row[low]=L.r[1]=50賦值給樞軸變量pivotkey，如圖所示。
第5-13行為while循環，目前low=1<high=9，執行內部語句。
第7行，L.r[high]=L.r[9]=20不大于pivitkey=50，因此不執行第8行。
第9行，交換L.r[low]與L.r[high]的值，使得L.r[1]=20，L.r[9]=50，如圖所示。
第10行，當L.r[low]=L.r[1]=20, pivotkey＝50，L.r[low]＜pivotkey，因此第11行，low++,此時low＝2。繼續循環，L.r[2]=10<50，low++，此時low＝3。L.r[3]=90＞50，退出循環。
第12行，交換L.r[low]＝L.r[3]與L.r[high]＝L.r[9]的值，使得L.r[3]＝50，L.r[9]＝90。此對相當于將一個比50大的值90交換到了50的右邊。注意此時low已經指向了3，如下圖所示。
繼續第5行,因為low＝3＜high＝9，執行循環體。
第7行嗎，當L.r[high]＝L.r[9]＝90， pivotkey＝50，L.r[high]＞pivotkey，因此第8行，high-，此時high=8。繼續循環，L.r[8]＝60＞50, high-，此時high＝7。L.r[7]＝80>50，high-，此時high＝6。L.r[6]＝40＜50，退出循環。
第9行，交換L.r[low]＝L.r[3]＝50與L.r[high]＝L.r[6]＝40的值，使得L.r[3]＝40,L.r[6]＝50,如下圖所示。
第10行，當L.r[low]＝L.r[3]＝40， pivotkey＝50, L.r［low]＜pivotkey，因此第11行, low++，此時low＝4。繼續循環L.r[4]＝30＜50，low++，此時low＝5。L.r[5]＝70＞50，退出循環。
12行，交換L.r[low]＝L.r[5]＝70與L.r[high]＝L.r[6]＝50的值，使得L.r[5]＝50，L.r[6]＝70，如圖所示。
再次循環。因low＝5＜high＝6，執行循環體后， low＝hlgh＝5，退出循環，如下圖所示。
最后第14行，返回low的值5。函數執行完成。接下來就是遞歸調用QSort(L,1,5-1)和QSort(L,5+1,9)，分別進行同樣的Partiotion操作，直到順序全部正確為止。
Partiotion函數的作用就是將選取的pivotkey不斷交換，將比它小的換到它的左邊，比它大的換到它的右邊，它也在交換中不斷更改自己的位置，直到完全滿足這個要求為止。
以上就是關于“Java數據結構重點知識有哪些”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
