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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄1 問題描述22 基本要求22.1問題分析及解決法案框架確定22.2程序設(shè)計(jì)22.3詳細(xì)設(shè)計(jì)和編碼23 算法思想24 模塊劃分34.1對(duì)各個(gè)模塊進(jìn)行功能的描述34.2模塊之間關(guān)系及其相互調(diào)用35 數(shù)據(jù)結(jié)構(gòu)55.1定義棧55.2定義隊(duì)列55.3棧的基本操作55.4隊(duì)列的基本操作66 測(cè)試數(shù)據(jù)67 測(cè)試情況68總結(jié)91 問題描述試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而+&則不是。棧和隊(duì)列是一種常見的數(shù)據(jù)結(jié)構(gòu)，是兩種非常重要

2、的線性結(jié)構(gòu)，也都是線性表，它們是操作受限的的線性表，有順序棧、鏈?zhǔn)綏?、鏈?zhǔn)疥?duì)列和循環(huán)隊(duì)列等形式。它們廣泛應(yīng)用在各種軟件系統(tǒng)中。本題就是要用這些線性結(jié)構(gòu)先完成基本的應(yīng)用，如回文，逆置。2 基本要求2.1問題分析及解決法案框架確定充分地分析和理解問題本身，使程序結(jié)構(gòu)清晰合理簡(jiǎn)單和易于調(diào)試，并確定每個(gè)函數(shù)的簡(jiǎn)單功能，以及函數(shù)之間的調(diào)用關(guān)系。2.2程序設(shè)計(jì)1、選擇順序棧和鏈隊(duì)列，完成回文判斷、字符串的逆置；2、選擇鏈棧和循環(huán)隊(duì)列，完成回文判斷、字符串的逆置；3、運(yùn)用掌握C語(yǔ)言編寫程序，實(shí)現(xiàn)所編程序的各個(gè)模塊功能。2.3詳細(xì)設(shè)計(jì)和編碼給出所有源程序清單，要求程序有充分的注釋語(yǔ)句，至少要注釋每個(gè)函數(shù)參數(shù)的

3、含義和函數(shù)返回值的含義。3 算法思想運(yùn)用棧和隊(duì)列算法，在序列依次輸入時(shí)將序列分別入棧和入隊(duì)列，利用棧FILO和隊(duì)列FIFO的特點(diǎn)，通過出棧和出隊(duì)列實(shí)現(xiàn)序列順序和逆序的比較，根據(jù)題目描述的回文序列判斷并輸出結(jié)果。定義順序棧和鏈隊(duì)列及關(guān)于它們的基本操作，如定義棧和隊(duì)列、求棧和隊(duì)列的長(zhǎng)度、入棧出棧、入隊(duì)列出隊(duì)列等。方便后面函數(shù)的調(diào)用，是實(shí)現(xiàn)程序的基石。（鏈棧和循環(huán)隊(duì)列也是如此）編寫函數(shù)來實(shí)現(xiàn)字符串的回文判斷，回文是利用了棧的反序輸出原則而隊(duì)列則是順序輸出這個(gè)思想來實(shí)現(xiàn)的。往棧和隊(duì)列輸入同一組字符，再將它們一起輸出，這樣棧輸出的字符就與原來的順序相反了，而隊(duì)列輸出的字符與原來的順序仍然是一樣的，這樣比

4、較它們輸出的字符是否相等就可以判斷是否是回文了。4 模塊劃分4.1對(duì)各個(gè)模塊進(jìn)行功能的描述本次設(shè)計(jì)共分為六個(gè)模塊，分別是：初始化模塊、輸入模塊、入棧模塊、入隊(duì)模塊、判斷模塊、輸出模塊。各個(gè)模塊功能如下表：表4-1模塊功能表模塊功能描述初始化描述棧、隊(duì)列等初始化輸入模塊字母序列輸入入棧模塊將輸入序列入棧入隊(duì)模塊將輸入序列入隊(duì)判斷模塊將序列正、逆比較輸出模塊判斷結(jié)果輸出4.2模塊之間關(guān)系及其相互調(diào)用模塊之間的關(guān)系如圖4-1所示：開始初始化模塊入棧模塊輸出模塊入隊(duì)模塊結(jié)束輸出模塊比較模塊出棧出隊(duì)列正、逆序判斷圖4-1模塊關(guān)系圖5 數(shù)據(jù)結(jié)構(gòu)5.1定義棧typedef struct/定義棧SElemTy

