انواع روشهای پيمايش عناصر درخت :
۱ - روش InOrder : در اين روش ابتدا عناصر نيمه سمت چپ درخت ، سپس ريشه و در آخر عناصر نيمه سمت راست درخت نمايش داده می شوند .
۲ - روش PreOrder : در اين روش ابتدا ريشه درخت ، سپس عناصر نيمه سمت چپ و در پايان عناصر نيمه سمت راست درخت نمايش داده می شوند .
۳ - روش PostOrder : در اين روش ابتدا عناصر نيمه سمت چپ درخت ، سپس عناصر نيمه سمت راست درخت و در پايان ريشه درخت نمايش داده می شوند .
بررسی متدهای کلاس CTree :
متد InsertNode : اگر گره ريشه برابر Null باشد value را برابر مقدار گره ريشه قرار می دهد . در غير اينصورت متد Insert مربوط به گره ريشه فراخوانی می شود .
متد PreorderTraversal : رشته چاپ عناصر ريشه را خالی می کند و سپس متد پيمايش Preorder را فراخوانی می کند .
متد InorderTraversal : رشته چاپ عناصر ريشه را خالی می کند و سپس متد پيمايش Inorder را فراخوانی می کند .
متد PostorderTraversal : رشته چاپ عناصر ريشه را خالی می کند و سپس متد پيمايش Postorder را فراخوانی می کند .
متد Get Output : عناصر پيمايش شده درخت را برمی گرداند .
يک برنامه نمونه :
ابتدا کلاسهای CTreeNode و CTree را به پروژه تان اضافه کنيد . سپس متغير زير را در قسمت کدنويسی فرمتان تعريف کنيد :

Dim mTree as New Ctree


سپس در فرمتان يک Textbox با نام Value و دو Command Button با نامهای Insert و Show قرار دهيد .
کد زير را برای وارد کردن عنصر به درخت برای دکمه Insert بنويسيد :

mTree.InsertNode(Value.Text)x


کد زير را برای پيمايش InOrder درخت برای دکمه Show بنويسيد :

Call mTree.InorderTraversal


شي Collection :
ويژوال بيسيک داراي شي پيش ساخته اي به نام Collection است که مي تواند مجموعه اي از مقادير با هر نوع داده اي را در خود ذخيره کند . در واقع عناصر موجود در يک Collection مي توانند داراي نوعهاي داده اي متفاوت باشند . شي Collection قابليت رشد ديناميک دارد .
شي Collection توسط کلمه کليدي New ايجاد مي شوند . توسط متد Add مي توان به Cllection عضو اضافه کرد و توسط متد Remove مي توان عضوي را از آن حذف کرد . هر عضو از Collection توسط متد Item قابل دستيابي است . با استفاده از خاصيت Count مي توان تعداد اعضاي موجود در Collection را تعيين نمود . بصورت پيش فرض اعضاي جديد به انتهاي Collection اضافه مي شوند ولي توسط آرگومانهاي اختياري متد Add مي توان محل اضافه شدن را تغيير داد .
متد Remove يک شماره مي گيرد که موقعيت عضوي را که مي خواهيم آنرا حذف کنيم مشخص مي کند .
توسط دستورات زير مي توان اعضاي يک Collection را نمايش داد :

Dim mCollection as New Collection
Dim element as Variant
.
.
.
For Each element In mCollection
Msgbox element


element متغيري از نوع variant براي اشاره به هر عضو Collection مي باشد .

کلاس درختهای جستجوی باينری

