2.1-數(shù)據(jù)的邏輯結(jié)構(gòu)ppt課件

1、 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)列隊(duì)列樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 散列存儲(chǔ)散列存儲(chǔ)索引存儲(chǔ)索引存儲(chǔ)串及數(shù)組串及數(shù)組Data_Structure = (D,S)2第2章 線性表n 了解線性表的特點(diǎn)及類型定義；n 掌握線性表的順序表示及實(shí)現(xiàn)，掌握線性表的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)單鏈表、雙向鏈表和循環(huán)鏈表）；n 算法設(shè)計(jì)層次3）：熟練掌握兩種線性表表示的創(chuàng)建

2、、插入、刪除和查找等基本操作；鏈表合并與分解，有序表插入；（靈活應(yīng)用，習(xí)題集2.33之前）n 了解一元多項(xiàng)式的表示和相加。第2章 線性表線性結(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ù)元素均只有一個(gè)后繼n2.1 線性表的邏輯結(jié)構(gòu)n定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表A,B,C,.Z)是一個(gè)線性表例學(xué)號(hào)姓名年齡001張三18002李四19數(shù)據(jù)元素元素文件n特征：n元素個(gè)數(shù)n表長(zhǎng)度，n=0空表n1in時(shí)nai的直接前驅(qū)

3、是ai-1，a1無(wú)直接前驅(qū)nai的直接后繼是ai+1，an無(wú)直接后繼n元素同構(gòu)，且不能出現(xiàn)缺項(xiàng) 類C描述建空表，求長(zhǎng)度，定位，插入等基本操作利用基本操作實(shí)現(xiàn)復(fù)雜操作 如線性表合并P20 例21 線性表合并 union 算法2.1 ListLength，GetElem，LocateElem，ListInsert時(shí)間復(fù)雜度 for X LocateElem 即OListLength(Lb)xListLength(La)）P21 例22 有序表合并到第三個(gè)表 MergeList 算法2.2時(shí)間復(fù)雜度 O（ ListLength(Lb)+ListLength(La) ）抽象數(shù)據(jù)類型線性表的定義P196

4、void Union(List &La, List Lb) / 算法2.1 / 將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中 int La_len,Lb_len,i; ElemType e; La_len = ListLength(La); / 求線性表的長(zhǎng)度 Lb_len = ListLength(Lb); for (i=1; i=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i個(gè)數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal) / La中不存在和e相同的數(shù)據(jù)元素 ListInsert(La, +La_len, e); / 插

5、入 / union7void MergeList(List La, List Lb, List &Lc) / 算法2.2 / 已知線性表La和Lb中的元素按值非遞減排列。 / 歸并La和Lb得到新的線性表Lc，Lc的元素也按值非遞減排列。 InitList(Lc); i=j=1; k=0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) / La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) ListIn

6、sert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i = La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j = Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / MergeListn2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)n順序表：n定義：用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表叫n元素地址計(jì)算方法：nLOC(ai)=LOC(a1)+(i-1)*LnLOC(ai+1)=LOC(ai)+Ln其中：nL一個(gè)

7、元素占用的存儲(chǔ)單元個(gè)數(shù)nLOC(ai)線性表第i個(gè)元素的地址nP22 圖2.2n特點(diǎn)：n實(shí)現(xiàn)邏輯上相鄰物理地址相鄰n實(shí)現(xiàn)隨機(jī)存取n實(shí)現(xiàn)：可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號(hào)M-1類C描述 定義結(jié)構(gòu)體類型SqList#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; /存儲(chǔ)空間基址int length; /當(dāng)前長(zhǎng)度int listsize; /當(dāng)前分配的存儲(chǔ)容量SqListP23 例 算法2.3 初始化操作Status InitList_Sq(SqLi

8、st &L) / 構(gòu)造一個(gè)空的線性表L。 L.elem = (ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) return OK; / 存儲(chǔ)分配失敗 L.length = 0; / 空表長(zhǎng)度為0 L.listsize = LIST_INIT_SIZE; /初始存儲(chǔ)容量 return OK; / InitList_Sq 空閑n插入n定義：線性表的插入是指在第i1i n+1個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素x，使長(zhǎng)度為n的線性表niiaaaaa,1,21 變成長(zhǎng)度為n+1的線性表niiaaxaaa,1,21 需將第i至

9、第n共n-i+1)個(gè)元素后移P24 算法2.411/ 算法2.4Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序線性表L的第i個(gè)元素之前插入新的元素e， / i的合法值為1iListLength_Sq(L)+1 if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 當(dāng)前存儲(chǔ)空間已滿，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*size

10、of (ElemType); if (!newbase) return ERROR; / 存儲(chǔ)分配失敗 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲(chǔ)容量 ElemType *q = &(L.elemi-1); / q為插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表長(zhǎng)增1 return OK; / ListInsert_Sq內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)

11、n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1x算法時(shí)間復(fù)雜度T(n)設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認(rèn)為n刪除n定義：線性表的刪除是指將第i1i n個(gè)元素刪除，使長(zhǎng)度為n的線性表niiaaaaa,1,21 變成長(zhǎng)度為n-1的線性表niiaaaaa,11,21 需將第i+1至第n共n-i)個(gè)元素前移P24 算法2.515Status ListD

