數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---車廂調(diào)度

1、<p>　　課 程 設(shè) 計(jì)</p><p><b>　?。〝?shù)據(jù)結(jié)構(gòu)）</b></p><p><b>　　二○一一年一月十日</b></p><p>　　課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定</p><p>　　Ⅰ、題目的目的和要求： </p><p>　　鞏固和加深對(duì)數(shù)

2、據(jù)結(jié)構(gòu)的理解，通過(guò)上機(jī)實(shí)驗(yàn)、調(diào)試程序，加深對(duì)課本知識(shí)的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)寫程序。</p><p>　?。?）通過(guò)本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。</p><p>　?。?）能針對(duì)給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計(jì)算法，進(jìn)而給出問(wèn)題的正確求解過(guò)程并編寫代碼實(shí)現(xiàn)。</p><p>　　Ⅱ、設(shè)計(jì)進(jìn)度及完成情況</p&

3、gt;<p>　　Ⅲ、主要參考文獻(xiàn)及資料</p><p>　　[1] 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）清華大學(xué)出版社 1999</p><p>　　[2] 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）清華大學(xué)出版社 1999</p><p>　　[3] 譚浩強(qiáng) C語(yǔ)言程序設(shè)計(jì) 清華大學(xué)出版社</p><p>　　[4] 與所用編程環(huán)境相配套

4、的C語(yǔ)言或C++相關(guān)的資料</p><p><b>　　Ⅳ、成績(jī)?cè)u(píng)定：</b></p><p>　　設(shè)計(jì)成績(jī)： （教師填寫）</p><p>　　指導(dǎo)老師： （簽字）</p><p>　　二○一一 年 一 月 十 日</p><

5、p><b>　　目 錄</b></p><p>　　第一章 概述……………………………………………………………1</p><p>　　第二章 系統(tǒng)分析………………………………………………………2</p><p>　　第三章 概要設(shè)計(jì)………………………………………………………</p><p>　　第四章 詳細(xì)設(shè)計(jì)…

6、……………………………………………………</p><p>　　第五章 運(yùn)行與測(cè)試……………………………………………………</p><p>　　第六章 總結(jié)與心得……………………………………………………</p><p>　　參考文獻(xiàn)………………………………………………………………</p><p><b>　　第一章 概述</b&

7、gt;</p><p>　　課程設(shè)計(jì)是實(shí)踐性教學(xué)中的一個(gè)重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個(gè)方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計(jì)是讓同學(xué)們對(duì)所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識(shí)?！稊?shù)據(jù)結(jié)構(gòu)》是一門重要的專業(yè)基礎(chǔ)課，是計(jì)算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)

8、用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。</p><p>　　在這次的課程設(shè)計(jì)中我選擇的題目是車廂調(diào)度。首先在教科書(shū)3.1.2節(jié)中提供的棧的順序存儲(chǔ)結(jié)構(gòu)SqStack之上實(shí)現(xiàn)棧的基本操作，即實(shí)現(xiàn)棧的類型。程序?qū)５娜魏未嫒。锤?，讀取和狀態(tài)判別等操作）必須借助于基本操作進(jìn)行。一般的說(shuō)，在操作過(guò)程的任何狀態(tài)下都有兩種

9、可能的操作：“入”和“出”。每個(gè)狀態(tài)下處理問(wèn)題的發(fā)發(fā)是相同的，這說(shuō)明問(wèn)題本身具有天然的遞歸性，可以參考用遞歸的算法實(shí)現(xiàn)。輸入序列可以僅由一對(duì)整型變量表示，即給出序列頭/尾編號(hào)。輸出序列用棧實(shí)現(xiàn)是方便的，只要再定義一個(gè)棧打印操作print（s），自低至頂順序地印出棧元素的值。</p><p>　　本部分主要說(shuō)明：課程設(shè)計(jì)的目的意義；對(duì)自己題目的問(wèn)題描述；以上為樣例，特別是字體，字號(hào)，行間距等均參照樣例，以下同。&l

