數(shù)據(jù)的線性結(jié)構(gòu)ppt課件(編輯修改稿)
2025-05-27 18:14 本頁面
【文章內(nèi)容簡介】 返回? 單鏈表的兩種形式heada1 ^ana2heada1 a2 ^an帶頭結(jié)點(diǎn)的單鏈表不帶頭結(jié)點(diǎn)的單鏈表指針變量 head中存放了鏈表中第一個(gè)結(jié)點(diǎn)的起始地址，稱之為 頭指針 。該指針變量是 “靜態(tài) ”定義的，即用 NODE * head。定義了指針變量 head。鏈表中的結(jié)點(diǎn)是 “動態(tài) ”生成的 (稱之為結(jié)點(diǎn)變量 )，每個(gè)結(jié)點(diǎn)可以存放一個(gè)數(shù)據(jù)元素和后繼結(jié)點(diǎn)的起始地址。最后一個(gè)結(jié)點(diǎn)因?yàn)闆]有后繼結(jié)點(diǎn)，故其指針域中存放 NULL(空地址 )。 當(dāng)鏈表中沒有數(shù)據(jù)元素 (即空表 )時(shí)，第一種單鏈表保留頭結(jié)點(diǎn)。即 ，后一種 head中為 NULL。^head? 建立一個(gè)空表的算法為 (帶頭結(jié)點(diǎn) )： NODE *initlist_link （ ） { NODE *p。 p = (NODE *) malloc ( sizeof(NODE) )。 pnext = NULL。 return ( p )。 }兩個(gè)標(biāo)準(zhǔn)函數(shù) malloc 和 free 設(shè)有變量定義： NODE *p。則 p=(NODE *) malloc (sizeof(NODE))的作用是由系統(tǒng)生成（得到）一個(gè) NODE類型的結(jié)點(diǎn)，同時(shí)將該結(jié)點(diǎn)的起始地址賦給指針變量 p。 free(p)的作用是由于系統(tǒng)回收（釋放）一個(gè)由 p所指向的 NODE類型的結(jié)點(diǎn)。 注意點(diǎn)： ① 每次調(diào)用 malloc或 free函數(shù)只能得到或釋放一個(gè)結(jié)點(diǎn)空間；② 用 malloc函數(shù)得到的結(jié)點(diǎn)中無確定的內(nèi)容，必須由程序員給予；③ 用 free函數(shù)釋放一個(gè)結(jié)點(diǎn)空間，指針變量本身并未釋放。① 建立單鏈表a. 正向建： b. 逆向建：heada1 ^ana2^a1headp2 p1p2 p1an an1 ^a1headan2^a1headpp算法的詳細(xì)描述讀者可參見本教材實(shí)踐篇的實(shí)驗(yàn) 2 ② 單鏈表的插入操作 要求在帶頭結(jié)點(diǎn)的單鏈表中第 i個(gè)位置上插入一個(gè)值為 x的新元素。算法思想： 定義三個(gè)指針變量 p、 q和 s； (算法描述 )? 在單鏈表中尋找第 i個(gè)元素位置，若找到，則由 q指向第 i個(gè)位置， p指向第 i1個(gè)位置，繼續(xù) b)； 否則結(jié)束。? 向系統(tǒng)申請一個(gè)由 s指向的新結(jié)點(diǎn)，并在數(shù)據(jù)域置入新元素 x。? 將 s指向的新結(jié)點(diǎn)插入 q之前，結(jié)束。xp 第 i1個(gè)位置 q 第 i個(gè)位置sint ListInsert( NODE *L, int i, elemtype x ) { int j。 NODE *p, *q, *s。 p = L。 q = Lnext。 j = 1。 while( q!=NULL amp。amp。 ji ) /*尋找第 i個(gè)結(jié)點(diǎn)， p指向第 i1個(gè)結(jié)點(diǎn)， q指向第 i個(gè)結(jié)點(diǎn)*/ { p = q。 q = qnext。 ++j。 } if ( q==NULL || ji ) /*找不到插入點(diǎn) */ return (ERROR)。 s = (NODE*) malloc ( sizeof(NODE) )。 /*建立新結(jié)點(diǎn) */ sdata = x。 snext = q。 /* 插入新結(jié)點(diǎn) */ pnext = s。 return ( OK )。} 該算法的時(shí)間復(fù)雜度為 O(n)。 返回③ 單鏈表的刪除操作 要求在帶頭結(jié)點(diǎn)的單鏈表中刪除第 i個(gè)位置的元素。p q 第 i個(gè)位置算法思想： （ 算法描述 ） 定義兩個(gè)指針變量 p和 q。a) 在單鏈表中尋找第 i個(gè)元素位置，若找到則由 q指向第 i個(gè)位置， p指向第 i1個(gè)位置，繼續(xù) b)， 否則結(jié)束。b) 從鏈表中刪除 q所指向的結(jié)點(diǎn)。c) 釋放 q所指向的結(jié)點(diǎn)空間，結(jié)束。int ListDelete ( NODE *L, int i ){ int j。 NODE *p, *q。 p = L。 q = Lnext。 j = 1。 while ( q != NULL amp。amp。 j i ) /*尋找第 i個(gè)結(jié)點(diǎn) */ { p = q。 q = qnext。 ++j。 } if ( q==NULL || ji ) /*刪除位置不合理 */ return ( ERROR )。 pnext = qnext。 /*刪除 q所指向結(jié)點(diǎn) */ free ( q )。 return ( OK )。} 該算法的時(shí)間復(fù)雜度為 O(n)。 返回 單循環(huán)鏈表 單循環(huán)鏈表是一種特殊的 單鏈表 ，其最后一個(gè)結(jié)點(diǎn)的指針域中不存放 NULL(空地址 )，而是放入了鏈表的頭指針。① 帶頭結(jié)點(diǎn)的單循環(huán)鏈表② 不帶頭結(jié)點(diǎn)的單循環(huán)鏈表head a1 ana2a1 a2 anhead空表時(shí) head雙向鏈表? 結(jié)點(diǎn)結(jié)構(gòu)： 鏈表中每一個(gè)結(jié)點(diǎn)除數(shù)據(jù)域和指向后繼結(jié)點(diǎn)的指針域外，增加了一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針域。 用類 C語言描述為： typedef struct dlnode { datatype data。 struct dlnode *prior, *next。 }DLNODE。 雙向鏈表在做插入和刪除操作時(shí)，不需要再用兩個(gè)指針在鏈表上移動。后繼指針域數(shù)據(jù)域
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1