課程設計：數(shù)據(jù)結構課程設計(精華版)

1/1課程設計：數(shù)據(jù)結構課程設計(精華版)

數(shù)據(jù)結構課程設計

設計說明書

N!非遞歸算法的設計與實現(xiàn)

同學成

學號1118064050

班級網(wǎng)絡1102班

成果

指導老師余冬梅

數(shù)學與計算機科學學院2023年1月5日

課程設計任務書

2023—2023學年第一學期

設計容：

本次課程設計的任務是N!非遞歸算法的設計與實現(xiàn)，在設計過程中應留意n值大小與數(shù)據(jù)類型表數(shù)圍之間的關系，并盡可能求出較大n值的階乘。

通過本次的實踐，要求同學完成以下任務：

（一）闡述設計思想，畫出流程圖；

（二）說明測試方法，寫出完整的運行結果；

（三）從時間、空間對算法效率進行分析；

（四）較好的界面設計；

（五）加強團隊合作精神，開拓創(chuàng)新力量；

（六）編寫課程設計報告，文檔資料完整規(guī)。

指導老師：余冬梅教研室負責人：余冬梅

課程設計評閱

名目

1課題描述(1)

2需求分析(1)

3概要設計(1)

4具體設計(2)

4.1定義存儲結構和部分代碼(2)

4.2流程圖(3)

5程序編碼(4)

6程序調(diào)試與測試(6)

7結果分析(8)

8總結(8)

9設計體會及今后的改進意見(8)

1課題描述

盡管遞歸算法是一種自然且合乎規(guī)律的解決問題的方式，但遞歸算法的執(zhí)行效率通常比較差。因此在求解很多問題時常采納遞歸算法來分析問題，用非遞歸方法來求解問題，另外一些程序不支持遞歸算法來求解問題，所以我們都會用非遞歸算法來求解問題。

本次課程設計主要容是：用非遞歸算法實現(xiàn)n!的計算，由于計算機中數(shù)據(jù)的存儲圍有限，而又要求出盡可能大的n的階乘的值，用鏈表構造n的運算結果的存儲結構，用鏈式存儲方式，最終輸出n!的運算結果。

本次課程設計的目的是：通過本次課程設計，可以使大家了解緩存中數(shù)據(jù)的存儲圍，提高自學力量，增加團隊合作意識。

2需求分析

在本次n!非遞歸算法的課程設計中主要用到的學問有：鏈表、函數(shù)，選擇條件中的結構語句（ifelse），和循環(huán)結構語句中的語句while語句、do…while語句和for語句，選擇語句if的運用。

對n!的非遞歸的算法，主要是運用非遞歸的算法實現(xiàn)n的階乘。

限制條件：

1.要求的n必需是整數(shù)；

2.n的圍；

3.數(shù)據(jù)類型和表數(shù)圍。

3概要設計

遞歸和非遞歸算法是相通的，遞歸是一種直接或間接調(diào)用自身的算法，而非遞歸不調(diào)用自身函數(shù)。

遞推采納的是遞歸和歸并法，而非遞推只采納遞歸法。遞推法一般簡單溢出，所以一般都采納遞推法分析，而用非遞推法設計程序。

本次試驗分為兩個步驟：

(1).實現(xiàn)階乘的模塊m(n):從2開頭連乘到n，實現(xiàn)求n的階乘，相對簡潔，簡單計算。

(2).當n較大時，假如用int型結果就會溢出，所以實現(xiàn)階乘需要特別處理:從較小值開頭，進行數(shù)值分解，比如將182分解為18和2，2存儲在鏈表數(shù)據(jù)域的其次個位置（第一個位置是1，表示0的階乘是1），然后將18作為進位，假如進位不為0，則連續(xù)分解。最終會以1,8,2的形式存儲在鏈表當中，這樣就不存在存的溢出。最終通過遍歷的方法，遍歷到最高位，及1，然后依次輸出后續(xù)的數(shù)字，便是階乘的結果。

