數(shù)據(jù)結(jié)構課程設計-迷宮、遍歷二叉樹、文章編輯

1、景德鎮(zhèn)陶瓷學院數(shù)據(jù)結(jié)構課程設計報告院系：信息工程學院專業(yè)：計算機科學與技術班級：計科2班學號：201310510112姓名：張旸一、 課程設計概述本次數(shù)據(jù)結(jié)構課程設計共完成了3個問題：迷宮問題；建立二叉樹，層序、先序遍歷；文章編輯使用語言：C語言、C+編譯環(huán)境：Windows7、Microsoft Visual Studio 2013、VC+ 6.0二、 課程設計內(nèi)容2.1題目一：迷宮問題1.問題描述 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。2.需求分析（1）實現(xiàn)一個以鏈表作存儲結(jié)構的棧類

2、型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中，(i,j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。（2）編寫遞歸形式算法，求得迷宮中所有可能的通路；（3）以方陣形式輸出迷宮及其通路（選做）。3.概要設計3.1設計原理程序的三大模塊：主程序模塊、棧模塊和迷宮模塊。主程序模塊：初始化迷宮模塊棧模塊：實現(xiàn)迷宮數(shù)據(jù)的抽象化和對迷宮數(shù)據(jù)的處理迷宮模塊：實現(xiàn)迷宮數(shù)據(jù)抽象類型int main() 初始化； 接受命令； 處理命令； 返回；各模塊之間的調(diào)用關系如下：主程序模塊迷宮模塊棧模塊3.2儲存結(jié)構設計3.2.1設定棧的抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對

3、象：D= ai|ai CharSet,i=1,2,n,n0 數(shù)據(jù)關系：R1=<ai-1, ai>| ai-1 , ai D,i=2,n 基本操作： InitStack(&S) 操作結(jié)果：構造一個空棧S。 DestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：銷毀棧S。 ClearStack(&S) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackEmpty(S) 初始條件：棧S已存在。 操作結(jié)果：若S為空棧，則返回TRUE,否則返回FALSE。 GetTop(S,&e) 初始條件：棧S已存在。 操作結(jié)果：若棧S不空，則以e返

4、回棧頂元素。 Push(&S,e) 初始條件：棧S已存在。 操作結(jié)果：在棧S的棧頂插入信的棧頂元素e。 Pop(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。ADT Stack3.2.2設定迷宮的抽象數(shù)據(jù)類型ADT maze 數(shù)據(jù)對象：D=ai,j | ai,j 0,1,0im+1,0jn+1,m,n10數(shù)據(jù)關系：R=ROW,COL ROW= <ai-1,j, ai,j >| ai-1,j , ai-1D,i=1,m+1,j=0,n+1 COL= <ai,j-1, ai,j >| ai,j-1 , ai-1D,

5、i=1,m+1,j=0,n+1 InitMaze (&M ,a ,row , col )初始條件：二維數(shù)組arow+2col+2已經(jīng)存在，其中自第一行至第row+1行、每行中自第1列至第col+1列的元素已經(jīng)有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構成迷宮的字符型數(shù)組，并在迷宮四周加上一圈障礙。 MazePath (&M)初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路，則按照所走的步驟，從小到大依次排列。 PrintMaze (M)初始條件：迷宮M已存在。操作結(jié)果：已字符形式輸出迷宮。ADT maze;3.2.3尋找公共路徑的實驗過程設定當前為出始值的入

6、口：Do   若當前位置可通，   則將當前位置插入棧頂；      若該位置是出口位置，則結(jié)束；      否則切換當前位置的東鄰方塊為新的當前位置；        否則     若棧不空且棧頂位置尚有其他方向未被探索，  則設定新的當前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置 的下一鄰塊；     

7、 若棧不為空且棧頂位置的四周均不可通，      則刪除棧頂位置；      若棧不為空，則重新測試新的棧頂位置，      直至找到一個可通的相鄰塊或出棧至?？眨?#160;             4.詳細設計4.1迷宮模塊以二維動態(tài)數(shù)組*mazemn表示迷宮，數(shù)組中元素值為0表示通路，1表示障礙。(1)坐標位置類型:str

8、uct Maze /定義描述迷宮中當前位置的結(jié)構類型int x; /當前位置的行坐標int y; /當前位置的列坐標int dir; /0:無路徑或已到達出口,1:下,2:右,3:上,4:左; (2)創(chuàng)建迷宮CreatMaze:int* CreatMaze(int &m, int &n); (3)輸出命宮路徑PrintPath:void PrintPath(Stack p); (4)恢復迷宮Restore:void Restore(int *maze, int m, int n); (5)尋找迷宮maze中從（0，0）到（m,n）的路徑Mazepath:bool Mazepat

9、h(int *maze, int m, int n);4.2棧模塊(1)棧類型Stack:class Stackprivate:LinkNode *top; /指向第一個結(jié)點的棧頂指針public:Stack(); /構造函數(shù)，置空棧Stack(); /析構函數(shù)void Push(Maze e); /把元素e壓入棧中Maze Pop(); /使棧頂元素出棧Maze GetTop(); /取出棧頂元素void Clear(); /把棧清空bool empty(); /判斷棧是否為空; (2)構造一個空棧Stack:Stack:Stack()top=NULL;(3)刪除棧Stack:Stack:S

10、tack() (4)進棧操作Push:void Stack:Push(Maze e) LinkNode *P;P=new LinkNode;P->data=e;P->next=top;top=P;(5)出棧操作Pop:Maze Stack:Pop() Maze Temp;LinkNode *P;P=top;top=top->next;Temp=P->data;delete P;return Temp;(6)取棧頂元素GetTop:Maze Stack:GetTop()return top->data;(7)清空棧Clear:void Stack:Clear() t

11、op=NULL;(8)判斷是否為空棧empty:bool Stack:empty() if(top=NULL) return 1;else return 0;4.3主程序模塊程序如下:int main()int m = 0, n = 0;int *maze;maze = CreatMaze(m, n);if (Mazepath(maze, m, n)cout << "迷宮路徑探索成功!n"else cout << "路徑不存在!n"system("pause");return 0;4.4函數(shù)調(diào)用關系的層次結(jié)構框

12、圖主程序PushStackCreatMazeInitializationReadCommandInterpretMazePathPopemptyGetTopPrintPathRestore4.5測試用例設計 1 2 3 4 5 6 7 80010001000100010000011010111001000010000010001010111100111000101110000005.運行結(jié)果及分析 5.1運行結(jié)果 5.2問題的模型化描述以及求解算法的簡要描述（1）計算機解迷宮問題通常使用的是“窮舉求解”的方法，即從設定的迷宮入口出發(fā)，然后順著某一個方向進行探索，如若能走通，則繼續(xù)往前行進；否則

13、沿著原路退回，換一個方向繼續(xù)探索路徑，直至找到出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路，路徑探索失敗。（2）可以以二維數(shù)組形式存儲迷宮數(shù)據(jù)，通常設定入口的下標為（1，1），出口的下標為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可設定有東、南、西、北四個方向可通；以行坐標、列坐標、數(shù)字化方向和方向四個字符的組合輸出迷宮路徑。5.3對于設計和編碼的討論與分析（1）剛著手解決這個迷宮問題的時候，首先要解決的就是如何實現(xiàn)迷宮問題求解。我們可以用“窮舉求解”的方法來尋找迷宮的解。于是，又有問題了，該如何窮舉？該怎么窮舉才不

14、會出錯？根據(jù)指導書上的需求，可以分為四個方向挨個探索。至于，如何儲存并實現(xiàn)這個迷宮，就得依賴于棧和二維數(shù)組的相關知識了。（2）在具體編碼時，也會遇到很多問題，譬如網(wǎng)絡上的一些代碼的運行會出現(xiàn)錯誤，需要自己動手動腦親自調(diào)試。這樣有助于對數(shù)據(jù)結(jié)構相關知識的理解，同時也達到了這門課程設計的實驗目的，那就是通過自己動手動腦體會算法與數(shù)據(jù)結(jié)構的相關思想，并將所學知識運用到實際的編程過程中，達到學以致用的目的。2.2題目二：建立二叉樹，層序、先序遍歷；1.問題描述建立二叉樹，層序、先序遍歷要求能夠輸入樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構的的輸入函數(shù)、輸出層序遍歷序列

15、的函數(shù)、輸出先序遍歷序列的函數(shù)。2.需求分析2.1主功能模塊根據(jù)提示信息,用戶可以方便地通過本程序來完成建立、遍歷二叉樹等操作。界面設計合理、美觀、人性化, 程序智能, 安全性高。2.2創(chuàng)建樹模塊當進入程序運行界面后,根據(jù)提示輸入需要建立的二叉樹,按照先序次序輸入各個結(jié)點的值, 完成二叉樹的建立。2.3遍歷樹模塊實現(xiàn)對該二叉樹的先序遞歸遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸遍歷、層序非遞歸遍歷等方式的遍歷操作,并輸出各遍歷序列。3.概要設計3.1主界面設計思想流程圖3.2創(chuàng)建二叉樹3.2.1二叉樹創(chuàng)建的思想(1)定義二叉樹結(jié)點值的類型為字符型。(2)設定結(jié)

16、點個數(shù)不超過10個。(3)按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹。相關函數(shù)如下: void CreateBiTree(BiTree &T)3.2.2二叉樹創(chuàng)建的算法流程圖開始創(chuàng)建二叉樹結(jié)束3.3先序遞歸遍歷3.3.1先序遞歸遍歷思想若二叉樹為空，則空操作，否則(1)訪問根結(jié)點；(2)先序遍歷左子樹；(3)先序遍歷右子樹. 相關函數(shù)如下: void PreOrderTraverse(BiTree T)3.3.2先序遞歸遍歷的算法流程圖開始判結(jié)點是否空訪問根結(jié)點結(jié)束按前根遍歷方式遍歷左子樹按前根遍歷方式遍歷右子樹YN3.4中序遞歸遍歷3.4.1中序遞歸遍歷思想若二叉樹為空

17、，則空操作，否則(1)中序遍歷左子樹；(2)訪問根結(jié)點；(3)中序遍歷右子樹. 相關函數(shù)如下: void InOrderTraverse(BiTree T)3.4.2中序遞歸遍歷的算法流程圖開始判結(jié)點是否空按中根遍歷方式遍歷左子樹結(jié)束訪問根結(jié)點按中根遍歷方式遍歷右子樹YN3.5后序遞歸遍歷3.5.1后序遞歸遍歷思想若二叉樹為空，則空操作；否則(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問根結(jié)點. 相關函數(shù)如下: void PostOrderTraverse(BiTree T)3.5.2后序遞歸遍歷的算法流程圖開始判結(jié)點是否空按后根遍歷方式遍歷左子樹結(jié)束按后根遍歷方式遍歷右子樹訪問根結(jié)點

18、YN3.6先序非遞歸遍歷3.6.1先序非遞歸遍歷思想(1)訪問結(jié)點的數(shù)據(jù)域；(2)指針指向p的左孩子結(jié)點；(3)從棧中彈出棧頂元素；(4)指針指向p的右孩子結(jié)點. 相關函數(shù)如下: void NRPreOrder(BiTree bt)3.6.2先序非遞歸遍歷的算法流程圖開始申請一個STL棧stack<*> s判結(jié)點是否空輸出結(jié)點值p->datas.push(p)結(jié)點的值變?yōu)樗淖蠛⒆优袛嘟Y(jié)點是否空p=s.pop()p=p->rchild結(jié)束判斷?；蚪Y(jié)點是否空NYNYN3.7中序非遞歸遍歷3.7.1中序非遞歸遍歷思想(1)指針指向p的左孩子結(jié)點；(2)從棧中彈出棧頂元素；(

19、3)訪問結(jié)點的數(shù)據(jù)域；(4)指針指向p的右孩子結(jié)點. 相關函數(shù)如下: void NRInOrder(BiTree bt)3.7.2中序非遞歸遍歷的算法流程圖開始申請一個STL棧stack<*> s判結(jié)點是否空s.push(p)結(jié)點的值變?yōu)樗淖蠛⒆优袛嘟Y(jié)點是否空輸出結(jié)點值p->datap=s.pop()p=p->rchild結(jié)束判斷?；蚪Y(jié)點是否空NYYNN3.8后序非遞歸遍歷3.8.1后序非遞歸遍歷思想若二叉樹為空，則空操作；否則引入棧和標記模擬遞歸工作棧, 初始時棧為空，相關函數(shù)如下: void NRPostOrder(BiTree bt);3.8.2后序非遞歸遍歷的

20、算法流程圖開始申請一個STL棧stack<*> s;用一個bool變量flag標記是否訪問flag=0 s.push(p)p=p->lchild top+判斷標志flag是否為1輸出結(jié)點的數(shù)據(jù)p->datap = s.pop()p= p->rchild結(jié)束NYYNNYYN判斷結(jié)點是否空判棧或結(jié)點是否空判斷結(jié)點是否空3.9層序非遞歸遍歷3.9.1層序非遞歸遍歷思想(1)訪問該元素所指結(jié)點。(2)若該元素所指結(jié)點的左右孩子結(jié)點非空, 則該元素所指結(jié)點的左孩子指針和右孩子指針順序入隊。相關函數(shù)如下: void LevelOrderTraverse(BiTree T)3.

21、9.2層序非遞歸遍歷的算法流程圖開始申請一個STL隊列queue<*> q結(jié)束N判結(jié)點是否空Y判左結(jié)點是否空q.push(p->rchild)q.push(p->lchild)判右結(jié)點是否空q.push(root);判隊列是否為空p=q.front()；輸出結(jié)點值p->data; q.pop()YYNNYN4.詳細設計 4.1主模塊本模塊定義了系統(tǒng)運行主界面的相關內(nèi)容和相關操作函數(shù), 源代碼如下: void main()BiTree T;T = NULL;int select;/cout<<"請按先序次序輸入各結(jié)點的值，以空格表示空樹(輸入時

22、可連續(xù)輸入):"<<endl;/ CreateBiTree(T);while (1)cout << "*遍歷二叉樹*n"cout << "*n"cout << "1.創(chuàng)建二叉樹 n"cout << "2.二叉樹的遞歸遍歷算法（前、中、后） n"cout << "3.二叉樹的層次遍歷算法 n"cout << "4.二叉樹的非遞歸遍歷算法（前、中、后） n"cout << &

23、quot;0.退出 n"cout << "*n"cin >> select;switch (select)case 0:return;case 1:cout << "請按先序次序輸入各結(jié)點的值，以空格表示空樹(輸入時可連續(xù)輸入):" << endl;CreateBiTree(T);break;case 2:if (!T) cout << "未建立樹，請先建樹！"elsecout << "n先序遍歷:n"PreOrderTraverse

24、(T);cout << "n中序遍歷:n"InOrderTraverse(T);cout << "n后序遍歷:n"PostOrderTraverse(T);break;case 3:cout << "n層序遍歷:n"LevelOrderTraverse(T);break;case 4:if (!T) cout << "未建立樹，請先建樹！"elsecout << "n先序遍歷:n"NRPreOrder(T);cout <<

25、"n中序遍歷:n"NRInOrder(T);cout << "n后序遍歷:n"NRPostOrder(T);break;default:cout << "請確認選擇項:n"/end switch/end while 4.2創(chuàng)建樹模塊源代碼如下: void CreateBiTree(BiTree &T)/按先序次序輸入, 構造二叉鏈表表示的二叉樹T, 空格表示空樹/ if(T) return;char ch;ch = getchar(); /不能用cin來輸入, 在cin中不能識別空格. if (ch =

26、 ' ') T = NULL;elseif (!(T = (BTNode *)malloc(sizeof(BTNode) cout << "malloc fail!"T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild); 4.3遍歷樹模塊本模塊包括了各種遍歷二叉樹的函數(shù)，源代碼如下: void PreOrderTraverse(BiTree T) /二叉樹的先序遍歷(遞歸)成員函數(shù)聲明void InOrderTraverse(BiTree T) /二叉樹的中序遍

27、歷(遞歸)成員函數(shù)聲明void PostOrderTraverse(BiTree T) /二叉樹的后序遍歷(遞歸)成員函數(shù)聲明void LevelOrderTraverse(BiTree T) / 二叉樹的層序遍歷(非遞歸)成員函數(shù)聲明void NRPreOrder(BiTree bt) / 二叉樹的先序遍歷(非遞歸)成員函數(shù)聲明void NRInOrder(BiTree bt) /二叉樹的中序遍歷(非遞歸)成員函數(shù)聲明void NRPostOrder(BiTree bt) /二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明5.運行結(jié)果及分析5.1運行結(jié)果ABCDEFHG隨機建立一棵樹。由數(shù)據(jù)結(jié)構的知識

28、，按照先序次序輸入各個節(jié)點的值為: ABD#CEG#F#H#(此處#代表空格)。在程序中輸入這些節(jié)點，創(chuàng)建樹，如下圖: 輸入1：創(chuàng)建二叉樹，輸出結(jié)果如下：輸入2：輸出該二叉樹的遞歸遍歷算法的遍歷結(jié)果, 輸出結(jié)果如下:輸入3：輸出該二叉樹的層序遍歷算法的遍歷結(jié)果, 輸出結(jié)果如下: 輸入4：輸出該二叉樹的非遞歸遍歷算法的遍歷結(jié)果, 輸出結(jié)果如下: 5.2算法分析5.2.1時間復雜度其實無論是先序遞歸遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸遍歷還是層序遍歷，其基本操作都是訪問二叉樹結(jié)點。因此對于擁有n個結(jié)點的二叉樹，其時間復雜度均為O(n)。5.2.2空間復雜度對

29、于采用遞歸的方法遍歷二叉樹, 即先序遞歸遍歷、中序遞歸遍歷以及后序遞歸遍歷，并不需要對其輔助空間就能實現(xiàn)對二叉樹的遍歷, 則空間復雜度為O(1)。對于采用非遞歸的方法遍歷二叉樹, 即先序非遞歸遍歷、中序非遞歸遍歷以及后序非遞歸遍歷, 所需輔助空間為遍歷過程中棧的最大容量, 即樹的深度, 一般情況下為 ，則空間復雜度為0（ ），最壞情況下為n, 則空間復雜度也為O(n)。2.3題目三：文章編輯1.問題描述輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。2.需求分析（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在

30、文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"；（3）輸出刪除某一字符串后的文章。3.概要設計3.1定義結(jié)構體 struct line，文本行采用順序存儲，行與行之間采用鏈式存儲。3.2主要函數(shù)int FindString(LINE * &he

31、ad,char *str) /*統(tǒng)計str在文章中出現(xiàn)的次數(shù)*/求在一行中Str出現(xiàn)的次數(shù)的流程圖：開始count=0;h=0;len1=0; len2=strlen(str);p->datai=str0i+k=0;j=0;p->datai+j=strjk+;j+;k=len2count+;i=i+k-1;結(jié)束YNYNNY .查找第一個字符，如果有第一個字符即p->datai=str0，設計數(shù)器k=0； 查找這個字符后面的字符與要查找的字符串是否匹配即 p->datai+j=strj，如果匹配則k+； 重復第二步，如果k=len2，則查找到count+；如果沒查找到，重

32、新進行第一步void delstringword(char *s,char *str) /*刪除字符串*s中的字符串*str*/ strpi jsfor(m=0;m<i;m+)tmpcount+=sm;for(n=j;n<len;n+)tmpcount+=sn;tmp實現(xiàn)思想： 從字符串s中尋找str第一次出現(xiàn)的位置 *p=strstr(s,str);len=strlen(s);i=len-strlen(p)即前i項恰好不含要刪除的 字符串，將前i項復制到tmp中； .j=i+strlen(str) 即要刪除的字符串在i+1和j之間，將j之后的字符串復制到tmp中；將tmp賦給串s

33、，返回s4.詳細設計 設計思想 （1）定義結(jié)構體：typedef struct line char *data; struct line *next;LINE;（2）輸出函數(shù)void OutPut(LINE * &head) 將頭指針賦值為p；通過do-while語句遍歷鏈表；（3）字符串的創(chuàng)建函數(shù)： void Create(LINE * &head) 用printf語句輸出一句提醒語句，請用戶輸入要編輯的文章 為鏈表建立一個附加表頭結(jié)點，將p付給表頭指針； 輸入字符串，同時判斷輸入的字符串是否滿足條件； 用if語句判斷文章是否輸入完成。 （4）統(tǒng)計文章中英文字母數(shù)：void

34、countLetter(LINE * &head) 將p付給表頭指針； 初始化count為0； 用do-while語句遍歷鏈表，同時統(tǒng)計字符串中英文字母數(shù) 用printf語句輸出文章中英文字母數(shù)，調(diào)用子函數(shù)menu()。（5）統(tǒng)計文章中數(shù)字個數(shù)：void countNumber(LINE* &head) 將p付給表頭指針； 初始化count為0； 用do-while語句遍歷鏈表，同時統(tǒng)計字符串中數(shù)字個數(shù)； 用printf語句輸出文章中數(shù)字個數(shù)，調(diào)用子函數(shù)menu()。（6）統(tǒng)計文章中的空格數(shù)：void countSpace(LINE * &head) 將p付給表頭指針；

35、 初始化count為0； 用do-while語句遍歷鏈表，同時統(tǒng)計字符串中空格數(shù)； 用printf語句輸出文章中空格數(shù)，調(diào)用子函數(shù)menu()。（7）統(tǒng)計文章總字數(shù)：void countAll(LINE * &head)將p付給表頭指針； 初始化count為0； 用do-while語句遍歷鏈表，同時統(tǒng)計字符串中總字數(shù)； 用printf語句輸出文章中總字數(shù)，調(diào)用子函數(shù)menu()。（8）查找字符串的函數(shù)：void FindString(LINE * &head)將p付給表頭指針；初始化count為0；初始化len1,用來保存當前行的總字符數(shù)；定義整型變量len2表示待統(tǒng)計字符串的

36、長度；用printf語句提醒用戶輸入要統(tǒng)計的字符串；用do-while語句遍歷鏈表，同時用for循環(huán)和if語句找出指定字符串在文章中出現(xiàn)的次數(shù)；用printf語句輸出指定字符串在文章中出現(xiàn)的總次數(shù)，調(diào)用子函數(shù)menu()。（9）刪除字符串的函數(shù)：void DelString(LINE * &head) 先創(chuàng)建一個delstringword，其中包含兩個字符串char *s和char *str，用*s表示輸入的字符串，*str表示要刪除的字符。這個函數(shù)的功能是找到字符串s在字符串中出現(xiàn)的位置并刪除該字符串。 定義字符串的刪除函數(shù)DelString(),用do-while語句遍歷鏈表，語句

37、中再套用if語句，并調(diào)用delstringword()進行刪除。（10）主函數(shù):void main() 用switch語句實現(xiàn)功能的調(diào)用。一個數(shù)字對應一個操作。5.運行結(jié)果及分析5.1運行結(jié)果輸入一段文章后以Ctrl+E作為結(jié)尾表示文章輸入結(jié)束然后分別輸入1、2、3、4、5、6、7進行測試，結(jié)果如下：5.2輸入問題解決優(yōu)化Q：在輸入文章時，往往要輸入多行文字，那么計算機怎樣識別文章是否結(jié)束輸入？輸出文章時，又怎樣處理表示結(jié)束的字符？A：輸入文章時，以Ctrl+E(E)表示結(jié)尾，當tmp0=5時，發(fā)現(xiàn)輸入E，則結(jié)束輸入。輸出時文章時，tmpstrlen(tmp)-1=5即發(fā)現(xiàn)表示結(jié)束的字符E，用

38、代碼p->datastrlen(tmp)-1='0'除去最后一個控制符 “E”即可解決問題。三、 課程設計總結(jié)數(shù)據(jù)結(jié)構課程設計的主要目的是學習并實踐運用一些常用的數(shù)據(jù)結(jié)構，闡明數(shù)據(jù)結(jié)構內(nèi)在的邏輯關系，討論它們在計算機中的存儲表示，并結(jié)合各種數(shù)據(jù)結(jié)構的知識，討論對他們實行的各種運算的實現(xiàn)算法。連續(xù)兩周的數(shù)據(jù)結(jié)構課程設計使我對數(shù)據(jù)結(jié)構與算法方面的知識有了更加深入的了解，也使我認識到自己在算法學習以及編程習慣上面還有很多的不足之處。今后我應當多讀一些數(shù)據(jù)結(jié)構算法與編程思想方面的書籍，注重理論與實踐的結(jié)合，多進行上機練習編寫程序，提高自己的實際動手能力和獨立思考的能力，不斷充實自

39、己，更好地掌握編程思想，培養(yǎng)自己運用數(shù)據(jù)結(jié)構和算法的相關思想解決問題的能力。同時，此次課程設計也使我對編程產(chǎn)生了興趣，特別是在通過查書籍資料以及網(wǎng)上資源的情況下能夠使程序運行成功，讓人十分地有成就感，參考網(wǎng)上的代碼并結(jié)合理論課知識讀懂程序代碼的設計思想及其設計理念，也讓我獲益頗多。最后，通過這次實踐，我們也應該認識到自己所學到的東西實在太淺太簡單太基礎，我們以后應當認真地學習專業(yè)知識，打好基礎，為自己的未來鋪路，因為成功是百分之九十九的汗水加上百分之一的靈感。景德鎮(zhèn)陶瓷學院數(shù)據(jù)結(jié)構課程設計源程序院系：信息工程學院專業(yè)：計算機科學與技術班級：計科2班學號：201310510112姓名：張旸使用語

40、言：C語言、C+編譯環(huán)境：Windows7、Microsoft Visual Studio 2013、VC+ 6.0源代碼一：迷宮問題#include<iostream>using namespace std;struct Maze /定義描述迷宮中當前位置的結(jié)構類型int x; /當前位置的行坐標int y; /當前位置的列坐標int dir; /0:無路徑或已到達出口,1:下,2:右,3:上,4:左;class LinkNode /鏈表結(jié)點friend class Stack;public:Maze data;LinkNode *next;class Stackprivate:

41、LinkNode *top; /指向第一個結(jié)點的棧頂指針public:Stack(); /構造函數(shù)，置空棧Stack(); /析構函數(shù)void Push(Maze e); /把元素e壓入棧中Maze Pop(); /使棧頂元素出棧Maze GetTop(); /取出棧頂元素void Clear(); /把棧清空bool empty(); /判斷棧是否為空;Stack:Stack()top = NULL;Stack:Stack()void Stack:Push(Maze e)LinkNode *P;P = new LinkNode;P->data = e;P->next = top;

42、top = P;Maze Stack:Pop()Maze Temp;LinkNode *P;P = top;top = top->next;Temp = P->data;delete P;return Temp;Maze Stack:GetTop()return top->data;void Stack:Clear()top = NULL;bool Stack:empty()if (top = NULL) return 1;else return 0;bool Mazepath(int *maze, int m, int n); /尋找迷宮maze中從（0，0）到（m,n）的

43、路徑void PrintPath(Stack p); /輸出迷宮的路徑void Restore(int *maze, int m, int n); /恢復迷宮int* CreatMaze(int &m, int &n); /獲取迷宮int* CreatMaze(int &m, int &n)/返回存取迷宮的二維指針int *maze; /定義二維指針存取迷宮int i = 0, j = 0;int a, b;cout << "請輸入迷宮的規(guī)模（行 列）:"cin >> a >> b;cout <<

44、; "請輸入迷宮內(nèi)容（以0表示通路，1表示障礙）:n"m = a;n = b; /m,n分別代表迷宮的行數(shù)和列數(shù)maze = new int *m + 2;for (i = 0; i<m + 2; i+)mazei = new intn + 2;for (i = 1; i <= m; i+) /輸入迷宮的內(nèi)容，0代表可通，1代表不通for (j = 1; j <= n; j+)cin >> mazeij;for (i = 0; i<m + 2; i+)mazei0 = mazein + 1 = 1;for (i = 0; i<n +

45、 2; i+)maze0i = mazem + 1i = 1;return maze;bool Mazepath(int *maze, int m, int n)/尋找迷宮maze中從（0，0）到（m,n）的路徑Stack q, p; /棧p、q分別存探索迷宮的過程和存儲路徑Maze Temp1, Temp2;int x, y, loop;int move42 = 0, 1 , 1, 0 , 0, -1 , -1, 0 ; /當前位置移動的4個方向Temp1.x = 1;Temp1.y = 1;q.Push(Temp1); /入口位置進棧p.Push(Temp1);maze11 = -1; /

46、標志入口位置已到達過while (!q.empty() /棧q非空，則反復探索Temp2 = q.GetTop();if (!(p.GetTop().x = q.GetTop().x&&p.GetTop().y = q.GetTop().y)p.Push(Temp2);/如果有新位置入棧，則把上一個探索的位置存入棧pfor (loop = 0; loop<4; loop+) /探索當前位置的4個相鄰位置x = Temp2.x + moveloop0; /計算出新位置x位置值y = Temp2.y + moveloop1; /計算出新位置y位置值if (mazexy = 0

47、) /判斷新位置是否可達Temp1.x = x;Temp1.y = y;mazexy = -1; /標志新位置已到達過q.Push(Temp1); /新位置入棧if (x = (m) && (y = (n) /成功到達出口Temp1.x = m;Temp1.y = n;Temp1.dir = 0;p.Push(Temp1); /把最后一個位置入棧PrintPath(p); /輸出路徑Restore(maze, m, n); /恢復路徑return 1;if (p.GetTop().x = q.GetTop().x&&p.GetTop().y = q.GetTop

48、().y)/如果沒有新位置入棧，則返回到上一個位置p.Pop();q.Pop();return 0; /查找失敗，迷宮無路經(jīng)void PrintPath(Stack p) /輸出路徑cout << "迷宮的路徑為n"cout << "括號內(nèi)的內(nèi)容分別表示為(行坐標,列坐標,數(shù)字化方向,方向)n"Stack t; /用于按從入口到出口存取路徑int a, b;Maze data;LinkNode *temp;temp = new LinkNode;temp->data = p.Pop(); /取棧p的頂點元素，即第一個位置t.

49、Push(temp->data); /第一個位置入棧tdelete temp;while (!p.empty() /棧p非空，則反復轉(zhuǎn)移temp = new LinkNode;temp->data = p.Pop(); /獲取下一個位置/得到行走方向a = t.GetTop().x - temp->data.x;b = t.GetTop().y - temp->data.y;if (a = 1) temp->data.dir = 1; /方向向下else if (b = 1) temp->data.dir = 2; /方向向右else if (a = -1)

50、 temp->data.dir = 3; /方向向上else if (b = -1) temp->data.dir = 4; /方向向左t.Push(temp->data); /新位置入棧delete temp;/輸出路徑，包括行坐標，列坐標，下一個位置方向while (!t.empty() /棧非空，繼續(xù)輸出data = t.Pop();cout << '(' << data.x << ',' << data.y << ',' << data.dir &l

51、t;< ","switch (data.dir)case 1:cout << ")n" break;case 2:cout << ")n" break;case 3:cout << ")n" break;case 4:cout << ")n" break;case 0:cout << "出口)n" break;void Restore(int *maze, int m, int n) /恢復探索過的迷宮int

52、i, j;for (i = 0; i<m + 2; i+) /遍歷指針for (j = 0; j<n + 2; j+)if (mazeij = -1) /恢復探索過位置mazeij = 0;int main()int m = 0, n = 0;int *maze;maze = CreatMaze(m, n);if (Mazepath(maze, m, n)cout << "迷宮路徑探索成功!n"else cout << "路徑不存在!n"system("pause");return 0;源代碼二：建立二叉樹，層序、先序遍歷#include