5、pe *base; /在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間，以元素為單位SqStack;順序棧5.2定義隊(duì)列typedef struct /定義隊(duì)列QElemType *base;/初始化時(shí)分配的存儲(chǔ)地址int front;/頭指針，若隊(duì)列不空，指向隊(duì)頭元素；int rear;/尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一位；SqQueue;5.3棧的基本操作Status InitStack (SqStack &S)操作結(jié)果：構(gòu)造一個(gè)空棧Status GetTop(SqStack S, SElem

6、Type &e)初始條件：棧S存在操作結(jié)果：用e返回S的棧頂元素，并返回OK，否則返回ERRORStatus Push(SqStack &S, SElemType e)初始條件：棧S存在操作結(jié)果：插入元素e為新的棧頂元素Status Pop(SqStack &S, SElemType &e)初始條件：棧S存在操作結(jié)果：刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORStatus DestroyStack (SqStack &S)初始條件：棧S存在操作結(jié)果：銷毀棧SStatus ClearStack (SqStack &S)初始條件：棧S存在操作結(jié)果：將棧S清空為空棧Status

7、StackEmpty (SqStack S)初始條件：棧S存在操作結(jié)果：置為空棧，返回OK，否則返回ERRORStatus StackLength (SqStack S)初始條件：棧S存在操作結(jié)果：棧的長(zhǎng)度5.4隊(duì)列的基本操作Status InitQueue (SqQueue &Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Qint QueueLength(SqQueue Q)初始條件：隊(duì)列Q存在操作結(jié)果：隊(duì)列長(zhǎng)度Status EnQueue(SqQueue &Q,QElemType e)初始條件：隊(duì)列Q存在操作結(jié)果：插入元素e作為隊(duì)列Q的新的隊(duì)尾元素Status DeQueue (SqQueue &Q,QEl

8、emType &e)初始條件：隊(duì)列Q存在操作結(jié)果：刪除隊(duì)頭元素6 測(cè)試數(shù)據(jù)（1）（2）qweewq（3）qwe7 測(cè)試情況7.1初始測(cè)試界面圖7-1初始測(cè)試界面7.2字符序列“”測(cè)試圖7-2字符序列測(cè)試界面7.3 字符序列“qweewq”測(cè)試圖7-3字符序列qweewq測(cè)試界面7.4 字符序列“qwe”的測(cè)試圖7-4字符序列qwe測(cè)試界面測(cè)試結(jié)果分析 分析：上面是對(duì)6給出的字符序列一一測(cè)試，并按照預(yù)定格式輸出。測(cè)試數(shù)據(jù)是滿足題目要求設(shè)定字符序列（一個(gè)以為結(jié)束符的字母序列），如（1）（2）qweewq（3）qwe。實(shí)驗(yàn)結(jié)果：1字符序列是回文字符序列。 2字符序列qweewq是回文字符序列。 3字

9、符序列qwe不是回文字符序列。8總結(jié)在本次課程設(shè)計(jì)中，我在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，通過分析查找資料請(qǐng)教同學(xué)最終完成了此次課程設(shè)計(jì)。通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識(shí)，例如：函數(shù)的調(diào)用應(yīng)注意先后順序，且每個(gè)函數(shù)中所申明的變量盡量不同，避免與全局變量重復(fù)定義。文件流應(yīng)用的輸入輸出，對(duì)棧與隊(duì)列也有了更深層次的了解。以前拿到問題就不加思索地做，做到最后自己都不知道自己做了什么，可是現(xiàn)在我知道了當(dāng)問題規(guī)模較大時(shí)，首先最重要的就是理清思路，知道要實(shí)現(xiàn)這個(gè)問題需要解決哪些問題，然后把這些問題分裝成函數(shù)模塊，各個(gè)擊破，最后在main函數(shù)里調(diào)用即可。

10、這次的課程設(shè)計(jì)可以看作是一次理論與實(shí)踐相結(jié)合的橋梁，通過這次的課程設(shè)計(jì)，我學(xué)習(xí)到了許多的知識(shí)，也認(rèn)識(shí)到了自己目前的不足，那就是缺乏相應(yīng)的知識(shí)與經(jīng)驗(yàn)，所以在運(yùn)用和操作方面體現(xiàn)了不足。但是，經(jīng)過這段時(shí)間對(duì)相關(guān)書籍的閱讀和查找，我順利的完成了設(shè)計(jì)，我還明白了在編寫程序的時(shí)候，應(yīng)該盡量使界面簡(jiǎn)潔大方，布局統(tǒng)一。變量類型的定義，一定要夠用就好，這樣程序就可以盡可能的減少對(duì)系統(tǒng)資源的占用。在設(shè)計(jì)時(shí)也免不了存在著一些不足，所以在今后的學(xué)習(xí)中我會(huì)努力取得更大的進(jìn)步，對(duì)于我不足的地方希望老師能夠及時(shí)給予批評(píng)，以便我在今后的學(xué)習(xí)或工作中能夠及時(shí)的改正。參考文獻(xiàn)1嚴(yán)蔚敏, 吳偉民.數(shù)據(jù)結(jié)構(gòu)M.清華大學(xué)出版社. 20

11、07. 2王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法M.中國(guó)鐵道出版社.2007.3何欽銘，陳根才.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M.浙江大學(xué)出版社.2007.4 譚浩強(qiáng).C+程序設(shè)計(jì)M.清華出版社.2000.附錄：（源程序設(shè)計(jì)源代碼）#include#include#include#include#includeusing namespace std;#define TRUE 1#define FLASE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef char SElemTyp

12、e;#define STACK_INIT_SIZE 100;/ 存儲(chǔ)空間初始分配量#define STACKINCREMENT 10;/ 存儲(chǔ)空間分配增量typedef struct/定義棧SElemType *base; /在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間，以元素為單位SqStack;/定義棧Status InitStack (SqStack &S)/ 構(gòu)造一個(gè)空棧S.base=(SElemType * )malloc(100 * sizeof(SElemType);/修改if(!S.

13、base)exit(OVERFLOW); /存儲(chǔ)分配失敗S.top =S.base ;S.stacksize = STACK_INIT_SIZE;return OK;Status GetTop(SqStack S, SElemType &e) /若棧不空，則用e返回S的棧頂元素，并返回OK，否則返回ERRORif(S.top =S.base )return ERROR;e=*(S.top -1);return OK;Status Push(SqStack &S, SElemType e) /插入元素e為新的棧頂元素if(S.top -S.base =S.stacksize )S.base =(

14、SElemType *)realloc(S.base,(S.stacksize +10 )*sizeof(SElemType);/修改if(!S.base )exit(OVERFLOW);S.top =S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top +=e;return OK;Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top =S.base )return ERROR;e=*-S.top ;return OK;Stat

