




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
遼寧科技大學(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)闂4鎯?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ā)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 多發(fā)傷的護(hù)理查房
- 變革理論與馬工學(xué)試題及答案
- 2024年投資咨詢(xún)工程師關(guān)鍵考點(diǎn)試題及答案
- 中學(xué)安全教育主題班會(huì)
- 貴州省黔東南南苗族侗族自治州岑鞏縣2025年一級(jí)建造師市政工程統(tǒng)考試題含解析
- 小學(xué)數(shù)學(xué)教育故事
- 公務(wù)員外出培訓(xùn)經(jīng)驗(yàn)分享
- 加強(qiáng)數(shù)據(jù)管理的行業(yè)主管計(jì)劃
- 投資咨詢(xún)工程師價(jià)值評(píng)估試題及答案
- 創(chuàng)建良好的前臺(tái)工作環(huán)境的計(jì)劃
- 2024年上海楊浦區(qū)社區(qū)工作者筆試真題
- 建筑消防工程監(jiān)理細(xì)則
- 天然氣站租賃合同
- 2024年貴州貴州烏江煤層氣勘探開(kāi)發(fā)有限公司招聘筆試真題
- (一模)2025年廣州市普通高中畢業(yè)班綜合測(cè)試(一)生物試卷
- 【公開(kāi)課】同一直線上二力的合成+課件+2024-2025學(xué)年+人教版(2024)初中物理八年級(jí)下冊(cè)+
- (正式版)HGT 22820-2024 化工安全儀表系統(tǒng)工程設(shè)計(jì)規(guī)范
- (高清版)TDT 1075-2023 光伏發(fā)電站工程項(xiàng)目用地控制指標(biāo)
- 四年級(jí)下冊(cè)音樂(lè)課件-4-聆聽(tīng)-小放驢-滬教版(共9張PPT)
- 引水工程壓力管道水壓試驗(yàn)施工方案
- 【縣級(jí)公開(kāi)課教案】高考英語(yǔ)閱讀七選五解題技巧指導(dǎo)
評(píng)論
0/150
提交評(píng)論