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