10、t;/p><p><b>　　第二章 系統(tǒng)分析</b></p><p><b>　　1.問(wèn)題分析：</b></p><p>　　可假設(shè)對(duì)二叉樹(shù)的n個(gè)結(jié)點(diǎn)從1到n編號(hào)，且令其先序序列為1，2，……，n，則不同的二叉樹(shù)所得到的中序序列不同。這樣，不同形態(tài)的二叉樹(shù)的數(shù)目正好是先序序列均為1，2，……，n的二叉樹(shù)所能得到的中序序列的數(shù)

11、目，而中序遍歷的過(guò)程實(shí)際上是一個(gè)結(jié)點(diǎn)進(jìn)棧和出棧的過(guò)程。因此，序列1，2，……，n按不同順序進(jìn)棧和出棧所能得到的排列的數(shù)目正好是由先序序列為1，2，……，n所能得到的中序序列的數(shù)目，也就是先序序列為1，2，……，n的不同形態(tài)的二叉樹(shù)的數(shù)目，其數(shù)目為 ：</p><p>　　1 （2n）！</p><p>　　Cn== ------ * -------

12、-</p><p>　　n+1 n！*n！</p><p><b>　　2.設(shè)計(jì)內(nèi)容：</b></p><p>　　現(xiàn)有n節(jié)車廂，按不同的順序進(jìn)棧和出棧，計(jì)算出所有的出棧序列并輸出。</p><p>　　例如：有4節(jié)車廂則輸出：</p><p>　　4 3 2 1</p&

13、gt;<p>　　2 3 4 1</p><p><b>　　3 4 2</b></p><p>　　3 4 2 1</p><p>　　2 3 1 4</p><p>　　1 3 2 4</p><p>　　3 2 1 4</p>&

14、lt;p>　　2 1 4 3</p><p>　　1 2 4 3</p><p>　　3 2 1 4</p><p>　　2 1 3 4</p><p>　　1 2 3 4</p><p>　　2 4 3 1</p><p>　　1 4 3 2&l

15、t;/p><p>　　本部主要說(shuō)明題目的基本要求，注意對(duì)題目的基本要求進(jìn)行詳細(xì)分析，盡量細(xì)化到程序中每個(gè)函數(shù)實(shí)現(xiàn)的功能都能在此處說(shuō)明。</p><p><b>　　第三章 概要設(shè)計(jì)</b></p><p>　　1．設(shè)定棧的抽象數(shù)據(jù)類型定義：</p><p>　　ADT Stack {</p><p>

16、　　數(shù)據(jù)對(duì)象：D={∈CharSet,i=1,2,...,n,,n≥0}</p><p>　　數(shù)據(jù)關(guān)系：R1={<∈D,i=2,...,n}</p><p><b>　　基本操作：</b></p><p>　　InitStack(&S)</p><p>　　操作結(jié)果：構(gòu)造一個(gè)空棧S。</p>

17、<p>　　DestroyStack(&S)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：銷毀棧S。</p><p>　　ClearStack(&S)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：將棧S清為空棧。</p>

18、<p>　　StackLength(S)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：返回棧S的長(zhǎng)度。</p><p>　　StackEmpty(S)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：若S為空棧，則返回TURE，否則返回FALSE。&l

19、t;/p><p>　　GetTop(S,&e)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：若S不空，則e返回棧頂元素。</p><p>　　Push（&S，&e）</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：在s的

20、棧頂插入新的棧頂元素e。</p><p>　　Pop(&S,&e)</p><p>　　初始條件：棧S已存在。</p><p>　　操作結(jié)果：刪除S的棧頂元素，并以e返回其值。</p><p>　　StackTraverse（S，visit（））</p><p>　　初始條件：棧S已存在。</p&

21、gt;<p>　　操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit（）。</p><p>　　}ADT Stack</p><p>　　2.本程序包含兩個(gè)模塊</p><p><b>　　1）主程序模塊：</b></p><p>　　Void main()</p><p>

22、;<b>　　{</b></p><p><b>　　初始化;</b></p><p><b>　　For循環(huán)}</b></p><p>　　2）棧模塊——實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型</p><p>　　各模塊之間的調(diào)用關(guān)系如下：</p><p><b