برای ايجاد درختهای جستجوی باينری در ويژوال بيسيک نياز به ايجاد دو کلاس داريم :
1 - کلاس CTreeNode که هر ند درخت دودويي را توصيف می کند . اين کلاس دارای يک متغير به نام mNodeData از نوع Variant برای نگهداری داده هر گره است . همچنين دارای دو متغير اشاره گر به نامهای mLeft و mRight می باشد که به ترتيب به فرزند چپ و فرزند راست درخت اشاره می کنند .
متد Get Data مقدار داده هر گره را بر می گرداند و متد Let Data مقدار داده هر گره را تنظيم می کند .
متد Get Left آدرس فرزند چپ هر گره را برمی گرداند و متد Let Left فرزند چپ هر گره را تنظيم می کند .
متد Get Right آدرس فرزند راست هر گره را برمی گرداند و متد Let Right فرزند راست هر گره را تنظيم می کند .
متد Insert برای اضافه کردن فرزند به يک گره به کار می رود . اگر مقدار گره ای که می خواهيم بعنوان فرزند به درخت اضافه کنيم کوچکتر از مقدار خود گره باشد بعنوان فرزند چپ و در غير اينصورت بعنوان فرزند راست به گره اضافه می شود . اضافه شدن نيز بدين صورت است که ابتدا بررسی می شود آیا گره قبلاً فرزندی داشته است يا نه ؟ اگر نداشته باشد ( mLeft و يا mRight برابر Nothing باشد ) اين گره جديد مستقيماً به گره متصل می شود اما اگر گره قبلاً فرزندی داشته باشد متد Insert برای آن فرزند اضافه می شود و اينکار تا جايی ادامه می يابد که به گره ای برسيم که فرزندی نداشته باشد :

Private mLeft as CtreeNode
Private mRight as CtreeNode
Private mNodeData as Variant

Public Property Get Data() as variant
Data=mNodeData
End property
Public Property Let Data(Byval vNewValue as Variant)x
MNodeData=vNewValue
End property
Public Property Get Left() as variant
Set Left=mLeft
End property
Public Property Let Left(Byval vNewValue as variant)x
Set mLeft=vNewValue
End property

Public Property Get Right() as variant
Set Right=mRight
End Property
Public Property Let Right(Byval vNewValue as variant)x
Set mRight=vNewValue
End Property

Public Sub Insert(value as variant)x
If valueIf mLeft Is Nothing Then
Set mLeft=New CtreeNode
MLeft.Data=value
Else
MLeft.Insert(value)x
End if
Elseif value>mNodeData then
If mRight Is Nothing then
Set mRight=New CtreeNode
MRight.Data=value
Else
MRight.Insert(value)x
End if
End if
End sub


2 - کلاس CTree : اين کلاس برای ايجاد درخت بکار می رود . اين کلاس دارای متغيری بنام mRoot از نوع CTreeNode برای تعريف ريشه درخت است . همچنين يک متغير mOutputString برای نمايش دادن اعضای درخت دارد .

Private mRoot as CtreeNode
Private mOutputString as String

Public Sub InsertNode(value as Varaint)x
If mRoot Is Nothing then
Set Mnode=New CtreeNode
MRoot.Data=value
Else
MRoot.Insert(value)x
End if
End sub

Public PreorderTraversal()x
MOutputString=””x
Call PreorderHelper(mRoot)x
End sub

Private Sub PreorderHelper(node As CtreeNode)x
If node Is nothing Then
Exit sub
End if
MOutputString=mOutputString & node.Data & “ “x
Call PreorderHelper(node.left)x
Call PreorderHelper(node.right)x
End sub

Public Sub InorderTraversal()x
MOutputString=””x
Call InorderHelper(mRoot)x
End sub

Private Sub InorderHelper(node as CtreeNode)x
If node Is nothing then
Exit sub
End if
Call InorderHelper(node.Left)x
MOutputString=mOutputString & node.Data & “ “x
Call InorderHelper(node.Right)x
End sub

Public PostorderTraversal()x
MOutputString=””x
Call PostorderHelper(mRoot)x
End sub

Private Sub PostorderHelper(node as CtreeNode)x
If node Is Nothing then
Exit sub
End if
Call PostorderHelper(node.Left)x
Call PostorderHelper(node.Right)x
MOutputString=mOutputString & node.Data & “ “x
End sub

