1、第二章 線性表,線性表是最簡單常用的數(shù)據(jù)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是應(yīng)用中最常用的存儲(chǔ)方法，這一部分內(nèi)容和方法掌握了，有助于理解和掌握后續(xù)章節(jié)的內(nèi)容，如棧隊(duì)列串是特殊的線性表，數(shù)組和廣義表是線性表的擴(kuò)展；有助于理解和掌握樹和圖等復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)和圖等復(fù)雜結(jié)構(gòu)的操作算法，因?yàn)闃浜蛨D的存儲(chǔ)結(jié)構(gòu)大多或是這兩種存儲(chǔ)結(jié)構(gòu)的擴(kuò)充，或是它們的組合，因此這一章的內(nèi)容非常重要，同學(xué)們要很好地學(xué)習(xí)理解和掌握。,第二章 線性表,第二章 線性表 2.1 線性表概念及基本操作 2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表

2、 2.4 一元多項(xiàng)式的表示及相加,第二章 線性表,在本課程介紹的幾種數(shù)據(jù)結(jié)構(gòu)中，線性表是最常簡單的，也是最常用的數(shù)據(jù)結(jié)構(gòu)，線性表在實(shí)際應(yīng)用大量使用，并不是一個(gè)陌生的概念。,線性表是n 個(gè)類型相同數(shù)據(jù)元素的有限序列， 通常記作（a1, a2, a3, , an ）。,2. 1 線性表的類型定義,例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，19，21） 例2、英文字母表（A, B, C, D, E Z ）。 例3、某單位的電話號(hào)碼簿。,一 線性表的邏輯結(jié)構(gòu),2.1 線性表的類型定義,說明：設(shè) A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一線性表 1） 線性表的數(shù)

3、據(jù)元素可以是各種各樣的，但同一線性表中的元素必須 是同一類型的； 2） 在表中 ai-1 領(lǐng)先于ai ，ai 領(lǐng)先于ai+1 ，稱ai-1 是ai 的直接前驅(qū)，ai+1 是 ai 的直接后繼； 3） 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前驅(qū)，有且僅有一個(gè)直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)； 4） 線性表中元素的個(gè)數(shù)n 稱為線性表的長度，n=0 時(shí)稱為空表； 5） ai是線性表的第i 個(gè)元素，稱i 為數(shù)據(jù)元素ai 的序號(hào)，每一個(gè)元素在線性表中的位置，僅取決于它的序號(hào)；,2.1 線性表的類型定義,線性表的其他表示方式 二元組