15、us DestroyStack (SqStack &S)/銷毀棧Sfree(S.base );S.base =NULL;S.top =NULL;S.stacksize =0;return OK;Status ClearStack (SqStack &S)/ 將棧S清空為空棧S.top =S.base ;return OK;Status StackEmpty (SqStack S) / 置為空棧，返回OK，否則返回ERRORif(S.base=S.top )return OK;elsereturn ERROR;Status StackLength (SqStack S)/棧的長(zhǎng)度int l;l=

16、S.top -S.base ;return l;typedef char QElemType;#define MAXQSIZE 100typedef struct /定義隊(duì)列QElemType *base;/初始化時(shí)分配的存儲(chǔ)地址int front;/頭指針，若隊(duì)列不空，指向隊(duì)頭元素；int rear;/尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一位；SqQueue;Status InitQueue (SqQueue &Q)/構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);

17、Q.front=Q.rear=0;return OK;int QueueLength(SqQueue Q)/隊(duì)列長(zhǎng)度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,QElemType e)/插入元素e作為隊(duì)列Q的新的隊(duì)尾元素若為滿回ERROR,否則返回OKif(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue (SqQueue &Q,QElemType &e)/刪除隊(duì)頭元素， 若為空返回ERROR否則返回OKif(Q.front=Q.rear)return ERROR;e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE;return OK; Status abc(string str)SqStack S;InitStack(S);SqQueue Q;InitQueue(