數(shù)據(jù)結(jié)構(gòu)課件chapter2

1、 數(shù)據(jù)結(jié)構(gòu) (DATA STRUCTURE)第二章 線性表線性表的定義與基本概念線性表的邏輯特點(diǎn)線性表的存儲結(jié)構(gòu)與主要操作 順序?qū)崿F(xiàn)順序表 鏈?zhǔn)綄?shí)現(xiàn)鏈表一元多項式及其相加22.1 線性表的定義與基本運(yùn)算1）定義： n( 0)個具有相同特性數(shù)據(jù)元素的有限序列。 記作: L = (a1, a2, , an） 表名a1 稱為表頭元素， an 稱為表尾元素 n 是表長度ai-1 稱為ai的直接前驅(qū)元素 ai+1稱為ai的直接后繼元素32）線性表的特點(diǎn)從邏輯上講，線性表中（非空）： 線性表是一種線性結(jié)構(gòu)存在唯一的“表頭”元素存在唯一的“表尾”元素除表頭元素外，其余元素有且僅有一個直接前驅(qū)除表尾元素外，其

2、余元素有且僅有一個直接后繼43）線性表的抽象數(shù)據(jù)類型定義 ADT List 數(shù)據(jù)對象: D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系: R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitList( &L ) 初始化 DestroyList( &L ) 結(jié)構(gòu)銷毀 ListEmpty( L ) ListLength( L ) GetElem( L, i, &e ) ADT List51）存儲方式：用一組地址連續(xù)的存儲單元順序存放線性表中邏輯相鄰的元素。 假定每個元素需占用d 個存儲單元，則n個元素的線性表存儲為： 第i個數(shù)據(jù)元素的存儲位置： Loc(a

3、i)=Loc(ai-1)+d 這種存儲結(jié)構(gòu)的線性表稱為順序表2.2 線性表的順序存儲和實(shí)現(xiàn)6用高級語言中的數(shù)組(一維)來表示順序表 # define MaxSize 100 /線性表的最大容量，假設(shè)為100typedef int Elemtype /每個元素的數(shù)據(jù)類型為Elemtype ，假設(shè)為int typedef struct SqList Elemtype dataMaxSize int length; / 線性表長度 ; / 順序表數(shù)據(jù)類型為SqList 3) 順序表的表示(數(shù)據(jù)類型描述)7 插入運(yùn)算: 在表中第i個元素前插入值為 x 新元素 4）順序表基本操作的實(shí)現(xiàn)算法 (a1，a2

4、，. ，ai-1，ai，ai+1，. ，an) (a1，a2，.，ai-1，x，ai，ai+1，.，an) 8順序表插入節(jié)點(diǎn)演示：9算法實(shí)現(xiàn)：SqList *Insert_SqList (SqList *L，int i，Elemtype x) / 在順序表L的第 i 個位置上插入一個值為 x 的新元素 if (iL-length+1) /檢查插入位置的正確性 printf (“插入位置i不合理！”); exit(1); /不合理，中止程序運(yùn)行 if (L-length = L-MaxSize-1) / 順序表是否已滿 printf (“順序表已滿，不能再插入！”); exit(1); / 表滿

5、,不能插入 for (m=L-length-1; m= i-1; -m) L-data m+1 = L-datam; / 結(jié)點(diǎn)后移 L-data i-1 = x; /新元素插入 L-length+; /表長+1 return L; /插入成功，返回 10算法分析： 時間復(fù)雜度： 時間主要耗費(fèi)在移動元素上, 移動元素個數(shù)與插入位置 i 有 問題規(guī)模：n=L.length最好：當(dāng) i=n+1, 結(jié)點(diǎn)后移語句不執(zhí)行，T(n)=O(1)最壞：當(dāng) i=1, 結(jié)點(diǎn)后移語句執(zhí)行n次，T(n)=O(n) 平均： T(n)=O(n) 11順序表刪除節(jié)點(diǎn)演示： 刪除運(yùn)算 (刪除表中第 i 個元素)12算法實(shí)現(xiàn)：S

6、qList *Delete_SqList(SqList *L, int i，Elemtype e) / 刪除順序表L中第 i 個元素，刪除元素的值保存在 e 中 if (iL-length) / 檢查刪除位置的正確性 printf (“插入位置i不合理！”); exit(1); /插入位置不合理，中止程序運(yùn)行 e = L-datai-1; /刪除ai之后，該數(shù)據(jù)就不存在，如果需要，先取出ai的值保存 for ( i; ilength-1; +i ) L-datai-1 = L-data i ; /結(jié)點(diǎn)前移 L-length = L-length-1; /表長-1 return L; /插入成功

