c語言課程設(shè)計(jì)報(bào)告-數(shù)獨(dú)解謎程序

1、<p><b>　　課程設(shè)計(jì)</b></p><p><b>　　數(shù)獨(dú)解謎程序</b></p><p>　　2015年4月20日</p><p><b>　　目 錄</b></p><p><b>　　一、使用資料2</b></p&g

2、t;<p><b>　　二、設(shè)計(jì)內(nèi)容11</b></p><p>　　三、詳細(xì)設(shè)計(jì)說明12</p><p>　　四、軟件使用說明13</p><p>　　五、附錄：部分程序清單（帶有較詳細(xì)的注釋）19</p><p><b>　　使用資料</b></p><

3、p>　　C++中棧結(jié)構(gòu)建立與操作</p><p><b>　　什么是棧結(jié)構(gòu)</b></p><p>　　棧結(jié)構(gòu)是從數(shù)據(jù)的運(yùn)算來分類的，也就是說棧結(jié)構(gòu)具有特殊的運(yùn)算規(guī)則，即：后進(jìn)先出。</p><p>　　我們可以把棧理解成一個大倉庫，放在倉庫門口（棧頂）的貨物會優(yōu)先被取出，然后再取出里面的貨物。</p><p>　

4、　而從數(shù)據(jù)的邏輯結(jié)構(gòu)來看，棧結(jié)構(gòu)起始就是一種線性結(jié)構(gòu)。</p><p>　　如果從數(shù)據(jù)的存儲結(jié)構(gòu)來進(jìn)一步劃分，棧結(jié)構(gòu)包括兩類：順序棧結(jié)構(gòu)：</p><p>　　即使用一組地址連續(xù)的內(nèi)存單元依次保存棧中的數(shù)據(jù)。在程序中，可以定義一個指定大小的結(jié)構(gòu)數(shù)組來作為棧，序號為0的元素就是棧低，再定義一個變量top保存棧頂?shù)男蛱柤纯?。鏈?zhǔn)綏＝Y(jié)構(gòu)：</p><p>　　即使用鏈

5、表的的形式保存棧中各元素的值。鏈表首部（head指針?biāo)赶蛟兀闂ｍ?，鏈表尾部（指向地址為NULL）為棧底。</p><p>　　在棧結(jié)構(gòu)中只能在一端進(jìn)行操作，該操作端稱為棧頂，另一端稱為棧底。也就是說，保存和取出的數(shù)據(jù)都只能從棧結(jié)構(gòu)的一端進(jìn)行。從數(shù)據(jù)的運(yùn)算角度來分析，棧結(jié)構(gòu)是按照“后進(jìn)先出”的原則處理結(jié)點(diǎn)數(shù)據(jù)的。</p><p>　　在棧結(jié)構(gòu)中，只有棧頂元素是可以訪問的，棧結(jié)構(gòu)的數(shù)據(jù)運(yùn)

6、算也是非常簡單。一般棧結(jié)構(gòu)的基本操作只有兩個：</p><p>　　入棧（Push）：將數(shù)據(jù)保存到棧頂?shù)牟僮?。進(jìn)行入棧操作前，先修改棧頂指針，使其向上移一個元素位置，然后將數(shù)據(jù)保存到棧頂指針?biāo)傅奈恢谩?lt;/p><p>　　出棧（Pop）：將棧頂數(shù)據(jù)彈出的操作。通過修改棧頂指針，使其指向棧中的下一個元素。</p><p>　　接下來，我們使用C++語言建立順序棧，并

7、完成順序棧結(jié)構(gòu)的基本運(yùn)算</p><p><b>　　準(zhǔn)備數(shù)據(jù)</b></p><p>　　準(zhǔn)備在棧操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。</p><p>　　#define MAXLEN 50</p><p>　　struct DATA</p><p><b>　　{</b>&

