c語(yǔ)言中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)是什么

c語(yǔ)言中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)是什么？這個(gè)問(wèn)題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見(jiàn)到的。希望通過(guò)這個(gè)問(wèn)題能讓你收獲頗深。下面是小編給大家?guī)?lái)的參考內(nèi)容，讓我們一起來(lái)看看吧！

站在用戶(hù)的角度思考問(wèn)題，與客戶(hù)深入溝通，找到唐山網(wǎng)站設(shè)計(jì)與唐山網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶(hù)體驗(yàn)好的作品，建站類(lèi)型包括：網(wǎng)站制作、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名注冊(cè)、虛擬主機(jī)、企業(yè)郵箱。業(yè)務(wù)覆蓋唐山地區(qū)。

c語(yǔ)言中，數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式；常見(jiàn)數(shù)據(jù)結(jié)構(gòu)有：線性數(shù)據(jù)結(jié)構(gòu)（數(shù)組、鏈表、棧、隊(duì)列和線性表）、樹(shù)形結(jié)構(gòu)（二叉樹(shù)、完全二叉樹(shù)、二叉查找樹(shù)、堆）、圖形結(jié)構(gòu)（有向圖和無(wú)向圖）。

教程

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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

大部分?jǐn)?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)都需要借助C語(yǔ)言中的指針和結(jié)構(gòu)體類(lèi)型

下面，進(jìn)入今天的重點(diǎn)啦O(∩_∩)O幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

（1）線性數(shù)據(jù)結(jié)構(gòu)：元素之間一般存在元素之間存在一對(duì)一關(guān)系，是最常用的一類(lèi)數(shù)據(jù)結(jié)構(gòu)，典型的有：數(shù)組、棧、隊(duì)列和線性表

（2）樹(shù)形結(jié)構(gòu)：結(jié)點(diǎn)間具有層次關(guān)系，每一層的一個(gè)結(jié)點(diǎn)能且只能和上一層的一個(gè)結(jié)點(diǎn)相關(guān)，但同時(shí)可以和下一層的多個(gè)結(jié)點(diǎn)相關(guān)，稱(chēng)為“一對(duì)多”關(guān)系，常見(jiàn)類(lèi)型有：樹(shù)、堆

（3）圖形結(jié)構(gòu)：在圖形結(jié)構(gòu)中，允許多個(gè)結(jié)點(diǎn)之間相關(guān)，稱(chēng)為“多對(duì)多”關(guān)系

下面分別對(duì)這幾種數(shù)據(jù)結(jié)構(gòu)做一個(gè)簡(jiǎn)單介紹：

1、線性數(shù)據(jù)結(jié)構(gòu)：典型的有：數(shù)組、棧、隊(duì)列和線性表

（1）數(shù)組和鏈表

a、數(shù)組：存放著一組相同類(lèi)型的數(shù)據(jù)，需要預(yù)先指定數(shù)組的長(zhǎng)度，有一維數(shù)組、二維數(shù)組、多維數(shù)組等

b、鏈表：鏈表是C語(yǔ)言中一種應(yīng)用廣泛的結(jié)構(gòu)，它采用動(dòng)態(tài)分配內(nèi)存的形式實(shí)現(xiàn)，用一組任意的存儲(chǔ)單元存放數(shù)據(jù)元素鏈表的，一般為每個(gè)元素增設(shè)指針域，用來(lái)指向后繼元素

c、數(shù)組和鏈表的區(qū)別：

從邏輯結(jié)構(gòu)來(lái)看：數(shù)組必須事先定義固定的長(zhǎng)度，不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況；鏈表動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配，可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況，且可以方便地插入、刪除數(shù)據(jù)項(xiàng)（數(shù)組中插入、刪除數(shù)據(jù)項(xiàng)時(shí)，需要移動(dòng)其它數(shù)據(jù)項(xiàng)）

從內(nèi)存存儲(chǔ)來(lái)看：（靜態(tài))數(shù)組從棧中分配空間（用NEW創(chuàng)建的在堆中）, 對(duì)于程序員方便快速,但是自由度小；鏈表從堆中分配空間, 自由度大但是申請(qǐng)管理比較麻煩

