第2章 線性表

1、第2章 線 性 表 在本課程介紹的幾種數(shù)據(jù)結(jié)構(gòu)中，線性表是最常簡單的，也是最常用的數(shù)據(jù)結(jié)構(gòu)，線性表在實(shí)際應(yīng)用大量使用，并不是一個(gè)陌生的概念。2.1 線性表基本特征和基本運(yùn)算 1線性表的定義 線性表是具有相同數(shù)據(jù)類型的n(n=0)個(gè)數(shù)據(jù)元素的有限序列，通常記為(a1，a2， ai-1，ai，ai+1，an)其中n為表長，n0時(shí)稱為空表。 姓名 電話號碼 蔡穎 63214444 陳紅 63217777 劉建平 63216666 王小林 63218888 張力 63215555 .例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某單

2、位的電話號碼簿。 為了存儲線性表，至少要保存兩類信息：1）線性表中的數(shù)據(jù)元素；2）線性表中數(shù)據(jù)元素的順序關(guān)系；如何在計(jì)算機(jī)中存儲線性表？如何在計(jì)算機(jī)中實(shí)現(xiàn)線性表的基本操作？ 線性表的順序存儲結(jié)構(gòu)，就是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n用順序存儲結(jié)構(gòu)存儲的線性用順序存儲結(jié)構(gòu)存儲的線性表表稱為順序表稱為順序表2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn) 線性表的順序存儲結(jié)構(gòu)2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)typedef struct int dataMAXSIZE; int n

3、; SeqList; 定義一個(gè)順序表：SeqList L ;2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)1線性表中數(shù)據(jù)元素的插入 功能：在順序表v 中的第 i ( 1=i=n+1)個(gè)數(shù)據(jù)元素之前插入一個(gè)新元素x, 插入前線性表為 (a1, a2, a3, ai-1 ,ai, an ) 插入后,線性表長度為n+1, 線性表為 (a1, a2, a3, ai-1 , x, ai, an ) 2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)void Insert(int A,int &n,int i,int x)int j;/檢驗(yàn)插入元素位置是否合法if (i n+1)printf

4、(i值錯(cuò)！n);2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)else/數(shù)組元素后移，為插入元素空出位置for (j=n-1;j=i-1;j-) Aj+1=Aj; /插入數(shù)據(jù)元素Ai-1=x;/數(shù)組元素個(gè)數(shù)加1 n+; 2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)2線性表中數(shù)據(jù)元素的刪除 假設(shè)要求刪除第i個(gè)數(shù)據(jù)元素，線性表元素在數(shù)組中必須連續(xù)排列，中間不能有空單元。 2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)void Delete(int A,int &n,int i)int j;/檢驗(yàn)刪除元素位置是否合法if(in)printf(i值錯(cuò)！n);2.2 線性表的順序存儲及運(yùn)算實(shí)現(xiàn)e

5、lse/數(shù)組元素前移，覆蓋待刪除元素for (j=i;jn;j+)Aj-1=Aj;/數(shù)組元素個(gè)數(shù)減1n-;2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)1.單鏈表 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)節(jié)點(diǎn)定義如下：typedef struct node int data; struct node *next; LNode，*LinkList；2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)回顧指針與結(jié)構(gòu)體的基礎(chǔ)知識2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)2.單鏈表的基本運(yùn)算 （1）遍歷 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)int Length(LinkList head) int count=0; /初始化計(jì)數(shù)器 LinkLis

6、t p=head; /初始化移動指針p while (p!=NULL) p=p-next; count+; return(count); /返回表長 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)（2）插入一個(gè)節(jié)點(diǎn) 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)void Insert (LinkList head,int i, int x) LinkList s,p; int j; s=(LinkList)malloc(sizeof(LNode); /生成一個(gè)新節(jié)點(diǎn) s-data=x; if(i=0) /如果i=0,則將s所指節(jié)點(diǎn)插入到表頭 s-next=head-next; head=s; 2.3 線性表的鏈?zhǔn)酱鎯?/p>

