數據結構課程設計報告

遼寧科技大學課程設計說明書設計題目： 數據結構課程設計ProjectforDataStructure學院、系： 軟件學院 專業(yè)班級： 學生姓名： 指導教師： 成績： 2012年01月06日目錄TOC\o"1-5"\h\z1、 數據結構程序訓練說明書 -2-1.1、 題目 -2-二叉樹 -2-進制轉換 -2-鏈表 -2-1.2、 設計要求 -2-\o"CurrentDocument"2、需求分析 -2-\o"CurrentDocument"2.1、 二叉樹 -2-\o"CurrentDocument"2.2、 進制轉換 -3-\o"CurrentDocument"2.3、 鏈表 -3-\o"CurrentDocument"3、概要設計: -5-3.1、 二叉樹 -5-3.2、 進制轉換 -5-3.3、 鏈表 -6-\o"CurrentDocument"4、詳細設計: -6-\o"CurrentDocument"4.1二叉樹實現的程序設計 -6-\o"CurrentDocument"4.2進制轉換實現的程序設計 -7-\o"CurrentDocument"4.3鏈表相關功能實現的程序設計 -8-\o"CurrentDocument"5、調試分析 -10-\o"CurrentDocument"5.1二叉樹實現的程序設計結果 -10-5.2進制轉換實現的程序設計結果 -10-5.3鏈表相關功能實現的程序設計結果 -10-\o"CurrentDocument"6、程序設計總結 -11-\o"CurrentDocument"7、參考文獻 -11-1、數據結構程序訓練說明書1?1、題目二叉樹進制轉換鏈表1?2、設計要求二叉樹：設計算法，在二叉樹輸入規(guī)則下，可以求出二叉樹的葉子個數與結點總個數。進制轉換：設計算法利用棧類實現把十進制整數轉換為二至九進制之間的任一進制輸出。鏈表：在一個有序表中插入一個元素，使得該表仍然有序。將一個鏈表中的元素進行拆分，將所有奇數放到一個鏈表中，將所有的偶數放到另個鏈表中。將兩個鏈表合并成一個鏈表。將一個鏈表中的所有元素逆序存儲并顯示。2、需求分析2L二叉樹分析算法：

二叉樹的輸入規(guī)則為：ABC##D##F###則輸出結果為ABCDEF,2.2二叉樹的輸入規(guī)則為：ABC##D##F###則輸出結果為ABCDEF,2.2、進制轉換分析算法：設定一個十進制數，例如20,要將其轉化二到九進制之間的任注：這里我使用的是轉化為二進制第一步：取20與2的余，得到0第二步：取10與2的余，得到0第三步：取5與2的余，得到1第四步：取2與2的余，得到0第五步：取1與2的余，得到1至此為止，算法結束。進制20除以2得10。10除以2得5。5除以2得2。2除以2得1。1除以2得0。鏈表分析算法：使得該表仍然有序在一個有序表中插入一個元素，

