2.1-數(shù)據(jù)的邏輯結構ppt課件

1、 數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結構線性結構 非線性結構非線性結構 順序存儲順序存儲 鏈式存儲鏈式存儲 線性表線性表棧棧隊列隊列樹形結構樹形結構圖形結構圖形結構數(shù)據(jù)結構的三個方面：數(shù)據(jù)結構的三個方面： 散列存儲散列存儲索引存儲索引存儲串及數(shù)組串及數(shù)組Data_Structure = (D,S)2第2章 線性表n 了解線性表的特點及類型定義；n 掌握線性表的順序表示及實現(xiàn)，掌握線性表的鏈式表示及實現(xiàn)單鏈表、雙向鏈表和循環(huán)鏈表）；n 算法設計層次3）：熟練掌握兩種線性表表示的創(chuàng)建

2、、插入、刪除和查找等基本操作；鏈表合并與分解，有序表插入；（靈活應用，習題集2.33之前）n 了解一元多項式的表示和相加。第2章 線性表線性結構特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼n2.1 線性表的邏輯結構n定義：一個線性表是n個數(shù)據(jù)元素的有限序列niaaaa,21如例 英文字母表A,B,C,.Z)是一個線性表例學號姓名年齡001張三18002李四19數(shù)據(jù)元素元素文件n特征：n元素個數(shù)n表長度，n=0空表n1in時nai的直接前驅

3、是ai-1，a1無直接前驅nai的直接后繼是ai+1，an無直接后繼n元素同構，且不能出現(xiàn)缺項 類C描述建空表，求長度，定位，插入等基本操作利用基本操作實現(xiàn)復雜操作 如線性表合并P20 例21 線性表合并 union 算法2.1 ListLength，GetElem，LocateElem，ListInsert時間復雜度 for X LocateElem 即OListLength(Lb)xListLength(La)）P21 例22 有序表合并到第三個表 MergeList 算法2.2時間復雜度 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); / 求線性表的長度 Lb_len = ListLength(Lb); for (i=1; i=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i個數(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 線性表的順序存儲結構n順序表：n定義：用一組地址連續(xù)的存儲單元存放一個線性表叫n元素地址計算方法：nLOC(ai)=LOC(a1)+(i-1)*LnLOC(ai+1)=LOC(ai)+Ln其中：nL一個

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

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

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

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

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

12、elete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在順序線性表L中刪除第i個元素，并用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指向結點的數(shù)據(jù)域(*p).nextp-next表示p指向結點的指針域生成一個LNode型新結點：p=(LNode *

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

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

15、s = (LinkList)malloc(sizeof(LNode); / 生成新結點 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_Lpabxs 插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-next=p-next;p-next=s;P30 算法 2.9時間復雜度 T(n) = O(n)Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在帶頭結點的單鏈線性表L中，刪除第i個元素，并由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; / 刪除并釋放結點 e = q-data; free(q); return OK; / ListDelete_LP30 算法2.10pabc時間復雜度 T(n) = O(n)刪除：單鏈表中刪除b，設p指向ap-next=p-next-next;void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序輸入n個元素的值，建立帶表頭結點的單鏈線性表

17、L L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一個帶頭結點的單鏈表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新結點 scanf(&p-data); /輸入元素值 p-next = L-next; L-next = p; / 插入到表頭 / CreateList_Lh頭結點an 0h頭結點an-10an a2.h頭結點an-10an ha1a2頭結點an .0h頭結點0 nOnT 動態(tài)建立單鏈表算法：設線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h

18、為頭指針nCreateList_L P30 算法 2.11算法評價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的頭結點作為Lc的頭結點 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的頭結點 / MergeList_L算法2.2 的兩種實現(xiàn)：算法2.7 順序，算法2.12 鏈接單鏈表特點它是一種動態(tài)結構，整個存儲空間為多個鏈表共用不需預先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢靜態(tài)鏈表 無指針類型語言 BASIC大數(shù)組 用游標指示器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)鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環(huán)狀n特點：從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率n操作與單鏈表基本一致,循環(huán)條件不同n單鏈表p或p-next=NULLn循環(huán)鏈表p或p-next=Hhh空表尾指針 合并簡化 P35 圖2.13temp = B-next;B-next = A-next;A-next = temp-next;A = B;n雙向鏈表double linked list）n單鏈表具有單向性的缺點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算法評價：T(n)=O(n)p-prior-next=p-next;p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 刪除帶頭結點的雙鏈循環(huán)線性表L的第i

22、個元素，i的合法值為1i表長 if (!(p = GetElemP_DuL(L, i) / 在L中確定第i個元素的位置指針p return ERROR; / p=NULL, 即第i個元素不存在 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為帶頭結點的雙向鏈表的頭指針。 / 當?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERROR DuLinkLis

23、t p; p = L-next; int j = 1; / 初始化，p指向第一個結點，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) / 在帶頭結點的雙鏈循環(huán)線性表L的第i個元素之前插入元素e， / i的合法值為1i表長+1。 if (!(p = GetElemP_DuL(L,

24、 i) / 在L中確定第i個元素的位置指針p return ERROR; / p=NULL, 即第i個元素不存在 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 算法評價：T(n)=O(n)小結：帶頭結點的線性鏈表 取消參數(shù)i 位序算法改寫 算法2.20 2.21n2.4 線性表的應用舉例n 一元多項式的表示及相加n一元多項式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示200001000231)(xxxS但對S(x)這樣的多項式浪費空間一般emmnxPxPxPxPee2