《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課堂課件-第2章-表

1、12022/9/15第二章 表 理解表是由同一類型的元素組成的有限序列的概念。 熟悉定義在抽象數(shù)據(jù)類型表上的基本運(yùn)算。 掌握實(shí)現(xiàn)抽象數(shù)據(jù)類型的一般步驟。 掌握用數(shù)組實(shí)現(xiàn)表的步驟和方法。 掌握用指針實(shí)現(xiàn)表的步驟和方法。 掌握用間接尋址技術(shù)實(shí)現(xiàn)表的步驟和方法。 掌握用游標(biāo)實(shí)現(xiàn)表的步驟和方法。 掌握單循環(huán)鏈表的實(shí)現(xiàn)方法和步驟。 掌握雙鏈表的實(shí)現(xiàn)方法和步驟。22022/9/15第二章 表2.1 ADT表 線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素

2、均只有一個(gè)后繼32022/9/15定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列例 英文字母表（A,B,C,.Z)是一個(gè)線性表特征：元素個(gè)數(shù)n表長度，n=0空表1itable=（ListItem）malloc (size*sizeof(ListItem); /*分配空間*/ L-maxsize=size; L-n=0; /*將當(dāng)前線性表長度置0*/ return L; /*成功，返回L*/ 82022/9/152、判斷表是否為空及求表長函數(shù)（1）判斷線性表L是否為空 int ListEmpty(List L) if (L-n=0) return TRUE; else return FALSE; （2

3、）求表長int GetLength(List L) return L-n; return L-n=0;以上兩個(gè)程序的時(shí)間復(fù)雜性均為：O(1)92022/9/153、元素x定位函數(shù) 返回元素x在表中的位置，當(dāng)元素x不在表中時(shí)返回0。int ListLocate (LISTItem x, List L) int i; for (i=0; in; i+) if (L-tablei=x) return +i; ？ return 0;此算法所用時(shí)間與元素x所在位置有關(guān)。假設(shè)x存在于第i個(gè)位置，則找到x需要比較i次。故在最壞情況下，時(shí)間性能為O(n)。102022/9/154、獲取線性表L中的某個(gè)數(shù)據(jù)元素

4、內(nèi)容的函數(shù)ListItem ListRetrieve(int k, List L) if (kL-n) return ERROR; /*判斷k值是否合理，若不合理，返回ERROR*/ return L-tablek-1; 時(shí)間復(fù)雜性O(shè)(1)112022/9/155、表元素插入運(yùn)算void ListInsert (k, x, L)定義：線性表的插入是指在第k（0k n）個(gè)元素之后插入一個(gè)新的數(shù)據(jù)元素x，使長度為n的線性表 變成長度為n+1的線性表 需將第i+1至第n共（n-k)個(gè)元素后移122022/9/15內(nèi)存a1a2ak+1ak+2an01kV數(shù)組下標(biāo)n-1k+1n12k+1元素序號(hào)k+2n

5、n+1內(nèi)存a1a2ak+1ak+2an01k-1V數(shù)組下標(biāo)n-1kn12k元素序號(hào)k+1nn+1an-1x132022/9/15int ListInsert (int k, ListItem x, List L) int i; if (L-n=L-maxsize) return ERROR; /*檢查是否有剩余空間*/ if (kL-n) return ERROR; /*檢查k值是否合理*/ for (i=L-n-1;i=k;i-) L-tablei+1=L-tablei; /*將線性表第k個(gè)元素之后的所有元素向后移動(dòng) L-tablek=x; /*將新元素的內(nèi)容放入線性表的第k+1個(gè)位置*/

6、L-n+; 142022/9/15算法時(shí)間復(fù)雜度T(n)設(shè)Pk是在第k個(gè)元素之后插入一個(gè)元素的概率，則在長度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：若假設(shè)在表中任何合法位置插入元素的機(jī)會(huì)是均等的，則：152022/9/156、表元素刪除運(yùn)算定義：線性表的刪除是指將第k（1i n）個(gè)元素刪除，使長度為n的線性表 變成長度為n-1的線性表 需將第k+1至第n共（n-k)個(gè)元素前移162022/9/15內(nèi)存a1a2akak+1an01k-1V數(shù)組下標(biāo)n-1kn12k元素序號(hào)k+1nn+1內(nèi)存a1a2ak+1V數(shù)組下標(biāo)01k-1n-2kn-112k元素序號(hào)k+1n-1nanak+

