數(shù)據(jù)結構第三版（陳元春）　線性表

1、第2章線性表2021年5月11日星期三1第 2 章 線 性 表 知 識 點 線性數(shù)據(jù)結構的定義與存儲 單鏈表的根本運算和算法 循環(huán)鏈表的根本特點 雙鏈表的結點形式和特點 雙鏈表的插入和刪除運算 難 點 雙鏈表插入、刪除運算的算法 利用鏈表結構的特點設計算法 要 求 熟練掌握以下內容: 順序表存儲地址的計算 單鏈表的結構特點和根本運算 第 2 章 目 錄2-1 線性表的定義與運算2-2 線性表的順序存儲 2-3 線性表的鏈式存儲結構小 結驗證性實驗2 線性表子系統(tǒng)自主設計實驗多項式求和實驗室完成，要求寫實驗報告作業(yè)與預習題 線性結構的根本特征:1集合中必存在唯一的一個“第一元素；2集合中必存在唯

2、一的一個 “最后元素;3除最后元素在外，均有 唯一的后繼；4除第一元素之外，均有 唯一的前驅。線性結構 是 一個數(shù)據(jù)元素的有序次序集52-1 線性表的定義與運算2-1-1 線性表的定義1線性表的定義 線性表是具有相同數(shù)據(jù)類型的nn=0個數(shù)據(jù)元素的有限序列，通常記為： (a1，a2， ai-1，ai，ai+1，an) 其中n為表長， n0 時稱為空表。 在線性表中相鄰元素之間存在著順序關系。對于元素ai 而言，ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。即：2線性表舉例1簡單的線性表 例如一年12個月： 1，2，3，4，5，6，7，8，9，10，11，12 在C或C+ +

3、語言中我們可以把它們定義為數(shù)值型。 又例如26個英文字母表： a，b，c，d，e，f，g，x，y，z 在C或C+ +語言中我們可以把它們定義為字符型。2復雜的線性表 例如我們曾經(jīng)在緒論中引用的一個學生入學情況表表2-1可以是用戶自定義的學生類型如C語言中的結構體或數(shù)據(jù)庫管理系統(tǒng)中的記錄。 由于表格中各記錄之間存在“一對一的關系，所以它也是一種線性表。3線性表的二元組表示： Linearity =D，R 數(shù)據(jù)對象：D=ai 1=i=0 數(shù)據(jù)關系： ai-1, aiD，2=i=n 稱 i 為 ai 在線性表中的位序。關系中是一個序偶的集合，它表示線性表中數(shù)據(jù)元素的相鄰關系，即 ai-1領先ai ，

4、ai領先 ai+1。2-1-2 線性表的根本操作 線性表上的根本操作有： 創(chuàng)立線性表：CreateList() 初始條件：表不存在 操作結果：構造一個空的線性表 求線性表的長度：LengthList(L) 初始條件：表L存在 操作結果：返回線性表中的所含元素的個數(shù)(3) 按值查找：SearchList(L,x)，是給定的一個數(shù)據(jù)元素。 初始條件：線性表L存在 操作結果：在表L中查找值為的數(shù)據(jù)元素，其結果返回在L中首次出現(xiàn)的值為的那個元素的序號或地址，稱為查找成功； 否那么，在L中未找到值為的數(shù)據(jù)元素，返回一個特殊值表示查找失敗。(4) 插入操作：InsList(L,i,x) 初始條件：線性表L

5、存在，插入位置正確 (1=i=n+1,為插入前的表長)。 操作結果：在線性表L的第 i 個位置上插入一個值為 x 的新元素，這樣使原序號為 i , i+1, . , n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2, . , n+1，插入后表長=原表長+1。(5) 刪除操作：DelList(L,i) 初始條件：線性表L存在，1=i=n。 操作結果：在線性表L中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為 i+1, i+2,., n 的元素變?yōu)樾蛱枮?i, i+1,.,n-1，新表長原表長-。(6) 顯示操作：ShowList(L) 初始條件：線性表L存在，且非空。 操作結果：顯示線性表L中的所有元素。其他可