4具體設計

4.1定義存儲結構和部分代碼

#include

//結構體列表

structNode

{

intdata;

Node*next;//指向大數(shù)的高位

Node*pre;//指向大數(shù)的低位

};

//非遞歸算法計算階乘

for(i=2;idata)+jinwei;

cur->data=temp%10;//取個位存下來,如91*2=182,取2存儲

jinwei=temp/10;//十位和百位作為進位,192中取18為進位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存儲下來

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作為進位

}

}

4.2流程圖

圖4.1主函數(shù)流程圖

5程序編碼

#include

structNode

{

intdata;

Node*next;//指向大數(shù)的高位

Node*pre;//指向大數(shù)的低位

};

voidmain

{

intn,temp,i,jinwei,mark;

Node*head,*cc,*cur;

charch;

printf("****計算階乘****\n\n");

while(1)

{

head=newNode;//存放第一個節(jié)點,值為1

head->data=1;

head->pre=head->next=NULL;

printf("Pleaseinputanumber:");

mark=scanf("%d",

if(ndata)+jinwei;

cur->data=temp%10;//取個位存下來,如91*2=182,取2存儲

jinwei=temp/10;//十位和百位作為進位,192中取18為進位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存儲下來

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作為進位

}

}

cur=head,i=0;

while(cur->next)

cur=cur->next;//遍歷到最高位

printf("%d!=",n);

while(cur)//從最高位到最低位打印

{

cc=cur;

printf("%d",cur->data);

cur=cur->pre;

deletecc;

}

printf("\n\n是否連續(xù)?(Y/N)\n");

getchar;

ch=getchar;

if(ch!='Y'

}

}

6程序調(diào)試與測試

(1)n=0：

圖6.10的階乘(2)n=-5：

圖6.2-5的階乘

(3)n=1024：

圖6.31024的階乘

7結果分析

在執(zhí)行函數(shù)的過程中，對上述提到的各種狀況做了推斷和提示，如：

輸入負數(shù)，系統(tǒng)會提示“輸入錯誤，請重新輸入：”；

輸入小數(shù)，系統(tǒng)會提示“輸入錯誤，請重新輸入：”。

本次設計的函數(shù)，能求出較大整數(shù)的階乘，能實現(xiàn)循環(huán)運算和退出功能。

算法的時間簡單度為：

O（n）=n*length*length;

算法的空間簡單度為:

O（n）=length;

8總結

在這次通信原理課設之后，靜下心來仔細總結，發(fā)覺收獲許多主要有三個方面：首先在這次課設中，我和小組其他成員經(jīng)受了很多歡樂與心酸，我和大家在一起爭論問題，有時候大家會愁眉不展，有時由于得到了隊員供應的一個好建議或者一個好的想法而興奮的去仿真調(diào)試，最主要的是我體會到了團隊協(xié)作的歡樂與好處，我和組員相互學習，共同進步。其次體會最深的就是自己實踐的力量還有待提高，平常的學習只是理論的，教育式的，有一點與實際不符，在這次課設過程中，我從最基本入手，建模規(guī)劃，調(diào)試，問題處理，我在實踐中一點點的提高，整個過程結束，我對設計過程有了基本的熟悉，對自己的努力方向也有了更加深刻的熟悉。最終就是自己心態(tài)的一個轉變，從前對于集體的工作總是拖拖拉拉，在原地踏步而不愿去實行行動，經(jīng)過這次課程設計，雖然做的題目很簡潔，但我熟悉到樂觀行動與合作的重要性，沒有什么天上掉餡餅的事，只要自己努力去做了，就會有相應的成效。

9設計體會及今后的改進意見

在做本次課程設計的時候，自己也相繼遇到了許多問題，許多自己的不足之處也暴露了出來，比如：剛開頭自己寫的代碼只能算到