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

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

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

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

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