8、lt;/p><p>　　string name;</p><p><b>　　int age;</b></p><p><b>　　};</b></p><p>　　struct StackType</p><p><b>　　{</b></p>

9、<p>　　DATA data[MAXLEN+1];</p><p><b>　　int top;</b></p><p><b>　　};</b></p><p>　　定義棧結(jié)構(gòu)的長度MAXLEN，棧結(jié)構(gòu)的數(shù)據(jù)元素類型DATA，以及棧結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)StackType。在數(shù)據(jù)結(jié)構(gòu)StackType中，data

10、為數(shù)據(jù)元素，top為棧頂?shù)男蛱?。?dāng)top=0時(shí)，表示棧為空，當(dāng)top=MAXLEN時(shí)表示棧滿。</p><p>　　數(shù)組元素都是充下標(biāo)0開始的，這里為了講述和理解方便，我們從下標(biāo)1開始記錄數(shù)據(jù)結(jié)點(diǎn)，下標(biāo)0的位置不用。初始化棧結(jié)構(gòu)</p><p>　　在使用棧結(jié)構(gòu)之前，首先需要創(chuàng)建一個空的順序棧，也就是初始化順序棧。順序棧的初始化操作如下：</p><p>　?。?

11、）按照符號常量MAXLEN指定大小申請一片內(nèi)存空間，用來保存棧中的數(shù)據(jù)</p><p>　?。?）設(shè)置棧頂指針的值為0，表示一個空棧。</p><p><b>　　示例代碼如下：</b></p><p>　　StackType *STInit()</p><p><b>　　{</b></p&

12、gt;<p>　　StackType *p;</p><p>　　if(p=new StackType)   //申請?？臻g </p><p><b>　　{</b></p><p>　　p->top=0;     //設(shè)置棧頂為0</p&

13、gt;<p>　　return p;     //返回棧頂指針 </p><p><b>　　} </b></p><p>　　return NULL; </p><p><b>　　}</b></p><p>　　

14、首先用new申請內(nèi)存，然后設(shè)置棧頂為0，然后返回申請內(nèi)存的首地址，申請失敗返回NULL;</p><p><b>　　判斷空棧</b></p><p>　　判斷棧結(jié)構(gòu)是否為空，如果是空棧，則表示該棧結(jié)構(gòu)中沒有數(shù)據(jù)，此時(shí)可以進(jìn)行入棧操作，但是不可以進(jìn)行出棧操作。</p><p><b>　　示例代碼如下：</b></p

15、><p>　　int STIsEmpty(StackType *s)</p><p><b>　　{</b></p><p><b>　　int t;</b></p><p>　　t=(s->top==0);     //通過棧頂?shù)闹颠M(jìn)行判斷<

16、;/p><p>　　return t; </p><p><b>　　}</b></p><p>　　輸入?yún)?shù)s為一個指向操作的棧的指針。根據(jù)棧頂指針top判斷是否為0，判斷棧是否為空。</p><p><b>　　判斷滿棧</b></p><p>　　判斷棧結(jié)構(gòu)是否為滿。如果是

17、滿棧，則表示該棧結(jié)構(gòu)中沒有多余的空間來保存額外數(shù)據(jù)。此時(shí)不可以進(jìn)行入棧操作，但是可以進(jìn)行進(jìn)棧操作。</p><p><b>　　示例代碼如下：</b></p><p>　　int STIsFull(StackType *s)</p><p><b>　　{</b></p><p><b>

18、　　int t;</b></p><p>　　t=(s->top==MAXLEN);</p><p>　　return t; </p><p><b>　　}</b></p><p>　　輸入?yún)?shù)s為一個指向操作的棧的指針。根據(jù)棧頂指針top判斷是否和MAXLEN相等，判斷棧是否已滿。</p>

