1、第二章 線性表,鏈表,單鏈表,定義 特點(diǎn) C描述 基本形態(tài) 基本操作實(shí)現(xiàn),一組數(shù)據(jù)項(xiàng)的集合，其中每個數(shù)據(jù)項(xiàng)都是一個結(jié)點(diǎn)的一部分，每個結(jié)點(diǎn)都包含指向下一個結(jié)點(diǎn)的鏈接（即指針）。,1.數(shù)據(jù)元素在“邏輯關(guān)系上的相鄰”用“指針”來表示。 2.單鏈表 中訪問數(shù)據(jù)元素時需從頭開始“順序訪問”。 3.比順序表的優(yōu)勢在于，提供高效地重排數(shù)據(jù)項(xiàng)的能力。,L,單鏈表的C描述,typedef struct LNode ElemType data; / 數(shù)據(jù)域 struct LNode *next; / 指針域 LNode, *LinkList;,LinkList L； / L 為單鏈表的頭指針,頭指針指向單鏈表中的

2、第一個結(jié)點(diǎn),用指針表示鏈接，用結(jié)構(gòu)體表示結(jié)點(diǎn)，結(jié)點(diǎn)是由數(shù)據(jù)項(xiàng)和鏈接組成的，鏈接是指向下一結(jié)點(diǎn)的指針。,單鏈表的基本形態(tài),空表 非空表,為了操作方便，在第一個結(jié)點(diǎn)之前虛加一個“頭結(jié)點(diǎn)”,啞元結(jié)點(diǎn),L,L-next = NULL;,不允許刪除操作,L,可以進(jìn)行插入、刪除操作,單鏈表基本操作,1、初始化（動態(tài)分配）,Stutas InitList(LinkList ,j,1,2,3,單鏈表基本操作,2、取單鏈表中指定位序的數(shù)據(jù)元素,演示例子：取單鏈表中第3個元素值,取元素的基本操作,單鏈表是一種“順序訪問”的結(jié)構(gòu)，為找第 i 個數(shù)據(jù)元素，必須先找到第( i-1 )個數(shù)據(jù)元素。,1.指針p始終指向單鏈

3、表中第j個結(jié)點(diǎn)； 2.移動指針，比較 j 和 i，相等則找到。,Status GetElem_L(LinkList L, int i, ElemType j = 1; / p指向第一個結(jié)點(diǎn)，j為計數(shù)器,while (p / 順指針向后查找，直到 p 指向第 i 個元素 / 或 p 為空,if ( p ,與順序表相比，鏈表不適合于查找第i個元素的操作。,單鏈表基本操作,3、插入（在第i個元素前插入e）,單鏈表中：,有序?qū)?改變?yōu)?和,在單鏈表中插入結(jié)點(diǎn)只需要修改指針。若要在第 i 個結(jié)點(diǎn)之前插入元素，修改的是第 (i-1) 個結(jié)點(diǎn)的指針。,Status ListInsert_L(LinkList

4、 ,p = L; j = 0; while (p / 尋找第 (i-1) 個結(jié)點(diǎn) if (p / 生成新結(jié)點(diǎn) s-data = e; s-next = p-next; p-next = s; / 插入 return OK;,s,p,有序?qū)?和 改變?yōu)?,單鏈表基本操作,4、刪除（第i個元素）,在單鏈表中刪除第 i 個結(jié)點(diǎn)時，要找到單鏈表中第(i-1)個結(jié)點(diǎn)，修改其指向后繼的指針。,q = p-next; p-next = q-next; e = q-data; free(q);,p,q,Status ListDelete_L(LinkList j = 0; while (p-next / 尋找

5、第 i-1 個結(jié)點(diǎn)，并令 p 指向它。 if (p-next p-next = q-next; / 刪除并釋放結(jié)點(diǎn) e = q-data; free(q); return OK; else return ERROR; / 刪除位置不合理,對比單鏈表和順序表的基本操作,插入和刪除的簡單性是鏈表存在的理由 只修改相關(guān)結(jié)點(diǎn)的指向保持鏈表特性 單鏈表的訪問方式是順序訪問 查找第i個數(shù)據(jù)項(xiàng)的代價，沿著鏈表，一個一個結(jié)點(diǎn)地訪問，直到找的這個數(shù)據(jù)項(xiàng),算法時間復(fù)雜度：,O(ListLength(L),單鏈表基本操作,5、清空,while (L-next) p=L-next; L-next=p-next; fr

6、ee(p); ,算法時間復(fù)雜度：,O(ListLength(L),單鏈表基本操作,6、銷毀,while(L) p=L-next; free(L); L=p; ,單鏈表基本操作,7、判空,if(L-next=NULL) return TRUE; else return FALSE;,8、求表長,int ListLength(LinkList L) p=L-next; i=0; while(p) i+; p=p-next; return i; ,單鏈表基本操作,9、搜索（查找元素）,p=L-next; i=1; while(p,從第一個結(jié)點(diǎn)開始搜索,搜索成功，返回位序；否則，返回0,單鏈表的應(yīng)用,

7、1.建立單鏈表,鏈表是一個動態(tài)結(jié)構(gòu)，它不需要預(yù)分配空間，因此生成鏈表的過程是一個結(jié)點(diǎn)“逐個插入” 的過程。,逆序建立單鏈表,順序建立單鏈表,新結(jié)點(diǎn)插入在頭結(jié)點(diǎn)的后面，作為重排鏈表后的第一個結(jié)點(diǎn),新結(jié)點(diǎn)插入在尾結(jié)點(diǎn)的后面，作為重排鏈表后的最后一個結(jié)點(diǎn),逆序建立單鏈表,操作步驟,建立一個帶頭結(jié)點(diǎn)的空單鏈表；,輸入數(shù)據(jù)元素ai，建立新結(jié)點(diǎn)p，并把p插入在頭結(jié)點(diǎn)之后成為第一個結(jié)點(diǎn)。,重復(fù)執(zhí)行步，直到完成單鏈表的建立。,a1,a1,a2,void CreateList_N(LinkList L-next = NULL; / 先建立一個帶頭結(jié)點(diǎn)的單鏈表,for (i = 1; i data); / 輸入元

8、素值 p-next = L-next; L-next = p; / 插入 ,順序建立單鏈表,操作步驟,建立一個帶頭結(jié)點(diǎn)的空單鏈表；,輸入數(shù)據(jù)元素ai，建立新結(jié)點(diǎn)，并把其插入在尾結(jié)點(diǎn)p之后成為最后一個結(jié)點(diǎn)。,重復(fù)執(zhí)行步，直到完成單鏈表的建立。,a1,p,a1,p,p,a2,p,a3,p,p,p,an,順序建立單鏈表：即新元素插入表尾,L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一個帶頭結(jié)點(diǎn)的單鏈表,時間復(fù)雜度為O(n),p=L; for(i=1;idata); q-next=p-next; p-next=q; p=q; ,

9、單鏈表的應(yīng)用,2.歸并有序鏈表,歸并有序單鏈表La和有序單鏈表Lb得到有序單鏈表Lc。,鏈表結(jié)點(diǎn)之間的關(guān)系是通過指針指向建立起來的，所以用鏈表進(jìn)行合并不需要另外開辟存儲空間，可以直接利用原來兩個表的存儲空間，合并過程中只需要把La和Lb兩個鏈表中的結(jié)點(diǎn)重新進(jìn)行鏈接即可。,單鏈表的應(yīng)用,歸并思想：,需要設(shè)立3個指針pa、pb、pc，其中pa和pb分別指向La和Lb中當(dāng)前待比較插入的結(jié)點(diǎn)，而pc指向Lc中當(dāng)前最后一個結(jié)點(diǎn)（Lc的表頭結(jié)點(diǎn)設(shè)為La的表頭結(jié)點(diǎn)）。指針的初值為：pa和pb分別指向La和Lb表中的第一個結(jié)點(diǎn)，pc指向空表Lc中的頭結(jié)點(diǎn)。通過比較指針pa和pb所指向的元素的值，依次從La或L

10、b中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc的最后，當(dāng)其中一個表變空時，只要將另一個表的剩余段鏈接在pc所指結(jié)點(diǎn)之后即可。,歸并有序單鏈表,void MergeList_L(LinkList ,算法時間復(fù)雜度：,O(m+n),算法空間復(fù)雜度：,O(1),單鏈表的應(yīng)用,3.稀疏多項(xiàng)式的運(yùn)算,稀疏多項(xiàng)式可以抽象成一個線性表。稀疏多項(xiàng)式的相加過程和歸并兩個有序表的過程極其類似。不同之處在于，多項(xiàng)式的相加過程在比較兩個多項(xiàng)式指數(shù)時要考慮三種情況（等于、小于、大于）。鏈?zhǔn)酱鎯Y(jié)構(gòu)更加靈活，合并過程空間復(fù)雜度為O(1)。,多項(xiàng)式A(x)=7+3x+9x8+5x17和多項(xiàng)式B(x)=8x+22x7-9x8,單鏈表

11、的應(yīng)用,稀疏多項(xiàng)式的相加,規(guī)則：對于兩個多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對應(yīng)系數(shù)相加，若其和不為零，則作為“和多項(xiàng)式”中的一項(xiàng)插入到“和多項(xiàng)式”鏈表中去；對于兩個多項(xiàng)式中指數(shù)不相同的項(xiàng)，則將指數(shù)值較小的項(xiàng)插入到“和多項(xiàng)式”鏈表中去?！昂投囗?xiàng)式”鏈表中的結(jié)點(diǎn)無需生成，而應(yīng)該從兩個多項(xiàng)式鏈表中摘取。,11 1,22 7,A,稀疏多項(xiàng)式相加,typedef struct PNode float coef; int expn; struct PNode *next; PNode ,*Polynomial;,用單鏈表表示多項(xiàng)式時，每個鏈表結(jié)點(diǎn)存儲多項(xiàng)式中的一個非零項(xiàng)，包括系數(shù)（coef）和指數(shù)（expn）兩個

12、數(shù)據(jù)域以及一個指針域（next）。,稀疏多項(xiàng)式相加,假設(shè)頭指針pa和pb的單鏈表分別為多項(xiàng)式A和B的存儲結(jié)構(gòu)，指針p1和p2分別指向A和B中當(dāng)前進(jìn)行比較的某個結(jié)點(diǎn)，則逐一比較兩個結(jié)點(diǎn)中的指數(shù)項(xiàng)，對于指數(shù)相同的項(xiàng)，對應(yīng)系數(shù)相加，若其和不為零，則將插入到“和多項(xiàng)式”鏈表中去；對于指數(shù)不相同的項(xiàng)，則通過比較將指數(shù)較小的項(xiàng)插入到“和多項(xiàng)式”鏈表中去。,稀疏多項(xiàng)式相加,void AddPolyn(Polynomial else,稀疏多項(xiàng)式相加, r=p1;p1=p1-next;free(r); r=p2;p2=p2-next;free(r); else if(p1-expnexpn) p3-next=p1;p3=p1;p1=p1-next; else p3-next =p2;p3=p2;p2=p2-next; p3-next=p1?p1:p2;