課前視頻學(xué)習(xí)任務(wù)1.4.4線性表的鏈?zhǔn)酱鎯?chǔ)-雙向鏈表應(yīng)用舉例（時(shí)長(zhǎng)：10分26秒）1.5棧和隊(duì)列（時(shí)長(zhǎng)：7分50秒）課前視頻學(xué)習(xí)任務(wù)課前視頻學(xué)習(xí)任務(wù)樣例代碼回顧（10分鐘）樣例程序回顧Ex1.4-雙鏈表表示無(wú)符號(hào)大數(shù)的加法實(shí)現(xiàn)參考代碼：UBigNumber.h、UBigNumber.c、test.c/p/2V4ZHDmK96//p/V9b9Sp7SRS//p/fvbKwjbwx6/課堂提問(wèn)（10分鐘）課堂提問(wèn)問(wèn)題1：無(wú)符號(hào)大數(shù)為什么需要使用雙鏈表存儲(chǔ)結(jié)構(gòu)而不是單鏈表存儲(chǔ)結(jié)構(gòu)？單鏈表適合從鏈?zhǔn)捉Y(jié)點(diǎn)往鏈尾結(jié)點(diǎn)方向的單向處理;遇到同時(shí)需要反方向處理應(yīng)用時(shí)，可以采用雙向鏈表存儲(chǔ)結(jié)構(gòu)。無(wú)符號(hào)大數(shù)從高位到低位的各位數(shù)字組成了線性表，用線性表知識(shí)可解決無(wú)符號(hào)大數(shù)的表示和操作。無(wú)符號(hào)大數(shù)位數(shù)不確定，可以采用鏈表表示。無(wú)符號(hào)大數(shù)顯示時(shí)需要從高位到低位次序進(jìn)行，運(yùn)算時(shí)又需要從低位到高位運(yùn)算，因此，無(wú)符號(hào)大數(shù)可以采用雙向鏈表存儲(chǔ)結(jié)構(gòu)。課堂提問(wèn)問(wèn)題2：無(wú)符號(hào)大數(shù)樣例Ex1.4中如何避免內(nèi)存泄漏？參考：樣例中采取了函數(shù)內(nèi)建立鏈表-無(wú)符號(hào)大數(shù)，將鏈表返回函數(shù)調(diào)用者，由函數(shù)調(diào)用者來(lái)通過(guò)銷毀鏈表操作釋放鏈表資源的策略，避免內(nèi)存泄漏。課堂提問(wèn)問(wèn)題3：樣例Ex1.4中為何需要無(wú)符號(hào)大數(shù)規(guī)范化表示的_Normalize函數(shù)？參考：無(wú)符號(hào)大數(shù)采用規(guī)范化表示，利用_Normalize函數(shù)去除高位多余0，同時(shí)保證至少含一位數(shù)，這樣，任何無(wú)符號(hào)大數(shù)只有一種唯一表示方式，有利于無(wú)符號(hào)大數(shù)的比較、顯示等處理，符合程序設(shè)計(jì)中模塊化處理原則，也有利于在無(wú)符號(hào)大數(shù)基礎(chǔ)上進(jìn)一步拓展有符號(hào)大數(shù)、超高精度實(shí)數(shù)等應(yīng)用。課堂提問(wèn)問(wèn)題4：用鏈表實(shí)現(xiàn)棧時(shí)，應(yīng)該使用單鏈表還是雙鏈表？鏈?zhǔn)捉Y(jié)點(diǎn)表示棧頂還是棧底元素？這個(gè)鏈表是否需要頭結(jié)點(diǎn)？11課堂提問(wèn)因?yàn)闂５幕静僮魃婕暗亩际菃畏较蛱幚礞湵恚虼?，為了?jié)省存儲(chǔ)空間、簡(jiǎn)化處理，應(yīng)該使用單鏈表而不是雙鏈表實(shí)現(xiàn)棧；鏈?zhǔn)捉Y(jié)點(diǎn)表示棧頂元素，這樣，入棧、出棧運(yùn)算時(shí)間復(fù)雜度均為O（1）；入棧、出棧操作都發(fā)生在棧頂，因此，在棧中單鏈表無(wú)需頭結(jié)點(diǎn)。課堂提問(wèn)問(wèn)題5：隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)時(shí)如何保證入隊(duì)列、出隊(duì)列運(yùn)算時(shí)間復(fù)雜度均為O（1）？如果隊(duì)列順序存儲(chǔ)時(shí)只設(shè)置隊(duì)首、隊(duì)尾位置下標(biāo)，如何區(qū)分隊(duì)滿、隊(duì)空？課堂提問(wèn)15圖1.11循環(huán)隊(duì)列示意圖課堂提問(wèn)隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，為避免大量元素移動(dòng)，保證入隊(duì)列、出隊(duì)列運(yùn)算時(shí)間復(fù)雜度均為O（1），將數(shù)組視為首、尾相接，循環(huán)使用，因此，也稱為循環(huán)隊(duì)列。循環(huán)隊(duì)列中，為區(qū)分隊(duì)列空和隊(duì)列滿兩種狀態(tài)，可以將只有一個(gè)空余單元時(shí)狀態(tài)視為隊(duì)滿狀態(tài)，因此，隊(duì)首、隊(duì)尾位置相同時(shí)視為隊(duì)空；隊(duì)尾的后一個(gè)位置為隊(duì)首時(shí)視為隊(duì)滿。C++標(biāo)準(zhǔn)模板庫(kù)（STL）提供了類和隊(duì)列的類模板。循環(huán)隊(duì)列的入隊(duì)列操作算法描述如下：//將元素x入pQueue所指隊(duì)列，成功返回1，失敗返回0boolEnQueue(structSeqQueue*pQueue,DataElemx){if((pQueue->iRear+1)%MaxSIZE==pQueue->iFront)return0;//下一位置已是隊(duì)首位置，隊(duì)滿pQueue->iDatasA[pQueue->iRear]=x;//保存元素pQueue->iRear=(pQueue->iRear+1)%MaxSIZE;//調(diào)整隊(duì)尾位置return1;}17課堂提問(wèn)問(wèn)題6：思考什么場(chǎng)景會(huì)使用棧，什么場(chǎng)景會(huì)使用隊(duì)列？參考：遞歸——棧，多線程處理——隊(duì)列課堂測(cè)試（5分鐘）作業(yè)解題思路15分鐘習(xí)題6：又見(jiàn)約瑟夫環(huán)：有M個(gè)人圍坐成一圈，編號(hào)依次從1開(kāi)始遞增直到M，現(xiàn)從編號(hào)為1的人開(kāi)始報(bào)數(shù)，報(bào)到N的人出列，然后再?gòu)南乱蝗碎_(kāi)始重新報(bào)數(shù)，報(bào)到N的人出列；重復(fù)這一過(guò)程，直至所有人出列。所有出列的人再次按出列順序圍坐成一圈，并從第1人開(kāi)始報(bào)數(shù)，這次為報(bào)到K的人出隊(duì)列，然后再?gòu)南乱蝗碎_(kāi)始重新報(bào)數(shù)，報(bào)到K的人出列；重復(fù)這一過(guò)程，直至所有人出列。求最后出列次序。題目輸入包括M、N、K三個(gè)正整數(shù)；N、K可能為1。題目要求按最后出隊(duì)列順序輸出他們的編號(hào)，每個(gè)測(cè)試用例結(jié)果占一行，每個(gè)編號(hào)占4位。如樣例輸入1035；程序應(yīng)該輸出：74161053289。解題思路：體現(xiàn)模塊化程序設(shè)計(jì)，用循環(huán)單鏈表代表人員組成的圈，也就是圓形隊(duì)列，指針指向循環(huán)單鏈表尾部結(jié)點(diǎn)，設(shè)計(jì)實(shí)現(xiàn)Append函數(shù)，實(shí)現(xiàn)在循環(huán)單鏈表尾部添加代表指定元素的一個(gè)結(jié)點(diǎn)，返回新循環(huán)單鏈表的尾結(jié)點(diǎn)指針。在主程序中先建立兩個(gè)空循環(huán)單鏈表，先循環(huán)M次調(diào)用AppendTail建立初始圓形隊(duì)列，在第5題基礎(chǔ)上，再通過(guò)調(diào)用AppendTail函數(shù)將游戲過(guò)程中出圓形隊(duì)列的人加入新圓形隊(duì)列尾部，循環(huán)進(jìn)行，直到原圓形隊(duì)列為空；然后，對(duì)新圓形隊(duì)列進(jìn)行同樣的操作，出圓形隊(duì)列的人組建起新圓形隊(duì)列；最后，調(diào)用顯示函數(shù)，顯示結(jié)果圓形隊(duì)列中所有人員，銷毀單鏈表即可實(shí)現(xiàn)。習(xí)題7：好玩的約瑟夫環(huán)：有M個(gè)人，編號(hào)分別為1到M，玩約瑟夫環(huán)游戲，最初時(shí)按編號(hào)順序排成隊(duì)列；每遍游戲開(kāi)始時(shí)，有一個(gè)正整數(shù)報(bào)數(shù)密碼N，隊(duì)列中人依次圍坐成一圈，從隊(duì)首的人開(kāi)始報(bào)數(shù)，報(bào)到N的人出列，然后再?gòu)某隽械南乱蝗碎_(kāi)始重新報(bào)數(shù)，報(bào)到N的人出列；重復(fù)這一過(guò)程，直至所有人出列，完成一遍游戲，所有出列的人形成新隊(duì)列；游戲可能玩很多遍，每遍有新報(bào)數(shù)密碼。求若干遍游戲完成后隊(duì)列次序。題目輸入包括若干個(gè)正整數(shù)（至少1個(gè)）,第一個(gè)正整數(shù)為玩游戲人數(shù)M，后續(xù)每個(gè)正整數(shù)為每遍游戲報(bào)數(shù)密碼，報(bào)數(shù)密碼可能為1，題目要求按出隊(duì)列順序輸出他們的編號(hào)。樣例輸入：10352；樣例輸出：46529137810。解題思路：在第6題基礎(chǔ)上，用循環(huán)單鏈表代表人員組成的圈，也就是圓形隊(duì)列，指針指向循環(huán)單鏈表尾部結(jié)點(diǎn)，先建立一個(gè)非空的循環(huán)隊(duì)列，每輪游戲時(shí)，從非空循環(huán)隊(duì)列出隊(duì)列的人員在出隊(duì)列后組成一個(gè)新循環(huán)隊(duì)列；循環(huán)進(jìn)行，最后留下的非空循環(huán)隊(duì)列就是結(jié)果隊(duì)列；最后，調(diào)用顯示函數(shù)，顯示結(jié)果圓形隊(duì)列中所有人員，銷毀循環(huán)單鏈表即可實(shí)現(xiàn)。習(xí)題8：無(wú)符號(hào)大數(shù)加、減運(yùn)算。程序設(shè)計(jì)中經(jīng)常遇到無(wú)符號(hào)大數(shù)加、減運(yùn)算問(wèn)題，請(qǐng)?jiān)跇永绦駿x1.4基礎(chǔ)上實(shí)現(xiàn)無(wú)符號(hào)大數(shù)減運(yùn)算。題目要求輸入兩個(gè)無(wú)符號(hào)大數(shù)，保證一個(gè)大數(shù)不小于第二個(gè)大數(shù)，輸出它們的和、差。樣例輸入1234567890987654321333888999666147655765659657669789687967867樣例輸出13822236566473119911235769675331086912125327996651544201031799。解題思路：在無(wú)符號(hào)大數(shù)相加樣例基礎(chǔ)上，實(shí)現(xiàn)兩個(gè)無(wú)符號(hào)大數(shù)相減運(yùn)算函數(shù)，類似兩個(gè)無(wú)符號(hào)大數(shù)相加算法，設(shè)一個(gè)借位變量iCarry，初值為0，從兩個(gè)雙向鏈表尾部結(jié)點(diǎn)開(kāi)始，兩相應(yīng)位、借位相減形成結(jié)果中新的高位，不夠減時(shí)再向高位借位；從低位到高位，循環(huán)進(jìn)行，直到減數(shù)處理完畢；如果被減數(shù)還有未處理位，同樣需要考慮借位因素后，將結(jié)果位保留在結(jié)果數(shù)高位，最后，進(jìn)行規(guī)整化處理形成最終結(jié)果雙鏈表。在主函數(shù)里，通過(guò)調(diào)用相應(yīng)函數(shù)實(shí)現(xiàn)功能即可。習(xí)題9：