19、;<p><b>　　清空棧</b></p><p>　　清空棧就是棧中所有的數(shù)據(jù)被清除。 示例代碼如下： </p><p>　　void STClear(StackType *s)</p><p><b>　　{</b></p><p><b>　　s->top=0;

20、</b></p><p><b>　　}</b></p><p>　　將棧頂指針top設(shè)置為0，表示執(zhí)行清空棧操作。（這里只是邏輯上將棧中數(shù)據(jù)清空，實(shí)際上只是將top設(shè)置為0，以后再添加數(shù)據(jù)會覆蓋原來的數(shù)據(jù)）</p><p><b>　　釋放空間</b></p><p>　　釋放空間是釋

21、放棧結(jié)構(gòu)所占用的內(nèi)存單元，使用delete釋放用new運(yùn)算符申請的內(nèi)存空間。</p><p><b>　　示例代碼如下：</b></p><p>　　void STFree(StackType *s)</p><p><b>　　{</b></p><p><b>　　delete s;&

22、lt;/b></p><p><b>　　}</b></p><p>　　在程序中直接調(diào)用delete運(yùn)算符釋放已分配的內(nèi)存空間。一般在不需要使用棧結(jié)構(gòu)時(shí)調(diào)用該函數(shù)，特別是在程序結(jié)束的時(shí)候。</p><p><b>　　入棧</b></p><p>　　入棧（Push）是棧結(jié)構(gòu)的基本操作，主要

23、操作是將數(shù)據(jù)元素保存到棧結(jié)構(gòu)。入棧操作的具體步驟如下：</p><p>　?。?）首先判斷棧頂top，如果top大于等于MAXLEN，則表示溢出，進(jìn)行出錯處理。否則執(zhí)行以下操作。</p><p>　?。?）設(shè)置top=top+1(棧頂指針加1，指向入棧地址)</p><p>　?。?）將入棧呀U尿素保存到top指向的位置。</p><p>&