7、及運(yùn)算實(shí)現(xiàn)else p=head; j=1; /j用來記錄節(jié)點(diǎn)個(gè)數(shù) /在單鏈表上查找第i個(gè)節(jié)點(diǎn)，由p所指向 while(p!=NULL & jnext; 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)if(p!=NULL) /找到插入位置，則把新節(jié)點(diǎn)插入其后 s-next=p-next; p-next=s; else printf(沒有對應(yīng)位置！n); 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)（3）刪除一個(gè)節(jié)點(diǎn) 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)算法執(zhí)行步驟描述：(1) 找到值為x的節(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束；(2) 判斷是否是首節(jié)點(diǎn)；(3) 刪除此節(jié)點(diǎn)，結(jié)束。請同學(xué)們寫出程序代碼！課堂習(xí)題一、選擇題

8、1鏈表不具有的特點(diǎn)是( )。A插入、刪除不需要移動元素 B可隨機(jī)訪問任一元素 C不必事先估計(jì)存儲空間 D所需空間與線性長度成正比2在一個(gè)長度為n的順序存儲線性表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移()個(gè)元素。An-i Bn-i+1 Cn-i-1 Di課堂習(xí)題3在單鏈表指針為p的節(jié)點(diǎn)之后插入指針為s的節(jié)點(diǎn)，正確的操作是( )。Ap-next=s;s-next=p-next;Bs-next=p-next;p-next=s;Cp-next=s;p-next=s-next;Dp-next=s-next;p-next=s;課堂習(xí)題4在一個(gè)單鏈表HL中，若要刪除由指針q

9、所指向節(jié)點(diǎn)的后繼節(jié)點(diǎn)，則執(zhí)行( )。Ap = q-next;p-next = q-next; Bp = q-next ;q-next = p-next;Cp = q-next ;q-next = p; Dq-next = q-next-next;q-next = q;5對于一個(gè)頭指針為head的帶頭節(jié)點(diǎn)的單鏈表，判定該表為空表的條件是( )。Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL課堂習(xí)題二、算法設(shè)計(jì)題1. 編寫一個(gè)算法，將一個(gè)順序表A(有n個(gè)元素)分拆成兩個(gè)順序表，使A中大于0的元素存放在B中，小于等于0的元素存放在C中。課

10、堂習(xí)題2. 已知一個(gè)單鏈表，編寫一個(gè)刪除其值為x的節(jié)點(diǎn)的前趨節(jié)點(diǎn)的算法。2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)3.循環(huán)鏈表 特點(diǎn)：將線性鏈表的最后一個(gè)結(jié)點(diǎn)的特點(diǎn)：將線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的第一個(gè)結(jié)點(diǎn)。指針指向鏈表的第一個(gè)結(jié)點(diǎn)。2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)區(qū)別：帶尾指針的循環(huán)鏈表在尾部插入結(jié)點(diǎn)更方便。2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)4.雙鏈表 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)（1）插入 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)(1) q-prior=p-prior;(2) q-next=p;(3) (p-prior)-next=q;(4) p-pr

11、ior=q; 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)（2）刪除 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)(1) (p-prior) -next=p-next;(2) (p-next) -prior=p-prior;2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)5.靜態(tài)鏈表 2.3 線性表的鏈?zhǔn)酱鎯斑\(yùn)算實(shí)現(xiàn)數(shù)組sd的定義如下： #define MAXSIZE /*足夠大的數(shù)*/ typedef struct int data; int next; SNode; /*節(jié)點(diǎn)類型*/SNode sdMAXSIZE; int SL,AV; /*兩個(gè)頭指針變量*/ 2.4 順序表和鏈表的比較 1每種存儲結(jié)構(gòu)的優(yōu)點(diǎn) 與缺點(diǎn)2.

12、 存儲結(jié)構(gòu)的選取 2.5 線性表的應(yīng)用1.順序表的應(yīng)用 例如，從鍵盤輸入某班學(xué)生程序設(shè)計(jì)課程考試成績，評定每個(gè)學(xué)生成績等級。如果高于平均分10分，則等級為優(yōu)秀；如果低于平均分10分，則等級為一般；否則等級為中等。 計(jì)算機(jī)計(jì)算機(jī) 領(lǐng)域：領(lǐng)域： P= (p0, p1, p2 , pn) Q= (q0, q1, q2, qm) R= (p0+q0, p1+q1, , pm+qm, pm+1, , pn )P (x) = p0 + p1 x + p2 x2 + + p + pn n x xn nQ (x) = q0 + q1 x + q2 x2+ + q + qm m x xm m 不失一般性，設(shè)不失

13、一般性，設(shè)mindex index ： p 所指結(jié)點(diǎn)應(yīng)為和多項(xiàng)式中的所指結(jié)點(diǎn)應(yīng)為和多項(xiàng)式中的結(jié)點(diǎn)結(jié)點(diǎn)p-index = q-index ：將：將p所指結(jié)點(diǎn)的系數(shù)所指結(jié)點(diǎn)的系數(shù)“加加”到到q所指結(jié)所指結(jié)點(diǎn)的系數(shù)上相加；點(diǎn)的系數(shù)上相加；p-index q-index ： 從表從表bh中刪除中刪除q 所指結(jié)點(diǎn)，并所指結(jié)點(diǎn)，并將其將其插入到插入到ah表表p所指結(jié)點(diǎn)之前；所指結(jié)點(diǎn)之前； void polyadd(NODE *ah, NODE * bh) NODE *pre_p, *p, *q, *temp; char comp; pre_p=ah; p=ah-next; q=bh-next; while

14、 (p!=NULL)&(q!=NULL) comp=compare(p-index, q-index) switch(comp)（接下頁） case next; break; case =: /兩者的指數(shù)值相等兩者的指數(shù)值相等 p-coef+=q-coef ; if (p-coef =0. 0) / 合并后系數(shù)為合并后系數(shù)為0 pre_p-next=p-next; free(p); else pre_p=p; p=pre_p-next; temp=q; q=q-next; free(temp); break; case : /多項(xiàng)式多項(xiàng)式A中當(dāng)前結(jié)點(diǎn)的指數(shù)值大中當(dāng)前結(jié)點(diǎn)的指數(shù)值大 temp=q-next; q-next=p; pre_p-next=q; pre_p=q; q=temp; if (q!=NULL) pre_p-next=q; free(bh); char compare ( int n1, int n2 ) if (n1n2) return( ); 小結(jié) 本章學(xué)習(xí)了線性表的順序存儲結(jié)構(gòu)本章學(xué)習(xí)了線性表的順序存儲結(jié)構(gòu)順序表，鏈?zhǔn)酱骓樞虮恚準(zhǔn)酱鎯Y(jié)構(gòu)儲結(jié)構(gòu),線性鏈表線性鏈表,循環(huán)鏈表循環(huán)鏈表, 雙