從訪問(wèn)方式來(lái)看：數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，因此，可以利用下標(biāo)索引進(jìn)行隨機(jī)訪問(wèn)；鏈表是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在訪問(wèn)元素的時(shí)候只能通過(guò)線性的方式由前到后順序訪問(wèn)，所以訪問(wèn)效率比數(shù)組要低

（2）棧、隊(duì)列和線性表：可采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的方法進(jìn)行存儲(chǔ)

順序存儲(chǔ)：借助數(shù)據(jù)元素在存儲(chǔ)空間中的相對(duì)位置來(lái)表示元素之間的邏輯關(guān)系

鏈?zhǔn)酱鎯?chǔ)：借助表示數(shù)據(jù)元素存儲(chǔ)地址的指針表示元素之間的邏輯關(guān)系

a、棧：只允許在序列末端進(jìn)行操作，棧的操作只能在棧頂進(jìn)行，一般棧又被稱(chēng)為后進(jìn)先出或先進(jìn)后出的線性結(jié)構(gòu)

順序棧：采用順序存儲(chǔ)結(jié)構(gòu)的棧稱(chēng)為順序棧，即需要用一片地址連續(xù)的空間來(lái)存儲(chǔ)棧的元素，順序棧的類(lèi)型定義如下：

鏈棧：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱(chēng)為鏈棧：

b、隊(duì)列：只允許在序列兩端進(jìn)行操作，一般隊(duì)列也被稱(chēng)為先進(jìn)先出的線性結(jié)構(gòu)
循環(huán)隊(duì)列：采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列，需要按隊(duì)列可能的最大長(zhǎng)度分配存儲(chǔ)空空，其類(lèi)型定義如下：

鏈隊(duì)列：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱(chēng)為鏈隊(duì)列，一般需要設(shè)置頭尾指針只是鏈表的頭尾結(jié)點(diǎn)：

c、線性表：允許在序列任意位置進(jìn)行操作，線性表的操作位置不受限制，線性表的操作十分靈活，常用操作包括在任意位置插入和刪除，以及查詢(xún)和修改任意位置的元素

順序表：采用順序存儲(chǔ)結(jié)構(gòu)表示的線性表稱(chēng)為順序表，用一組地址連續(xù)的存儲(chǔ)單元一次存放線性表的數(shù)據(jù)元素，即以存儲(chǔ)位置相鄰表示位序相繼的兩個(gè)元素之間的前驅(qū)和后繼關(guān)系，為了避免移動(dòng)元素，一般在順序表的接口定義中只考慮在表尾插入和刪除元素，如此實(shí)現(xiàn)的順序表也可稱(chēng)為棧表：

線性表：一般包括單鏈表、雙向鏈表、循環(huán)鏈表和雙向循環(huán)鏈表

單鏈表：

雙向鏈表：

線性表兩種存儲(chǔ)結(jié)構(gòu)的比較：

順序表：

優(yōu)點(diǎn)：在順序表中，邏輯中相鄰的兩個(gè)元素在物理位置上也相鄰，查找比較方便，存取任一元素的時(shí)間復(fù)雜度都為O(1)

缺點(diǎn)：不適合在任意位置插入、刪除元素，因?yàn)樾枰苿?dòng)元素，平均時(shí)間復(fù)雜度為O(n)

鏈表：

優(yōu)點(diǎn)：在鏈接的任意位置插入或刪除元素只需修改相應(yīng)指針，不需要移動(dòng)元素；按需動(dòng)態(tài)分配，不需要按最大需求預(yù)先分配一塊連續(xù)空空

缺點(diǎn)：查找不方便，查找某一元素需要從頭指針出發(fā)沿指針域查找，因此平均時(shí)間復(fù)雜度為O(n)

2、樹(shù)形結(jié)構(gòu)：結(jié)點(diǎn)間具有層次關(guān)系，每一層的一個(gè)結(jié)點(diǎn)能且只能和上一層的一個(gè)結(jié)點(diǎn)相關(guān)，但同時(shí)可以和下一層的多個(gè)結(jié)點(diǎn)相關(guān)，稱(chēng)為“一對(duì)多”關(guān)系，常見(jiàn)類(lèi)型有：樹(shù)、堆