6、根據(jù)實際需要設計2-2-1 順序表 線性表的順序存儲是指在用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把用這種存儲形式存儲的線性表稱為順序表。順序表的邏輯順序和物理順序是一致的。如圖2-1 所示。 設 a 1 的存儲地址LOC(a 1)為首地址B，每個數(shù)據(jù)元素占d個存儲單元，那么第i個數(shù)據(jù)元素的地址為： LOC(ai)=LOC(a 1)+(i-1)*d (1=i=n) 即： LOC(ai)=B+(i-1)*d (1=ilast=-1; / 初始化順序表為空 return Lq;/ 返回指向順序表的指針Lq 此時，順序表只有一個指針Lq指向，該順序表空間并無名字。 如果順序表在主函數(shù)中

7、作了如下定義，那么順序表L的空間分配在內存區(qū)。void main() SeqList L; / 這里的L是順序表類型的結構體變量，而非指針 InitList(&L); / 調用InitList()函數(shù)初始化順序表L 由于順序表L在內存區(qū)已分配空間，初始化函數(shù)只需設置好last指示標志的初值即可，代碼如下：void InitSeqList(SeqList *Lq) Lq-last=-1; / 初始化順序表為空2插入運算 線性表的插入是指在表的第i個位置上插入一個值為 x 的新元素，插入后使原表長為 n的表，成為表長為 n+1 的表。 順序表插入結點運算的步驟如下： (1) 將anai 之間的所有

8、結點依次后移，為新元素讓出第i個位置； (2) 將新結點x插入到第i個位置； (3) 修改 last 指針相當于修改表長，使之仍指向最后一個元素。 算法如下： int InsList(SeqList *L，int i，datatype x) int j; if (L-last=MAXLEN-1) printf (“順序表已滿！); return(-1); / 表滿，不能插入 if (iL-last+2) / 檢查給定的插入位置的正確性 printf (“位置出錯！); return(0); for(j=L-last;j=i-1;j-) / 結點移動 L-dataj+1=L-dataj; L-d

9、atai-1=x; / 新元素插入 L-last+; / last仍指向最后元素 return (1); / 插入成功，返回 動畫演示要注意的問題是： 1 順序表中數(shù)據(jù)區(qū)域有MAXLEN個存儲單元，所以在插入時先檢查順序表是否已滿，在表滿的情況下不能再做插入，否那么產(chǎn)生溢出錯誤。2檢驗插入位置的有效性，這里 i 的有效范圍是：1=i=n+1，其中 n 為原表長。3 注意數(shù)據(jù)的移動方向，必須從原線性表最后一個結點(an)起往后移動，如圖2-3所示。 插入算法的時間性能分析如下： 順序表上的插入運算，時間主要消耗在數(shù)據(jù)的移動上，在第i個位置上插入x，從an到ai都要向下移動一個位置，共需要移動ni

10、1個元素，而i的取值范圍為：1in1，即有n1個位置可以插入。 設在第i個位置上作插入的概率為Pi，那么平均移動數(shù)據(jù)元素的次數(shù)： 設Pi=1(n1)，即在等概率情況下，那么： 這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復雜度為O(n)。3 刪除運算 線性表的刪除運算是指將表中第 i 個元素從線性表中去掉，刪除后使原表長為 n 的線性表： (a1，a2，. ，ai-1，ai，ai+1，.，an)變?yōu)楸黹L為 n1 的線性表： (a1，a2，. ，ai-1， ai+1，. ，an-1)。 i 的取值范圍為：1=i=n 。 順序表刪除結點運算的步驟如下： (1) 將ai+1an 之

11、間的結點依次順序向前移動。 (2) 修改last指針相當于修改表長使之仍指向最后一個元素。 順序表中的刪除元素ai前后的情況如圖2- 4所示。 刪除算法如下：int DeleteList (SeqList *Lq;int i) int j; if(iLq-last+1) / 檢查空表及刪除位置的合法性 printf (不存在第i個元素); return (0); for(j=i;jlast;j+) / 向上移動 Lq-dataj-1=Lq-dataj; Lq-last-; / last仍指向最后元素 return(1); / 刪除成功 動畫演示 本算法請注意以下問題： 1首先要檢查刪除位置的有