7、2172022/9/15算法評(píng)價(jià)設(shè)Qi是刪除第i個(gè)元素的概率，則在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低。182022/9/157、輸出順序表中所有元素的運(yùn)算void PrintList(List L) int i; for(i=0;in;i+) ItemShow(L-tablei); /*此函數(shù)用以輸出元素*/ 時(shí)間復(fù)雜性：O(n)192022/9/152.2.4順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰無須為表示表中元素之間的順序關(guān)系增加額外的存儲(chǔ)空間可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)插

8、入、刪除操作需要移動(dòng)大量的元素（除操作在表尾的位置進(jìn)行外）預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充202022/9/152.3 用指針實(shí)現(xiàn)表2.3.1 用指針實(shí)現(xiàn)表的特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ak，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn)數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域 指針域結(jié)點(diǎn)212022/9/15例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHE

9、NGZHOU存儲(chǔ)地址1713192531374331first第一個(gè)元素指針ZHAOQIANSUNLIZHOUWUZHENGWANG0first222022/9/15實(shí)現(xiàn)typedef struct node * link;typedef struct node ListItem element; link next;Node;datalinkp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap-data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).linkp-link表示p指向結(jié)點(diǎn)的指針域2.3.2 單鏈表的數(shù)據(jù)類型定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表，也叫線性鏈表232022/9/15h空表ha1a

10、2an 頭結(jié)點(diǎn)頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空據(jù)此可定義用指針實(shí)現(xiàn)表的結(jié)構(gòu)List如下：typedef struct llist *List;typedef struct llist link first;Llist;242022/9/152.3.3 單鏈表的基本運(yùn)算1、創(chuàng)建一個(gè)空表List ListInit() List L=malloc(sizeof*L); L-first=NULL; return L;2、判斷當(dāng)前表L是否為空表Int ListEmpty(List L) return L-first=NULL; 252022/9/153、求表

