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

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

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

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

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