Public Property Get Output() as Varaint
Output=mOutputString
End Property

مثالی از استفاده از کلاسهای ليست پيوندی :
ابتدا کلاسهايي که در جلسه قبل معرفی شد را به پروژه تان اضافه کنيد . سپس در بخش کدنويسی فرمتان ، ابتدا يک شی از نوع کلاس Clist بصورت زير تعريف کنيد :

Dim list as New Clist


در فرمتان سه CommandButton با نامهای AddFirst ، AddLast و ShowList و نيز يک TextBox با نام ListMember قرار دهيد .
کد زير را برای رويداد کليک شدن دکمه AddFirst بنويسيد :

Call list.InsertAtFront(ListMember.text)x


کد زير را برای رويداد کليک شدن دکمه AddLast بنويسيد :

Call list.InsertAtBack(ListMember.text)x


کد زير را برای رويداد کليک شدن دکمه ShowList بنويسيد :

Dim elements as New ClistIterator
Set elements=list.Iterator
If elements.HasMoreItems=false then msgbox ("list is empty")x
Else
While elements.HasMoreItems
Msgbox(elements.NextItem)x
Wend
end if

پشته :
پشته نوعي ليست پيوندي است که گره هاي جديد ، فقط به انتهاي آن مي توانند اضافه شوند . بهمين دليل به پشته ، ساختمان داده LIFO مي گويند . قسمت لينک آخرين گره پشته با Nothing مقدار دهي مي شود که نشان دهنده پايين پشته است .
روالهاي اصلي پشته Push و Pop هستند .
Push يک گره جديد به بالاي پشته اضافه مي کند و Pop از بالاي پشته گره اي را حذف کرده و مقدار داده آن را بر مي گرداند .

ليست پيوندي

همانطور که گفته شد ليست پيوندي مجموعه اي از يکسري داده است که اين داده ها از نوع اشيا خودارجاعي هستند . ( هر شي خودارجاعي داراي يک متغير نوع variant براي نگهدار مقدار و يک اشاره گر به شي بعدي است ) . هر عضو ليست پيوندي را يک گره گويند . هر ليست پيوندي از طريق يک اشاره گر به اولين گره قابل دسترسي است . گره هاي بعدي از طريق قسمت لينک موجود در هر گره قابل دسترس هستند . همچنين لينک آخرين گره با Nothing تنظيم مي شود که انتهاي ليست را نشان مي دهد .
مزيت اصلي ليست هاي پيوندي نسبت به آرايه اينست که تعداد عناصر ليست پيوندي قابل تغيير است . بعبارت ديگر ليست هاي پيوندي بصورت ديناميک هستند و طول آنها قابل تغيير است اما سايز آرايه ثابت است . ( البته ويژوال بيسطک از آرايه هاي با سايز متغير نيز پشتيباني مي کند اما اين عمل تغيير سايز اتوماتيک نيست .)
عمل درج در ليست پيوندي ساده است و تنها بايستي دو اشاره گر تغيير يابد .
ليست هاي پيوندي را مي توان به سادگي با قراردادن هر عضو جديد در محل صحيح بصورت sortشده نگهداري کرد .
اعضاي ليست پيوندي در حافظه بصورت پيوسته ذخيره نمي شوند بنابراين نمي توان فوراً به هر عضو ليست دسترسي داشت ( بر خلاف آرايه ) .
براي ايجاد ليست پيوندي در ويژوال بيسيک نياز به سه کلاس است :

 

مقدمه :