（1）二叉樹(shù)：二叉樹(shù)是一種遞歸數(shù)據(jù)結(jié)構(gòu)，是含有n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，二叉樹(shù)具有以下特點(diǎn)：

二叉樹(shù)可以是空樹(shù)；二叉樹(shù)的每個(gè)結(jié)點(diǎn)都恰好有兩棵子樹(shù)，其中一個(gè)或兩個(gè)可能為空；二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的位置不能顛倒，若改變兩者的位置，就成為另一棵二叉樹(shù)

（2）完全二叉樹(shù)：從根起，自上而下，自左而右，給滿(mǎn)二叉樹(shù)的每個(gè)結(jié)點(diǎn)從1到n連續(xù)編號(hào)，如果每個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱(chēng)為完全二叉樹(shù)

a、采用順序存儲(chǔ)結(jié)構(gòu)：用一維數(shù)組存儲(chǔ)完全二叉樹(shù)，結(jié)點(diǎn)的編號(hào)對(duì)于與結(jié)點(diǎn)的下標(biāo)（如根為1，則根的左孩子為2i=21=2，右孩子為2i+1=21+1=2）

b、采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

二叉鏈表：

三叉鏈表：它的結(jié)點(diǎn)比二叉鏈表多一個(gè)指針域parent，用于執(zhí)行結(jié)點(diǎn)的雙親，便于查找雙親結(jié)點(diǎn)

兩種存儲(chǔ)結(jié)構(gòu)比較：對(duì)于完全二叉樹(shù)，采用順序存儲(chǔ)結(jié)構(gòu)既能節(jié)省空間，又可利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹(shù)中的位置及結(jié)點(diǎn)之間的關(guān)系，但采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一般二叉樹(shù)容易造成空間浪費(fèi)，鏈?zhǔn)浇Y(jié)構(gòu)可以克服這個(gè)缺點(diǎn)

（3）二叉查找樹(shù)：二叉查找樹(shù)又稱(chēng)二叉排序樹(shù)，或者是一課空二叉樹(shù)，或者是具有如下特征的二叉樹(shù)：

a、若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值

b、若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值

c、它的左、右子樹(shù)也分別是二叉查找樹(shù)

（4）平衡二叉樹(shù)：平衡二叉查找樹(shù)簡(jiǎn)稱(chēng)平衡二叉樹(shù)，平衡二叉樹(shù)或者是棵空樹(shù)，或者是具有下列性質(zhì)的二叉查找樹(shù)：它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1

平衡二叉樹(shù)的失衡及調(diào)整主要可歸納為下列四種情況：LL型、RR型、LR型、RL型

（5）樹(shù)：樹(shù)是含有n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹(shù)種： a、有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)

b、當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一個(gè)集合本身又是一棵樹(shù)，并且T1,T2,…,Tm稱(chēng)為根的子樹(shù)

（6）堆：堆是具有以下特性的完全二叉樹(shù)，其所有非葉子結(jié)點(diǎn)均不大于（或不小于）其左右孩子結(jié)點(diǎn)。若堆中所有非葉子結(jié)點(diǎn)均不大于其左右孩子結(jié)點(diǎn)，則稱(chēng)為小頂堆（小根堆），若堆中所有非葉子結(jié)點(diǎn)均不小于其左右孩子結(jié)點(diǎn)，則稱(chēng)為大頂堆（大根堆）

（7）并查集：并查集是指由一組不相交子集所構(gòu)成的集合，記作：S={S1,S2,S3,…,Sn}

（8）B樹(shù)

3、圖形結(jié)構(gòu)：在圖形結(jié)構(gòu)中，允許多個(gè)結(jié)點(diǎn)之間相關(guān)，稱(chēng)為“多對(duì)多”關(guān)系，可分為有向圖和無(wú)向圖

感謝各位的閱讀！看完上述內(nèi)容，你們對(duì)c語(yǔ)言中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)是什么大概了解了嗎？希望文章內(nèi)容對(duì)大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

標(biāo)題名稱(chēng)：c語(yǔ)言中常見(jiàn)數(shù)據(jù)結(jié)構(gòu)是什么
網(wǎng)址分享：http://m.jiaotiyi.com/article/peijsi.html