有符號(hào)大數(shù)加、減運(yùn)算。請(qǐng)?jiān)跇永绦駿x1.4基礎(chǔ)上實(shí)現(xiàn)無(wú)符號(hào)大數(shù)比較運(yùn)算（小于、小于等于、等于、大于、大于等于），并進(jìn)一步實(shí)現(xiàn)有符號(hào)大數(shù)的加、減運(yùn)算。題目要求輸入兩個(gè)有符號(hào)大數(shù)，輸出它們的和、差。樣例輸入-1234567890987654321333888999666147655765659657669789687967867樣例輸出-1086912125327996651544201031799-1382223656647311991123576967533解題思路：在樣題和第8題基礎(chǔ)上，繼續(xù)實(shí)現(xiàn)無(wú)符號(hào)大數(shù)比較函數(shù)，再建立新結(jié)構(gòu)體BigNumber，用來(lái)表示有符號(hào)大數(shù)，包含兩個(gè)采用：用于表示絕對(duì)值的UBigNumber類型value成員和用于表示符號(hào)位的整型sign成員；然后，分別設(shè)計(jì)算法實(shí)現(xiàn)兩個(gè)有符號(hào)大數(shù)相加、相減。兩個(gè)有符號(hào)大數(shù)相加時(shí)，如果符號(hào)位相同，結(jié)果有符號(hào)大數(shù)符號(hào)也一樣，絕對(duì)值部分為兩個(gè)絕對(duì)值相加；兩個(gè)有符號(hào)大數(shù)符號(hào)位不同時(shí)，比較兩個(gè)數(shù)的絕對(duì)值，結(jié)果數(shù)的絕對(duì)值為原先兩數(shù)中大絕對(duì)值減小絕對(duì)值，符號(hào)位與原先大的有符號(hào)數(shù)相同；兩個(gè)有符號(hào)大數(shù)相減，相當(dāng)于加上改變符號(hào)后的減數(shù)，就可以實(shí)現(xiàn)。在主函數(shù)里，通過(guò)分析輸入字符串，得到有符號(hào)大數(shù)的符號(hào)位和絕對(duì)值，建立有符號(hào)大數(shù)，調(diào)用相應(yīng)加、減函數(shù)實(shí)現(xiàn)運(yùn)算，再調(diào)用顯示函數(shù)顯示有符號(hào)大數(shù)，最后，注意銷毀有關(guān)有符號(hào)大數(shù)，釋放鏈表。習(xí)題10：編寫(xiě)程序分別采用順序存儲(chǔ)結(jié)構(gòu)和