7、，返回13算法分析： 時間復(fù)雜度：時間主要耗費(fèi)在移動元素上，移動元素個數(shù)與要刪除元素所在的位置有關(guān)問題規(guī)模：n=L.length最好：當(dāng)i=n, 結(jié)點(diǎn)前移語句不執(zhí)行，T(n)=O(1)最壞：當(dāng)i=1, 結(jié)點(diǎn)前移語句執(zhí)行n次，T(n)=O(n) 平均： T(n)=O(n) 14 存儲方式：用一組任意的存儲單元來存儲線性表中的結(jié)點(diǎn)。用指針實(shí)現(xiàn)線性表中各結(jié)點(diǎn)的邏輯關(guān)系。根據(jù)鏈接方式不同，分為：單鏈表、循環(huán)鏈表、雙向鏈表 根據(jù)鏈表實(shí)現(xiàn)不同，分為：靜態(tài)鏈表、動態(tài)鏈表2.3 線性表的鏈?zhǔn)酱鎯蛯?shí)現(xiàn)152.3.1 單鏈表 (Singly Linked List)1) 特點(diǎn)： 單鏈表中每個結(jié)點(diǎn)的結(jié)構(gòu)為： 單鏈

8、表的簡化示意圖為: (a1,a2,a3 ,a4) 頭指針 結(jié)點(diǎn)可以不連續(xù)存儲 表容易擴(kuò)充16 單鏈表的存儲映像172）帶表頭結(jié)點(diǎn)的單鏈表在實(shí)際應(yīng)用中，往往在第一個結(jié)點(diǎn)前附設(shè)一個表頭結(jié)點(diǎn)，該結(jié)點(diǎn)本身可不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實(shí)現(xiàn)。 非空表 空表 183）單鏈表的數(shù)據(jù)類型描述 typedef struct Lnode ElemType data; /數(shù)據(jù)域 Struct Lnode *next; /指針域Lnode;typedef LNode *LinkList; LinkList L; /定義單鏈表, 頭指針L 表中第一元素: (*L).n