使得該表仍然有序通過判斷條件找到指定的插入位置然后通過進行插入新的結點插入到鏈表中。將一個鏈表中的元素進行拆分，將所有奇數放到一個鏈表中，將所有的偶數放到另一個鏈表中。判定a[i]中存放的數為奇數還是偶數，開辟不同的鏈表空間，用不同的指針的數據域進行存儲。將兩個鏈表合并成一個鏈表。順序輸出數組中奇數，定義一個指針跟隨著奇數的移動而移動到奇數結束，然后，將該指針的next域指向偶數的頭指針的next域，然后一次輸出偶數鏈表中偶數，通過此種方法就可以將奇數鏈表和偶數鏈表鏈接起來輸出。將一個鏈表中的所有元素逆序存儲并顯示。元素要按逆序存儲，采用尾差法進行新鏈表的生成。(如圖所示)3、概要設計3.1、 二叉樹設計二叉樹實現算法，利用遞歸實現前序遍歷，采用先序遍歷非遞歸方法求二叉樹葉子節(jié)點的個數，采用遞歸方法求節(jié)點總個數。求該二叉樹的葉子節(jié)點的個數：樹的葉子節(jié)點為樹中沒有孩子節(jié)點的節(jié)點，該二叉樹中葉子節(jié)點為：CDF。將二叉樹中的所有節(jié)點定義為根節(jié)點，如果節(jié)點既沒有左孩子也沒有右孩子則可以斷定該節(jié)點為葉子節(jié)點，累加。其中先序遍歷非遞歸的方法來判斷節(jié)點是否為葉子節(jié)點。求二叉樹的節(jié)點總數：求節(jié)點的總數采用的是遞歸的算法實現函數功能，二叉樹中所有非空的節(jié)點的個數即為二叉樹的節(jié)點總數。所以只需要從根節(jié)點開始判定節(jié)點是否為空，左孩子和右孩子均設定為根節(jié)點，采用的是遞歸的算法判斷其是否為空，然后采用累加的方法就可以求出輸入的二叉樹中節(jié)點的總數。3.2、 進制轉換設計算法利用棧類實現，因為棧存儲的特點是前進后出。在本題當中，我們需要將第一次與轉換的進制數相余得到的結果排放在剩余相余得到的結果的前面，所以我們應該用棧進行存放。3.3、鏈表在一個有序表中插入一個元素，使得該表仍然有序單鏈表的插入算法：按從小到大的順序輸入，當插入的數大于數組中的某一個數時，循環(huán)結束，這時發(fā)現指針q指向的是比輸入的數要大的數據域中，所以必須設定一個指針p使得其保存工作指針q的上一個位置，這樣保證循環(huán)結束的時候要插入的位置為比數e要大得的數前一個數的后面。將一個鏈表中的元素進行拆分，將所有奇數放到一個鏈表中，將所有的偶數放到另一個鏈表中。判定條件為：判定a[i]中存放的數為奇數還是偶數，判定條件為：如果a[i]與2取余，得到的數為1則說明a[i]為奇數，否則為偶數。開辟不同的鏈表空間，用不同的指針的數據域進行存儲。將兩個鏈表合并成一個鏈表。順序輸出數組中奇數，定義一個指針跟隨著奇數的移動而移動到奇數結束，然后，將該指針的next域指向偶數的頭指針的next域，然后一次輸出偶數鏈表中偶數，通過此種方法就可以將奇數鏈表和偶數鏈表鏈接起來輸出。將一個鏈表中的所有元素逆序存儲并顯示。元素要按逆序存儲，所以在設計算法時，只需要將數組中的最后一個數存放到單鏈表中的第一個位置，輸出。就可以完成逆序存儲的效果。4、詳細設計4.1二叉樹實現的程序設計/*遞歸實現前序遍歷*/template<classT>voidBiTree<T>::PreOrder(BiNode<T>*root)(if(root==NULL)return;else(cout<<root->data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}/*求二叉樹葉子節(jié)點的個數(先序遍歷非遞歸)*/；template<classT>intBiTree<T>::CountLeaf(BiNode<T>*root)(SeqStack<BiNode<T>*>S;BiNode<T>*x;intn=0;if(root)S.Push(root);while(!S.Empty())(x=S.Pop();if(!x->lchild&&!x->rchild)n++;if(x->rchild)S.Push(x->rchild);if(x->lchild)S.Push(x->lchild);}returnn;}/*求節(jié)點的總數*/template<classT>intBiTree<T>::Count(BiNode<T>*root)(if(!root)return0;elsereturnCount(root->lchild)+Count(root->rchild)+1;}4.2進制轉換實現的程序設計voidSeqsteak::Push(inte)(if(top==Maxsize-1)throw"上溢〃；top++;inti;cout<<"輸入要轉化的進制數："<<"\n";cin>>i;cout<<"\n";while(e!=0)(data[top]=e%i;e=e/i;top++;}top二top-1;}intSeqsteak::pop()(if(top==-1)throw"下溢〃；inte;e=data[top--];returne;}4.3鏈表相關功能實現的程序設計〃實現長度為n的鏈表的構造函數，使用尾插法實現template<classT>LinkList<T>::LinkList(Ta[],intn)(inti;first=newNode<T>;//申請頭結點；Node<T>*r,*e;//定義尾指針r,每個新結點er=first;for(i=0;i<n;i++)(e=newNode<T>;//為每個新結點申請空間e->data=a[i];r->next=e;r=e;//將指針p移動到新結點的位置}r->next=NULL;//循環(huán)結束后將最后一個元素即尾指針r的next域置為空〃逆序存儲,尾插法Node<T>*l,*m;nixu=newNode<T>;l=nixu;for(i=n-1;i>=0;i--)(m=newNode<T>;m->data=a[i];l->next=m;l=m;}l->next=NULL;〃按奇數和偶數存儲Node<T>*t,*s,*p;jishu=newNode<T>;oushu=newNode<T>;t=jishu;s=oushu;for(i=0;i<n;i++)(e=newNode<T>;p=newNode<T>;if(a[i]%2==1)(e->data=a[i];t->next=e;t=e;}else(p->data=a[i];s->next=p;s=p;}t->next=NULL;s->next=NULL;}}〃在鏈表中插入指定元素template<classT>voidLinkList<T>::Insert(Te)(Node<T>*s,*p,*q;//s為新插入元素結點，p為工作指針q=first;p=q;while(q&&e>q->data)(p=q;q=q->next;}s=newNode<T>;//給新元素結點申請空間s->data=e;s->next=p->next;//先將s指向p的下一個元素位置x即a[x-1]p->next=s;〃再將p指向新元素結點位置}

5、調試分析5.1二叉樹實現的程序設計結果響C:\W5ndows\syste響C:\W5ndows\system32\cmd.exe輸入一顆二叉樹的前序遍歷二riBCttttDttttEFttft#二叉樹的煎序遍歷加。BCDEF二叉變的葉子節(jié)點留個款加3二薈城B穗的個教泓&按任意鋌繼續(xù)---.5.25.2進制轉換實現的程序設計結果5.35.3鏈表相關功能實現的程序設計結果函C:\Windows\system32\cmd.exe539_L5-L±.4>^中？表篆表蓄2429421i函C:\Windows\system32\cmd.exe539_L5-L±.4>^中？表篆表蓄2429421i152345223415295214522ii1251344523fr方果元-:>S8A?,兀劇苛餐插要-6、程序設計總結本程序在剛開始調試時有許多錯誤，但在我的努力及同學的幫助下都被一一克服，現在在操作本程序時可根據提示進行相關操作，能正確輸出結果。在剛開始的幾次調試中曾經出現過不能運行、不會正確輸出結果、不能進行循環(huán)練習等等問題。經過我的努力及同學的幫助，這些問題得到克服，并且使程序的功能也得到了一定的完善，并且給出正確答案。在這次設計過程中，不僅復習課本上所學知識，還通過查資料、問同學學到了課本上沒有的知識。從而啟發(fā)