建站
咨詢
售后
建站咨詢
新聞中心
作為我們最先接觸的兩個數(shù)據(jù)結構，鏈表和線性表的優(yōu)缺點都較為明顯，并且二者互相補足
成都創(chuàng)新互聯(lián)公司是專業(yè)的集安網(wǎng)站建設公司，集安接單;提供成都網(wǎng)站制作、網(wǎng)站設計,網(wǎng)頁設計,網(wǎng)站設計,建網(wǎng)站,PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行集安網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!文章目錄- 鏈表和線性表的優(yōu)缺點
- 線性表
- 線性表的組成
- 線性表的缺點
- 線性表的優(yōu)點
- 鏈表
- 鏈表的組成
- 鏈表的缺點
- 鏈表的缺點
- 總結
首先，我們來談談線性表SeqList
線性表 （linear list） 是 數(shù)據(jù)結構 的一種，一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。類似于數(shù)組，其本質(zhì)是一塊連續(xù)的地址空間
圖片來自百度
因為其內(nèi)容包含多個變量，所以C語言使用結構體來構造
共三個變量：
1.所存儲數(shù)據(jù)類型的指針，用來接收之后malloc，動態(tài)開辟的空間
2.Size，表示當前線性表所存儲元素個數(shù)
3.Capacity，表示當前線性表所能存儲的大元素個數(shù)
詳細的實現(xiàn)這里就不贅述了
接下來是就來講解線性表的缺點
線性表的缺點如線性表的本質(zhì)所表現(xiàn)的，線性表是一塊連續(xù)的空間，如同數(shù)組一樣，我們需要手動開辟，而且需要指定大小的開辟。
那么就出現(xiàn)第一個問題，開辟多大的空間呢？
這只是問題的表層，很多人也知道，即使我們開辟的過大，過小，我們都可以通過realloc，重新開辟空間，并且realloc可以幫我們copy原先的數(shù)據(jù).
但這又有個問題，realloc多大呢，我們總不能插入一個數(shù)據(jù)，就重新realloc一塊比原先空間多一的空間吧？比較適合的擴大數(shù)目是—原先的兩倍。
但這樣也會在后來造成內(nèi)存浪費，比如我要存130，原先100，那就要realloc200的空間，70個空間將造成浪費
所以，線性表的第一個缺點：容易造成空間浪費
PS：realloc會考察原先空間后是否有足夠的空間，若有，是原地擴容。
若沒有足夠空間，則會在別處申請一塊空間，并拷貝原先的值
第二個缺點：頭部中間插入和刪除效率低
當我們要在線性表的頭部或中間插入和刪除元素時，我們需要將位置后的元素，往后移動，這就導致效率低
但是，線性表也并不是一無是處
線性表的優(yōu)點同樣，因為線性表的本質(zhì)，是一塊連續(xù)的空間
線性表可以通過下標訪問元素，很多算法是需要兼容這一點的，比如快排和二分查找
鏈表和線性表有很大不同
最明顯的還是數(shù)據(jù)的存儲，鏈表并不是連續(xù)的地址空間，他是無序的，散的，但這并不違反其線性結構，因為其組成有指針指向當前鏈表的下一個節(jié)點，實現(xiàn)數(shù)據(jù)的線性聯(lián)系
鏈表內(nèi)部主要有三大區(qū)分
循環(huán) 非循環(huán)
帶哨兵衛(wèi)的頭 不帶頭
單向 雙向
因此，鏈表有八種類型
其中單向，不帶頭，非循環(huán)鏈表是oj題最常見的，因為其結構簡單，功能少，所以相應的題考驗學生的思維能力。
而雙向，帶頭，循環(huán)鏈表是結構最復雜，全面的鏈表，所以其功能較為強大
此處舉例雙向，帶頭，循環(huán)鏈表
圖片來自百度
任意位置插入刪除效率高
因為鏈表并不是連續(xù)的空間，插入和刪除只要對指定位置的前后做操作就好
并且通過封裝的FindList函數(shù)，O(N)的查找，再在指定位置插入刪除O(N)即可
按需申請釋放空間
每一次的插入刪除，只需要申請一塊空間即可，和原本的空間沒有影響
實際操作，鏈表會更為的舒服
但鏈表的缺點也很明顯
鏈表的缺點不支持隨機訪問。（用下標訪問）
意味著，一些排序，二分查找，等算法在這種結構不適用
大致的線性表和鏈表的總結就到這。
一句話，數(shù)據(jù)結構是數(shù)據(jù)存儲，應用的框架，容器。
具體使用要依情況而定
感謝閱讀
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
文章題目：鏈表和線性表的優(yōu)缺點-創(chuàng)新互聯(lián)
當前地址：http://www.dlmjj.cn/article/ccooph.html
