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