線(xiàn)性表chap-資料下載頁(yè)
2025-09-25 19:42本頁(yè)面
【正文】 ink = p。 (3) prlinkllink = s。 (2) srlink = prlink。 (4) prlink = s。 (1) (2) (4) (3) A B C p s (1) (4) (3) (2) 應(yīng)用舉例 — Josephus問(wèn)題 n個(gè)人圍坐在一圓桌周?chē)?， 現(xiàn)從第 s個(gè)人開(kāi)始報(bào)數(shù) ， 數(shù)到第 m的人出列 ， 然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)， 數(shù)到第 m的人又出列 ， 如此反復(fù)直到所有的人全部出列為止 。 Josephus問(wèn)題是：對(duì)于任意給定的 n,s和 m， 求出按出列次序得到的 n個(gè)人員的序列 。 現(xiàn)以 n=8， s=1， m=4為例，問(wèn)題的求解過(guò)程如下列圖所示。圖中 s1指向開(kāi)始報(bào)數(shù)位置，帶圓圈的是本次應(yīng)出列人員。若初始順序?yàn)?n1， n2， n3， n4， n5， n6， n7， n8，則問(wèn)題的解為 n4， n8， n5， n2， n1， n3， n7， n6。 (c) n4 n8 n5 (d) n4 n8 n5 n2 (a) n4 (b) n4 n8 (e) n4 n8 n5 n2 n1 (f) n4 n8 n5 n2 n1 n3 (g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6 步驟 ： 1: 建立順序表 2: 出列 時(shí)間復(fù)雜度分析 ：出列元素的刪除（移動(dòng)實(shí)現(xiàn)）為基本運(yùn)算（每次最多 i1個(gè)元素移動(dòng)，需要 n1次） (n1)+(n2)+…… +1 = n(n1)/2 = O(n2) 順序表方式實(shí)現(xiàn) 循環(huán)鏈表方式實(shí)現(xiàn) 步驟： 1：建立帶頭結(jié)點(diǎn)的循環(huán)單鏈表 2：尋找第 s個(gè)結(jié)點(diǎn)，輸出并刪除第 m個(gè)節(jié)點(diǎn)。 時(shí)間復(fù)雜度分析 ：三部分時(shí)間（ 創(chuàng)建鏈表 ： O(n)+求第 s個(gè)結(jié)點(diǎn) ： O(s)+ 求 n個(gè)第 m個(gè)應(yīng)出列的元素 ： O(m*n)) 上機(jī)完成 “ 循環(huán)鏈表方式實(shí)現(xiàn) Josephus問(wèn)題 ” 典型應(yīng)用 ：一元多項(xiàng)式表達(dá)與實(shí)現(xiàn) 一元多項(xiàng)式 ： Pn(x)=p0+p1x+p2x2+… +pn xn 線(xiàn)性表表示 ： P=(p0, p1, p2, … , pn) 順序表表示 ： 只存系數(shù) （ 第 i個(gè)元素存 xi的系數(shù) ） 特殊問(wèn)題： p(x) = 1+2x10000+4x40000 浪費(fèi)空間 鏈表表示 ： 每個(gè)結(jié)點(diǎn)結(jié)構(gòu) 相加運(yùn)算 ： 相同指數(shù)對(duì)應(yīng)結(jié)點(diǎn)的系數(shù)項(xiàng)相加 ， 如和為 0， 刪除結(jié)點(diǎn) ， 否則必定為和鏈表的一個(gè)結(jié)點(diǎn) 。 （ 實(shí)質(zhì)上就是兩個(gè)單鏈表的合并問(wèn)題 ） 系數(shù) 指數(shù) 0 1 1 0 2 10000 4 40000 ^ 本章主要討論了線(xiàn)性表的概念 、 存儲(chǔ)表示以及基本運(yùn)算的實(shí)現(xiàn) ， 需要重點(diǎn)掌握 。 線(xiàn)性表是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu) ， 它是n個(gè)元素的有限序列 。 常用存儲(chǔ)方式： 順序 、 鏈接存儲(chǔ)結(jié)構(gòu) ； 順序存儲(chǔ)結(jié)構(gòu) 中 ， 物理位置相鄰表達(dá)邏輯關(guān)系相鄰；只存儲(chǔ)數(shù)據(jù)元素自身信息 ， 存儲(chǔ)密度大 、 空間利用率高；元素定位通過(guò)簡(jiǎn)單公式 ， 是隨機(jī)存取結(jié)構(gòu)；但數(shù)據(jù)元素的插入 、 刪除是通過(guò)大量的元素移動(dòng)完成 ， 時(shí)間效率低；必須事先估計(jì)最大元素?cái)?shù) 。 小結(jié) 鏈接存儲(chǔ)結(jié)構(gòu) 中 ， 結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)和釋放的；數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)附加指針表達(dá)；插入 、 刪除只需要修改指針即可 ， 不必移動(dòng)大量的數(shù)據(jù)元素；缺點(diǎn)是需要附加的指針 ， 存儲(chǔ)密度降低；元素的訪(fǎng)問(wèn)需要從頭結(jié)點(diǎn)開(kāi)始順鏈一個(gè)一個(gè)結(jié)點(diǎn)進(jìn)行 ， 是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 。 鏈表： 單鏈表 、 循環(huán)鏈表 、 雙向鏈表 、 靜態(tài)鏈表 （ 游標(biāo) ） 結(jié)合 Josephus問(wèn)題和一元多項(xiàng)式表達(dá)討論了順序表和鏈表的應(yīng)用 。 另外 ， 常用算法的時(shí)間復(fù)雜度分析也是需要掌握的 。 限制使用雙向鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)根據(jù)用戶(hù)輸入的一個(gè)整數(shù)（該整數(shù)表示精確到小數(shù)點(diǎn)后的位數(shù)，可能要求精確到小數(shù)點(diǎn)后 500位），高精度計(jì)算 ?值?？梢岳梅慈呛瘮?shù)冪級(jí)展開(kāi)式來(lái)進(jìn)行計(jì)算： ???????? ????????? ????? ????? ?? 12212753 )12())!1((2 )!12(7642 531542 3132 1a r c si n nn xnn nxxxxx當(dāng) x=1/2時(shí)， arcsinx=?/6 與是可以利用下面的關(guān)系式來(lái)求得 ?值。 122n, 21)12()2()12(R6 ???????? ?nmnn RnnnR 其中?作業(yè) 設(shè) A與 B分別為兩個(gè)帶有頭結(jié)點(diǎn)的有序循環(huán)鏈表 （ 所謂有序是指鏈接點(diǎn)按數(shù)據(jù)域值大小鏈接 ， 本題不妨設(shè)按數(shù)據(jù)域值從小到大排列 ） ， list1和 list2分別為指向兩個(gè)鏈表的指針 。 請(qǐng)寫(xiě)出將這兩個(gè)鏈表合并為一個(gè)帶頭結(jié)點(diǎn)的有序循環(huán)鏈表的算法 。 書(shū)面作業(yè)：書(shū) p48(1, 2, 3, 8, 9) 閉卷考試中的大部分題目將從練習(xí)題中選擇 。 思考 p49上機(jī)練習(xí) 1（ 第二次上機(jī)作業(yè) ）
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1