23、>　　主程序模塊</b></p><p><b>　　棧模塊</b></p><p><b>　　本章主要介紹</b></p><p>　　1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) </p><p>　　主要介紹在實(shí)驗(yàn)中采用（或設(shè)計(jì)）的數(shù)據(jù)結(jié)構(gòu)以及原因。</p><p><

24、b>　　2、算法的設(shè)計(jì)</b></p><p>　　主要說(shuō)明本設(shè)計(jì)從總體上劃分幾個(gè)模塊，每個(gè)模塊需要完成的功能是什么？定義每個(gè)模塊對(duì)應(yīng)的函數(shù)接口，用偽代碼（類C或C++）設(shè)計(jì)每個(gè)模塊對(duì)應(yīng)的算法。</p><p>　　3、抽象數(shù)據(jù)類型的 設(shè)計(jì)</p><p>　　根據(jù)所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和接口函數(shù)，寫出抽象數(shù)據(jù)類型定義或者簡(jiǎn)單類定義。</p>

25、<p><b>　　第四章 詳細(xì)設(shè)計(jì)</b></p><p><b>　　1）棧類型；</b></p><p>　　typedef struct stacklist</p><p><b>　　{</b></p><p>　　SElemType *base;<

26、;/p><p>　　SElemType *top;</p><p>　　int stacksize;</p><p><b>　　}SqStack;</b></p><p>　　棧的基本操作設(shè)置如下：</p><p>　　void Stack_init(SqStack *s)//初始化，設(shè)s為空棧&l

27、t;/p><p>　　void Stack_Push(SqStack *s,SElemType e)//若分配空間成功，則在s的棧頂插入新的元素e，并返回TRUE</p><p>　　//若棧不變，并返回FALSE</p><p>　　SElemType Stack_Pop(SqStack *s)</p><p>　　Status Stack_E

28、mpty(SqStack *s)</p><p>　　Status Stack_Full(SqStack *s)</p><p>　　void Stack_printreverse(SqStack s)</p><p>　　void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)

29、</p><p><b>　　2)代碼</b></p><p>　　#include <iostream> </p><p>　　using namespace std;</p><p>　　typedef int SElemType;</p><p>　　typedef int St

30、atus;</p><p>　　int end;/*最后一個(gè)車廂的號(hào)碼*/</p><p>　　long total=0;/*總的組合方案數(shù)目*/</p><p>　　typedef struct stacklist</p><p><b>　　{</b></p><p>　　SElemType

31、*base;</p><p>　　SElemType *top;</p><p>　　int stacksize;</p><p><b>　　}SqStack;</b></p><p>　　void Stack_init(SqStack *s)</p><p><b>　　{</

32、b></p><p>　　s->base=(SElemType *)malloc(end*sizeof(int));</p><p>　　if(!s->base) exit(0);</p><p>　　s->top=s->base;</p><p>　　s->stacksize=end;</p>

33、<p><b>　　}</b></p><p>　　void Stack_Push(SqStack *s,SElemType e)</p><p><b>　　{</b></p><p>　　*(s->top)++=e;</p><p><b>　　}</b>

