構造演算法

㈠ 數據結構C語言版 二叉樹構造演算法實驗 在鍵盤上怎麼輸入

同學你好：我幫你看了你的程序：這是修改了的程序：希望你能採納：

這是實驗結果：是正確的

#include"stdio.h"

#include"stdlib.h"

#defineOK1

#defineERROR0

typedefcharTElemType;

typedefintStatus;

typedefstructBiTNode{//結點結構

TElemType data;

structBiTNode *lchild,*rchild;

//左右孩子指針

//以下是建立二叉樹存儲結構

StatusCreateBiTree(BiTree&T){

//請將該演算法補充完整，參見第6章課件演算法或課本

charch;

scanf("%c",&ch);

if(ch=='#')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

T->data=ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

}//CreateBiTree

voidPreorder(BiTreeT)

{

if(NULL==T)

{

return;

}

else

{

printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

voidInorder(BiTreeT)

{//中序遍歷二叉樹

//請將該演算法補充完整，參見第6章課件演算法

if(T)

{

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

}

}

voidPostorder(BiTreeT)

{//後序遍歷二叉樹

//請將該演算法補充完整，參見第6章課件演算法

if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

}

//以下是求葉子結點數

voidCountLeaf(BiTreeT,int&count){

//請將該演算法補充完整，參見第6章課件演算法

if(T){

if((!T->lchild)&&(!T->rchild))

count++;

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}

//以下是求二叉樹的深度

intDepth(BiTreeT){

//請將該演算法補充完整，參見第6章課件演算法

intdepthval,depthLeft,depthRight;

if(!T) depthval=0;

else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

if(depthLeft>depthRight)depthval=1+depthLeft;

elsedepthval=1+depthRight;

}

returndepthval;

voidmain(){

BiTreeT;

ints=0,d;

printf(" creatofthebitree: ");

CreateBiTree(T);

printf(" outputresultofPreorder: ");

Preorder(T);

printf(" outputresultofInorder: ");

Inorder(T);

printf(" outputresultofPostorder: ");

Postorder(T);

CountLeaf(T,s);

d=Depth(T);

printf(" leaves=%d ",s);

printf(" depth=%d ",d);

}

㈡ 哈夫曼樹構造演算法中j<n+i是什麼意思

先看一下哈夫曼樹的構造規則是：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

用數據表示哈夫曼樹的話，首先有n個權值點，其初始化就是從 0 到 n -1，先從這裡面查找兩個權值最小的結點，就是遍歷一遍，把最小的值取出來。X1 和X2 要記錄著兩個權值在哪個位置。
然後把這兩個權值加起來的和放回到數組n的位置，然後繼續遍歷這個數據，現在是從0 到n了，當然原來X1 和X2位置的兩個點不用管，已經有父節點了。繼續上述過程直到只有一個節點位置。

如 1 2 3 4 5 6構造哈夫曼樹，先初始化parent 為 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先從上述中選取兩個權值最小的節點 1 和 2，構造樹變為3，放到數組6的位置，原權值序列變為：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到3 和 3，放到數組7的位置，權值序列變為：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
繼續選取 兩個最小權值且parent為-1的點。找到4 和5，到數組8的位置，權值序列變為：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到6 和6，到數組9的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到9 和12，到數組10的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
結束
所以你說的j < n + i，由於每次選取兩個權值的點權值和做為新的節點放在數組後面，當然下一次循環的時候要多一次循環。
X1 和X2要記錄下選擇兩個權值，將其父節點的位置設置為新的權值點位置。

㈢ 什麼是演算法構造演算法的基本思想是什麼

1順序結構
按從上到下的順序進行
2選擇結構
根據條件作判斷,再決定執行哪一種操作的演算法結構
必須包含判斷框
3循環結構

㈣ FP-tree的FP-tree構造演算法

輸入：事務資料庫D和最小支持度閾值minσ。
輸出：D所對應的FP-tree。
方法：FP-tree是按以下步驟構造的：
(1)掃描事務庫D，獲得D中所包含的全部頻繁項集1F，及它們各自的支持度。對1F中的頻繁項按其支持度降序排序得到L。
(2)創建FP-tree的根結點T，以「null」標記。再次掃描事務庫。對於D中每個事務，將其中的頻繁項選出並按L中的次序排序。設排序後的頻繁項表為[p|P]，其中p是第一個頻繁項，而P是剩餘的頻繁項。調用insert_tree([p|P],T)。insert_tree([p|P],T)過程執行情況如下：如果T有子女N使N .item_name=p.item_name，則N的計數增加1；否則創建一個新結點N，將其計數設置為1，鏈接到它的父結點T，並且通過node_link將其鏈接到具有相同item_name的結點。如果P非空，遞歸地調用insert_tree(P，N)。FP-tree是一個高度壓縮的結構，它存儲了用於挖掘頻繁項集的全部信息。FP-tree所佔用的內存空間與樹的深度和寬度成比例，樹的深度一般是單個事務中所含項目數量的最大值；樹的寬度是平均每層所含項目的數量。由於在事務處理中通常會存在著大量的共享頻繁項，所以樹的大小通常比原資料庫小很多。頻繁項集中的項以支持度降序排列，支持度越高的項與FP-tree的根距離越近，因此有更多的機會共享結點，這進一步保證了FP-tree的高度壓縮。

㈤ 小世界網路模型的NW小世界模型構造演算法

1、一個環狀的規則網路開始：網路含有N個結點，每個結點向與它最臨近K個結點連出K條邊，並滿足N>>K>>ln(N)>>1。
2、隨機化加邊：以概率p在隨機選取的一對節點之間加上一條邊。其中，任意兩個不同節點之間至多隻能有一條邊，並且每一個節點都不能有邊與自身相連。改變p值可以實現從最臨近耦合網路(p=0)向全局耦合網路(p=1)轉變。當p足夠小和N足夠大時，NW小世界模型本質上等同於WS小世界模型。

㈥ 小世界網路模型的WS小世界模型構造演算法

1、一個環狀的規則網路開始：網路含有N個結點，每個節點向與它最臨近的K個節點連出K條邊，並滿足N>>K>>ln(N)>>1。
2、隨機化重連：以概率p隨機地重新連接網路中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網路中隨機選擇的一個節點。其中規定，任意兩個不同的節點之間至多隻能有一條邊，並且每一個節點都不能有邊與自身相連。這樣就會產生pNK/2條長程的邊把一個節點和遠處的結點聯系起來。改變p值可以實現從規則網路(p=0)向隨機網路(p=1)轉變。

㈦ 二叉樹 構造演算法

http://www.programfan.com/club/showbbs.asp?id=13378
自己去看看哈

㈧ 最優二叉樹演算法的構造演算法

從上述演算法中可以看出，F實際上是森林，該演算法的思想是不斷地進行森林F中的二叉樹的「合並」，最終得到哈夫曼樹。
在構造哈夫曼樹時，可以設置一個結構數組HuffNode保存哈夫曼樹中各結點的信息，根據二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n－1個結點，所以數組HuffNode的大小設置為2n－1，數組元素的結構形式如下： weight lchild rchild parent 其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數組HuffNode中的序號，從而建立起結點之間的關系。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為－1，當結點加入到樹中時，該結點parent的值為其雙親結點在數組HuffNode中的序號，就不會是－1了。
構造哈夫曼樹時，首先將由n個字元形成的n個葉結點存放到數組HuffNode的前n個分量中，然後根據前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合並為一個較大的子樹，每次構成的新子樹的根結點順序放到HuffNode數組中的前n個分量的後面。
下面給出哈夫曼樹的構造演算法。
const maxvalue= 10000; {定義最大權值}
maxleat=30; {定義哈夫曼樹中葉子結點個數}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procere CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造演算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {輸入葉子結點個數}
for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}
begin
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode[i].weight); {輸入n個葉子結點的權值}
for i:=0 to n-1 do {構造哈夫曼樹}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n i-1 do
if (HuffNode[j].weight
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight
begin m2:=HuffNode[j].weight; x2:=j; end;
{將找出的兩棵子樹合並為一棵子樹}
HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;
HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;
HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;
end;
end;

㈨ 3DGIS中幾種多解析度模型構造演算法的性能比較研究

摘要：本文對開源3DGIS軟體VTP中的三種視點相關多解析度地形模型生成演算法-McNally演算法、Rottger演算法和TopoVista演算法進行了比較實驗研究。結果表明，在三角形數取1000時，如果使用三角彤帶繪制，則McNally演算法的運行速度最快，如果沒有使用，則TopoVista演算法最快；Rottger演算法在CLOD演算法中速度最慢，但是彈跳現象不如其他演算法明顯，效果要好；當三角形數量大於5000時，Rottger演算法的表現始終優於McNally演算法。