1、第一次上機(jī)一、線性表逆置的順序?qū)崿F(xiàn)該問(wèn)題本身已經(jīng)是抽象數(shù)學(xué)模型，故不再進(jìn)行建模分析。reverse 函數(shù)：reverse 的實(shí)現(xiàn)思路是順序表首位對(duì)應(yīng)位置兩兩 element 的交換。循環(huán)的控制需要表長(zhǎng)作為依據(jù)，交換過(guò)程依靠賦值語(yǔ)句實(shí)現(xiàn)。程序調(diào)試中出現(xiàn)：兩兩交換的語(yǔ)句一開(kāi)始寫(xiě)錯(cuò)了。這是一個(gè)相當(dāng)基礎(chǔ)的語(yǔ)句，應(yīng)寫(xiě)為（若 a，b 值交換，;a=b;b=t;反應(yīng)自己 C 語(yǔ)言的基礎(chǔ)較差。還有就是循環(huán)的控制，在 n/2 時(shí)停止。時(shí)間代價(jià)分析：reverse 函數(shù)將順序表中所有元素逆置，對(duì)表的操作時(shí)間復(fù)雜度相當(dāng)于取出每個(gè)元素，為 O(n)。二、線性表逆置的實(shí)現(xiàn)由于沒(méi)有搞清楚有無(wú)頭結(jié)點(diǎn)的鏈表各種運(yùn)算實(shí)現(xiàn)之間的

2、差別，我此題花費(fèi)了大量時(shí)間。最終我設(shè)計(jì)的算法是利用無(wú)頭結(jié)點(diǎn)的鏈表實(shí)現(xiàn)的。同上，直接分析算法設(shè)計(jì)。在主函數(shù)通過(guò)尾插法實(shí)現(xiàn)鏈表初始化，重點(diǎn)在 reverse 算法的設(shè)計(jì)，還要設(shè)計(jì)鏈表輸出函數(shù)。reverse 算法：利用 pqt 三結(jié)點(diǎn)在鏈表上移動(dòng)修改前兩個(gè)結(jié)點(diǎn)的指向關(guān)系，關(guān)鍵在處理循環(huán)停止后的幾個(gè)剩余結(jié)點(diǎn)。實(shí)際上循環(huán)停止時(shí) t 是最后一個(gè)結(jié)點(diǎn)，此時(shí) p、q、t 之間指向關(guān)系都需要修改。此外，此時(shí)原來(lái)的第一個(gè)結(jié)點(diǎn)成為最后一個(gè)結(jié)點(diǎn)，需要將它指向 NULL。程序調(diào)試中：reverse 算法循環(huán)條件的確定 reverse 算法循環(huán)終止后的操作pr函數(shù)處理無(wú)頭結(jié)點(diǎn)的鏈表的輸出，其中第一個(gè)結(jié)點(diǎn)需要單獨(dú)處理1.

3、2.3.時(shí)間與空間代價(jià)分析：因?yàn)橹羔?pqt 需要在整個(gè)鏈表上滑動(dòng)，因此此算法時(shí)間復(fù)雜度為 O(n)三、有序表歸并的應(yīng)用：南北河流徑流量匯總1.問(wèn)題描述分析：分別給出中國(guó)北方、南方河流徑流量排序表個(gè)，需要匯總成一個(gè)總表。抽象為數(shù)學(xué)模型：有兩個(gè)遞減排序的順序表 A、B，將它們的元素按照遞減排序到表 C 中。特殊性在于，該順序表元素是一個(gè)結(jié)構(gòu)體，了 char *(河流名)和（徑流量）兩個(gè)元素。在比較元素大小時(shí)比較的是 amount 的數(shù)值大小。2.數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)：江河信息結(jié)點(diǎn)結(jié)構(gòu)： struct RiverNodechar *RiverName; amount;typedef struct R

4、iverNode *PRiverNode;順序表結(jié)構(gòu)體：struct SeqListn;struct RiverNode * element;/順序表內(nèi)容為河流結(jié)構(gòu)體指針;依次徑流量函數(shù)：傳入下標(biāo) i，輸出該河流信息結(jié)點(diǎn)PRiverNode retrieve_seq(PSeqList palist,i);函數(shù)：在 palist 表尾p 結(jié)點(diǎn)insertt_seq(PSeqList palist,n,PRiverNode p);輸出函數(shù)：按照“序號(hào)pr(PSeqList palist);徑流量”的格式輸出union 函數(shù)算法：通過(guò)兩表中元素依次比較較大的一個(gè)數(shù)，在一個(gè)表完畢后將另一個(gè)表剩余的部分

5、。3.調(diào)試中：此題關(guān)鍵于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，運(yùn)用結(jié)構(gòu)體指針做 element 后，知道頭指針和下標(biāo) i 即可通過(guò) palistelementi.amount 方式調(diào)用任意一個(gè)江河信息，這樣比較和retrieve 函數(shù)，則大大簡(jiǎn)化了算法。都不需調(diào)用問(wèn)題是開(kāi)始對(duì)于結(jié)構(gòu)體數(shù)組不熟悉，初始化和數(shù)值調(diào)用都比較復(fù)雜。不會(huì)使用下標(biāo)，就不斷用 for 循環(huán)使指針自加，過(guò)程中出了很多錯(cuò)誤。心得和體會(huì)這一次作業(yè)是我第一次自己編寫(xiě)較為復(fù)雜的程序，付出了大量的時(shí)間和精力，但可以說(shuō)當(dāng)完成的時(shí)候還是收獲很大的。1. 對(duì)于順序表、鏈表基本函數(shù)操作能熟練運(yùn)用了2. 對(duì)于順序表、鏈表的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)理解更深。順序表的序處理的時(shí)候也是比較方便的。更便捷，而鏈表運(yùn)用順對(duì)于函數(shù)參數(shù)和返回值的設(shè)計(jì)有了自己的體會(huì)。第一題的無(wú)頭結(jié)點(diǎn)鏈表逆置加深了我對(duì)頭結(jié)