34、;</p><p>　　SElemType Stack_Pop(SqStack *s)</p><p><b>　　{</b></p><p>　　if(s->top==s->base)</p><p><b>　　return 0;</b></p><p>　　

35、return *(--(s->top));</p><p><b>　　}</b></p><p>　　Status Stack_Empty(SqStack *s)</p><p><b>　　{</b></p><p>　　if(s->top==s->base)</p>

36、;<p><b>　　return 1;</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　Status Stack_Full(SqStack *s)</p><p><b>　　

37、{</b></p><p>　　if(s->top-s->base==end)</p><p><b>　　return 1;</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p>

38、<p>　　void Stack_printreverse(SqStack s)</p><p><b>　　{</b></p><p><b>　　int *po;</b></p><p>　　po=s.base;</p><p>　　printf("\t[%ld]: &quo

39、t;,total);</p><p>　　for(;po!=s.top;) </p><p>　　printf("%d ",*po++);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void

40、search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)</p><p><b>　　{</b></p><p>　　if(!Stack_Empty(inputPoint))</p><p><b>　　{</b></p><

41、p>　　Stack_Push(tempPoint,Stack_Pop(inputPoint));</p><p>　　search(inputPoint,tempPoint,outputPoint);</p><p>　　Stack_Push(inputPoint,Stack_Pop(tempPoint));</p><p><b>　　}</

42、b></p><p>　　if(!Stack_Empty(tempPoint))</p><p><b>　　{</b></p><p>　　Stack_Push(outputPoint,Stack_Pop(tempPoint));</p><p>　　search(inputPoint,tempPoint,out

43、putPoint);</p><p>　　Stack_Push(tempPoint,Stack_Pop(outputPoint));</p><p><b>　　}</b></p><p>　　if(Stack_Full(outputPoint))</p><p><b>　　{</b></p

44、><p><b>　　total++;</b></p><p>　　Stack_printreverse(*outputPoint);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　主函

45、數(shù)：</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　SqStack input,temp,output;</p><p><b>　　int i;</b></p><p>　　printf(&quo

46、t;\n\n\t\t\t\t車廂調(diào)度\n");</p><p>　　printf("\n\t請(qǐng)輸入車廂長(zhǎng)度: ");</p><p>　　scanf("%d",&end);</p><p>　　/*初始化三個(gè)棧*/</p><p>　　Stack_init(&input);&l

47、t;/p><p>　　Stack_init(&temp);</p><p>　　Stack_init(&output);</p><p>　　/*將車廂號(hào)碼進(jìn)棧*/</p><p>　　for(i=end;i>=1;i--)</p><p>　　Stack_Push(&input,i);<

48、;/p><p>　　search(&input,&temp,&output);</p><p><b>　　}</b></p><p>　　設(shè)計(jì)抽象數(shù)據(jù)類型對(duì)應(yīng)的類定義。（如用C實(shí)現(xiàn)則沒(méi)有這項(xiàng)）</p><p><b>　　設(shè)計(jì)每個(gè)成員函數(shù)；</b></p><

49、;p><b>　　設(shè)計(jì)主函數(shù)</b></p><p><b>　　第五章 運(yùn)行與測(cè)試</b></p><p><b>　　輸入3，結(jié)果如下：</b></p><p><b>　　輸入4，結(jié)果如下：</b></p><p><b>　　第六章

50、 總結(jié)與心得</b></p><p>　　通過(guò)對(duì)本學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)，我完成了本次的課程設(shè)計(jì)報(bào)告，其中得到了很多的體會(huì)，也了解到很多的知識(shí)點(diǎn)。我明白了課程設(shè)計(jì)是大學(xué)教育中一個(gè)重要的實(shí)踐教學(xué)環(huán)節(jié)。在課程設(shè)計(jì)過(guò)程中,我根據(jù)具體設(shè)計(jì)題目，運(yùn)用自己所學(xué)的知識(shí)，獨(dú)立地進(jìn)行設(shè)計(jì)和實(shí)驗(yàn)。除了鞏固、加深和融合自己所學(xué)的數(shù)據(jù)結(jié)構(gòu)專業(yè)課程知識(shí)外，更重要的是培養(yǎng)了我多方面的能力，如獨(dú)立思考能力、綜合設(shè)計(jì)能力、實(shí)踐動(dòng)手

51、能力、開(kāi)拓創(chuàng)新能力、自學(xué)能力、文獻(xiàn)檢索能力等等。通過(guò)這次的課程設(shè)計(jì)，我也了解到自己所學(xué)的一些不足之處，以及一些還不了解的知識(shí)點(diǎn)，以后會(huì)加強(qiáng)學(xué)習(xí)，把不懂的弄懂</p><p><b>　　參考文獻(xiàn):</b></p><p>　　[1] 嚴(yán)蔚敏、吳偉民主編 《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版） 清華大學(xué)出版社 2002</p><p>　　[2] 殷

52、人昆等著 《數(shù)據(jù)結(jié)構(gòu)》（C++版） 清華大學(xué)出版社 2001</p><p>　　[3] 金遠(yuǎn)平著 《數(shù)據(jù)結(jié)構(gòu)》（C++描述） 清華大學(xué)出版社 2005 </p><p>　　[4] 許卓群等著 《數(shù)據(jù)結(jié)構(gòu)與算法》 高等教育出版社 2004</p><p>　　[5]