4、表示 L= ，其中D= a1,a2, a3, . an S= R R=, , 圖示表示,頂點(diǎn)：表示數(shù)據(jù) 邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系,2.1 線性表的類型定義,ADT List 數(shù)據(jù)對(duì)象: D=ai| ai ElemSet i=1,2,3.,n, n 0 數(shù)據(jù)關(guān)系: R1=| ai-1,aiD, i=1,2,3.,n, n 0 基本操作: 初始化操作: InitList( 返回空表: ListEmpty(L), 若L為空表,返回TRUE,否則FALSE 元素計(jì)數(shù): ListLength(L),返回L中元素個(gè)數(shù) 返回位序: LocateElem(L,e, compare( ) ,返回L中第1個(gè)

5、與e滿足compare( )的數(shù)據(jù)元素的位序.若這樣的數(shù)據(jù)元素不存在,返回0 GetElem(L, i , ,2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn),順序表的類型定義 #define LIST_INIT_SIZE 100 / 線性表存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10 / 線性表存儲(chǔ)空間的分配增量 typedef struct ElemType * elem; /線性表存儲(chǔ)空間基址 int length; /當(dāng)前線性表長度 int listsize; /當(dāng)前分配的線性表存儲(chǔ)空間大小 /（以sizeof(ElemType)為單位） SqList;,SqList ：類型名

6、， SqList類型的變量是結(jié)構(gòu)變量，它的三個(gè)域分別是： *elem：存放線性表元素的一維數(shù)組基址；其存儲(chǔ)空間在初始化操作（建空表）時(shí)動(dòng)態(tài)分配； length：存放線性表的表長； listsize：用于存放當(dāng)前分配（存放線性表元素）的存儲(chǔ)空間的大小。,2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn),存放線性表元素 的一維數(shù)組,設(shè) A = （a1,a2 , a3 , . an ）是一線性表，L是SqList 類型的結(jié)構(gòu)變量，用于存放線性表A，則L在內(nèi)存中的狀態(tài)如圖所示：,順序表通過 元素的存儲(chǔ)順序 反映線性表元素間的邏輯關(guān)系,2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn),二、順序表的基本操作算法 插入 insert(v, x

7、, i) 功能：在順序表v 中的第 i ( 1link=NULL; p-link=q;p=q; return(head); ,插入結(jié)點(diǎn),q=(NODE *)malloc(sizeof(NODE); q-data=a; q-link=p-link; p-link=q;,head,y,x,p,head,3 插入操作 Insert_link(NODE *head, int x, int i) 功能：在線性鏈表的第i個(gè)元素結(jié)點(diǎn)之前插入一個(gè)新元素結(jié)點(diǎn)x； 插入操作圖示：,2. 3. 1 線性鏈表,插入前,插入后,head,head,2. 3. 1 線性鏈表,插入操作主要步驟： 1）查找鏈表L的第 i-1

8、個(gè)元素結(jié)點(diǎn)； 2）為新元素建立結(jié)點(diǎn)； 3）修改第 i-1個(gè)元素結(jié)點(diǎn)的指針和新元素結(jié)點(diǎn)指針完成插入；,Int insert_link(NODE *head,int x, int i) NODE *p,*s;int j; p=head;j=0; while (p!=NULL) ,刪除結(jié)點(diǎn),q=p-link; p-link=q-link; free(q);,head,y,x,q,head,p,p,2. 3. 1 線性鏈表,刪除操作主要步驟： 1）查找鏈表的第 i-1個(gè)元素結(jié)點(diǎn),使指針p指向它, 將指針q指向第i個(gè)結(jié)點(diǎn)； 2）修改第 i-1個(gè)元素結(jié)點(diǎn)指針，使其指向第i個(gè)元素結(jié)點(diǎn)的后繼； 3) 回收q指

9、針?biāo)傅牡趇個(gè)結(jié)點(diǎn)空間；,2. 3. 1 線性鏈表,刪除前,刪除后,p,p,q,q,在線性鏈表中刪除第i個(gè)結(jié)點(diǎn) Int delete_link(NODE *head, int i) NODE *p,*q;int j; p=head;j=0; while (p!=NULL) ,2.3.1 線性鏈表,三 線性鏈表的其他操作的實(shí)現(xiàn),例：將兩個(gè)遞增有序線性鏈表歸并成一個(gè)遞減有序表。 設(shè)線性表A、B分別用頭指針為head_a 、 head_b 的兩個(gè)帶頭結(jié)點(diǎn)的線性鏈表存儲(chǔ), 歸并后的遞減有序表頭指針為head, 將兩表數(shù)據(jù)較小的結(jié)點(diǎn)依次取出插入到新表,利用基本操作 直接對(duì)鏈表進(jìn)行操作,2.3.1 線性鏈

10、表,線性鏈表歸并操作圖示,7,3,n,9,5,2,n,7,head_a,head_b,7,9,head,3,8,5,NODE * merge_link( NODE *head_a, NODE *head_b) NODE *p, *q, *head; head=(NODE *)malloc(sizeof (NODE); head-link=NULL; p=head_a-link; q=head_b-link; while(p!=NULL) ,while(p!=NULL) head_a-link=p-link;p-link=head-link; head-link=p; p=head_a-link

11、; while(q!=NULL) head_b-link=q-link;q-link=head-link; head-link=q; q=head_b-link; free(head_a); free(head_b); return(head); ,2. 3. 1 線性鏈表小結(jié),線性鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),線性鏈表的特點(diǎn) 1 通過保存直接后繼元素的存儲(chǔ)位置來表示 數(shù)據(jù)元素之間的邏輯關(guān)系； 2 插入刪除操作通過修改結(jié)點(diǎn)的指針實(shí)現(xiàn)； 3 不能隨機(jī)存取元素；,1 循環(huán)鏈表的概念 循環(huán)鏈表是線性表的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的特點(diǎn)是將線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的第一個(gè)結(jié)點(diǎn) 2 循環(huán)鏈表圖

