[課件]數(shù)據(jù)結(jié)構(gòu)第二章線性表.ppt

第二章 線性表,線性結(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è)后繼,2.1 線性表的類型定義（P18-19） 定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列,例 英文字母表（A,B,C,Z)是一個(gè)線性表,特征：（P19） 元素個(gè)數(shù)n表長(zhǎng)度，n=0空表 1in時(shí) ai的直接前驅(qū)是ai-1，a1無(wú)直接前驅(qū) ai的直接后繼是ai+1，an無(wú)直接后繼 i為數(shù)據(jù)元素ai在線性表中的位序,2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 順序表： 定義：用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表叫 元素地址計(jì)算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù) LOC(ai)線性表第i個(gè)元素的地址 LOC(a1)起始地址，基地址 特點(diǎn)： 實(shí)現(xiàn)邏輯上相鄰物理地址相鄰 實(shí)現(xiàn)隨機(jī)存取 實(shí)現(xiàn)：可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn),#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType * elem; int length; int listsize; SqList;,數(shù)據(jù)元素不是簡(jiǎn)單類型時(shí),可定義結(jié)構(gòu)體數(shù)組,動(dòng)態(tài)申請(qǐng)內(nèi)存 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);,插入 定義：線性表的插入是指在第i（1i n+1）個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素x，使長(zhǎng)度為n的線性表,變成長(zhǎng)度為n+1的線性表,需將第i至第n共（n-i+1)個(gè)元素后移,算法,Ch2_1.c,x,算法時(shí)間復(fù)雜度T(n) 設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：,刪除 定義：線性表的刪除是指將第i（1i n）個(gè)元素刪除，使長(zhǎng)度為n的線性表,變成長(zhǎng)度為n-1的線性表,需將第i+1至第n共（n-i)個(gè)元素前移,算法,Ch2_2.c,算法評(píng)價(jià) 設(shè)Qi是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：,故在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低,合并順序表 已知順序表La和Lb的順序按值非遞減排列，歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減排列 基本操作是“復(fù)制”，設(shè)2個(gè)指針i和j，分別指向2個(gè)表當(dāng)前處理的元素，當(dāng)i不大于j時(shí)復(fù)制i所指元素到Lc中，否則復(fù)制j所指元素到Lc中,Ch2_3.c,順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) 優(yōu)點(diǎn) 邏輯相鄰，物理相鄰 可隨機(jī)存取任一元素 存儲(chǔ)空間使用緊湊 缺點(diǎn) 插入、刪除操作需要移動(dòng)大量的元素 預(yù)先分配空間需按最大空間分配，利用不充分 表容量難以擴(kuò)充,2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 特點(diǎn)： 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素 利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素 每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息 結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲(chǔ)位置,例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,頭指針,實(shí)現(xiàn),typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList;,LNode *h,*p;,(*p)表示p所指向的結(jié)點(diǎn) (*p).datap-data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域 (*p).nextp-next表示p指向結(jié)點(diǎn)的指針域,生成一個(gè)新結(jié)點(diǎn)：p=(LinkList) malloc ( sizeof ( Lnode ); 系統(tǒng)回收p結(jié)點(diǎn)：free(p),線性鏈表 定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫，也叫單鏈表,頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空,單鏈表的基本運(yùn)算 查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL 算法描述,算法評(píng)價(jià),插入：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入x，已知p指向a,s-next=p-next;,p-next=s;,算法描述,算法評(píng)價(jià),Ch2_4.c,算法描述,算法評(píng)價(jià),刪除：?jiǎn)捂湵碇袆h除b，設(shè)p指向a,p-next=p-next-next;,Ch2_5.c,動(dòng)態(tài)建立單鏈表算法：設(shè)線性表n個(gè)元素已存放在數(shù)組a中，建立一個(gè)單鏈表，h為頭指針,算法描述,算法評(píng)價(jià),Ch2_6.c,單鏈表特點(diǎn) 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用 不需預(yù)先分配空間 指針占用額外存儲(chǔ)空間 不能隨機(jī)存取，查找速度慢,循環(huán)鏈表(circular linked list) 循環(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或p-next=h,雙向鏈表（double linked list） 單鏈表具有單向性的缺點(diǎn) 結(jié)點(diǎn)定義,typedef struct DuLNode ElemType tata; struct DuLNode *prior,*next; DuLNode ,*DuLinkList;,p-prior-next= p= p-next-proir;,刪除,算法描述,算法評(píng)價(jià)：T(n)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,Status ListDelete_Dul(DuLinkList return OK ,Status ListInsert_Dul(DuLinkList return OK ,算法描述,算法評(píng)價(jià)：T(n)=O(1),插入,2.4 線性表的應(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)可以用順序存儲(chǔ)結(jié)構(gòu)