24、lt;b>　　示例代碼如下:</b></p><p>　　int PushST(StackType *s,DATA data)</p><p><b>　　{</b></p><p>　　if((s->top+1)>MAXLEN)</p><p><b>　　{</b>

25、</p><p>　　cout<<"棧溢出"<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　s->data[++s->top]=data;  

26、;   //將元素壓入棧 </p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　輸入?yún)?shù)s為一個指向操作的棧的指針，輸入?yún)?shù)data是需要入棧的數(shù)據(jù)元素。程序首先判斷棧是否溢出，如果溢出就給出警告，不進(jìn)行入棧操作，否則修改棧頂指針

27、，即top先加1，然后將data放到top現(xiàn)在指向的數(shù)據(jù)單元。</p><p><b>　　出棧</b></p><p>　　出棧（Pop）是占據(jù)誒狗的基本操作，主要操作與入棧相反，它是從棧頂彈出一個數(shù)據(jù)元素，出棧操作的具體步驟如下：</p><p>　?。?）首先判斷棧頂top，如果top等于0，則表示為恐慌在哪，進(jìn)行出錯處理。否則執(zhí)行下面的

28、操作。</p><p>　　（2）將棧頂指針top所指向的位置的元素返回（實(shí)際是返回的指針）</p><p>　?。?）將top的減1，指向棧的下一個元素，原來?xiàng)ｍ數(shù)脑乇粡棾觥?lt;/p><p>　　DATA * PopST(StackType *s)</p><p><b>　　{</b></p><

29、;p>　　if(s->top==0)</p><p><b>　　{</b></p><p>　　cout<<"棧為空，不能再輸出！"<<endl;</p><p><b>　　exit(0);</b></p><p><b>　　}

30、</b></p><p>　　return &(s->data[s->top--]);</p><p><b>　　}</b></p><p>　　當(dāng)棧中有數(shù)據(jù)時(shí)，該函數(shù)返回值是一個指向DATA類型數(shù)據(jù)的指針。</p><p><b>　　讀取點(diǎn)結(jié)構(gòu)</b></

31、p><p>　　讀取點(diǎn)結(jié)構(gòu)也就是讀取棧結(jié)構(gòu)中結(jié)點(diǎn)的數(shù)據(jù)。由于棧結(jié)構(gòu)只能在一端進(jìn)行操作，因此這里的讀操作其實(shí)就是讀站點(diǎn)的數(shù)據(jù)。</p><p>　　需要注意的是，讀節(jié)點(diǎn)數(shù)據(jù)的操作和出棧操作不同。讀結(jié)點(diǎn)操作僅僅是顯示棧頂結(jié)點(diǎn)數(shù)據(jù)的內(nèi)容，而出棧操作則將棧頂數(shù)據(jù)彈出。</p><p><b>　　示例代碼如下：</b></p><p&g

32、t;　　DATA *PeekST(StackType *s)</p><p><b>　　{</b></p><p>　　if(s->top==0)</p><p><b>　　{</b></p><p>　　cout<<"棧已空"<<endl;&l

33、t;/p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　return &(s->data[s->top]);</p><p><b>　　}</b></p><p>　　對比出棧

34、的示例代碼，不難發(fā)現(xiàn)讀取點(diǎn)結(jié)構(gòu)同樣返回了棧頂結(jié)點(diǎn)的地址，但是卻沒有使top減1.</p><p>　　二、設(shè)計(jì)內(nèi)容 </p><p>　　開發(fā)一款“數(shù)獨(dú)”計(jì)算程序</p><p>　　規(guī)則：將數(shù)字1-9放置在每個小格里，使得每一行、沒一列、每一個3*3的方框里都沒有重復(fù)的數(shù)字即可。</p><p><b>　　要求：&l

35、t;/b></p><p>　　（1）、自行輸入數(shù)獨(dú)表格中數(shù)字</p><p>　?。?）、組成數(shù)獨(dú)網(wǎng)格</p><p>　?。?）、依次填入數(shù)字1-9檢查約束條件</p><p>　?。?）、輸出符合約束條件的結(jié)果</p><p><b>　　三、詳細(xì)設(shè)計(jì)說明</b></p>

36、<p><b>　　1.數(shù)獨(dú)小游戲說明</b></p><p>　　數(shù)獨(dú)游戲在9×9的方格內(nèi)進(jìn)行,分為3×3的小方格,被稱為“區(qū)”:區(qū)數(shù)獨(dú)游戲的目的是根據(jù)下列規(guī)則,用1至9之間的數(shù)字填滿空格,一個格子只能填入一個數(shù)字。每個數(shù)字在每一行只能出現(xiàn)一次。每個數(shù)字在每一列只能出現(xiàn)一次。每個數(shù)字在每一區(qū)只能出現(xiàn)一次</p><p><b&g

37、t;　　2.數(shù)獨(dú)程序流程圖</b></p><p><b>　　四、軟件使用說明</b></p><p>　　工具： vc++6.0；</p><p><b>　　輸入數(shù)據(jù) </b></p><p><b>　　運(yùn)行結(jié)果</b></p><p&g

38、t;　　五、附錄：部分程序清單（帶有較詳細(xì)的注釋）</p><p>　　#include<stdio.h>/*數(shù)字0表示該位置為空，待填入數(shù)字{0,0,4,6,0,2,0,9,1},{2,1,0,9,8,4,0,5,6},{9,0,0,0,7,1,4,2,0},{1,2,5,0,6,0,3,4,7},{4,7,6,0,0,0,9,8,5},{8,3,9,0,4,0,1,6,2},{0

39、,9,1,2,5,0,0,0,4},{5,8,0,4,1,6,0,3,9},{6,4,0,3,0,7,5,0,0}};*/int data[9][9] = {{0,7,0,2,6,0,9,0,0},{3,0,0,0,0,8,0,0,7}, {0,9,0,0,5,7,0,0,0}, {5,0,0,0,0,0,0,7,0}, {0,4,7,3,1,2,8,5,0}, {0,8,0,0,0,0,0,0,1}, {0,0