 |
|
 |
|
|
|
数据库中节点值使用字符串表示，后来证明没什么意义，但其中一些思想和代码还是不错的，写出来分享一下。窗体设计可从代码中推理出来，不再贴图了。
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Data.Sql;
using System.Data.SqlClient;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Diagnostics;
/*程序主要功能：动态生成一棵树，新节点的值由其父节点和同一个链上的其他节点值相加得到，且树中不存在重复值
*
*
*/
namespace ShortestAddChain
{
public partial class Form1 : Form
{
string conn = "Password=good;Persist Security Info=True;User ID=sa;Initial Catalog=addchain;Data Source=.";
private Stopwatch stw = new Stopwatch();
public Form1()
{
InitializeComponent();
}
int compare(string value1, string value2)
{//比较两个数的大小，这两个数存储于string类型变量，且低位在前，高位在后，若value1大于value2返回1，小于返回-1，相等返回0
if (value1.Length > value2.Length)
{
return 1;
}
else if (value1.Length < value2.Length)
{
return -1;
}
else
{
for (int i = value1.Length - 1; i >= 0; i--)
{
if (value1[i] > value2[i])
return 1;
else if (value1[i] < value2[i])
return -1;
}
return 0;
}
}
string addnumber(string value1, string value2)
{//把两个整数相加，这两个整数都存储于string类型变量中，且低位在前，高位在后
string result = "";
string temp;
if (value1.Length < value2.Length)
{//保证value1长度大于value2，或二者长度相等
temp = value1;
value1 = value2;
value2 = temp;
}
int c = 0;//加法进位
int i;
for (i = 0; i < value2.Length; i++)
{
int t = value1[i] - '0' + value2[i] - '0' + c;
result += (t % 10).ToString();
c = t / 10;
}
while (i < value1.Length)
{
int t = value1[i] - '0' + c;
result += (t % 10).ToString();
c = t / 10;
i++;
}
if (c != 0)
result += (c % 10).ToString();
return result;
}
private void output(Int32 position)
{//输出最短加法链，其参数表示该节点在数据库中的记录号
Int32 j = position;
string shortestaddchain = "";
TBResult.Text = "The shortest addchain is:rn";
int chainlength = 0;
while (j >= 1)
{
string sql = "select reverse(nodevalue) as nodevalue,parentposition from addchaintable where id =" + j.ToString();
SqlDataAdapter adapter = new SqlDataAdapter(sql, conn);
DataSet ds = new DataSet();
adapter.Fill(ds);
DataTable dt = ds.Tables[0];
shortestaddchain = "," + dt.Rows[0]["nodevalue"].ToString() + shortestaddchain;
j = int.Parse(dt.Rows[0]["parentposition"].ToString());
chainlength++;
dt.Dispose();
ds.Dispose();
adapter.Dispose();
}
shortestaddchain = "1" + shortestaddchain;
chainlength++;
TBResult.Text += shortestaddchain;
stw.Stop();
TBResult.Text += "rnrnThe length of the addchain is " + chainlength.ToString();
TBResult.Text += "rnrn" + "I have run for " + stw.Elapsed.Hours.ToString() + " Hours " + stw.Elapsed.Minutes.ToString() + " Minutes " + stw.Elapsed.Seconds.ToString() + " Seconds " + stw.Elapsed.Milliseconds.ToString() + " MilliSeconds";
stw.Reset();
return;
}
protected void DoSql(string sql)//执行sql语句
{
SqlConnection conn1 = new SqlConnection();//创建连接对象
conn1.ConnectionString = conn.ToString();//给连接字符串赋值
conn1.Open();//打开数据库
SqlCommand cmd = new SqlCommand(sql, conn1);
cmd.ExecuteNonQuery();//
conn1.Close();//关闭数据库
}
private void BtnSearch_Click(object sender, EventArgs e)
{
stw.Start();
if (TBNumber.Text.Trim() == string.Empty)
return;
for (int ii = 0; ii < TBNumber.Text.Length; ii++)
if (TBNumber.Text[ii] < '0' || TBNumber.Text[ii] > '9')
{
TBResult.Text = "Data Error!";
return;
}
string number = "";
for (int ii = TBNumber.Text.ToString().Trim().Length - 1; ii >= 0; ii--)
number += TBNumber.Text[ii];
/*if (int.Parse(number) <= 0)
{
TBResult.Text = "Data Error!";
return;
}*/
string sql = "select * from addchaintable where nodevalue='" + number.ToString() + "'";
SqlDataAdapter adapter = new SqlDataAdapter(sql, conn);
DataSet ds = new DataSet();
adapter.Fill(ds);
DataTable dt = ds.Tables[0];
Int32 start, end;
if (dt.Rows.Count > 0)
{
output(Int32.Parse(dt.Rows[0]["id"].ToString()));
dt.Dispose();
ds.Dispose();
adapter.Dispose();
return;
}
else
{//数据库中尚未存储该节点的加法链，则先计算，然后输出它的最短加法链
while (true)
{
int hasfound = 0;//本次扩展时是否发现目标值
dt.Dispose();//释放资源
ds.Dispose();
adapter.Dispose();
string[] chain;
chain = new string[100];//存放start位置的节点所在的加法链
int c = 0;//当前加法链的大小
int level = 0;
sql = "select top 1 id,nodevalue,level from addchaintable where childcount = 0 order by id";
adapter = new SqlDataAdapter(sql, conn);
ds = new DataSet();
adapter.Fill(ds);
dt = ds.Tables[0];//重新从数据库中获取数据，获得start的值，即从此开始扩展树
start = Int32.Parse(dt.Rows[0]["id"].ToString());
level = Int32.Parse(dt.Rows[0]["level"].ToString());
//chain[c++] = dt.Rows[0]["nodevalue"].ToString();
sql = "select top 1 id from addchaintable order by id desc";
adapter = new SqlDataAdapter(sql, conn);
ds = new DataSet();
adapter.Fill(ds);
dt = ds.Tables[0];//重新从数据库中获取数据，获得start的值，即从此开始扩展树
end = Int32.Parse(dt.Rows[0]["id"].ToString());
Int32 j = start;
while (j > 0)
{
sql = "select nodevalue,parentposition from addchaintable where id =" + j.ToString();
adapter = new SqlDataAdapter(sql, conn);
ds = new DataSet();
adapter.Fill(ds);
dt = ds.Tables[0];
chain[c++] = dt.Rows[0]["nodevalue"].ToString();
j = Int32.Parse(dt.Rows[0]["parentposition"].ToString());
}
chain[c] = "1";
dt.Dispose();//释放资源
ds.Dispose();
adapter.Dispose();
int haschild = 0;
for (; c >= 0; c--)
{//将start位置的节点值与该加法链中前面的数值按从小到大的顺序相加
string testnumber = addnumber(chain[0].ToString(), chain[c].ToString());
SqlDataAdapter adaptersearch;
string sqlsearch = "select id from addchaintable where nodevalue='" + testnumber.ToString() + "'";
adaptersearch = new SqlDataAdapter(sqlsearch, conn);
DataSet dssearch = new DataSet();
adaptersearch.Fill(dssearch);
DataTable dtsearch = dssearch.Tables[0];
int found = dtsearch.Rows.Count;
dtsearch.Dispose();
dssearch.Dispose();
adaptersearch.Dispose();
if (found == 0)
{//树中尚无该节点值，则插入
end++;
string sqlinsert = "insert into addchaintable(id,level,nodevalue,parentposition,childcount) values('";
sqlinsert += end.ToString();
sqlinsert += "','";
sqlinsert += (level + 1).ToString();
sqlinsert += "','";
sqlinsert += testnumber.ToString();
sqlinsert += "','";
sqlinsert += start.ToString();
sqlinsert += "','0')";
DoSql(sqlinsert);
//更新父节点的子节点个数字段
haschild++;
if (compare(testnumber, number) == 0)
{
hasfound = end;
}
}
}
if (haschild == 0)
{//start位置上的节点没有子节点
string sqlupdate1 = "update addchaintable set childcount= -1 where id='" + start.ToString() + "'";
DoSql(sqlupdate1);
}
else
{
string sqlupdate1 = "update addchaintable set childcount= " + haschild.ToString() + " where id='" + start.ToString() + "'";
DoSql(sqlupdate1);
}
if (hasfound != 0)
{
output(hasfound);
dt.Dispose();//释放资源
ds.Dispose();
adapter.Dispose();
return;
}
Application.DoEvents();//若程序执行时间较长，可以响应其他事件
}
}
}
}
}