12、elete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在順序線性表L中刪除第i個(gè)元素，并用e返回其值。 / i的合法值為1iListLength_Sq(L)。 if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p為被刪除元素的位置 e = *p; / 被刪除元素的值賦給e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; pdata表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp-next表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(LNode *

13、)malloc(sizeof(LNode);系統(tǒng)回收p結(jié)點(diǎn)：free(p)n線性鏈表n定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫，也叫單鏈表ha1a2頭結(jié)點(diǎn)an .h空表頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空單鏈表的基本運(yùn)算取元素：GetElem_LP29 算法 2.8時(shí)間復(fù)雜度 T(n) = O(n)Status GetElem_L(LinkList &L,int i, ElemType &e) / 算法2.8 / L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。 / 當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERROR p = L-next; j = 1; / 初始化，p指

14、向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器 while (p & jnext; +j; if ( !p | ji ) return ERROR; / 第i個(gè)元素不存在 e = p-data; / 取第i個(gè)元素 return OK; / GetElem_L24Status ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個(gè)元素之前插入元素e p = L; j = 0; while (p & j next; +j; / 尋找第i-1個(gè)結(jié)點(diǎn) if (!p | j i-1) return ERROR; / i小于1或者大于表長(zhǎng)

15、s = (LinkList)malloc(sizeof(LNode); / 生成新結(jié)點(diǎn) s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_Lpabxs 插入：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向as-next=p-next;p-next=s;P30 算法 2.9時(shí)間復(fù)雜度 T(n) = O(n)Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值 p = L; j = 0;

16、while (p-next & j next; +j; if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理 q = p-next; p-next = q-next; / 刪除并釋放結(jié)點(diǎn) e = q-data; free(q); return OK; / ListDelete_LP30 算法2.10pabc時(shí)間復(fù)雜度 T(n) = O(n)刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向ap-next=p-next-next;void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表

17、L L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新結(jié)點(diǎn) scanf(&p-data); /輸入元素值 p-next = L-next; L-next = p; / 插入到表頭 / CreateList_Lh頭結(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)0 nOnT 動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h

18、為頭指針nCreateList_L P30 算法 2.11算法評(píng)價(jià)27合并有序鏈表MergeList_L P31 算法 2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 已知單鏈線性表La和Lb的元素按值非遞減排列。 / 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。 pa = La-next; pb = Lb-next; Lc = pc = La; / 用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) while (pa & pb) if (pa-data data) pc-next = pa; pc = pa

19、; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段 free(Lb); / 釋放Lb的頭結(jié)點(diǎn) / MergeList_L算法2.2 的兩種實(shí)現(xiàn)：算法2.7 順序，算法2.12 鏈接單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用不需預(yù)先分配空間指針占用額外存儲(chǔ)空間不能隨機(jī)存取，查找速度慢靜態(tài)鏈表 無(wú)指針類型語(yǔ)言 BASIC大數(shù)組 用游標(biāo)指示器cur代替指針P32 圖2.10備用鏈表：未使用的分量數(shù)組元素）P33 例2-3 (A-B)U(B-A)算法2.14-2.

20、17圖2.11 數(shù)組靜態(tài)鏈表1 備用鏈表 0n循環(huán)鏈表(circular linked list)n循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀n特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率n操作與單鏈表基本一致,循環(huán)條件不同n單鏈表p或p-next=NULLn循環(huán)鏈表p或p-next=Hhh空表尾指針 合并簡(jiǎn)化 P35 圖2.13temp = B-next;B-next = A-next;A-next = temp-next;A = B;n雙向鏈表double linked list）n單鏈表具有單向性的缺點(diǎn)n結(jié)點(diǎn)定義typedef struct DulNode

21、ElemType data; struct DulNode *prior,*next;DulNode, *DulLinkList;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表： LABbcapp-prior-next= p= p-next-proir;bcaP刪除P37 算法2.19 ListDelete_DuL算法評(píng)價(jià)：T(n)=O(n)p-prior-next=p-next;p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i

22、個(gè)元素，i的合法值為1i表長(zhǎng) if (!(p = GetElemP_DuL(L, i) / 在L中確定第i個(gè)元素的位置指針p return ERROR; / p=NULL, 即第i個(gè)元素不存在 e = p-data; p-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; / ListDelete_DuL32DuLinkList GetElemP_DuL(DuLinkList L, int i) / L為帶頭結(jié)點(diǎn)的雙向鏈表的頭指針。 / 當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERROR DuLinkLis

23、t p; p = L-next; int j = 1; / 初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器 while (p!=L & jnext; +j; if (p=L | jprior = p-prior; 2. p-prior-next = s; 3. s-next = p; 4. p-prior = s;xSbaP插入34P36 算法2.18Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) / 在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素之前插入元素e， / i的合法值為1i表長(zhǎng)+1。 if (!(p = GetElemP_DuL(L,

24、 i) / 在L中確定第i個(gè)元素的位置指針p return ERROR; / p=NULL, 即第i個(gè)元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode) return ERROR; s-data = e; s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; return OK; / ListInsert_DuL 算法評(píng)價(jià)：T(n)=O(n)小結(jié)：帶頭結(jié)點(diǎn)的線性鏈表 取消參數(shù)i 位序算法改寫(xiě) 算法2.20 2.21n2.4 線性表的應(yīng)用舉例n 一元多項(xiàng)式的表示及相加n一元多項(xiàng)式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示200001000231)(xxxS但對(duì)S(x)這樣的多項(xiàng)式浪費(fèi)空間一般emmnxPxPxPxPee2