目錄

• 線性表的定義
• 抽象數(shù)據(jù)類型
• 線性表的存儲結(jié)構(gòu)
• • 一、線性表的順序存儲結(jié)構(gòu)
  • • 順序表
    • • 靜態(tài)順序表
      • 動態(tài)順序表
  • 二、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
  • • 單鏈表
    • • 不帶頭結(jié)點的單鏈表
      • 帶頭結(jié)點的單鏈表

線性表的定義

線性表(List): 由零個或者多個數(shù)據(jù)元素組成的有限序列。
線性表首先它是一個序列，也就是說元素之間是有先來后到的。
若元素存在多個，則第一個元素?zé)o前驅(qū)，而最后一個元素?zé)o后繼，其他元素都只有一個直接前驅(qū)，和只有一個直接后繼。
線性表的定義：
若將線性表記為（a1,a2,…an-1,an),則表中an-1領(lǐng)先于an,an領(lǐng)先于an+1,稱an-1是an的直接前驅(qū)元素，an+1是an的直接后繼元素。
所以線性表元素的個數(shù)n(n>=0）定義為線性表的長度，當(dāng)n=0時，稱為空表。

抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型：就是把數(shù)據(jù)類型和相關(guān)的操作捆綁一起。
抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)化格式：
ADT 抽象數(shù)據(jù)類型名
Data
數(shù)據(jù)元素之間邏輯關(guān)系的定義
Operation
操作
endADT

線性表的抽象數(shù)據(jù)類型
ADT 線性表(List)
Data
線性表的數(shù)據(jù)對象集合為{ a1,a2,a3,a4…an},每個元素的類型均為ElemType(這里假設(shè)元素的類型為ElemType)。
其中，除了 第一個元素a1外，每一個元素都有且只有一個直接前驅(qū)元素，除了最后一個元素an外，每一個元素都有且
只有一個直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一 一對應(yīng)的。
Operation
InitList(&L): 初始化得到一個空表L,初始化成功返回0 ，否則返回-1。
ListEmpty(L): 判斷表是否空。如果空返回 1 否則返回 0。
ListFull(L): 判斷表是否滿，如果滿的話返回 1 否則返回 0。
CreateList(&L): 如果創(chuàng)建成功返回 1 否則返回 錯誤代碼。
ListLength(L): 返回表的長度。
LocateElem(L,e) : 查找e在表中的位置，找到返回 位序 否則 返回 -1。
ListInsert(&L,i,e): 在表的第 i 個位置插入數(shù)據(jù)元素 e 插入成功返回 0 否則返回 錯誤信息。
ListDelete(&L,i,&e): 刪除表中的第 i 個數(shù)據(jù)元素返回被刪除元素的值。刪除成功返回 0 否則返回錯誤代碼。
VisitList(L,i,&e): 訪問線性表第 i 個位置的元素 并用 e 返回元素的值，成功返回 0 失敗返回 錯誤代碼。
ShowList(L): 打印輸出線性表的內(nèi)容到屏幕或文件中。
DestroyList(&L): 撤銷線性表L ,回收L的存儲空間。
endADT

線性表的存儲結(jié)構(gòu)

線性表的存儲結(jié)構(gòu)分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)

一、線性表的順序存儲結(jié)構(gòu)

線性表的順序順序存儲是指：用一組地址連續(xù)連續(xù)的存儲單元來依次存放線性表中的數(shù)據(jù)。
線性表的順序存儲結(jié)構(gòu)示意圖

順序表

采用順序存儲的線性表簡稱為順序表
這種方式與高級程序設(shè)計語言中一維數(shù)組的表示和實現(xiàn)相一致，所以也稱為數(shù)組表示法。

線性表順序存儲結(jié)構(gòu)的優(yōu)缺點:
優(yōu)點：
無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間。
可以快速地存取表中任意位置的元素。
缺點:
插入和刪除操作需要移動大量元素。
當(dāng)線性表長度變化較大時，難以確定存儲空間的容量。
容易造成存儲空間的“碎片”(因為通過數(shù)組來存儲的，是一塊連續(xù)的存儲空間)

靜態(tài)順序表

類型定義

