線性表-數(shù)據(jù)結(jié)構(gòu).ppt_第1頁
線性表-數(shù)據(jù)結(jié)構(gòu).ppt_第2頁
線性表-數(shù)據(jù)結(jié)構(gòu).ppt_第3頁
線性表-數(shù)據(jù)結(jié)構(gòu).ppt_第4頁
線性表-數(shù)據(jù)結(jié)構(gòu).ppt_第5頁
已閱讀5頁,還剩107頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第二章 線性表,課前導(dǎo)學(xué),2.1 線性表的類型定義 2.2 線性表的順序表示與實(shí)現(xiàn) 2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 2.4 一元多項(xiàng)式的表示及相加,學(xué)習(xí)目標(biāo),1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系。 2. 熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 3. 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合。 4. 結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。,重點(diǎn)和難點(diǎn),鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求,分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系,區(qū)分鏈表中的

2、頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。,線性結(jié)構(gòu)的特點(diǎn),在數(shù)據(jù)元素的非空有限集中 存在唯一一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素; 存在唯一一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素; 除第一個(gè)數(shù)據(jù)元素之外,每個(gè)元素都只有一個(gè)前驅(qū); 除最后一個(gè)數(shù)據(jù)元素之外,每個(gè)元素都只有一個(gè)后繼。,線性表的定義,一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。 除了第一個(gè)元素沒有直接前驅(qū)和最后一個(gè)元素沒有直接后繼之外,其余的每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。,線性表的特征,有窮性:由有限個(gè)元素組成,元素個(gè)數(shù)n表長度,n=0空表。設(shè)線性表為 (a1,a2, . . . ,ai,. . . ,an), 稱

