ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش اول
مقدمه
ساختارهای داده ای از نظر تعداد اعضا به دو دسته استاتیک و دینامیک تقسیم می شوند . ساختارهای استاتیک مثل آرایه های یک بعدی و آرایه های دو بعدی ، تعداد اعضای آنها در زمان طراحی برنامه مشخص می شود و در طول اجرای برنامه ثابت است اما تعداد اعضای ساختارهای داده ای دینامیک در طول اجرای برنامه تغییر می کند . لیست پیوندی ( LinkList ) ، پشته ( Stack ) ، صف ( Queue ) و درختهای باینری ( Tree Binary) ، نمونه هایی از ساختارهای داده ای دینامیک هستند .
لیست پیوندی شامل مجموعه ای از عناصر داده ای است که اضافه و حذف اعضا در هر جای لیست ممکن است .
پشته یک ساختار داده ای مهم در کامپایلرها و سیستم های عامل است که عمل اضافه و حذف عناصر از ابتدای آن انجام می شود .
صف یک ساختار داده ای است که عمل اضافه کردن از انتها و عمل حذف کردن از ابتدای آن انجام می شود .
درختهای دودویی برای جستجوی بسیار سریع ، ذخیره سازی داده ها و کامپایل عبارات استفاده می شوند .
نوع داده Variant :
نوع داده variant برای متغیرهایی بکار می رود که بطور صریح نوع آنها تعریف نشده است مثال :
این نوع داده می تواند هر نوع داده ای را در خود ذخیره کند . همچنین برای ایجاد ساختارهای داده ای مثل لیست های پیوندی ، صف ، پشته و درخت مناسب است .
نوع داده موجود در variant می توان توسط توابع VarType و TypeName تعیین کرد . تابع VarType یک مقدار صحیح برمی گرداند که نشان دهنده نوع ذخیره شده در variant است .
مثال :
در اینصورت مقدار بازگشتی ( VarType( value برابر 4 خواهد بود .
تابع TypeName یک رشته برمی گرداند که نشان دهنده نام نوع داده ذخیره شده در variant است .
اخذ حافظه بطور دینامیک Dynamic Memory Allocation :
برای ایجاد و نگهداری ساختارهای داده ای دینامیک بایستی در هنگام اجرای برنامه بتوان فضای بیشتری برای نگهداری داده های جدید بدست آورد . با استفاده از کلمه کلیدی New می توان در ویژوال بیسیک حاقظه دینامیک گرفت :
Set NewNode=New ListNode
که ListNode یک شی از ساختار داده ای مورد نظر ماست .
کلاسهای خود ارجاعی:
کلاس خودارجاعی نوعی کلاس است که دارای یک اشاره گر ( Pointer ) به یک شی از همان نوع کلاس باشد . برای مثال اگر کلاس ما به اسم ClistNode باشد و متغیر زیر را در آن تعریف کنیم ، این کلاس یک کلاس خود ارجاعی است :
از mNextNode برای لینک دادن اعضای یک ساختار داده ای دینامیک بهم استفاده می شود ( بعبارت دیگر گره زدن یک شی از کلاس ClistNode به یک شی دیگر از همان کلاس ) . شی های خودارجاعی می توانند به همدیگر لینک شوند و ساختارهای داده ای مثل لیست پیوندی ، صف ، پشته و درخت را ایجاد کنند .
شکل زیر دو شی خود ارجاعی را نشان می دهد که بصورت یک لیست بهم لینک شده اند . عبارت NULL بدین معنا است که شی خودارجاعی به شی دیگری اشاره نمی کند ( Nothing ) و نشان دهنده انتهای ساختار داده است .
ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش دوم
لیست پیوندی
همانطور که گفته شد لیست پیوندی مجموعه ای از یکسری داده است که این داده ها از نوع اشیا خودارجاعی هستند . ( هر شی خودارجاعی دارای یک متغیر نوع variant برای نگهدار مقدار و یک اشاره گر به شی بعدی است ) . هر عضو لیست پیوندی را یک گره گویند . هر لیست پیوندی از طریق یک اشاره گر به اولین گره قابل دسترسی است . گره های بعدی از طریق قسمت لینک موجود در هر گره قابل دسترس هستند . همچنین لینک آخرین گره با Nothing تنظیم می شود که انتهای لیست را نشان می دهد .
مزیت اصلی لیست های پیوندی نسبت به آرایه اینست که تعداد عناصر لیست پیوندی قابل تغییر است . بعبارت دیگر لیست های پیوندی بصورت دینامیک هستند و طول آنها قابل تغییر است اما سایز آرایه ثابت است . ( البته ویژوال بیسطک از آرایه های با سایز متغیر نیز پشتیبانی می کند اما این عمل تغییر سایز اتوماتیک نیست .)
عمل درج در لیست پیوندی ساده است و تنها بایستی دو اشاره گر تغییر یابد .
لیست های پیوندی را می توان به سادگی با قراردادن هر عضو جدید در محل صحیح بصورت sortشده نگهداری کرد .
اعضای لیست پیوندی در حافظه بصورت پیوسته ذخیره نمی شوند بنابراین نمی توان فوراً به هر عضو لیست دسترسی داشت ( بر خلاف آرایه ) .
برای ایجاد لیست پیوندی در ویژوال بیسیک نیاز به سه کلاس است :
1 – کلاس ClistNode : کلاسی است که هر گره از لیست را توصیف می کند :
2 – کلاس Clist برای توصیف لیست پیوندی .
mFirstNode برای اشاره به اولین ClistNode و mLastNode برای اشاره به آخرین ClistNode در یک شی clist بکار می رود . زمانیکه یک Clsit ایجاد می شود این دو متغیر با Nothing تنظیم می شوند . روال Property Get Iterator یک شی ClistIterator برمی گرداند که می توان از آن برای حرکت در بین اعضای لیست استفاده کرد .
عملکرد روال InsertAtFront :
a – فراخوانی IsEmpty برای تعیین خالی بودن لیست
b – اگر لیست خالی باشد mFirstNode و mLastNode به New ClsitNode اشاره می کنند .
c – اگر لیست خالی نباشد گره جدید توسط اشاره دادن tempNode به اولین گره لیست و سپس اشاره دادن mFirstNode به گره New ClsitNode و سپس اشاره دادن mFirstNode.NextNode به tempNode ساخته می شود .
d – تنظیم mFirstNode.Data با مقدار مورد نظر
عملکرد روال InsertAtBack :
a – فراخوانی IsEmpty برای تعیین خالی بودن لیست
b – اگر لیست خالی باشد mFirstNode و mLastNode به New ClsitNode اشاره می کنند .
c – اگر لیست خالی نباشد گره جدید توسط اشاره دادن tempNode به آخرین گره لیست و سپس اشاره دادن mLastNode به گره New ClsitNode و سپس اشاره دادن tempNode.NextNode به mLastNode ساخته می شود .
d – تنظیم mLastNode.Data با مقدار مورد نظر
عملکرد روال RemoveFromFront :
a – اگر لیست خالی باشد Null برگشت داده می شود .
b – اگر لیست خالی نباشد داده mFirstNode به removeItem اختصاص داده می شود .
c – اگر لیست فقط یک گره داشته باشد mFirstNode و mLastNode با Nothing مقدار دهی می شوند و گره از لیست حذف می شود .
d – اگر گره بیش از یک عضو داشته باشد mFirstNode برابر mFirstNode.NextNode می شود .
e – مقدار removeItem برگشت داده می شود .
عملکرد روال RemoveFromBack :
a – اگر لیست خالی باشد Null برگشت داده می شود .
b – اگر لیست خالی نباشد داده mLastNode به removeItem اختصاص داه می شود .
c – اگر لیست یک گره داشته باشد mFirstNode و mLastNode با Nothing مقدار دهی می شوند و گره از لیست حذف می شود .
d – اگر لیست بیش از یک گره داشته باشد متغیر current برابر mFirstNode می شود . سپس با استفاده از current روی گره های لیست حرکت می کنیم تا به گره ای برسیم که به آخرین گره اشاره می کند . سپس mLastNode را به گره ای که current به آن اشاره می کند قرار می دهیم و مقدار current.NextNode را Nothing می کنیم تا بعنوان آخرین گزه لیست معرفی شود .
e – مقدار removeItem برگشت داده می شود .
3 – کلاس ClistIterator : این کلاس برای حرکت روی گره های لیست و دستکاری هر گره بکار می رود . از حرکت کننده ها برای چاپ لیست و یا انجام دادن عملی بر روی هر عضو Clist می توان استفاده کرد . این کلاس دارای دو متغیر از نوع ClistNode به نامهای mBookmark و mFirstNode است . متغیر mFirstNode به اولین گره در Clist اشاره می کند و متغیر mBookmark موقعیت فعلی حرکت کننده بر روی Clist را نشان می دهد . روال Property Let StartNode این دو متغیر را مقدار دهی اولیه می کند . تابع NextItem اگر مقدار mBookmark برابر Null باشد ، Null برگشت می دهد و در غیراینصورت مقدار tempData را برابر mBookmark.Data و مقدار mBookmark را برابر mBookmark.NextNode قرار می دهد . تابع HasMoreItems اگر لیست دارای چندین عضو باشد True برمی گرداند . روال ResetBookmark حرکت کننده را به ابتدای لیست منتقل می کند .
در بخش سوم نمونه برنامه ای را با استفاده از این کلاسها خواهیم ساخت .
ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش سوم
مثالی از استفاده از کلاس های لیست پیوندی:
ابتدا کلاسهایی که در جلسه قبل معرفی شد را به پروژه تان اضافه کنید . سپس در بخش کدنویسی فرمتان ، ابتدا یک شی از نوع کلاس Clist بصورت زیر تعریف کنید :
در فرمتان سه CommandButton با نامهای AddFirst ، AddLast و ShowList و نیز یک TextBox با نام ListMember قرار دهید .
کد زیر را برای رویداد کلیک شدن دکمه AddFirst بنویسید :
کد زیر را برای رویداد کلیک شدن دکمه AddLast بنویسید :
Call list.InsertAtBack(ListMember.text)x
کد زیر را برای رویداد کلیک شدن دکمه ShowList بنویسید :
پشته:
پشته نوعی لیست پیوندی است که گره های جدید ، فقط به انتهای آن می توانند اضافه شوند . بهمین دلیل به پشته ، ساختمان داده LIFO می گویند . قسمت لینک آخرین گره پشته با Nothing مقدار دهی می شود که نشان دهنده پایین پشته است .
روالهای اصلی پشته Push و Pop هستند .
Push یک گره جدید به بالای پشته اضافه می کند و Pop از بالای پشته گره ای را حذف کرده و مقدار داده آن را بر می گرداند .
ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش چهارم
کلاس پشته:
همانطور که در بخش قبل گفته شد پشته نوعی لیست پیوندی است که گره های جدید فقط به انتهای آن اضافه شوند . روالهای اصلی پشته Push و Pop هستند .
Push یک گره جدید به بالای پشته اضافه می کند و Pop از بالای پشته گره ای را حذف کرده و مقدار داده آن را بر می گرداند .
یک کلاس پشته را با استفاده از کلاس Clist و بصورت زیر پیاده سازی می کنیم :
Private list As New Clist
Public Sub Push(value as Variant)x
List.InsertAtFront(value)x
End sub
Public Function Pop As Variant
Pop=list.RemoveFromFront()x
End Function
Public Function IsStackEmpty() As Boolean
IsStackEmpty=list.IsEmpty()x
End function
Public Property Get Iterator() as variant
Set Iterator=list.Iterator
End Property
در این کلاس ابتدا یک شی از نوع کلاس Clist تعریف شده است . سپس متدهای Push توسط متد InsertAtFront و Pop توسط متد RemoveFromFront پیاده سازی شده اند .
یک برنامه نمونه:
برای نوشتن یک برنامه برای کار با پشته ابتدا کلاس Stack را که کد آن را در بالا دیدید به پروژه تان اضافه کنید . سپس در بخش کد مربوط به فرمتان ابتدا یک شی از نوع کلاس Stack بصورت زیر تعریف کنید :
Dim mStack as New Stack
سپس در فرمتان سه CommandButton با نامهای Push و Pop و ShowStack و نیز یک TextBox با نام StackMember قرار دهید .
کد زیر را برای کلیک شدن دکمه Push بنویسید :
mStack.push(StackMember.text)x
کد زیر را برای کلیک شدن دکمه Pop بنویسید :
StackMember.text=mStack.Pop()x
کد زیر را برای کلیک شدن دکمه ShowStack بنویسید :
Dim elements as New ClistIterator
Set elements=mStack.Iterator
If elements.HasMoreItems=false then msgbox "stack is empty"x
Else
While elemets.HasMoreItems
Msgbox elements.NextItem
Wend
ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش پنجم
صف :
صف نوعی ساختار داده ای است که گره ها از ابتدای صف ( سر صف head ) حذف می شوند و از انتهای صف ( ته صف tail ) اضافه می شوند . بنابر این ، صف یک ساختار داده ای FIFO است . صف دارای دو متد به نامهای AddQueue و DelQueue است که اولین متد ، عنصری را به انتهای صف اضافه می کند و دومین متد ، عنصری را از ابتدای صف حذف می کند .
برای ایجاد کلاس Cqueue از کلاس Clist استفاده می کنیم :
Private list as New Clist
Public Sub AddQueue(value as Variant)x
List.InsertAtBack(value)
End sub
Public Function DelQueue() as Variant
DelQueue=list.RemoveFromFront
End function
Public property Get Iterator() as Variant
Set Iterator=list.Iterator
End Property
درخت :
لیستهای پیوندی ، پشته ها و صف ها جزو ساختارهای داده ای خطی هستند در حالیکه یک درخت ، یک ساختار داده ای دو بعدی با خصوصیات ویژه ای است . گره های درخت دارای دو یا چند لینک هستند . در اینجا در مورد درختهای دودویی یا باینری بحث می کنیم که در آن همه گره ها دارای دو لینک هستند . گره ریشه اولین گره در درخت است . هر لینک گره ریشه ، به یک فرزند اشاره می کند . به فرزندان یک گره Siblings می گویند . به گره بدون فرزند ، برگ یا Leaf گفته می شود .
درختهای جستجوی باینری درخت هایی هستند که در آنها مقدار فرزند چپ هر گره کمتر از گره پدر و مقدار فرزند سمت راست هر گره بیشتر از گره پدر می باشد .
ایجاد ساختارهای داده ای در ویژوال بیسیک - بخش پایانی
انواع روشهای پیمایش عناصر درخت :
۱ - روش InOrder : در این روش ابتدا عناصر نیمه سمت چپ درخت ، سپس ریشه و در آخر عناصر نیمه سمت راست درخت نمایش داده می شوند .
۲ - روش PreOrder : در این روش ابتدا ریشه درخت ، سپس عناصر نیمه سمت چپ و در پایان عناصر نیمه سمت راست درخت نمایش داده می شوند .
۳ - روش PostOrder : در این روش ابتدا عناصر نیمه سمت چپ درخت ، سپس عناصر نیمه سمت راست درخت و در پایان ریشه درخت نمایش داده می شوند .
مثال : درخت زیر را در نظر بگیرید :
نتیجه پیمایش InOrder درخت : 1,3,4,5,6,7,8
نتیجه پیمایش PreOrder درخت : 5,3,1,4,7,6,8
نتیجه پیمایش PostOrder درخت : 1,4,3,6,8,7,5
بررسی متدهای کلاس 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 می باشد .
تست هایی برای ایجاد ساختارهای داده ای در ویژوال بیسیک
۱.نوع داده Variant برای ایجاد چه ساختارهای داده ای مناسب است؟
الف)پیوندی ب)صف
ج)پشته و درخت د)همه موارد
۲.مزیت اصلی لیست های پیوندی نسبت به آرایه اینست که تعداد عناصر لیست پیوندی............
الف)قابل تغییراست ب)قابل تغییرنیست
ج)قابل حذف است د)همه موارد
۳.کلاس ClistNode چه نوع کلاسی است؟
الف)کلاسی است که هر گره از لیست را توصیف می کند
ب)کلاسی است برای توصیف لیست پیوندی
ج)این کلاس برای حرکت روی گره های لیست ودستکاری هرگره بکارمیرود
د)هیچکدام
۴.پشته نوعی لیست پیوندی است که گره های جدید ، فقط میتوانندبه........
الف)ابتدای آنها اضافه میشود
ب)انتهای آن اضافه میشود
ج)وسط آن اضافه میشود
د)اصلا اضافه نمیشود