Public Class Form1 ‘M3P31 資料結構-是否為樹
Const MaxN As Integer = 20
Dim adj(MaxN, MaxN) As
Boolean
Dim nds(MaxN) As Boolean
Private Sub
Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
Me.Hide()
FileOpen(1,
"in1.txt", OpenMode.Input)
FileOpen(2,
"in2.txt", OpenMode.Input)
FileOpen(3,
"out.txt", OpenMode.Output)
For fn = 1 To 2
If fn = 2 Then
PrintLine(3)
Dim n As Short =
LineInput(fn)
For k = 1 To n
Dim s As
String = LineInput(fn)
PrintLine(3,
m3p31(s))
Next
Next
End
End Sub
Function m3p31(ByVal s As
String) As String
m3p31 = "T"
ttrim(s, " ", " ") : ttrim(s, ",
", ",") : ttrim(s, " ,", ",") ‘2空轉1空、 去逗後空、 去逗前空
Dim egs() =
s.Split(" ")
Dim egcnt As Integer =
egs.Length '邊數
Dim st As Integer ' dfs的起點
Array.Clear(adj, 0,
MaxN * MaxN) : Array.Clear(nds, 0, MaxN)
For i = 0 To egcnt - 1
Dim xy() =
egs(i).Split(",")
Dim x As Integer =
xy(0), y As Integer = xy(1)
adj(x, y) = True :
adj(y, x) = True
nds(x) = True :
nds(y) = True
st = x
Next
Dim ndcnt As Integer =
0 '節點數
For i = 0 To MaxN
If nds(i) Then
ndcnt += 1
Next
If ndcnt <>
egcnt + 1 Then
Return
"F"
Else
dfs(st)
For i = 0 To MaxN
If nds(i) Then
Return "F" '有節點未訪
Next
End If
End Function
Sub dfs(ByVal st As
Integer)
nds(st) = False '訪過 註銷
For v = 0 To MaxN
If nds(v) And
adj(st, v) Then dfs(v)
Next
End Sub
Sub ttrim(ByRef s As
String, ByVal a As String, ByVal b As String) ‘將a 取代為 b
Do Until InStr(s, a) =
0
s = s.Replace(a,
b)
Loop
End Sub
End Class
Public Class Form1 ‘M3P32 資料結構-樹葉節點到根節點之路徑
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles MyBase.Load
FileOpen(1, "in1.txt", OpenMode.Input)
FileOpen(2, "in2.txt", OpenMode.Input)
FileOpen(3, "out.txt", OpenMode.Output)
For fn = 1 To 2
If fn=2 Then PrintLine(3)
Dim n As Integer = LineInput(fn)
For i = 1 To n
If i > 1 Then LineInput(fn)
Dim nds As Integer =
LineInput(fn)
Dim par(100) As Integer '父是誰
Dim chi(100) As Boolean '是否有子？
For j = 1 To nds
Dim xy() =
LineInput(fn).Split(",")
Dim x As Integer = xy(0), y
As Integer = xy(1)
par(x) = y ' x 的父是 y
chi(y) = True ' y 有子
Next
Rem 以下為測試用多印的
For j = 0 To nds - 1 '印各節點的父，是否有子？
Print(3, j & ":
" & par(j) & " :" & IIf(chi(j), "Y",
"N") & " ")
Next
PrintLine(3)
Rem 以上為多印的
For j = 0 To nds - 1
If Not chi(j) Then ‘沒有兒子即是葉節點
Dim cnt = 0
Dim s As String =
""
Dim p = par(j)
Do Until par(p) = 99
If cnt > 0 Then
s &= ("," & p) Else s &= p
cnt += 1
p = par(p)
Loop
If cnt > 0 Then s =
"{" & s & "}" Else s = "N"
PrintLine(3, j &
":" & s)
End If
Next
Next
Next
End
End Sub End Class
發表文章
