日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
常用數(shù)據(jù)結(jié)構(gòu)：線性結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。常見的數(shù)據(jù)結(jié)構(gòu)分類方式如下圖：

目前創(chuàng)新互聯(lián)已為1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站托管運(yùn)營、企業(yè)網(wǎng)站設(shè)計(jì)、賀蘭網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

常用的線性結(jié)構(gòu)有：線性表，棧，隊(duì)列，循環(huán)隊(duì)列，數(shù)組。線性表中包括順序表、鏈表等，其中，棧和隊(duì)列只是屬于邏輯上的概念，實(shí)際中不存在，僅僅是一種思想，一種理念；線性表則是在內(nèi)存中數(shù)據(jù)的一種組織、存儲(chǔ)的方式。

順序表

順序表將元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲(chǔ)單元中，在內(nèi)存物理上是連續(xù)的。如下圖：

順序表存儲(chǔ)密度較大，節(jié)省空間；但需要事先確定容量，在時(shí)間性能方面，讀運(yùn)算較快，時(shí)間復(fù)雜度為O(1)；查找運(yùn)算為O(n/2)，和鏈表同樣；插入運(yùn)算和刪除運(yùn)算如果要操作中間一個(gè)元素，比如3，那么就需要把3后面的元素全部進(jìn)行移動(dòng)，因此時(shí)間復(fù)雜度相對(duì)鏈表要大一些，插入時(shí)間復(fù)雜度***為O(0)或最壞為O(n)；刪除時(shí)間復(fù)雜度為O([n-1]/2)；

鏈表

鏈表擁有很多結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)前半部分是數(shù)據(jù)域，后半部分是指針域，指針域指針指向下一個(gè)結(jié)點(diǎn)；鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。

單鏈表：

 

從上圖可以看出，單鏈表的上一個(gè)結(jié)點(diǎn)指針指向下一個(gè)結(jié)點(diǎn)，***一個(gè)結(jié)點(diǎn)的指針域?yàn)閚ull。

結(jié)點(diǎn)的刪除：

 

刪除一個(gè)結(jié)點(diǎn)，如刪除上圖中q結(jié)點(diǎn)，只需將p結(jié)點(diǎn)中的指針域指向a3，然后將a2釋放掉（free）即可。

結(jié)點(diǎn)的插入：

 

插入一個(gè)結(jié)點(diǎn)，如插入上圖中s結(jié)點(diǎn)，首先將s的指針域指向a2（也就是把s的next賦值為p的next），然后將p結(jié)點(diǎn)的指針域指向x即可（p的next指向x）。

循環(huán)鏈表

 

循環(huán)鏈表與單鏈表唯一不同之處是，循環(huán)鏈表的***一個(gè)結(jié)點(diǎn)指針不為空，而是指向頭結(jié)點(diǎn)。結(jié)點(diǎn)的插入和刪除和單鏈表非常相似，就不再示范了。

雙鏈表

 

雙鏈表擁有一前一后兩個(gè)指針域，從兩個(gè)不同的方向把鏈表連接起來，如此一來，從兩個(gè)不同的方向形成了兩條鏈，因此成為雙鏈表。因此，雙鏈表的靈活度要大于單鏈表。

結(jié)點(diǎn)的刪除：

 

雙鏈表的操作比單鏈表要稍顯復(fù)雜（按照單鏈表思路來做其實(shí)也不難），如上圖，要?jiǎng)h除p節(jié)點(diǎn)，首先需要將a1的后驅(qū)指向a3，然后將a3的前驅(qū)指向a1，***將p節(jié)點(diǎn)釋放掉即可。

結(jié)點(diǎn)的插入：

如上圖，插入q結(jié)點(diǎn)，首先要按照方向，將步驟拆分，首先將q節(jié)點(diǎn)的前驅(qū)指向p結(jié)點(diǎn)后驅(qū)，緊接著將x后驅(qū)指向a2；然后按照順序完成圖中所示的3、4步即可。

從空間性能來看，鏈表的存儲(chǔ)密度要差一些，但在容量分配上更靈活一些。從時(shí)間性能來看，查找運(yùn)算與順序存儲(chǔ)相同，插入運(yùn)算和刪除運(yùn)算的時(shí)間復(fù)雜度為O(1)，要更優(yōu)于順序存儲(chǔ)，但讀運(yùn)算則弱一些，為O([n+1]/2)，***為1，最壞為n。

