課程設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(精華版)

1/1課程設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(精華版)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

設(shè)計(jì)說(shuō)明書

N!非遞歸算法的設(shè)計(jì)與實(shí)現(xiàn)

同學(xué)成

學(xué)號(hào)1118064050

班級(jí)網(wǎng)絡(luò)1102班

成果

指導(dǎo)老師余冬梅

數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2023年1月5日

課程設(shè)計(jì)任務(wù)書

2023—2023學(xué)年第一學(xué)期

設(shè)計(jì)容：

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

通過(guò)本次的實(shí)踐，要求同學(xué)完成以下任務(wù)：

（一）闡述設(shè)計(jì)思想，畫出流程圖；

（二）說(shuō)明測(cè)試方法，寫出完整的運(yùn)行結(jié)果；

（三）從時(shí)間、空間對(duì)算法效率進(jìn)行分析；

（四）較好的界面設(shè)計(jì)；

（五）加強(qiáng)團(tuán)隊(duì)合作精神，開(kāi)拓創(chuàng)新力量；

（六）編寫課程設(shè)計(jì)報(bào)告，文檔資料完整規(guī)。

指導(dǎo)老師：余冬梅教研室負(fù)責(zé)人：余冬梅

課程設(shè)計(jì)評(píng)閱

名目

1課題描述(1)

2需求分析(1)

3概要設(shè)計(jì)(1)

4具體設(shè)計(jì)(2)

4.1定義存儲(chǔ)結(jié)構(gòu)和部分代碼(2)

4.2流程圖(3)

5程序編碼(4)

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

7結(jié)果分析(8)

8總結(jié)(8)

9設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)(8)

1課題描述

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

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

本次課程設(shè)計(jì)的目的是：通過(guò)本次課程設(shè)計(jì)，可以使大家了解緩存中數(shù)據(jù)的存儲(chǔ)圍，提高自學(xué)力量，增加團(tuán)隊(duì)合作意識(shí)。

2需求分析

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

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

限制條件：

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

2.n的圍；

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

3概要設(shè)計(jì)

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

遞推采納的是遞歸和歸并法，而非遞推只采納遞歸法。遞推法一般簡(jiǎn)單溢出，所以一般都采納遞推法分析，而用非遞推法設(shè)計(jì)程序。

本次試驗(yàn)分為兩個(gè)步驟：

(1).實(shí)現(xiàn)階乘的模塊m(n):從2開(kāi)頭連乘到n，實(shí)現(xiàn)求n的階乘，相對(duì)簡(jiǎn)潔，簡(jiǎn)單計(jì)算。

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

4具體設(shè)計(jì)

4.1定義存儲(chǔ)結(jié)構(gòu)和部分代碼

#include

//結(jié)構(gòu)體列表

structNode

{

intdata;

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

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

};

//非遞歸算法計(jì)算階乘

for(i=2;idata)+jinwei;

cur->data=temp%10;//取個(gè)位存下來(lái),如91*2=182,取2存儲(chǔ)

jinwei=temp/10;//十位和百位作為進(jìn)位,192中取18為進(jìn)位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存儲(chǔ)下來(lái)

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作為進(jìn)位

}

}

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("****計(jì)算階乘****\n\n");

while(1)

{

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

head->data=1;

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

printf("Pleaseinputanumber:");

mark=scanf("%d",

if(ndata)+jinwei;

cur->data=temp%10;//取個(gè)位存下來(lái),如91*2=182,取2存儲(chǔ)

jinwei=temp/10;//十位和百位作為進(jìn)位,192中取18為進(jìn)位

if(cur->next==NULL)

break;

cur=cur->next;

}

while(jinwei!=0)

{

cc=newNode;

cc->data=jinwei%10;//18中取8存儲(chǔ)下來(lái)

cc->pre=cur;

cc->next=NULL;

cur->next=cc;

cur=cc;

jinwei/=10;//18中取1作為進(jìn)位

}

}

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)試與測(cè)試

(1)n=0：

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

圖6.2-5的階乘

(3)n=1024：

圖6.31024的階乘

7結(jié)果分析

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

輸入負(fù)數(shù)，系統(tǒng)會(huì)提示“輸入錯(cuò)誤，請(qǐng)重新輸入：”；

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

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

算法的時(shí)間簡(jiǎn)單度為：

O（n）=n*length*length;

算法的空間簡(jiǎn)單度為:

O（n）=length;

8總結(jié)

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

9設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)

在做本次課程設(shè)計(jì)的時(shí)候，自己也相繼遇到了許多問(wèn)題，許多自己的不足之處也暴露了出來(lái)，比如：剛開(kāi)頭自己寫的代碼只能算到