數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))word格式(已修改)
2025-01-28 17:03 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用一、問題描述 二叉樹是一種常見的數(shù)據(jù)結(jié)構(gòu)，在實(shí)際中應(yīng)用十分廣泛。二叉樹有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)，可以運(yùn)用遞歸和非遞歸設(shè)計(jì)算法，能夠求解節(jié)點(diǎn)在二叉樹中的層次數(shù)等問題。在實(shí)際應(yīng)用中，要求以同學(xué)錄為例完成系統(tǒng)的設(shè)計(jì)與管理。二、基本要求 選擇合適的存儲(chǔ)結(jié)構(gòu)，完成二叉樹的建立。最好采用順序和鏈?zhǔn)絻煞N方法。 在順序二叉樹中求解節(jié)點(diǎn)所在層次數(shù)。 在鏈?zhǔn)蕉鏄渲星蠼夤?jié)點(diǎn)所在層次數(shù)。 以同學(xué)錄為例，利用二叉樹存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)建立、查找、新增、刪除等功能。三、測試數(shù)據(jù) 分別以順序和鏈?zhǔn)酱鎯?chǔ)測試圖示二叉樹中節(jié)點(diǎn)E所在層次： 同學(xué)錄的測試數(shù)據(jù)： 趙一,19790101,15811111111,0807011001 錢二,19800202,15822222222,0807011002 孫三,19810303,15833333333,0807011003 李四,19820404,15844444444,0807011004 在上表的的基礎(chǔ)上，測試表的建立，以及記錄的新增、修改、刪除等。四、算法思想 在順序二叉樹下求節(jié)點(diǎn)所在層次數(shù) 本題中順序二叉樹按照滿二叉樹的原則建立，空節(jié)點(diǎn)存“0”。故節(jié)點(diǎn)所在層次count與節(jié)點(diǎn)下標(biāo)m有如下關(guān)系： 1)初始層次數(shù)count=1，當(dāng)m=0時(shí)，所查節(jié)點(diǎn)不存在 2)當(dāng)m非0時(shí)，令m=m/2，count加一 3)m不為1時(shí)，返回層次數(shù)count；m為1時(shí)，重復(fù)步驟2) 在鏈?zhǔn)蕉鏄湎虑蠊?jié)點(diǎn)所在層次數(shù) 算法要用非遞歸算法求解二叉樹中給定節(jié)點(diǎn)的深度，為實(shí)現(xiàn)層次非遞歸求解，必須借用數(shù)據(jù)結(jié)構(gòu)保存將要訪問的節(jié)點(diǎn)，在函數(shù)CengciTree(BiTreeLink T,char c)中用數(shù)組queue實(shí)現(xiàn)此功能。具體編程時(shí)，用變量n保存當(dāng)前訪問的節(jié)點(diǎn)的層次數(shù)目并初始化為1，front和rear是數(shù)組queue中當(dāng)前正在訪問的節(jié)點(diǎn)的下標(biāo)以及可插入節(jié)點(diǎn)的下標(biāo)，而flag起到標(biāo)志作用用來表明是否要增加當(dāng)前的層次數(shù)n。 算法開始時(shí)，首先判斷樹是否為空，若為空樹退出程序；若樹不為空，則先判斷根節(jié)點(diǎn)的值是否與要查找節(jié)點(diǎn)的值相等，若相等則返回n，否則將當(dāng)前層次n加1，并將根節(jié)點(diǎn)的左孩子、右孩子以及根節(jié)點(diǎn)本身插入到數(shù)組queue中?？赡?，有人會(huì)問為什么還要將根節(jié)點(diǎn)插入到數(shù)組queue中？這里，將根節(jié)點(diǎn)插入到數(shù)組queue中的目的是，當(dāng)queue[front]保存的是根節(jié)點(diǎn)的指針時(shí)，二叉樹的一層節(jié)點(diǎn)遍歷結(jié)束了，需要將當(dāng)前層次數(shù)n加1并讓queue[rear]保存根節(jié)點(diǎn)的指針。算法的核心部分就是while循環(huán)里面的內(nèi)容，首先讓標(biāo)志flag值為0,如果queue[front]不為空且queue[front]data的值等于要查找的值c，程序結(jié)束返回n即可；若queue[front]的值是指向根節(jié)點(diǎn)的指針，表明當(dāng)前層次上的所有節(jié)點(diǎn)都已經(jīng)訪問過了，要訪問下一個(gè)層次的節(jié)點(diǎn)了，故要把n加1并讓flag值為1以表明在數(shù)組的插入位置queue[rear]需要賦值為跟節(jié)點(diǎn)的指針；如果，均不是上述情況，則將queue[front]的左孩子、右孩子都放到數(shù)組queue中，并將front指向下一個(gè)元素。重復(fù)上述循環(huán)，直到找到了要查找的值，或者遍歷了所有的節(jié)點(diǎn)。 同學(xué)錄的實(shí)現(xiàn) 本題的一個(gè)實(shí)際應(yīng)用是實(shí)現(xiàn)同學(xué)錄，我們采用二叉樹存儲(chǔ)結(jié)構(gòu)，利用預(yù)置數(shù)組建立二叉樹；先序方式遍歷二叉樹并輸出；遞歸算法實(shí)現(xiàn)對同學(xué)錄的查找；基于查找實(shí)現(xiàn)對同學(xué)錄的修改和新增成員；求所要操作節(jié)點(diǎn)的父親節(jié)點(diǎn)，從而順利的編寫對同學(xué)錄的刪除操作。五、模塊劃分：在順序二叉樹下求節(jié)點(diǎn)所在層次數(shù)（1）void Creattree()其功能是建立順序二叉樹；（2）void Cengcitree()其功能是求節(jié)點(diǎn)層次在鏈?zhǔn)蕉鏄湎虑蠊?jié)點(diǎn)所在層次數(shù)（1）int CreateBiTree(BiTreeLink *T)其功能是建立二叉樹；（2）void PreOrderTraverse(BiTreeLink T) 其功能是先序遍歷二叉樹；（3）int CengciTree(BiTreeLink T,char c) 其功能是求層次數(shù)（1）int n=0,front=0,rear=0,flag。初始化隊(duì)列；（2）(front+1)%MAXSIZE!=rear判斷隊(duì)列不滿。以同學(xué)錄為例，利用二叉樹存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)建立、查找、新增、刪除等功能。（1）void CreateBiTree(DataType *items,BiTree *T)其功能是建立同學(xué)錄（2）void PreOrderTraverse(BiTree T)（3）PBTNode SearchTree(BiTree T,char *ch)（4）void ModifyTree(BiTree T)（5）void DeleteTree(BiTree T)main()主函數(shù)，功
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1