實(shí)現(xiàn)兩個(gè)鏈表的合并數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(已修改)
2025-06-21 17:36 本頁面
【正文】 1 一、 課程設(shè)計(jì)題目： 實(shí)現(xiàn)兩個(gè)鏈表的合并 二、 基本功能要求： 1. 建立兩個(gè)鏈表 A 和 B，鏈表元 素 個(gè)數(shù)分別為 m和 n個(gè)。 2. 假設(shè)元 素 分別為 (x1,x2,?xm) ，和 (y1,y2, ?yn) 。把它們合并成一個(gè)線 性 表 C，使得： 當(dāng) m=n 時(shí)， C=x1,y1,x2,y2,?xn,yn,?,xm 當(dāng) nm 時(shí)， C=y1,x1,y2,x2,?ym,xm,?,yn 3. 輸出線 性 表 C： 用直接插入排序法對(duì) C進(jìn)行升序排序，生成鏈表 D，并輸出鏈表 D。 三、 測(cè)試數(shù)據(jù)： 1. A 表（ 30， 41， 15， 12， 56， 80） B 表（ 23， 56， 78， 23， 12， 33， 79， 90， 55） 2. A 表（ 30， 41， 15， 12， 56， 80， 23， 12， 34） B 表（ 23， 56， 78， 23， 12） 四、 理論分析結(jié)果： 1. A 表的數(shù)據(jù)元素個(gè)數(shù) m=6， B表的數(shù)據(jù)元素個(gè)數(shù) n=9，此時(shí) mn 分析合并結(jié)果：當(dāng) mn時(shí)，應(yīng)該先插入 B表中的數(shù)據(jù)元素，在偶數(shù)位插入 B 表中的數(shù)據(jù)元素，在奇數(shù)位插入 A表中的數(shù)據(jù)元素，最后插入 B 表中剩 余的數(shù)據(jù)元素。 C=23， 30， 56， 41， 78， 15， 23， 12， 12， 56， 33， 80， 79， 90， 55 排序結(jié)果： D=12， 12， 15， 23， 23， 30， 33， 41， 55， 56， 56， 78， 79， 80， 90 2. A 表的數(shù)據(jù)元素個(gè)數(shù) m=9， B表的數(shù)據(jù)元素個(gè)數(shù) n=5，此時(shí) mn 分析合并結(jié)果：當(dāng) m=n 時(shí)，應(yīng)該先插入 A 表中的數(shù)據(jù)元素，在偶數(shù)位插入 A 表中的數(shù)據(jù)元素，在奇數(shù)位插入 B 表中的數(shù)據(jù)元素，最后插入 A表中剩余的數(shù)據(jù)元素。 C=30， 23， 41， 56， 15， 78， 12， 23， 56， 12， 80， 23， 12， 34 排序結(jié)果： D=12， 12， 12， 15， 23， 23， 23， 30， 34， 41， 56， 56， 78， 80 2 五、 設(shè)計(jì)步驟： 分析問題，給出數(shù)學(xué)模型，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)： 1) 分析問題特點(diǎn)，用數(shù)學(xué)表達(dá)式或其它形式描述其數(shù)學(xué)模型。 2) 選擇能夠體現(xiàn)問題本身特點(diǎn)的一種或幾種邏輯結(jié)構(gòu)。 3) 依據(jù)邏輯結(jié)構(gòu)和問題特點(diǎn)，設(shè)計(jì)并選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)應(yīng)的算法實(shí)現(xiàn)有區(qū)別）。 算法設(shè)計(jì) ： 1) 確定所需模塊：對(duì)于復(fù)雜的程序設(shè)計(jì)，要充分利用模塊化程序設(shè)計(jì)方法和面向?qū)ο笏枷?，自頂向下，逐步?xì)化。 2) 各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼 表示。 3) 模塊之間的調(diào)用關(guān)系：給出算法各模塊之間的關(guān)系圖示。 上機(jī)實(shí)現(xiàn)程序： 為提高工作效率，充分利用上機(jī)調(diào)試時(shí)間，在上機(jī)之前應(yīng)列出程序清單。 有代表性的各種測(cè)試數(shù)據(jù)去驗(yàn)證算法及程序的正確性： 根據(jù)課程設(shè)計(jì)的要求對(duì)給定的數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證算法以及程序的正確性。 算法分析及優(yōu)化： 經(jīng)過上機(jī)調(diào)試，源程序運(yùn)行正確，并且實(shí)現(xiàn)算法要求的功能，解決課程設(shè)計(jì)題目中給出的問題后，分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如有可能對(duì)程序進(jìn)行優(yōu)化改進(jìn)。 六、 模塊劃分： ： 主要包括單鏈表的存儲(chǔ)結(jié)構(gòu)、初始化、求數(shù)據(jù)元素個(gè)數(shù)、插入、刪除數(shù)據(jù)元素、取數(shù)據(jù)元素、撤消單鏈表的函數(shù)。 2. 單鏈表操作頭文件： 主要包括單鏈表測(cè)試、單鏈表合并、單鏈表合并排序函數(shù)。 ： 主要包括文件包含、數(shù)據(jù)導(dǎo)入和操作模塊程序。 3 七、 算法設(shè)計(jì)： 帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)結(jié)構(gòu) typedef struct Node { D
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1