12、效性，刪除第i個元素，i的取值為： 1=ilast的值為-1，條件iL-last+1也包括了對表空的檢查。 3刪除 ai 之后，該數(shù)據(jù)那么已不存在，如果需要，必須先取出 ai 后，再將其刪除。 刪除算法的時間復雜度分析： 與插入運算相同，其時間主要消耗在了移動表中的元素上，刪除第i個元素時，其后面的元素ai1an都要向前移動一個位置，共移動了ni個元素，所以平均移動數(shù)據(jù)元素的次數(shù)： 在等概率情況下，pi1n，那么：這說明在順序表上作刪除運算時大約需要移動表中一半的元素，顯然該算法的時間復雜度為O(n)。 4 按值查找 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。算法如下：in

13、t LocationSeqList(SeqList *L, datatype x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; / 返回的是存儲位置 上述算法的主要運算是比較。顯然比較的次數(shù)與x在表中的位置和表的長度MAXLEN有關。當a1x時，比較一次成功；當anx時比較n次成功。平均比較次數(shù)為 (n1)/2，時間復雜度為O(n)。預習題鏈表的存儲結構有何特點？在進行鏈表的插入與刪除元素操作時應該特別注意什么操作？什么是頭結點？它有什么作用？循環(huán)鏈表的結構特點是什么？雙向鏈表的結構特點是什么？鏈表

14、和順序表各根本操作各有什么特點？用一組 地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。修改指針語句的次序。鏈表的第一結點之前附設的一個結點。統(tǒng)一空表和非空表的操作。表中最后一個結點的指針域指向頭結點。結點有兩個指針域，其一指向前驅，另一指向后繼。2-3 線性表的鏈式存儲1順序存儲的優(yōu)點： 可以隨機存取表中任意一個元素； 存儲位置可以用公式：B+(i-1)*d 計算； 節(jié)約存儲空間。2順序存儲的缺點： 對順序表作插入、刪除時需要通過移動大量的數(shù)據(jù)元素，影響了運行效率。 線性表預先分配空間時，必須按最大空間分配，存儲空間得不到充分的利用。 表的容量難以擴充對有些高級語言而言。2-3-1 線性鏈表1.

15、線性鏈式存儲結構的特點1用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。2單鏈表的每個結點由一個數(shù)據(jù)域和一個指針域組成： 結點中存放數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存放其后繼地址的域稱為指針域。3單鏈表的存取必須從頭指針開始 如線性表a1,a2,a3,a4,a5,a6,a7,a8對應的鏈式存儲結構如圖2-6所示。 Ha1 a2 an 圖2-7 單鏈表示意圖 首先必須將第一個結點的地址1000放到一個頭指針變量如H中，最后一個結點沒有后繼，其指針域必需置空，說明此表到此結束。這樣就可以從第一個結點的地址開始，順著指針依次找到每個結點。 作為線性表的一種存儲結構，我們考慮的是結點間的邏輯結構，而對每個結點的

16、實際地址并不關心，所以通常的線性鏈表用圖2-7的形式表示。2. 關于頭指針、頭結點和開始結點1頭指針指向鏈表中第一個結點頭結點或無頭結點時的開始結點的指針。2頭結點在開始結點之前附加的一個結點。3開始結點在鏈表中，存儲第一個數(shù)據(jù)元素a1的結點。頭結點有何作用？3. 結點的描述 單向鏈表由一個個結點構成，在C或C+中可以用“結構體指針來描述。typedef struct linknode / 定義結點的結構體 datatype data; struct linknode *next; LinkNode，*LinkList; / 定義結點類型LinkNode， / 定義結點指針類型LinkList

17、 上面定義的LinkNode是結點的類型，LinkList是指向LinkNode類型結點的指針類型。為了增強程序的可讀性，通常將標識一個鏈表的頭指針說明為LinkList類型的變量，如LinkList L。當L有定義時，值要么為NULL，那么表示一個空表；要么為第一個結點的地址，即鏈表的頭指針；將操作中用到指向某結點的指針變量說明為LinkNode *類型，如LinkNode *p；那么語句： p=new LinkNode;完成了申請一塊LinkNode類型的存儲單元的操作，并將其地址賦值給變量p，如圖2-8所示。2-3-2 線性表上根本運算的實現(xiàn)1.建立線性鏈表1在鏈表的頭部建立線性表的算法

18、：圖2-9 在頭部插入建立單鏈表圖LinkNode *CreateLinkList()/ 頭插法建立線性鏈表 LinkNode *head,*p,*s; int x; int z=1,n=0; / n用來記錄表長 head=NULL; / 初始化頭指針為空 printf(ntt建立一個線性表); printf(ntt說明：請逐個輸入整數(shù)，結束標記為-1！n); while(z) printf(tt輸入：); scanf(%d,&x); if (x!=-1)/ 輸入-1完成建立 s=new LinkNode; n+; / 插入一個結點，結點數(shù)n增加1 s-data=x; s-next=head;

19、 head=s; else z=0; / 輸入循環(huán)結束 return head;/返回創(chuàng)立鏈表的頭指針 動畫演示2在鏈表的尾插入結點建立線性表LinkNode *CreateLinkList()/尾插法建立線性鏈表 LinkNode *head,*p,*s; int x, z=1,n=0;/ n用來存儲表長 head=NULL; p=head; printf(ntt建立一個線性表); printf(ntt說明：請逐個輸入整數(shù)，結束標記為-1！n); while(z) printf(tt輸入：); scanf(%d,&x); if(x!=-1)/ 輸入數(shù)據(jù)不等于-1那么構造結點并插入 s=new

20、 LinkNode;/ 給新結點開辟空間 s-data=x;/ 構造新結點 s-next=NULL; if(!head) head=s; / 將構造好的結點插入鏈表尾部 else p-next=s; p=s; n+; / 表長加1 else z=0;/ 輸入-1那么循環(huán)結束 return head;/ 返回建立好的單鏈表頭指針 為了方便操作，有時在鏈表的頭部參加一個“頭結點，頭結點的類型與數(shù)據(jù)結點一致，標識鏈表的頭指針變量L中存放該結點的地址，這樣即使是空表，頭指針變量L也不為空。頭結點的參加使得上述問題不再存在。 頭結點的參加完全是為了運算的方便，統(tǒng)一了空表和非空表的操作，它的數(shù)據(jù)域無定義，

21、指針域中存放的是第一個數(shù)據(jù)結點的地址，空表時為空，如圖2-11(a)所示；非空線性鏈表如圖2-11b。 圖2-11b 帶頭結點非空線性鏈表H a1 a2 an 2. 求表長 算法思路：設一個移動指針和計數(shù)器n，初始化后，所指結點后面假設還有結點，向后移動，計數(shù)器加1。(1) 設L是帶頭結點的線性鏈表(線性表的長度不包括頭結點) 算法如下：int LenList1 (LinkList L) Node * p=L; / p指向頭結點 int n=0; while (p-next) p=p-next; n+ / p所指的是第 n 個結點 return n; 2 設L是不帶頭結點的線性鏈表，算法如下：

22、int LenList2 (LinkList L) Node * p=L; int n; if (p=NULL) return 0; / 空表的情況 n=1; / 在非空表的情況下，p所指的是第一個結點; while (p-next ) p=p-next; n+ return n; 上述算法的時間復雜度均為O(n)。 很明顯，帶頭結點的鏈表的算法更簡潔，邏輯更清楚，因此在以后的算法中不加說明那么認為線性鏈表是帶頭結點的。 指針的小結 假設p是一個pointer類型，應正確區(qū)分指針型變量、指針、指針所指的結點和結點的內容這四個密切相關的不同概念：p的值如果有的話是一個指針，即是一個所指結點的地址

23、 。該指針假設不是NULL指向的某個node型結點用*p來標識。結點 *p是由兩個域組成的記錄，這兩個域分別用pdata域和pnext域來標識，它們各有自己的值，pdata的值是一個數(shù)據(jù)元素，pnext的值是一個指針。 3查找操作1序號查找 SearchList1(L,i) 算法思路：從鏈表的第一個元素結點開始，判斷當前結點是否是第i個，假設是，那么返回該結點的指針，否那么繼續(xù)下一個，直到鏈表結束。假設沒有第個結點那么返回空。 LinkNode *SearchList1(LinkList L,int i)/ 在帶頭結點的線性鏈表L中查找第i個元素結點，找到后返回其 /指針，否那么返回空 Lin

24、kNode *p=L; int j=0; while(p-next!=NULL&jnext; j+; if(j=i) return p; else return NULL; 2按值查找 SearchList2(L,x) 算法思路：從鏈表的第一個元素結點開始，判斷當前結點其值是否等于 x，假設是，返回該結點的指針，否那么繼續(xù)下一個，直到鏈表結束。假設找不到那么返回空。算法如下：以上兩個算法的時間復雜度均為O(n)。LinkNode *SearchList2(LinkList L,datatype x) /在帶頭結點的線性鏈表L中查找值為x的結點，找到后返回其 /指針，否那么返回空 LinkNod

25、e *p=L-next; while(p!=NULL&p-data!=x) p=p-next; if(p-data=x) return p; else return NULL; 4插入1后插結點：設p指向線性鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的后面，插入示意圖如圖2-12。插入結點操作： s-next=p-next; p-next=s; / 兩個指針的操作順序不能交換動畫演示 圖2-13 在*p之 前插*s2前插結點：設p指向鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的前面，插入示意圖如圖2-13所示，與后插不同的是：首先要找到*p的前驅*q，然后再

26、完成在*q之后插入*s，設線性鏈表頭指針為L，操作如下： x head p q 132 與后插不同的是：首先要找到*p的前驅*q，然后再完成在*q之后插入*s，設線性鏈表頭指針為L，操作如下:q=L;while (q-next!=p) q=q-next; / 找*p的直接前驅s-next=q-next; q-next=s; 后插操作的時間復雜性為O(1)，前插操作因為要找 *p 的前驅，時間性能為O(n)； 能否優(yōu)化算法，使時間性能為O(1)呢？其實我們更關心的是數(shù)據(jù)元素之間的邏輯關系，所以仍然可以將 *s 插入到 *p 的后面，然后將-data與s-data交換即可，這樣即滿足了邏輯關系，也

27、能使得時間復雜性為O(1)。插入結點操作： s-next=p-next; p-next=s; / 兩個指針的操作順序不能交換 t=p-data; / 交換-data與s-data p-data=s-data; s-data=t; 3插入運算 InsList(L,i,x) 算法思路 找到第i個結點，假設不存在那么結束，假設存在繼續(xù)下一步； 申請一個新結點，并賦值； 將新結點插入。void InsertList(LinkList head,int i,char x) / 插入結點元素 LinkNode *s,*p; p=head; int j=0; while(p!=NULL & jnext; /

28、 后移指針 if (p!=NULL) s=new LinkNode; s-data=x; / 插入結點 s-next=p-next; / 修改指針 p-next=s; n+; / 表的長度加1 else printf(ntt線性表為空或插入位置超出! n); 這個算法的時間復雜度為O(n)。 5刪除 1刪除結點：設p指向線性鏈表中某結點，刪除*p。操作示意圖如圖2-14所示。 圖2-14 刪除*P 通過示意圖可見，要實現(xiàn)對結點*p的刪除，首先要找到*p的前驅結點*q，然后完成指針的操作即可。指針的操作由以下語句實現(xiàn)： q-next=p-next; delete (p);動畫演示 顯然找*p前驅

29、的時間復雜性為O(n)。假設要刪除*p的后繼結點(假設存在)，那么可以直接完成： s=p-next; p-next=s-next; delete(s); 該操作的 時間復雜性為O(1) 。2刪除運算思路 如果鏈表為空，那么不能進行刪除操作； 查找值為x的結點，并得到其先驅結點； 將值為x的結點從鏈表中刪除。算法如下： LinkList DeleteList(LinkList head,char x) LinkNode *p,*q; if (head=NULL) printf(tt單鏈表為空！n); return head; if (head-next=NULL) if (head-data!=

30、x)/ 只有一個結點，并且不是待刪結點 printf(tt未找到待刪除的結點！); return head; else / 只有一個結點，并且是待刪結點 delete head; / 釋放被刪除結點的空間 return NULL; q=head; p=head-next; while(p!=NULL&p-data!=x)/ 查找待刪除結點 q=p; p=p-next; if (p!=NULL) q-next=p-next; delete p; n-; printf(tt %c已經(jīng)被刪除！,x); else printf(tt未找到待刪除的結點！n); 算法的時間復雜度為O(n)。通過上面的學習

31、我們可知： ( 1 ) 在線性鏈表上插入、刪除一個結點，必須知道其前驅結點。 ( 2 ) 線性鏈表不具有按序號隨機訪問的特點，只能從頭指針開始一個個順序進行。2-3-3 循環(huán)鏈表1特點 將線性單鏈表中最后一個結點的指針域指向頭結點，整個鏈表頭尾結點相連形成一個環(huán)就構成了單循環(huán)鏈表。如圖2-15所示。2-15 帶頭結點的單循環(huán)鏈表a非空表b空表HanHa12在循環(huán)鏈表上的操作 循環(huán)鏈表上的操作和非循環(huán)鏈表上的操作根本相同，差異在于算法中循環(huán)條件不是判斷指針是否為空P-NEXT=NULL，而是判斷指針是否為頭指針： P-NEXT=head;3在循環(huán)鏈表中設尾指針可以簡化某些操作 線性鏈表只能從頭結

32、點開始遍歷整個鏈表，而對于單循環(huán)鏈表那么可以從表中任意結點開始遍歷整個鏈表，不僅如此，有時對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結點的指針T來標識，可以使得操作效率得以提高。當知道其尾指針T后，其另一端的頭指針是T-next-next表中代頭結點，僅改變兩個指針值即可，其運算時間復雜度為O(1)。 例如：對兩個單循環(huán)鏈表H1 、H2的連接操作，是將H2的第一個數(shù)據(jù)結點接到H1的尾結點，如用頭指針標識，那么需要找到第一個鏈表的尾結點，其時間復雜性為O(n)，而鏈表假設用尾指針T1 、T2來標識，那么時間性能為O(1)。操作如下： p= T1

33、next; /保存T1 的頭結點指針 T1-next=T2-next-next; / 頭尾連接 free(T2-next); / 釋放第二個表的頭結點 T2-next=p; / 組成循環(huán)鏈表圖2-16 兩個用尾指針標識的單循環(huán)鏈表的連接4. 關于存儲密度1存儲密度是指結點數(shù)據(jù)本身所占的存儲空間和整個結點結構所占的存儲空間之比。即： 順序表的存儲密度等于1，而鏈表的存儲密度小于1。2采用鏈式存儲比采用順序存儲占用更多的存儲空間，是因為鏈式存儲結構增加了存儲其后繼結點地址的指針域。3存儲空間完全被結點值占用的存儲方式稱為緊湊存儲；否那么稱為非緊湊存儲。顯然，順序存儲是緊湊存儲，而鏈式存儲是非緊湊存

34、儲。存儲密度d值越大，表示數(shù)據(jù)結構所占的存儲空間越少。整個結點實際分配的存儲位結點數(shù)據(jù)占的存儲位存儲密度=d2-3-4 雙向鏈表1單向鏈表的缺點 單向鏈表只能順指針往后尋找其它結點。假設要尋找結點的前驅，那么需要從表頭指針出發(fā)。克服上述缺點可以采用雙向鏈表。2雙向鏈表 雙向鏈表由一個數(shù)據(jù)域和兩個指針域組成。1結點的結構如圖2-17所示。圖2-17 雙向鏈表的結點結構2空的雙向循環(huán)鏈表如圖2-18所示。ABCDhead3非空雙向循環(huán)鏈表如圖2-19所示。 圖2-19 非空雙向循環(huán)鏈表3雙鏈表的C或C+語言描述 struct cdlist datatype data;/結點數(shù)據(jù) struct cd

35、list *front;/指向先前結點的指針 struct cdlist *rear; /指向后繼結點的指針4雙鏈表的操作1刪除結點具體操作描述： p-front-rear=p-rear;p-rear-front=p-front;delete p;2插入結點具體操作描述：p-frony=q;p-rear=q-rear; q-rear-front=p;q-rear=p; q P1線性表是一種最簡單的數(shù)據(jù)結構，數(shù)據(jù)元素之間存在著一對一的關系。其存儲方法通常采用順序存儲和鏈式存儲。2線性表的順序存儲可以采用結構體的形式，它含有兩個域。一個整型的長度域，用以存放表中元素的個數(shù)；另一個數(shù)組域，用來存放元素，其類型可以根據(jù)需要而定。順序存儲的最大優(yōu)點是可以隨機存取，且存儲空間比較節(jié)約，而缺點是表的擴充困難，插入、刪除要做大量的元素移動。3線性表的鏈式存儲是通過結點之間的鏈接而得到的。根據(jù)鏈接方式又可以分為：單鏈表、雙鏈表和循環(huán)鏈表等。 小 結4單鏈表有一個數(shù)據(jù)域data和一個指針域