9、ext L-next 第一個元素的值：L-next-data194）單鏈表基本操作的實(shí)現(xiàn) 建立單鏈表 分析 首先建立一個空表 從線性表尾元素開始，逐個建立結(jié)點(diǎn)，并將結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)后面。20建立單鏈表演示：21算法實(shí)現(xiàn) Linklist CreateList_L (int n) LinkList L; L= (LinkList) malloc(sizeof(Lnode); L-next=NULL; /建立一個空表 for( i=n; i0 ; -i ) p= (LinkList) malloc(sizeof(Lnode); /為新結(jié)點(diǎn)分配存儲單元 scanf(&P-data); /讀入要插入

10、元素值 p-next= L-next; L-next=p; /修改鏈接關(guān)系 return L; 算法分析：時間復(fù)雜度 T(n) =O(n)22插入操作前插入:在單鏈表的第 i 個結(jié)點(diǎn)前插入一個新元素x(插入前) (插入后)23單鏈表插入節(jié)點(diǎn)演示：24 算法實(shí)現(xiàn)：Linklist ListInsert (LinkList L, int i, Elemtype x ) /在帶頭結(jié)點(diǎn)單鏈表第 i 個結(jié)點(diǎn)前插入新元素x p=L; j=0; while ( p != NULL & ji-1 ) return Error; newnode= (LinkList ) malloc(sizeof(Lnode)

11、; /創(chuàng)建新結(jié)點(diǎn),其數(shù)據(jù)為x newnodedata=x; newnodenext = pnext; pnext = newnode; return (L); 算法分析：時間復(fù)雜度 T(n) =O(n)25刪除操作刪除: 刪除表中第i個元素在單鏈表中刪除第i個結(jié)點(diǎn)26單鏈表刪除節(jié)點(diǎn)演示：27 算法實(shí)現(xiàn)：Linklist ListDelete (LinkList L, int I,ElemType &e ) /在單鏈表中刪除第 i 個結(jié)點(diǎn) p =L; j = 0; while ( p next & ji-1) return Error; q=pnext; pnext=qnext; /重新鏈接 e

12、= qdata; free(q); /釋放q結(jié)點(diǎn) return(L); 算法分析：時間復(fù)雜度 T(n) =O(n)282.3.2 單向循環(huán)鏈表 1）存儲特點(diǎn)： 單向循環(huán)鏈表是單鏈表的變形。單向循環(huán)鏈表最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)使整個鏈表形成一個環(huán)。 形式一：帶頭指針的單向循環(huán)鏈表 29 形式二：帶尾指針的單向循環(huán)鏈表 終端結(jié)點(diǎn)：*rear 首元結(jié)點(diǎn)：rear-next-next302）單向循環(huán)鏈表的表示：同單鏈表 Typedef struct Lnode ElemType data; /數(shù)據(jù)域 Struct Lnode *next; /指針域 Lnode;3）基本運(yùn)算的實(shí)現(xiàn)： 建立單向循環(huán)

13、鏈表： 求表長： 查找： 插入： 刪除：略有不同，如何判斷到達(dá)表尾同單鏈表31 求表長： int Listlength_CL (LinkList L) j=0; p=L-next; while (p!= L） j+; p=p-next; return(j); 322.3.3 雙向鏈表 1）存儲特點(diǎn)： 每個結(jié)點(diǎn)有兩個指針域，其中一個指向直接后繼，一個指向直接前驅(qū)。 結(jié)點(diǎn)結(jié)構(gòu)： 形式一：雙向鏈表 形式二：雙向循環(huán)鏈表 332）雙向鏈表的表示typedef struct DuLnode ElemType data; /數(shù)據(jù)域 Struct DuLnode * prior, *next; /指針域Du

14、Lnode；typedef DuLnode *DuLinkList；p-next-prior = p-prior-next343）雙向鏈表基本操作的實(shí)現(xiàn) 建立雙向鏈表 求表長 查找 插入 刪除可以順一個方向進(jìn)行，算法同單向或單向循環(huán)鏈表35 插入(在第 i 個元素前插入元素 x )分析： 從表頭開始，查找定位到第 i 個元素，找到后，令指針 p 指向它 為待插入元素申請一結(jié)點(diǎn)空間 s,令 sdata= x 修改鏈接關(guān)系： s-prior = p-prior; p-prior-next=s; s-next=p; p-prior=s;36算法實(shí)現(xiàn)：DuLinkList ListInsert_Dul

15、(DuLinklist L,int i, Elemtype x) / 在雙向鏈表的第 i 個結(jié)點(diǎn)前插入一個新元素 x DuLinklist p, s; int j=0； p=L; while ( p != NULL & ji ) printf (參數(shù)i 錯); exit (1); /第 i 個結(jié)點(diǎn)不存在, 不能插入 if (! (s(DuLinklist)malloc(sizeof(DuLnode) /為新結(jié)點(diǎn)申請存儲空間 exit(1); /存儲分配失敗，中止程序運(yùn)行 s-datax; s-priorp-prior; p-prior-nexts; s-nextp; p-priors; ret

16、urn L; 37 刪除 (刪除第 i 個元素 )分析： 從表頭開始，查找定位到第 i 個元素，找到后，令指針 p 指向它 修改鏈接關(guān)系： p-prior-next=p-next; p-next-prior=p-prior； 釋放p所指結(jié)點(diǎn)空間： free(p)38算法實(shí)現(xiàn)：DuLinkList ListDelete_Dul (DuLinklist L, int i, ElemType &e) / 刪除雙向鏈表中第 i 數(shù)據(jù)元素 DuLinklist p; int j=0; p=L; while ( p != NULL & ji ) printf (參數(shù)i 錯); exit (1); /第i個

17、結(jié)點(diǎn)不存在, 不能刪除 e=p-data; /保存被刪除結(jié)點(diǎn)的值 p-prior-next p-next; p-next-prior p-prior; free (p); / 釋放結(jié)點(diǎn)空間 return L; 39 n 階多項式 Pn(x) 有n+1項。 系數(shù) a0, a1, a2, , an 指數(shù) 0, 1, 2, , n 按升冪排列 多項式2.4 一元多項式及其相加402）多項式的存儲表示第一種：順序存儲結(jié)構(gòu)這種存儲表示適用于指數(shù)連續(xù)排列的多項式。但對于指數(shù)不全的多項式如 P101(x) = 3 + 5x50 - 14x101采用此種存儲方式不經(jīng)濟(jì)。41在多項式的鏈表表示中，每個結(jié)點(diǎn)包括兩個數(shù)據(jù)域：系數(shù)項、指數(shù)項，一個指針域。優(yōu)點(diǎn)：多項式的項數(shù)可以動態(tài)地增長，不存在存儲溢出問題插入、刪除方便，不移動元素，多項式運(yùn)算方便。例如：AH = 1 - 10 x6 + 2x8 +7x14