ساختارهاي داده اي از نظر تعداد اعضا به دو دسته استاتيک و ديناميک تقسيم مي شوند . ساختارهاي استاتيک مثل آرايه هاي يک بعدي و آرايه هاي دو بعدي ، تعداد اعضاي آنها در زمان طراحي برنامه مشخص مي شود و در طول اجراي برنامه ثابت است اما تعداد اعضاي ساختارهاي داده اي ديناميک در طول اجراي برنامه تغيير مي کند . ليست پيوندي ( LinkList ) ، پشته ( Stack ) ، صف ( Queue ) و درختهاي باينري ( Tree Binary) ، نمونه هايي از ساختارهاي داده اي ديناميک هستند .
ليست پيوندي شامل مجموعه اي از عناصر داده اي است که اضافه و حذف اعضا در هر جاي ليست ممکن است .
پشته يک ساختار داده اي مهم در کامپايلرها و سيستم هاي عامل است که عمل اضافه و حذف عناصر از ابتداي آن انجام مي شود .
صف يک ساختار داده اي است که عمل اضافه کردن از انتها و عمل حذف کردن از ابتداي آن انجام مي شود .
درختهاي دودويي براي جستجوي بسيار سريع ، ذخيره سازي داده ها و کامپايل عبارات استفاده مي شوند .

نوع داده Variant :