3、 i 為 ai 在線性表中的位序。 有序性:線性表元素之間存在序偶關(guān)系,1in時(shí) ai的直接前驅(qū)是ai-1,a1無直接前驅(qū) ai的直接后繼是ai+1,an無直接后繼 同一性:線性表屬于同類數(shù)據(jù)元素組成,每一個(gè)對(duì)象都屬于同一數(shù)據(jù)對(duì)象,抽象數(shù)據(jù)類型線性表的定義如下:,ADT List 數(shù)據(jù)對(duì)象:D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系:R1 |ai-1 ,aiD, i=2,.,n 基本操作: (1)InitList( GetElem(LB, i)e 依值在線性表LA中進(jìn)行查訪; LocateElem(LA, e, equal( ) 若不存在,則插入之。 ListI

4、nsert(LA, n+1, e) 算法的時(shí)間復(fù)雜度: O(ListLength(LA) ListLength(LB)),思路:,實(shí)現(xiàn):void union(List ,結(jié)構(gòu)體類型的使用,結(jié)構(gòu)體的定義方式: struct 結(jié)構(gòu)體名 成員列表 變量名稱; 例如: typedef struct student int num; /學(xué)號(hào) char name20; int age; stu; /定義一種學(xué)生結(jié)構(gòu)體類型,并將此類型重新定義名稱為stu類型,結(jié)構(gòu)體變量的引用:,結(jié)構(gòu)體變量名.成員名。student1.num=20; 指向結(jié)構(gòu)體變量的指針的使用 stu *p;/p為指向結(jié)構(gòu)體類型的指針 p=

5、 則*p代表的結(jié)構(gòu)體變量student1 通過p引用結(jié)構(gòu)體變量的成員為 p-num 或者(*p).num。,2.2線性表的順序存儲(chǔ)結(jié)構(gòu),定義:線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素。 使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。 假設(shè)線性表中有n個(gè)元素,每個(gè)元素占L個(gè)單元,第一個(gè)元素的地址為loc(a1),則可以通過如下公式計(jì)算出第i個(gè)元素的地址Loc(ai): loc(ai+1) =loc(ai)+L loc(ai) =loc(a1)+(i-1)L (2-2) 其中l(wèi)oc(a1) 稱為基址。,線性表

6、的順序存儲(chǔ)結(jié)構(gòu)是一種隨即存取的存儲(chǔ)結(jié)構(gòu),只要確定了起始位置,就可以訪問表中的任何一個(gè)元素。,數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的誤區(qū),只動(dòng)眼、耳,不動(dòng)手 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的有效方法是動(dòng)手,動(dòng)腦。 (2)有的同學(xué)認(rèn)為,數(shù)據(jù)結(jié)構(gòu)是C語言的延續(xù),這是一種錯(cuò)誤的想法。 C語言僅僅是一個(gè)程序設(shè)計(jì)工具,而數(shù)據(jù)結(jié)構(gòu)則是程序設(shè)計(jì)的思想和靈魂,在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中經(jīng)常會(huì)接觸到C語言的知識(shí),這只不過是借用C語言這個(gè)工具來表達(dá)數(shù)據(jù)結(jié)構(gòu)的思想而已,我們也可以不選用C語言,而選擇其它語言,如PASCAL、JAVA等,所以,不應(yīng)該把數(shù)據(jù)結(jié)構(gòu)當(dāng)成C語言來學(xué)習(xí)。 死記硬背 分析每一種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方式和操作算法,養(yǎng)成提出問題、分析問題和解決問

7、題的思維習(xí)慣,提升自己分析問題和解決問題的能力。,課程回顧,線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表的初始化 線性表插入操作,順序存儲(chǔ)結(jié)構(gòu)的C語言定義,#define LIST_INT_SIZE 100 #define LISTINCREAMENT 10 typedef struct ElemType *elem; / 線性表占用的數(shù)組空間。 int length;/ 線性表的長度 int listsize; /當(dāng)前分配的存儲(chǔ)容量 SeqList;,線性表的基本操作在順序表中的實(shí)現(xiàn),InitList( If (! L-elem) exit(OVERFLOW); /存儲(chǔ)分配失敗 L-length=0; /空

8、表長度為0 L-listsize= LIST_INIT_SIZE; /初始存儲(chǔ)容量 return OK; /InitList_Sq,二、線性表的順序表插入操作 ListInsert( if (i L.length+1) return ERROR; / 插入位置不合法 if (L-length = L- listsize) . q = ,newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/ 當(dāng)前存儲(chǔ)空間已滿 L- elem=

9、newbase; L- list size+=LISTINCREMENT;,考慮移動(dòng)元素的平均情況:,假設(shè)在第 i 個(gè)元素之前插入的概率為 則在長度為n 的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為:,若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的,則移動(dòng)元素的期望值為:,線性表操作 ListDelete( i elemi-1= L- elemi; / 被刪除元素之后的元素左移 -L- length; / 表長減1 return OK;,*e= L-elemi-1; / 被刪除元素的值賦給 e k= L- length-1; / 表尾元素的位置,if (i L.length) re

10、turn ERROR; / 刪除位置不合法,考慮移動(dòng)元素的平均情況:,假設(shè)刪除第 i 個(gè)元素的概率為 , 則在長度為n 的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為:,若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的,則移動(dòng)元素的期望值為:,int LocateElem_Sq(SqList L, ElemType e,) / 在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素, / 若存在,則返回它的位序,否則返回 0 / LocateElem_Sq,if (i = L.length) return i; else return 0;,int i i= 1; / i 的初值為第 1 元素的位

11、序,while (i = L.length ,/找到滿足條件的元素,/ 沒有找到滿足條件的元素,時(shí)間復(fù)雜度為:0(L.length),線性表的查找操作,例如:順序表,e =,38,i,1,2,3,4,1,8,50,可見,基本操作是, 將順序表中的元素 逐個(gè)和給定值 e 相比較。,順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn):,優(yōu)點(diǎn): 邏輯相鄰,物理相鄰 可隨機(jī)存取任一元素 存儲(chǔ)空間使用緊湊 缺點(diǎn) 插入、刪除操作需要移動(dòng)大量的元素,順序表習(xí)題作業(yè):,學(xué)號(hào)結(jié)尾為1,3,5的同學(xué)交作業(yè),作業(yè)內(nèi)容:教材算法2.7,完整的c程序結(jié)構(gòu)。,線性表的合并問題,例1、已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列,現(xiàn)要將LA和LB

12、歸并為一個(gè)新的鏈表LC,且LC中的數(shù)據(jù)元素仍按非值遞減有序排序。 例如:LA(3,5,8,11) LB(2,6,8,9,11,15,20) 則LC(2,3,5,6,8,8,9,11,11,15,20),線性表的一般算法: Void MergeList(List La,List Lb,List Lc) InitList(Lc); ij1;k0; La_lenListLength(La);Lb_lenListLength(Lb); While((i=La_len) /Mergelist,順序表中的實(shí)現(xiàn) Void MergeList(SqList La, SqList Lb, SqList *Lc)

13、 int *pa,*pb,*pc,* pa_last,* pb_last; pa=La.elem;pb=La.elem; Lc-listsize=Lc.length=La.length+ Lb.length; pc=Lc-elem=(ElemType*)malloc(Lc-istsize*sizeof(ElemType); If(!Lc-elem) exit(overfiow); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last ,2.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn),特點(diǎn): 用一組任意的存儲(chǔ)單元存儲(chǔ)

14、線性表的數(shù)據(jù)元素 利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素ai,除存儲(chǔ)本身信息外,還需存儲(chǔ)其直接后繼的信息 結(jié)點(diǎn):數(shù)據(jù)元素ai 的存儲(chǔ)映像。 數(shù)據(jù)域:元素本身信息 指針域:指示直接后繼的存儲(chǔ)位置,例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,頭指針,2.3.1 單鏈表 (或線性鏈表),1. 定義:結(jié)點(diǎn)中只含一個(gè)指針域的鏈表。 2. 特征 每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。 線性結(jié)構(gòu) 結(jié)點(diǎn)可以不連續(xù)存儲(chǔ) 表可擴(kuò)充,data next,3. 單鏈表的存儲(chǔ)映像,free,(a)

15、可利用存儲(chǔ)空間,a1,a3,a2,a4,free,first,(b) 經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu),以線性表中第一個(gè)數(shù)據(jù)元素 的存儲(chǔ)地址作為線性表的地址,稱作線性表的頭指針,頭結(jié)點(diǎn),頭指針,頭指針,有時(shí)為了操作方便,在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”,以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針,空指針,線性表為空表時(shí), 頭結(jié)點(diǎn)的指針域?yàn)榭?4. 單鏈表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)用C語言中的“結(jié)構(gòu)指針”來描述,typedef struct LNode ElemType data; struct LNode *next; LNode ,*LinkList;,struct LNode ElemType data; stru

16、ct LNode *next; ; typedef LNode * LinkList;,單鏈表特點(diǎn): 它是一種動(dòng)態(tài)結(jié)構(gòu),整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 不需預(yù)先分配空間 指針占用額外存儲(chǔ)空間 不能隨機(jī)存取,查找速度慢,生成一個(gè)LNode型新結(jié)點(diǎn):p=(LinkList)malloc(sizeof(LNode); 系統(tǒng)回收p結(jié)點(diǎn):free(p),線性表的操作 GetElem(L, i, j = 1; / p指向第一個(gè)結(jié)點(diǎn),j為計(jì)數(shù)器,while (p / 順指針向后查找,直到 p 指向第 i 個(gè)元素 / 或 p 為空,if ( !p | ji ) return ERROR; / 第 i 個(gè)元素不存在

17、 *e = p-data; / 取得第 i 個(gè)元素 return OK;,單鏈表中的插入與刪除,插入 第一種情況:在第一個(gè)結(jié)點(diǎn)前插入 s = (LinkList)malloc(sizeof(LNode);/ 生成新結(jié)點(diǎn) if ( s = null) return ERROR; s-data = e; s-next = first ; first = s;,(插入前) (插入后),a1,a2,first,e,s,e,s,a1,first,a2,ai,e,(插入前) (插入后),第二種情況:在鏈表中間插入 s-next = p-next; p-next = s;,ai,ai-1,p,e,ai-1,

18、s,p,s,第三種情況:在鏈表末尾插入 s-next= p-next; p-next = s;,(插入前) (插入后),e,s,e,s,p,p,單鏈表的插入算法,int ListInsert_L ( LinkList L, int i, int e ) / 在帶頭結(jié)點(diǎn)的單鏈線性表L中第 i 個(gè)位置之前插入元素 e LNode *p,*s; int j; p = L; j = 0; while ( p ,刪除 第一種情況: 刪除表中第一個(gè)元素 第二種情況: 刪除表中或表尾元素,在單鏈表中刪除含ai的結(jié)點(diǎn),ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,刪除前,刪除后,p-next =

19、 q-next,單鏈表的刪除算法,int ListDelete_L ( LinkList L, int i, int *e ) / 在帶頭結(jié)點(diǎn)的單鏈線性表 L 中,刪除第 i 個(gè)元素,并由 e 返回其值 LNode *p,*q; int j; p = L; j = 0; while ( p-next / LinkDelete_L,T(n)=O(n),5. 動(dòng)態(tài)建立單鏈表算法:,動(dòng)畫2-3-2.swf演示,算法評(píng)價(jià),算法思路: (1)創(chuàng)建頭結(jié)點(diǎn) (2)逆序創(chuàng)建結(jié)點(diǎn)n,修改結(jié)點(diǎn)指針,再創(chuàng)建結(jié)點(diǎn)n-1,直到結(jié)點(diǎn)1,void CreateList_L ( LinkList *L, int n ) /

20、逆位序輸入 n 個(gè)數(shù)據(jù)元素的值,建立帶頭結(jié)點(diǎn)的單鏈表 L LNode *p; int i; * L = ( LinkList ) malloc ( sizeof ( LNode ) ); (*L)-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表 for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新結(jié)點(diǎn) scanf (%d , / 修改單鏈表頭結(jié)點(diǎn)的指針域 ,/單鏈表的建立算法,void init_linklist(LinkList *l) /*對(duì)單鏈表進(jìn)行初始化*/ *l=(LinkLis

21、t)malloc(sizeof(Node); (*l)-next=NULL; void CreateList_L ( LinkList L, int n ) / 逆位序輸入 n 個(gè)數(shù)據(jù)元素的值,建立帶頭結(jié)點(diǎn)的單鏈表 L LNode *p; int i; for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新結(jié)點(diǎn) scanf (%d , / 修改單鏈表頭結(jié)點(diǎn)的指針域 ,線性表的合并問題,例1、已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列,現(xiàn)要將LA和LB歸并為一個(gè)新的鏈表LC,且LC中的數(shù)據(jù)元素仍

22、按非值遞減有序排序。 例如:LA(3,5,8,11) LB(2,6,8,9,11,15,20) 則LC(2,3,5,6,8,8,9,11,11,15,20),線性表的一般算法: Void MergeList(List La,List Lb,List Lc) InitList(Lc); ij1;k0; La_lenListLength(La);Lb_lenListLength(Lb); While((i=La_len) /Mergelist,順序表中的實(shí)現(xiàn) Void MergeList(SqList La, SqList Lb, SqList *Lc) Pa=La.elem;pb=La.elem

23、; Lc-listsize=Lc.length=La.length+ Lb.length; Pc=Lc-elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); If(!Lc.elem) exit(overfiow); Pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; While(pa=pa_last ,例: 將兩個(gè)有序鏈表歸并為一個(gè)有序鏈表,void MergeList_L ( LinkList La, LinkList Lb, LinkList *Lc, ) / 歸并 La 和

24、 Lb 得到新的單鏈表 Lc ,Lc 的元素也按非遞減排列 Node *pa,*pb; pa = La-next; pb = Lb-next; *Lc = pc = La; / 用 La 的頭結(jié)點(diǎn)作為 Lc 的頭結(jié)點(diǎn) while ( pa / 釋放 Lb 的頭結(jié)點(diǎn) / MergeList_L,一、概念題 在順序表中要插入一個(gè)元素平均需要移動(dòng)_次元素,具體移動(dòng)元素的個(gè)數(shù)與_ _ _ _ _有關(guān)。,n/2,元素的具體位置, 單鏈表中,除頭節(jié)點(diǎn)外,任一節(jié)點(diǎn)的存儲(chǔ)位置由_確定。,其前驅(qū)節(jié)點(diǎn)指針域的值,頭結(jié)點(diǎn)、頭指針、和第一個(gè)結(jié)點(diǎn)的區(qū)別。,順序存儲(chǔ)結(jié)構(gòu)是通過( )表示元素之間的關(guān)系的,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過

25、( )表示元素之間的關(guān)系的。(北京理工2001)。 在單鏈表L中,指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是( )。(合肥工業(yè)大學(xué)1999)。 在單鏈表p所指結(jié)點(diǎn)之后插入s節(jié)點(diǎn)的基本操作是( )。(青島大學(xué))。 對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表,判定該表為空的條件是( )。 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種( )。(北京理工2006). 對(duì)于一個(gè)線性表即要求能夠進(jìn)行較快速的插入和刪除操作,又要求存儲(chǔ)結(jié)構(gòu)能夠反映出來數(shù)據(jù)之間的邏輯關(guān)系,則應(yīng)該采用( )存儲(chǔ)結(jié)構(gòu)。(哈工大2005) 對(duì)于順序表,訪問元素和增加、刪除元素的時(shí)間復(fù)雜度是分別是( )、( )。,畫出下列各語句執(zhí)行后各指針及鏈表的示意圖。,L(

26、LinkList)malloc(sizeof(LNode); P=L;,for(I=1;Inext= (LinkList)malloc(sizeof(LNode) P=P-next; P-data=I*2-1; ,P-next=NULL;,For(I=4;I=1;I+) ins_Linklist(L,I+1,I*2),For(I=1;I=3;I+) Del_Linklist(L,i);,有一個(gè)單鏈表,頭指針為head,編寫一個(gè)函數(shù),計(jì)算數(shù)據(jù)域?yàn)閤的節(jié)點(diǎn)的個(gè)數(shù)。 設(shè)計(jì)思想: 遍歷鏈表,設(shè)立一個(gè)計(jì)數(shù)器,每當(dāng)遇到一個(gè)數(shù)據(jù)域?yàn)閄的節(jié)點(diǎn),計(jì)數(shù)器加1。 自己動(dòng)手寫。,int count(Linklist

27、head,int x) node *head, node *p; int j=0; p=head; while(p!=NULL) if(p-data=x) j+; p=p-next; return (j); ,實(shí)現(xiàn)單鏈表的就地逆置算法,即在原表的存儲(chǔ)空間將線性表(a1,a2,an)逆置為(an,an-1,a1)。 設(shè)順序表L是一個(gè)遞增有序表,試寫一算法,將x插入L中,并使L仍是一個(gè)有序表。 編寫程序,刪除線性表a中第i個(gè)元素起的k個(gè)元素。,下面我們將看幾個(gè)在線性表中經(jīng)常會(huì)出現(xiàn)的算法和概念題。 練習(xí)1、把L中值為奇數(shù)的結(jié)點(diǎn)刪除,并用來生成新表L1。,算法思想: 生成一個(gè)新的節(jié)點(diǎn),表示新的鏈表頭節(jié)

28、點(diǎn)。 從第一個(gè)節(jié)點(diǎn)開始,判斷其奇偶性。 若為奇數(shù),則將其鏈到新的鏈表上,否則比較下一個(gè)。,status List_L(LinkList L) p = L; q = p-next; (p為前驅(qū)結(jié)點(diǎn)地址指針變量) s = (LinkList) malloc ( sizeof (Lnode); s-next = NULL; L1 = S ; while (q!= NULL) if (q -data mod 2 = 0) p = q ; q = q-next ; else p-next = q-next; q-next = s-next ;s-next = q ; q = p-next ; retur

29、n OK; ,8. 靜態(tài)鏈表,動(dòng)態(tài)鏈表 鏈表中的結(jié)點(diǎn)空間都是動(dòng)態(tài)申請(qǐng)和釋放的。 在有些高級(jí)語言(如BASIC)中,沒有提供指針類型,此時(shí)若仍想采用鏈表作為線性表存儲(chǔ)結(jié)構(gòu)? 則只能借助一維數(shù)組來模擬鏈表,,定義:用數(shù)組描述的鏈表叫靜態(tài)鏈表 存儲(chǔ)結(jié)構(gòu): #define MAXSIZE = 100; /靜態(tài)鏈表的最大長度 typedef struct ElemType data; int cur; /游標(biāo),代替指針指示結(jié)點(diǎn)在數(shù)組中的位置 component,SLinkListMAXSIZE; 目的是為了在不設(shè)指針類型的高級(jí)程序設(shè)計(jì)語言中使用鏈表結(jié)構(gòu)。樹的雙親表示法、圖的鄰接表表示法、表插入排序、等都

30、用到了靜態(tài)鏈表。,靜態(tài)鏈表結(jié)構(gòu)示例,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,插入shi,修改前的狀態(tài),修改后的狀態(tài),刪除zheng,S0.cur指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置,shi,9,5,5,8,游標(biāo)cur PK 指針next,1、指針next是個(gè)地址,游標(biāo)cur是? int cur;指示后繼元素在數(shù)組中的相對(duì)位置 2、指針后移實(shí)現(xiàn)了,游標(biāo)cur后移呢? p = p-next; 已知:SLinkList S; i = Si.cur;,一般情況下,對(duì)靜態(tài)鏈表S,如果Si.data=ak,則 ak+1= S?.data,Si.cur,靜態(tài)鏈表的

31、存儲(chǔ)結(jié)構(gòu),#define MAXSIZE = 100; /靜態(tài)鏈表的最大長度 typedef struct ElemType data; int cur; /游標(biāo),代替指針指示結(jié)點(diǎn)在數(shù)組中的位置 component,SLinkListMAXSIZE;,在靜態(tài)鏈表中查找第1個(gè)具有給定值e的結(jié)點(diǎn),int LocateElem_SL ( SLinkList, S,ElemType e ) i = S 0.cur; /i 指向表第一個(gè)結(jié)點(diǎn),相當(dāng)于p=p-next while ( i /LocateElem_SL,2.3.2 循環(huán)鏈表 (Circular List),循環(huán)鏈表是單鏈表的變形。 循環(huán)鏈表最

32、后一個(gè)結(jié)點(diǎn)的 link 指針不 為NULL,而是指向了表的前端。 為簡化操作,在循環(huán)鏈表中往往加入頭結(jié)點(diǎn)。 循環(huán)鏈表的特點(diǎn)是:只要知道表中某一結(jié)點(diǎn)的地址,就可搜尋到所有其他結(jié)點(diǎn)的地址。,循環(huán)鏈表的示例 帶頭結(jié)點(diǎn)的循環(huán)鏈表,a1,a2,a3,an,first,an,first,a2,a1,first,(空表),(非空表),搜索成功,搜索不成功,循環(huán)鏈表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,current,current,current,current,current,current,current,current,循環(huán)鏈表的操作和

33、單鏈表基本一致,差別僅在于,判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”,而是“后繼是否為頭結(jié)點(diǎn)”。,帶尾指針的循環(huán)鏈表,rear,31,48,15,57,22,如果插入與刪除僅在鏈表的兩端發(fā)生,可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。 在表尾插入,時(shí)間復(fù)雜性 O(1) 在表尾刪除,時(shí)間復(fù)雜性 O(n) 在表頭插入,相當(dāng)于在表尾插入 在表頭刪除,時(shí)間復(fù)雜性 O(1),頭指針指向表尾的好處是既能立即找到鏈表的尾結(jié)點(diǎn),也容易找到鏈表中的第一個(gè)結(jié)點(diǎn)。 P35頁圖2.13 鏈表A,B直接合并: trilA-next=trilB-next; trilB-next=trilA-next;,靜態(tài)鏈表 單循環(huán)鏈

34、表,2.3.3 雙向鏈表 (Doubly Linked List),雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。 雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域, 結(jié)構(gòu)如下: 雙向鏈表通常采用帶頭結(jié)點(diǎn)的循環(huán)鏈表形式。,前驅(qū)方向 后繼方向,prior data next,雙向鏈表C語言的定義,typedef struct node ElemType data; struct node *prior,*next; JD;,空雙向循環(huán)鏈表:,非空雙向循環(huán)鏈表:,結(jié)點(diǎn)指向 p-prior-next = p = p-next-prior,p-prior,p-next,p,prior,next,雙向循環(huán)鏈表的搜

35、索算法,搜索成功,搜索不成功,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,雙向鏈表插入算法描述,void ins_dulist(JD* p,int x) JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; ,算法實(shí)現(xiàn),算法評(píng)價(jià):T(n)=O(n),雙向鏈表的插入操作算法: Status ListInsert_DuL ( DuLinkList / ListInsert_DuL,算法評(píng)價(jià):T(n)=O(n

36、),雙向鏈表刪除算法描述,void del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); ,算法實(shí)現(xiàn),p-prior-next=p-next;,p-next-prior=p-prior;,雙向鏈表的刪除操作算法: Status ListDelete_DuL ( DuLinkList / ListDelete_DuL,算法評(píng)價(jià):T(n)=O(n),2.3.4 順序表與鏈表的比較,(1)基于空間的比較 存儲(chǔ)分配的方式 順序表的存儲(chǔ)空間是一次分配的 鏈表的元素的存儲(chǔ)空間是動(dòng)態(tài)分配的 存儲(chǔ)密度 = 結(jié)點(diǎn)數(shù)據(jù)本身所占的

37、存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量 順序表的存儲(chǔ)密度 = 1 鏈表的存儲(chǔ)密度 1,(2)基于時(shí)間的比較 存取方式 順序表可以隨機(jī)存取,也可以順序存取 鏈表是順序存取的 插入/刪除時(shí)移動(dòng)元素個(gè)數(shù) 順序表平均需要移動(dòng)近一半元素 鏈表不需要移動(dòng)元素,只需要修改指針 若插入/刪除僅發(fā)生在表的兩端,宜采用帶尾指針的循環(huán)鏈表,如何選擇存儲(chǔ)結(jié)構(gòu)呢?,若線性表的操作主要是進(jìn)行查找,很少做插入和刪除時(shí),宜采用順序表做存儲(chǔ)結(jié)構(gòu)。 對(duì)于頻繁進(jìn)行插入和刪除的線性表, 宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。 在求長度,查找元素時(shí)不如順序表。,用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí), 存在的問題:,1單鏈表的表長是一個(gè)隱含的值;,2在單鏈表的

38、最后一個(gè)元素之后插入元素時(shí), 需遍歷整個(gè)鏈表;,3在鏈表中,元素的“位序”概念淡化,結(jié)點(diǎn)的 “位置”概念加強(qiáng)。,四、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型,typedef struct LNode / 結(jié)點(diǎn)類型 ElemType data; struct LNode *next; *Link, *Position;,typedef struct / 鏈表類型 Link head, tail; / 分別指向頭結(jié)點(diǎn)和 最后一個(gè)結(jié)點(diǎn)的指針 int len; / 指示鏈表長度 LinkList;,課程回顧,上機(jī)出現(xiàn)問題 調(diào)試 鏈表和順序表的區(qū)別 循環(huán)鏈表 雙向鏈表,2.4 一元多項(xiàng)式的表示及相加,1. 一元多項(xiàng)式

39、的表示,n 階多項(xiàng)式 Pn(x) 有 n+1 項(xiàng)。 系數(shù) P0, P1, P2, , Pn 指數(shù) 0, 1, 2, , n。按升冪排列,若: 對(duì)S(x)這樣的多項(xiàng)式采用全部存儲(chǔ)的方式則浪費(fèi)空間。怎么辦? 一般n次多項(xiàng)式可以寫成:,因此可以用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表來表示:,ADT Polynomial 數(shù)據(jù)對(duì)象: 數(shù)據(jù)關(guān)系:,抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下:,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每個(gè)元素包含一個(gè) 表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) ,R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指數(shù)值ai中的指數(shù)值 ,CreatPolyn ( struct node *next; JD, *Polylist ;,(2) 通過鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù),以輸入系數(shù)0為結(jié)束標(biāo)志,并約定建立多項(xiàng)式鏈表時(shí),總是按指數(shù)從大到小的順序排列。 算法描述:從鍵盤接受輸入的系數(shù)和指數(shù); 用尾插法建立一元多項(xiàng)式的鏈表。,Polylist polycreate() Polynode *head, *rear, *s; int c

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論