作者ideaup (ideaupsoho)
看板C_Sharp
標題Re: [問題] 用c#建tree
時間Fri May 4 08:10:37 2012
※ 引述《happykeny (白目小子)》之銘言：
: 請問要怎麼宣告tree的結構??
: 以前只用過C寫指標 對於C#不是很清楚
: 爬文過了 = ="
: 哪位大大可以教一下 3Q !!!
class Node
{
static public int m;
public int ct, Jx, has,PxPos;
public long[] key;
public int[] child;//index oh child-node[]
public Node parent;
static public long HashKey(string key0)
{
return Int32.Parse(key0);
}
public Node(int j)
{
ct = 0; Jx = j; parent = null; PxPos = 0;
key = new long[m+1];
child = new int[m+1];
}
public void Init(string str)
{
string[] arr = str.Split(",".ToCharArray());
int j;
for (j = 0; j < arr.Length; j += 2)
{
key[j] = long.Parse(arr[j]);
child[j + 1] = Int32.Parse(arr[j + 1]);
}
ct = j / 2;
}
public override string ToString() //new
{
string str = "";
int j;
str += "[" + child[0] + "],";
for (j = 0; j <=ct; j++)
{
str += key[j];//key[j].ToString() + ",";//
+child[j].ToString() + ",";
str += ",[" + child[j] + "],";
}
return str;
}
public int IndexOf(long key0)
{
int j, cmp;
has = 0;
for (j = 0; j <ct; j++)
{
if (key0 == key[j]) { has = 1; return j; }
else if (key0 < key[j+1]) break;
}
return j;
}
public int Add(long key0, int NodeJx)
{
++ct;
key[ct] = key0; child[ct] = NodeJx;
return ct;
}
public int Add(Node xnode, int fg)
{
int j,j0=ct;
for (j = 1; j <=xnode.ct; ++j) { key[j0+j-1] = xnode.key[j];
child[j0+j-1] = xnode.child[j]; }
ct += xnode.ct - 1;
return ct++;
}
public int Add(Node xnode, int j0,int j9)
{
int j,ct0=ct;
for (j = j0; j <= j9; ++j) { key[ct0 + j] = xnode.key[j];
child[ct0 + j] = xnode.child[j]; }
ct += j9-j0+1;
return ct;
}
public int Insert(int pos,long key0, int NodeJx)
{
int j;
string str = "";
str += "pos,ct=" + pos + "," + ct + "," + key.Length; //key[2] =
1; key[1] = 1; key[0]=1;
++ct;
for (j = ct; j > pos; --j) { str += ",j=" + j;
MessageBox.Show(str); key[j] = key[j - 1]; child[j] = child[j - 1]; }
key[pos] = key0; child[pos] = NodeJx;
return 1;
}
public int Delete(int pos, int fg)
{
int j;
for (j = pos; j <ct; ++j) { key[j] = key[j + 1]; child[j] =
child[j + 1]; }
--ct;
return 1;
}
public int DeleteTop(int ct0, int fg)
{
int j;
for (j = 0; j < ct-ct0; ++j) { key[j] = key[ct0 + j]; child[j] =
child[ct0+j]; }
return 1;
}
}
class BTree //m-way search tree
{
int m,m2,max;
public int SxJx, has;
Node root, SxParent,node0;
Node[] node;
public BTree(int m0,int max0)
{
m = m0; m2 = (m+1) / 2; max = max0;
Node.SetM(m);
node = new Node[max0];
}
public void Init(int fg)
{
int j;
for (j = 0; j < max; j++) node[j] = new Node(j);
node0 = root = node[0];
}
Node Free(int fg)
{
int j;
for (j=1;j<max;j++)//index=0,cannot use
if (node[j].ct == 0) { node[j].Jx = j; return node[j]; }
node[j] = new Node(j);
return node[j];
}
public string MyLink(Node p)
{
int j,link;
string str="";
for (j = 0; j <= p.ct; j++)
{
link = p.child[j];
if (link == 0) continue;
Node q = node[link]; str+=q.ToString();
}
return str;
}
public string List()
{
int j, link;
string str = "";
StringBuilder sb = new StringBuilder();
sb.AppendLine(root.ToString());
sb.AppendLine(MyLink(root));
for (j = 0; j <= root.ct; j++)
{
link = root.child[j];
if (link == 0) continue;
Node q = node[link];
sb.AppendLine (MyLink(q));
}
return sb.ToString ();
}
Node Split(Node old,int fg) {
int j, ct2 = m-(m2-1);
Node p2 = Free(0); //p2.parent = old.parent;
for (j=0;j<ct2+1;j++) { p2.key[j]=old.key[m2+j];
p2.child[j]=old.child[m2+j]; }
p2.ct=m-m2;
old.ct = m2-1;
return p2;
}
public Node search(string key00, int fg)
{
Node p=root,q=node0;
int childx;
long key0 = Node.HashKey(key00);
{
SxJx = p.IndexOf(key0);
if (p.has > 0) { has = 1; return p; }
q = p; childx=p.child[SxJx];
p =node[childx];
}
has = 0;
return q;
}
public int Insert(string key00, int fg)
{
}
public int Delete(string key0, int fg)
{
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.163.6.210
1F：推 LaPass:咦? 怎麼是是連到parent而不是連樹根? 05/04 09:41
2F：推 LaPass:說錯，怎麼是是連到parent而不是連child? 05/04 09:47
3F：→ ideaup:where? 05/04 20:26