نوع داده variant براي متغيرهايي بکار مي رود که بطور صريح نوع آنها تعريف نشده است مثال :
Dim value As Variant
اين نوع داده مي تواند هر نوع داده اي را در خود ذخيره کند . همچنين براي ايجاد ساختارهاي داده اي مثل ليست هاي پيوندي ، صف ، پشته و درخت مناسب است .
نوع داده موجود در variant مي توان توسط توابع VarType و TypeName تعيين کرد . تابع VarType يک مقدار صحيح برمي گرداند که نشان دهنده نوع ذخيره شده در variant است .
مثال :
Dim value as Variant
value=”Hello”x
در اينصورت مقدار بازگشتي ( VarType( value برابر 4 خواهد بود .
تابع TypeName يک رشته برمي گرداند که نشان دهنده نام نوع داده ذخيره شده در variant است .

اخذ حافظه بطور ديناميک Dynamic Memory Allocation :

براي ايجاد و نگهداري ساختارهاي داده اي ديناميک بايستي در هنگام اجراي برنامه بتوان فضاي بيشتري براي نگهداري داده هاي جديد بدست آورد . با استفاده از کلمه کليدي New مي توان در ويژوال بيسيک حاقظه ديناميک گرفت :
Set NewNode=New ListNode
که ListNode يک شي از ساختار داده اي مورد نظر ماست .

کلاسهاي خود ارجاعي :

کلاس خودارجاعي نوعي کلاس است که داراي يک اشاره گر ( Pointer ) به يک شي از همان نوع کلاس باشد . براي مثال اگر کلاس ما به اسم ClistNode باشد و متغير زير را در آن تعريف کنيم ، اين کلاس يک کلاس خود ارجاعي است :
Private mNextNode as ClistNode
از mNextNode براي لينک دادن اعضاي يک ساختار داده اي ديناميک بهم استفاده مي شود ( بعبارت ديگر گره زدن يک شي از کلاس ClistNode به يک شي ديگر از همان کلاس ) . شي هاي خودارجاعي مي توانند به همديگر لينک شوند و ساختارهاي داده اي مثل ليست پيوندي ، صف ، پشته و درخت را ايجاد کنند .
شکل زير دو شي خود ارجاعي را نشان مي دهد که بصورت يک ليست بهم لينک شده اند . عبارت NULL بدين معنا است که شي خودارجاعي به شي ديگري اشاره نمي کند ( Nothing ) و نشان دهنده انتهاي ساختار داده است .

ايجاد ساختارهاي داده اي در ويژوال بيسيک - بخش پايانی

انواع روشهای پيمايش عناصر درخت :
۱ - روش InOrder : در اين روش ابتدا عناصر نيمه سمت چپ درخت ، سپس ريشه و در آخر عناصر نيمه سمت راست درخت نمايش داده می شوند .
۲ - روش PreOrder : در اين روش ابتدا ريشه درخت ، سپس عناصر نيمه سمت چپ و در پايان عناصر نيمه سمت راست درخت نمايش داده می شوند .
۳ - روش PostOrder : در اين روش ابتدا عناصر نيمه سمت چپ درخت ، سپس عناصر نيمه سمت راست درخت و در پايان ريشه درخت نمايش داده می شوند .
مثال : درخت زير را در نظر بگيريد :

مثالی از استفاده از کلاسهای ليست پيوندی :
ابتدا کلاسهايي که در جلسه قبل معرفی شد را به پروژه تان اضافه کنيد . سپس در بخش کدنويسی فرمتان ، ابتدا يک شی از نوع کلاس Clist بصورت زير تعريف کنيد :

Dim list as New Clist


در فرمتان سه CommandButton با نامهای AddFirst ، AddLast و ShowList و نيز يک TextBox با نام ListMember قرار دهيد .
کد زير را برای رويداد کليک شدن دکمه AddFirst بنويسيد :

Call list.InsertAtFront(ListMember.text)x


کد زير را برای رويداد کليک شدن دکمه AddLast بنويسيد :

Call list.InsertAtBack(ListMember.text)x


کد زير را برای رويداد کليک شدن دکمه ShowList بنويسيد :

Dim elements as New ClistIterator
Set elements=list.Iterator
If elements.HasMoreItems=false then msgbox ("list is empty")x
Else
While elements.HasMoreItems
Msgbox(elements.NextItem)x
Wend
end if



پشته :
پشته نوعي ليست پيوندي است که گره هاي جديد ، فقط به انتهاي آن مي توانند اضافه شوند . بهمين دليل به پشته ، ساختمان داده LIFO مي گويند . قسمت لينک آخرين گره پشته با Nothing مقدار دهي مي شود که نشان دهنده پايين پشته است .
روالهاي اصلي پشته Push و Pop هستند .
Push يک گره جديد به بالاي پشته اضافه مي کند و Pop از بالاي پشته گره اي را حذف کرده و مقدار داده آن را بر مي گرداند .


در بخش چهارم کلاسی را برای کار با پشته معرفی خواهم کرد .

ايجاد ساختارهاي داده اي در ويژوال بيسيک - بخش دوم

ليست پيوندي

همانطور که گفته شد ليست پيوندي مجموعه اي از يکسري داده است که اين داده ها از نوع اشيا خودارجاعي هستند . ( هر شي خودارجاعي داراي يک متغير نوع variant براي نگهدار مقدار و يک اشاره گر به شي بعدي است ) . هر عضو ليست پيوندي را يک گره گويند . هر ليست پيوندي از طريق يک اشاره گر به اولين گره قابل دسترسي است . گره هاي بعدي از طريق قسمت لينک موجود در هر گره قابل دسترس هستند . همچنين لينک آخرين گره با Nothing تنظيم مي شود که انتهاي ليست را نشان مي دهد .
مزيت اصلي ليست هاي پيوندي نسبت به آرايه اينست که تعداد عناصر ليست پيوندي قابل تغيير است . بعبارت ديگر ليست هاي پيوندي بصورت ديناميک هستند و طول آنها قابل تغيير است اما سايز آرايه ثابت است . ( البته ويژوال بيسطک از آرايه هاي با سايز متغير نيز پشتيباني مي کند اما اين عمل تغيير سايز اتوماتيک نيست .)
عمل درج در ليست پيوندي ساده است و تنها بايستي دو اشاره گر تغيير يابد .
ليست هاي پيوندي را مي توان به سادگي با قراردادن هر عضو جديد در محل صحيح بصورت sortشده نگهداري کرد .
اعضاي ليست پيوندي در حافظه بصورت پيوسته ذخيره نمي شوند بنابراين نمي توان فوراً به هر عضو ليست دسترسي داشت ( بر خلاف آرايه ) .
براي ايجاد ليست پيوندي در ويژوال بيسيک نياز به سه کلاس است :

1 – کلاس ClistNode :

2 – کلاس Clist براي توصيف ليست پيوندي .
3 – کلاس ClistIterator :