[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第04次課線性表b-閱讀頁(yè)
2024-11-03 00:02本頁(yè)面
【正文】 free(Lb)。 //插入剩余段 while(paamp。pb) //將 pa 、 pb結(jié)點(diǎn)按大小依次插入 C中 { if(padata=pbdata) {pcnext=pa。 pa=panext。 pc=pb。 pb=Lbnext。只要定義一個(gè)結(jié)構(gòu)類型（含 數(shù)據(jù)域 和 指示域 ）數(shù)組，就可以完全描述鏈表，這種鏈表稱為 靜態(tài)鏈表 。 討論 1： 用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？ 靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器 就可以了。 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 27頁(yè) 討論 2： 鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？ 答：能。) 。 討論 3： 單鏈表只能查找結(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？ 答： 能 。) 。 prior data next 這種有兩個(gè)指針的鏈表稱為 雙向鏈表 。參見(jiàn)教材 P36－ 38。 ? 特點(diǎn) ： 從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率 ? 操作與單鏈表基本一致 ,循環(huán)條件不同 – 單鏈表 p或 plink=NULL – 循環(huán)鏈表 p或 plink=H h h 空表 ? 循環(huán)鏈表 (circular linked list) 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 29頁(yè) – 雙向鏈表 （ double linked list） 單鏈表具有單向性的缺點(diǎn) typedef struct node { datatype element。 }JD。 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 30頁(yè) b c a P void del_dulist(JD *p) {ppriornext=pnext。 free(p)。 pnextprior=pprior。 s=(JD*)malloc(sizeof(JD))。 sprior=pprior。 snext=p。 } – 算法描述 – 算法評(píng)價(jià)： T(n)=O(1) x S b a P ? 插入 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 32頁(yè) 5. 鏈表的運(yùn)算效率分析 1. 查找 因線性鏈表 不能順序存取 ，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。 但是，如果要在單鏈表中進(jìn)行 前插 或 刪除 操作， 由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為 O(n)。 在 n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *P，需找到它的 ，其時(shí)間復(fù)雜度為 。簡(jiǎn)言之 ， 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一 （ 1:1）的 。 鏈?zhǔn)酱鎯?chǔ) 時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。缺點(diǎn)是插入或刪除元素效率低。缺點(diǎn)是存儲(chǔ)密度?。?1），存儲(chǔ)空間利用率低。 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 36頁(yè) 應(yīng)用舉例 1. 一元多項(xiàng)式的數(shù)學(xué)通式？ 2. 用 C語(yǔ)言如何描述它的定義？ 3. 如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？ 一元多項(xiàng)式的計(jì)算 (參見(jiàn)嚴(yán)教材 P46 – 55) 討論： 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 37頁(yè) 1. 一元多項(xiàng)式的數(shù)學(xué)通式？ 一元多項(xiàng)式的通式可表示為： 20 1 2( ) . . . nnnP x p p x p x p x? ? ? ? ?0 1 2( , , , ... )nP p p p p?20 1 2( ) . . . mmmQ x q q x q x q x? ? ? ? ?0 1 2( , , , ... )mQ q q q q?( ) ( ) ( )n n mR x P x Q x??0 0 1 1 1( , , ... , , , ... , )m m m nR p q p q p q p p?? ? ? ?假定 mn 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 38頁(yè) 分析： 一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用 順序表 存儲(chǔ)，又可用 鏈表 存儲(chǔ)。 typedef struct poly_node { int coef。 //exponent指數(shù) poly_pointer link。 poly_pointer a, b, c。 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 41頁(yè) 實(shí)現(xiàn)思路： 依次比較 Pa和 Pb所指結(jié)點(diǎn)中的指數(shù)項(xiàng) ， 依 Paexpon == Pbexpon等情況 ， 再?zèng)Q定是將兩系數(shù)域的數(shù)值相加 （ 并判其和是否為 0） ，還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表 c中
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1