當(dāng)前位置:首頁 > 公眾號精選 > strongerHuang
[導(dǎo)讀]關(guān)注、星標(biāo)公眾號,不錯過精彩內(nèi)容 素材來源:C語言中文網(wǎng) 編輯整理:strongerHuang 地址: http://c.biancheng.net/view/3329.html 數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中非常常見,現(xiàn)在各種算法基本都牽涉到數(shù)據(jù)結(jié)構(gòu),因此,掌握數(shù)據(jù)結(jié)構(gòu)算是軟件工程師的必備技能。 一、什


關(guān)注、星標(biāo)公眾,不錯過精彩內(nèi)容

素材來源:C語言中文網(wǎng)

編輯整理:strongerHuang

地址:
http://c.biancheng.net/view/3329.html

數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中非常常見,現(xiàn)在各種算法基本都牽涉到數(shù)據(jù)結(jié)構(gòu),因此,掌握數(shù)據(jù)結(jié)構(gòu)算是軟件工程師的必備技能。


一、什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu),直白地理解,就是研究數(shù)據(jù)的存儲方式。

我們知道,數(shù)據(jù)存儲只有一個目的,即為了方便后期對數(shù)據(jù)的再利用,就如同我們使用數(shù)組存儲 {1,2,3,4,5} 是為了后期取得它們的加和值,無緣由的數(shù)據(jù)存儲行為是對存儲空間的不負(fù)責(zé)任。

因此,數(shù)據(jù)在計算機存儲空間的存放,決不是胡亂的,這就要求我們選擇一種好的方式來存儲數(shù)據(jù),而這也是數(shù)據(jù)結(jié)構(gòu)的核心內(nèi)容。


數(shù)據(jù)存儲

一直以來大家面對的數(shù)據(jù)存儲,都是類似存儲 1、 2、{a,b,c}、 "http://www.strongerhuang.com"  這樣的問題,解決方式無疑是用變量或者數(shù)組對數(shù)據(jù)進(jìn)行存儲,即:

int a=1;
int b=2;
char str[3]={'a','b','c'};
char *data="http://www.strongerhuang.com";


但是,如果要存儲這樣一組數(shù)據(jù):{張亮,張平,張華,張群,張晶,張磊},數(shù)據(jù)之間具有這樣的關(guān)系:張亮是張平、張華和張群的父親,同時張平還是張晶和張磊的父親,數(shù)據(jù)之間的關(guān)系如圖 1 所示:




對于存儲之間具有復(fù)雜關(guān)系的數(shù)據(jù),如果還是用變量或數(shù)組來存儲(比如用數(shù)組存儲 {“張亮”,"張平",“張華”,"張群","張晶","張磊"} ),數(shù)據(jù)存儲是沒有問題,但是無法體現(xiàn)數(shù)據(jù)之間的邏輯關(guān)系,后期根本無法使用,顯然不明智。


針對此類數(shù)據(jù),數(shù)據(jù)結(jié)構(gòu)中提供有專門的樹結(jié)構(gòu)來存儲這類數(shù)據(jù)。


再比如,導(dǎo)航無疑是出游旅行的必備神器,在我們程序員眼中,無論是哪款導(dǎo)航軟件,其導(dǎo)航功能的實現(xiàn)都需要大量地圖數(shù)據(jù)的支持。很明顯,這些數(shù)據(jù)絕不是使用變量或數(shù)組進(jìn)行存儲的,那樣對于數(shù)據(jù)的使用簡直是個悲劇。


針對此類數(shù)據(jù),數(shù)據(jù)結(jié)構(gòu)提供了圖存儲結(jié)構(gòu),專門用于存儲這類數(shù)據(jù)。


二、數(shù)據(jù)結(jié)構(gòu)存儲分類

大致包含以下幾種存儲結(jié)構(gòu):

  • 線性表,還可細(xì)分為順序表、鏈表、棧和隊列;

  • 樹結(jié)構(gòu),包括普通樹,二叉樹,線索二叉樹等;

  • 圖存儲結(jié)構(gòu);


三、線性表

線性表結(jié)構(gòu)存儲的數(shù)據(jù)往往是可以依次排列的,就像小朋友手拉手,每位學(xué)生的前面和后面都僅有一個小朋友和他拉手,具備這種“一對一”關(guān)系的數(shù)據(jù)就可以使用線性表來存儲。



例如,存儲類似 {1,3,5,7,9} 這樣的數(shù)據(jù)時,各元素依次排列,每個元素的前面和后邊有且僅有一個元素與之相鄰(除首元素和尾元素),因此可以使用線性表存儲。