數(shù)組的長度與線性表的當(dāng)前長度需要區(qū)分：
數(shù)組的長度是存放線性表的存儲空間的總長度，一般初始化后不變。而線性表的當(dāng)前長度是線性表中元素的個數(shù)，是會變化的。
一些簡單的算法



順序表的創(chuàng)建

順序表的插入和刪除
原理圖：

插入算法的思路：
如果插入的位置不合理，拋出異常。
如果線性表長度大于等于數(shù)組長度，則拋出異?；騽討B(tài)增加數(shù)組容量。
從最后一個元素開始向前遍歷到第 i 個位置，分別將它們都向后移動一個位置。
這時候要插入的位置有空間了，把要插入的數(shù)據(jù)插入。
表長長度加1。

刪除算法的思路：
如果刪除的位置不合理，拋出異常。
取出刪除的元素。
從刪除元素開始向后遍歷到最后一個元素位置，分別將它們都向前移動一個位置。
表長長度減1。

代碼實現(xiàn)：

我們來分析一下，插入和刪除的時間復(fù)雜度。
最好的情況:
插入和刪除操作剛好要求在最后一個位置操作，因為不需要移動任何元素，
所以此時的時間復(fù)雜度為O(1)。
最壞的情況:
如果要插入和刪除的位置是第一個元素
那就意味著要移動所有的元素向后或者向前，所以這個時間復(fù)雜度為O(n)。
至于平均情況，就取中間值O((n+1)/2)。
按照時間復(fù)雜度的化簡規(guī)定，平均情況復(fù)雜度簡化后為O(n)。

動態(tài)順序表

類型定義

一些算法

其他的一些算法和靜態(tài)順序表的算法幾乎一樣就不列舉了。

二、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：是用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素，這組存儲單元可以在內(nèi)存中的任意位置。也就是說這組存儲單元，可以是連續(xù)的，也可以是不連續(xù)的，可以是部分連續(xù)的也可以是部分不連續(xù)的。

在鏈?zhǔn)酱鎯Y(jié)構(gòu)中除了要存儲數(shù)據(jù)信息外，還要存儲它的后繼元素的存儲地址(指針)。
我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域。指針域中的信息稱為指針或鏈。這兩部分信息組成的數(shù)據(jù)元素稱為
結(jié)點(Node)。

采用鏈?zhǔn)絻Υ娼Y(jié)構(gòu)的線性表稱為鏈表。
鏈表中每個結(jié)點的存儲地址存放在其前驅(qū)結(jié)點的next域中，然而首元結(jié)點(即第一個結(jié)點)無直接前驅(qū)，因此，我們需要設(shè)置一個頭指針(head)用來存放首元結(jié)點的存儲地址。由于，尾元結(jié)點（即最后一個結(jié)點）無直接后繼，故尾元結(jié)點的指針域為空(NULL)。
有時為了在對鏈表進(jìn)行操作時能夠統(tǒng)一處理空表和非空表的情況，或者能夠統(tǒng)一對首元結(jié)點和其他結(jié)點的處理過程，我們在鏈表的首元結(jié)點之前增設(shè)了一個結(jié)點，我們稱為頭結(jié)點(Head Node)。相對于頭結(jié)點而言，其余結(jié)點稱為表結(jié)點。

頭指針與頭結(jié)點的異同：

頭指針
-頭指針是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指什。
-頭指針具有標(biāo)識作用，所以常用頭指針冠以鏈表的名字(指針變量的名字)。
-無論鏈表是否為空，頭指針均不為空。
-頭指針是鏈表的必要元素。

頭結(jié)點
-頭結(jié)點是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一個元素的結(jié)點之前， 其數(shù)據(jù)域一般無意義(但也可以用來存放鏈表的長度)。
-有了頭結(jié)點，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點起操作與其它結(jié)點的操作就統(tǒng)一了。
-頭結(jié)點不一定是鏈表的必須要素。

單鏈表

單鏈表的結(jié)點結(jié)構(gòu)：

不帶頭結(jié)點的單鏈表

線性表L(a1 , a2 , a3 , a4…an-1,an)的單鏈表存儲結(jié)構(gòu)為：

帶頭結(jié)點的單鏈表

線性表L(a1 , a2 , a3 , a4…an-1,an)的帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)為：

總結(jié)

以上是生活随笔為你收集整理的线性表简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。