12、示,2. 3.2 單向循環(huán)鏈表,(a)非空表 （b）空表,2. 3.2 單向 循環(huán)鏈表,說明 在解決某些實(shí)際問題時(shí)循環(huán)鏈表可能要比線性鏈表方便些。如將一個(gè)鏈表鏈在另一個(gè)鏈表的后面； 循環(huán)鏈表與線性鏈表操作的主要差別是算法中循環(huán)結(jié)束的條件不是p或p-link是否為NULL,而是它們是否等于首指針； 對(duì)循環(huán)鏈表，有時(shí)不給出頭指針，而是給出尾指針,a,a1,an,給出尾指針的循環(huán)鏈表,2. 3.2 單向 循環(huán)鏈表,b,a,a1,an,b1,bn,q,q,p,p,p=a-link; q=b-link; a-link=q-link; b-link=p; free(q);,約瑟夫回環(huán)問題 Void lea

13、d (NODE * head, int m) NODE *p, *q; int i; p=head; q=NULL; i=1; while(p-link!=p) while(ilink!=p) i+; q=p; p=p-link; if (p-link!=p) i=1; printf( “%d”, p-data); q-link=p-link; q=p; p=p-link; free(q); else printf(“%d”, p-data); ,1 雙向鏈表的概念,2. 3.3 雙向鏈表,(a)結(jié)點(diǎn)圖示,存儲(chǔ)數(shù)據(jù)元素,存儲(chǔ)后繼結(jié)點(diǎn) 的地址,存儲(chǔ)前趨結(jié)點(diǎn) 的地址,雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針

14、域，一個(gè)指向直接后繼元素結(jié)點(diǎn)，另一個(gè)指向直接前趨元素結(jié)點(diǎn)。,2. 3.3 雙向鏈表,2 雙向鏈表圖示,head,Struct node int data struct node * llink, *rlink; ,在雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針變化情況,在雙向鏈表中插入一個(gè)結(jié)點(diǎn)時(shí)指針的變化情況,p,p,2. 3.3 雙向鏈表,3、雙向鏈表的基本操作算法,2. 3.3 雙向鏈表,1）插入操作算法 (在p 所指結(jié)點(diǎn)之后插入q 結(jié)點(diǎn)的過程 ) q=(NODE *)malloc(sizeof (NODE); q-data=x; q-rlink=p-rlink; q-llink=p; p-rlink=q;

15、(q-rlink)-llink=q;,2. 3.3 雙向鏈表,2）刪除操作算法 (p-llink)-rlink=p-rlink; (p-rlink)-llink=p-llink; free(p);,2. 4 一元多項(xiàng)式的表示及相加,計(jì)算機(jī) 領(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 + + pn xn Q (x) = q0 + q1 x + q2 x2+ + qm xm 不失一般性，設(shè)mindex index ： p

16、所指結(jié)點(diǎn)應(yīng)為和多項(xiàng)式中的結(jié)點(diǎn) p-index = q-index ：將p所指結(jié)點(diǎn)的系數(shù)“加”到q所指結(jié) 點(diǎn)的系數(shù)上相加； p-index q-index ： 從表bh中刪除q 所指結(jié)點(diǎn)，并將其 插入到ah表p所指結(jié)點(diǎn)之前；,一元多項(xiàng)式的相加算法（算法2.8）,void polyadd(NODE *ah, NODE * bh) NODE *pre_p, *p, *q, *temp; char comp; pre_p=ah; p=ah-next; q=bh-next; while (p!=NULL) break; case =: /兩者的指數(shù)值相等 p-coef+=q-coef ; if (p-c

17、oef =0. 0) / 合并后系數(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)式A中當(dāng)前結(jié)點(diǎn)的指數(shù)值大 temp=q-next; q-next=p; pre_p-next=q; pre_p=q; q=temp; ,續(xù),if (q!=NULL) pre_p-next=q; free(bh); char compare ( int n1, int n2 ) if (n1); ,第二章 線性表小結(jié),本章學(xué)習(xí)了線性表的順序存儲(chǔ)結(jié)構(gòu)順序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),線性鏈表,循環(huán)鏈表, 雙向鏈表，以及在這兩種存儲(chǔ)結(jié)構(gòu)下如何實(shí)現(xiàn)線性表的基本操作。這里再一次需要強(qiáng)調(diào)：本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)