線性表并不是一種具體的存儲結(jié)構(gòu),它包含順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu),是順序表和鏈表的統(tǒng)稱。


1.順序表

順序表,簡單地理解,就是常用的數(shù)組,只是換了個名字而已,例如使用順序表存儲 {1,3,5,7,9},如圖所示:




由于順序表結(jié)構(gòu)的底層實現(xiàn)借助的就是數(shù)組,因此對于初學(xué)者來說,可以把順序表完全等價為數(shù)組,但實則不是這樣。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)存儲方式的一門學(xué)科,它囊括的都是各種存儲結(jié)構(gòu),而數(shù)組只是各種編程語言中的基本數(shù)據(jù)類型,并不屬于數(shù)據(jù)結(jié)構(gòu)的范疇。


2.鏈表

我們知道,使用順序表(底層實現(xiàn)靠數(shù)組)時,需要提前申請一定大小的存儲空間,這塊存儲空間的物理地址是連續(xù)的,如圖 1 所示。

鏈表則完全不同,使用鏈表存儲數(shù)據(jù)時,是隨用隨申請,因此數(shù)據(jù)的存儲位置是相互分離的,換句話說,數(shù)據(jù)的存儲位置是隨機的。

為了給各個數(shù)據(jù)塊建立“依次排列”的關(guān)系,鏈表給各數(shù)據(jù)塊增設(shè)一個指針,每個數(shù)據(jù)塊的指針都指向下一個數(shù)據(jù)塊(最后一個數(shù)據(jù)塊的指針指向 NULL),就如同一個個小學(xué)生都伸手去拉住下一個小學(xué)生的手,這樣,看似毫無關(guān)系的數(shù)據(jù)塊就建立了“依次排列”的關(guān)系,也就形成了鏈表,如圖所示:




3.棧和隊列

棧和隊列隸屬于線性表,是特殊的線性表,因為它們對線性表中元素的進(jìn)出做了明確的要求。

中的元素只能從線性表的一端進(jìn)出(另一端封死),且要遵循“先入后出”的原則,即先進(jìn)棧的元素后出棧。



棧結(jié)構(gòu)如上圖所示,像一個木桶,棧中含有 3 個元素,分別是 A、B 和 C,從在棧中的狀態(tài)可以看出 A 最先進(jìn)的棧,然后 B 進(jìn)棧,最后 C 進(jìn)棧。根據(jù)“先進(jìn)后出”的原則,3 個元素出棧的順序應(yīng)該是:C 最先出棧,然后 B 出棧,最后才是 A 出棧。

隊列中的元素只能從線性表的一端進(jìn),從另一端出,且要遵循“先入先出”的特點,即先進(jìn)隊列的元素也要先出隊列。



 

隊列結(jié)構(gòu)如上圖所示,隊列中有 3 個元素,分別是 A、B 和 C,從在隊列中的狀態(tài)可以看出是 A 先進(jìn)隊列,然后 B 進(jìn),最后 C 進(jìn)。根據(jù)“先進(jìn)先出”的原則,3 個元素出隊列的順序應(yīng)該是 A 最先出隊列,然后 B 出,最后 C 出。


四、樹存儲結(jié)構(gòu)

樹存儲結(jié)構(gòu)適合存儲具有“一對多”關(guān)系的數(shù)據(jù)。




如上圖所示,其中張平只有一個父親,但他卻有兩(多)個孩子,這就是“一對多”的關(guān)系,滿足這種關(guān)系的數(shù)據(jù)可以使用樹存儲結(jié)構(gòu)。


五、圖存儲結(jié)構(gòu)

圖存儲結(jié)構(gòu)適合存儲具有“多對多”關(guān)系的數(shù)據(jù)。



 

如上所示,從 V1 可以到達(dá) V2、V3、V4,同樣,從 V2、V3、V4 也可以到達(dá) V1,這就是“多對多”的關(guān)系,滿足這種關(guān)系的數(shù)據(jù)可以使用圖存儲結(jié)構(gòu)。


免責(zé)聲明: 本文來源網(wǎng)絡(luò),版權(quán)歸原作者所有。如涉及作品版權(quán)問題,請與我聯(lián)系刪除。
推薦閱讀:
實時內(nèi)核和實時操作系統(tǒng)有何不同?
開源協(xié)議是什么?開源等于免費嗎?
為什么有IPv4、IPv6 卻沒有IPv5?

關(guān)注 微信公眾號『strongerHuang』,后臺回復(fù)“1024”查看更多內(nèi)容,回復(fù)“加群”按規(guī)則加入技術(shù)交流群。


長按前往圖中包含的公眾號關(guān)注

免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!

本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