棧

上面提到棧屬于一個(gè)邏輯概念，棧的實(shí)現(xiàn)可以用順序也可以用鏈?zhǔn)健Ｋ裱冗M(jìn)后出原則，如下圖：

Java中測試代碼如下：

 
 
 
 
    
  
  
  
  
  1. package com.snail.test;  
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. import java.util.Stack;  
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. public class TestStack {  
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.     public static void main(String[] args) {  
    8. 
  
  
  
  
  8.           
    9. 
  
  
  
  
  9.         Stack stack = new Stack();  
    10. 
  
  
  
  
  10.         stack.push("NO1");  
    11. 
  
  
  
  
  11.         stack.push("NO2");  
    12. 
  
  
  
  
  12.         stack.push("NO3");  
    13. 
  
  
  
  
  13.           
    14. 
  
  
  
  
  14.         System.out.println("初始數(shù)量：" + stack.size());  
    15. 
  
  
  
  
  15.  
    16. 
  
  
  
  
  16.         while(!stack.isEmpty()){  
    17. 
  
  
  
  
  17.             System.out.println(stack.pop());  
    18. 
  
  
  
  
  18.         }     
    19. 
  
  
  
  
  19.           
    20. 
  
  
  
  
  20.         System.out.println("取完后的數(shù)量：" + stack.size());  
    21. 
  
  
  
  
  21.     }  
    22. 
  
  
  
  
  22. } 
    23.

隊(duì)列

隊(duì)列遵循先進(jìn)先出的原則，如下圖：

Java中測試代碼如下：

 
 
 
 
    
  
  
  
  
  1. package com.snail.test;  
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. /**  
    4. 
  
  
  
  
  4.  *  
    5. 
  
  
  
  
  5.  * @author Zang XT  
    6. 
  
  
  
  
  6.  */ 
    7. 
  
  
  
  
  7. import java.util.Queue;  
    8. 
  
  
  
  
  8. import java.util.LinkedList;  
    9. 
  
  
  
  
  9. public class TestQueue {  
    10. 
  
  
  
  
  10.     public static void main(String[] args) {  
    11. 
  
  
  
  
  11.         Queue queue = new LinkedList();  
    12. 
  
  
  
  
  12.           
    13. 
  
  
  
  
  13.         queue.offer("NO1");  
    14. 
  
  
  
  
  14.         queue.offer("NO2");  
    15. 
  
  
  
  
  15.         queue.offer("NO3");  
    16. 
  
  
  
  
  16.           
    17. 
  
  
  
  
  17.         System.out.println("初始數(shù)量" + queue.size());  
    18. 
  
  
  
  
  18.         String str;  
    19. 
  
  
  
  
  19.         while((str=queue.poll())!=null){  
    20. 
  
  
  
  
  20.             System.out.println(str);  
    21. 
  
  
  
  
  21.         }  
    22. 
  
  
  
  
  22.         System.out.println("取出后數(shù)量" + queue.size());  
    23. 
  
  
  
  
  23.     }  
    24. 
  
  
  
  
  24. } 
    25.

運(yùn)行結(jié)果順序?yàn)椋撼跏紨?shù)量3，NO1，NO2，NO3，取出后數(shù)量0。

隊(duì)列還有一種形式為循環(huán)隊(duì)列，如下圖：

循環(huán)隊(duì)列有兩個(gè)指針，頭指針head和尾指針tail，尾指針一般指向的不是隊(duì)尾元素實(shí)際地址，而是指向?qū)嶋H地址的下一個(gè)空地址，因此，循環(huán)隊(duì)列一般犧牲***一個(gè)空間，用來計(jì)算該隊(duì)列是否滿了，判斷方式是tail+1 = head，既該隊(duì)列已滿。

為了盡可能的說清楚，插了大量圖片，希望理解。以后有時(shí)間將繼續(xù)分析樹、圖等數(shù)據(jù)結(jié)構(gòu)。


網(wǎng)站名稱：常用數(shù)據(jù)結(jié)構(gòu)：線性結(jié)構(gòu)
瀏覽地址：http://m.5511xx.com/article/dpogiph.html