11、長函數(shù)Int ListLength(List L) int len=0; link p; p=L-first; while(p) /*通過對(duì)表L進(jìn)行線性掃描計(jì)算*/ len+; p=p-next; return len; 時(shí)間復(fù)雜性為：O(n)思考？： 如何改進(jìn)使得時(shí)間復(fù)雜性降為O(1)262022/9/154、從表首開始逐個(gè)元素向后進(jìn)行線性掃描直至找到L中第k個(gè)元素ListItem ListRetrieve(int k,List L) int i; link p; if(kfirst; i=1; while(inext; i+; return p-element; 時(shí)間復(fù)雜性為：O(k) 2

12、72022/9/155、定位元素x (查找運(yùn)算) 查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回X結(jié)點(diǎn)的位置；否則返回0；int ListLocate(ListItem x, List L) int i=1; link p; p=L-first; while(p&p-element!=x) p=p-next; i+; return p? i:0; /如果p為空，說明x不存在返回0；否則返回其位置i282022/9/15While循環(huán)中語句頻度為若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為n算法評(píng)價(jià)292022/9/156、在位置k后插入元素x 函數(shù)的運(yùn)算步驟是：先掃描鏈表找到插入位置p，然后建立一個(gè)存儲(chǔ)

13、待插入元素x的新結(jié)點(diǎn)y，再將結(jié)點(diǎn)y插入到結(jié)點(diǎn)p之后。 插入的示意圖如下： yyy-next = first;firstfirst = y;py-next = p-next;p-next = y;302022/9/15Void LsitInsert(int k, ListItem x, List L) link p, y; int i； if (k first; /找插入位置 for ( i= 1; i next; y = NewNode( ); y-element = x; if (k) y-next = p-next; / 在位置p處插入 p-next = y; else y-next =

14、first; first = y; /在表首插入需要特殊處理（若引入表頭結(jié)點(diǎn)則可納入 一般情況） 其時(shí)間復(fù)雜性為O(k)算法的主要計(jì)算時(shí)間用于尋找正確的插入位置，故312022/9/157、刪除位置k處的元素給x 函數(shù)的運(yùn)算步驟是：依次處理以下3種情況。（）k1。其刪除的示意圖如下p=q-next;q-next = p-next;Free p;給出越界信息；直接修改表首指針first，刪除表首元素322022/9/15ListItme ListDelete(int k, List L) link p, q; ListItem x; int i; if (k first) Error(OutOf

15、Bounds ); p = L-first; if (k = 1) / 刪除表首元素需要特殊處理 L-first = pnext; else / 找表中第k-1個(gè)元素所在結(jié)點(diǎn)q q =L- first; for ( i = 1; i next; p = q-next; /讓p指向 第k個(gè)元素所在結(jié)點(diǎn) q-next = p-next; / 刪除結(jié)點(diǎn)p x = p-element; / 第k個(gè)元素存入x并釋放結(jié)點(diǎn)p free( p ); return x; 算法主要時(shí)間用于尋找待刪除元素所在結(jié)點(diǎn)，故其所需時(shí)間為O(k)332022/9/157、輸出鏈表中所有元素:void PrintList (L

16、ist L) link p; for (p = L-first; p; p = p-next) ItemShow(p-element); 時(shí)間復(fù)雜性 O（n）342022/9/15動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針?biāo)惴ㄔu(píng)價(jià)h頭結(jié)點(diǎn)an 0h頭結(jié)點(diǎn)an-10an a2.h頭結(jié)點(diǎn)an-10an ha1a2頭結(jié)點(diǎn)an .0h頭結(jié)點(diǎn)0352022/9/152.3.4單鏈表特點(diǎn)優(yōu)點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用不需預(yù)先分配空間（動(dòng)態(tài)生成鏈表）避免了數(shù)組要求連續(xù)的存儲(chǔ)單元的缺點(diǎn)，因而在執(zhí)行插入或刪除運(yùn)算時(shí)，不再需要移動(dòng)元素來騰出空間或填補(bǔ)空缺。

17、(當(dāng)元素的粒度很大時(shí)，移動(dòng)元素是很費(fèi)時(shí)的。)缺點(diǎn)指針占用額外存儲(chǔ)空間不能隨機(jī)存取，查找速度慢362022/9/152.4 用間接尋址方法實(shí)現(xiàn)表2.4.1 用間接尋址方法實(shí)現(xiàn)表的原因及實(shí)現(xiàn)原因：綜合數(shù)組和指針實(shí)現(xiàn)兩者的優(yōu)點(diǎn)。實(shí)現(xiàn)：將數(shù)組和指針兩種實(shí)現(xiàn)方式結(jié)合起來，讓數(shù)組中原來存儲(chǔ)元素的地方改為存儲(chǔ)指向元素的指針。 其結(jié)構(gòu)圖如下：372022/9/15List ListInit(int size) List L= (List)malloc(sizeof *L); L-n=0; L-maxsize=size; L-table = (addr *)malloc(size*sizeof(addr); r

18、eturn L;382022/9/15int ListEmpty(List L) return L-n=0;int ListLength(List L) return L-n;392022/9/15ListItem ListRetrieve(int k,List L) if (kL-n) Error(out of bounds); return *L-tablek-1;int ListLocate(Listitem x,List L) int i; for (i=0;in;i+) if (*L-tablei = x) return +i; return 0;402022/9/15void Li

19、stInsert(int k,ListItem x,List L) int i; if (kL-n) Error(“out of bounds”); if (L-n = L-maxsize) Error(“out of memory”); for (i = L-n-1;i=k;i-) L-tablei+1=L-tablei; L-tablek = NewNode(); *L-tablek=x; L-n+;412022/9/15ListItem ListDelete(int k,List L) int i;ListItem x; addr p; if (kL-n) Error(“out of b

20、ounds”); p = L-tablek-1; x=*p for (i=k;in;i+) L-tablei-1=L-tablei; L-n-; free(p); return x;422022/9/15void PrintList(List L) int i; for (i=0;in;i+) ItemShow(*L-tablei);432022/9/152.4.2 用間接尋址實(shí)現(xiàn)表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)： (1)與用數(shù)組實(shí)現(xiàn)一樣，可以方便地隨機(jī)存取表中任一位置的元素。 (2)與用指針實(shí)現(xiàn)一樣，在執(zhí)行插入或刪除運(yùn)算時(shí)，不需要移動(dòng)元素來騰出空間或填補(bǔ)空缺。 缺點(diǎn)： (1)與用數(shù)組實(shí)現(xiàn)一樣，需要預(yù)先確定ta

21、ble的大小。當(dāng)表 長變化很大時(shí)，這比較難。 (2)與用指針實(shí)現(xiàn)一樣，需要額外的存儲(chǔ)空間，即額外的 指針數(shù)組table 。442022/9/152.5 用游標(biāo)實(shí)現(xiàn)表2.5.1 用游標(biāo)實(shí)現(xiàn)表原因及實(shí)現(xiàn)原因：對(duì)于有多個(gè)同類表的應(yīng)用，希望通 過自主調(diào)濟(jì)內(nèi)存資源，達(dá)到資源的更 有效合理的利用。實(shí)現(xiàn)：從操作系統(tǒng)申請(qǐng)一個(gè)較大的數(shù)組S，然后自主地支配S中的單元，在S中用游標(biāo)模擬指針實(shí)現(xiàn)表，并讓多個(gè)同類的表共享這個(gè)數(shù)組，如右圖。數(shù)組S12存放著相同類型的兩個(gè)表A和B,其中表A含有3個(gè)元素；表B含有2個(gè)元素。如圖：first1指示S中尚未被使用的子段的起始單元； first2指示S中被使用過、但目前處于閑置的單

22、元組成的一條可管理的鏈。讓其中的單元優(yōu)先于first1指示的子段中的單元滿足應(yīng)用的需要。 452022/9/152.5.2 用游標(biāo)實(shí)現(xiàn)表的優(yōu)缺點(diǎn)優(yōu)點(diǎn):可實(shí)現(xiàn)多個(gè)同類的表共享同一片連續(xù)存儲(chǔ) 空間，給用戶予資源調(diào)濟(jì)的自主權(quán)。缺點(diǎn):應(yīng)該向操作系統(tǒng)申請(qǐng)多大的連續(xù)存儲(chǔ)空間 依賴于具體的應(yīng)用，不容易把握。462022/9/152.6 循環(huán)鏈表2.6.1 單循環(huán)鏈表 循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向表首結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p-next=NULL循環(huán)鏈表p-next=first(a)非空表 (b)空表因此

23、，找最后元素只需O(1),找首元素仍只需O(1)。前提？472022/9/152.7 用雙鏈實(shí)現(xiàn)表2.7.1 雙向鏈表原因： 無論用指針實(shí)現(xiàn)表還是用單循環(huán)鏈表實(shí)現(xiàn)表時(shí)，對(duì)于表中任一元素x,都不可能在O(1)時(shí)間里找到它的前驅(qū)。為了能在O(1)時(shí)間里既能找到前驅(qū)又能找到后繼，提出了雙鏈表。 在用指針實(shí)現(xiàn)表的每一個(gè)結(jié)點(diǎn)中增加一個(gè)指向前驅(qū)的指針。結(jié)構(gòu)如下圖。pp-left-right = p = p-right-left;482022/9/152.7.2 雙向循環(huán)鏈表L空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABpp-left-right = p = p-right-left;492022/9/15p-left-right=p-right;p-right-left=p-left;free(p);刪除算法描述算法評(píng)價(jià)：T(n)=O(1)p-left-right=p-right;p-right-left=p-left;bcap502022/9/15 s-left=p-left; p-left-right=s; s-right=p; p-left=s;算法描述算法評(píng)價(jià)：T(n)=O(1)xSbaP插入512022/9/152.8 線性表的應(yīng)用舉例 一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示：可用線性表P表示但對(duì)S(x)這樣的多項(xiàng)式浪費(fèi)空間一般其中用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示其存儲(chǔ)結(jié)構(gòu)可