PDA

View Full Version : لیست پیوندی در سی شارپ



hassan_kahrizy
سه شنبه 22 آذر 1384, 15:11 عصر
بسمه تعالی
با سلام خدمت دوستان
می شه نحوه پیاده سازی لیست پیوندی در سی شارپ رو توضح بدید؟

shahab_ss
سه شنبه 22 آذر 1384, 18:18 عصر
dar c# chizi be name pointer vojod nadare ama age bekhay az oon estefadeh koni bayad ebarate UNSAFE ro ghabl az tabeii ke mikhay toosh az pointer estefade koni benevisi.baraye etela ate bishtar donbale hamon ebarat search kon.

ARA
چهارشنبه 30 آذر 1384, 00:26 صبح
میتونی یک کلاس که عضو قبل و بعدش رو بشناسه تعریف کنی دیگه مشکل اشاره گر و دردسر هاش رو هم ندازی من یک درخت اینجوری پیاده سازی کردم برای پروژه هوش مصنوعی

hassan_kahrizy
یک شنبه 04 دی 1384, 02:04 صبح
بسمه تعالی
با سلام
می شه یک مثال بزنید
با تشکر

Artz_6
جمعه 18 اسفند 1385, 01:06 صبح
در #C بجای اشارهگر ها باید از ارجاعها استفاده شود !!! برای نمونه به کد زیر دقت کنید؟:متفکر:




// ------class node------
public class node{
public char inf;
public node next;

public node()
{
inf='#';
next=null;
}
}
// ------class linkedlist------
public class linkedlist{
int length;
node next;

public linkedlist(){
length=0;
next=null;
}

ghafoori
جمعه 18 اسفند 1385, 07:18 صبح
دوست عزیز با وجود کلاس arraylist دیگر نیاز به لیستهای پیوندی نیست این کلاس یک ارایه با طول متغییر است و کار با ان هم خیلی راحت است

hamed jalili
پنج شنبه 03 آبان 1386, 15:43 عصر
من از MSDN نتونستم چیزی راجع به ArryList پیدا کنم ،
میشه شما یه مثال بزنین ؟
ممنون .











.

ghafoori
پنج شنبه 03 آبان 1386, 16:10 عصر
System.Collections.ArrayList array = new System.Collections.ArrayList();
array.Add("ali");
array.RemoveAt(0);

hamed jalili
پنج شنبه 03 آبان 1386, 16:34 عصر
هیچ محدودیتی در این کلاس وجود نداره ؟
یعنی به هر طول دلخواه میشه اونو ادامه داد ؟


راستی ، میشه یه عنصر رو به خانه ی دلخواه از این آرایه اضافه کرد و یا به خانه ای مشخص دسترسی داشت ؟







.

Mahdi.Kiani
پنج شنبه 03 آبان 1386, 17:05 عصر
دوست عزیز با وجود کلاس arraylist دیگر نیاز به لیستهای پیوندی نیست این کلاس یک ارایه با طول متغییر است و کار با ان هم خیلی راحت است

1) Arraylist هیچ ربطی به لیست های پیوندی نداره
دلیل : ساختمان داده این دو با هم فرق می کنند
2)Arraylist در دات نت 2 با وجود Generic ها شدیدا توصیه میشه که استفاده نشه
دلیل : ArrayList ها SafeCode نیستند و کد های Unsafe تولیدمی کنند (خواستید بگین تا بیشتر توضیح بدم)
3) به جای ArrayList ها از genericList ها استفاده بشه
دلیل :
1 ) همه خواص ArrayList ها را داره
2) Safe می باشد
نمونه :



List<int> IntegerList = newList<int>();
IntegerList.Add(25);
.
.
.
.
IntegerList.Add(40);






می شه نحوه پیاده سازی لیست پیوندی در سی شارپ رو توضح بدید؟




برای لیست پیوندی از LinkedList<T> استفاده بشه
به جای T میتونین نوع دلخواه خودتون را بذارین

این کلاس تمامی اعمالی که میشه روی یک لیست پیوندی را انجام داد براتون مهیا میکنه
نمونه



LinkedList<int> LList = newLinkedList<int>();
LinkedListNode<int> newNode = newLinkedListNode<int>(10);
LList.AddFirst(newNode);
LList.AddAfter(newNode, 20);
.
.
.
.
LList.Remove(newNode);
.
.
.



اکثر DataStructure ها(مثل Stack و QUEUE و ...) در سی شارپ پیاده سازی شدند که میتونین از
System.Collections.Generic; پیداشون کنید(برای حالت Generic)
برای غیر generic هم از
System.Collections میتونین استفاده کنین که البته لیست پیوندی فقط در generic ها پیاده سازی شده
موفق باشید

Mahdi.Kiani
پنج شنبه 03 آبان 1386, 17:18 عصر
دوست عزیز با وجود کلاس arraylist دیگر نیاز به لیستهای پیوندی نیست

فرض کنید لیست من به این شکل باشه




index value
0 10
1 5
2 10
3 20



حالا من میخوام بعد از خانه 2 مقدار 15 را وارد کنم . به طوری که لیست من در پایان به این شکل باشند




index value
0 10
1 5
2 10
3 15
4 20



میشه بگین چگونه با ArrayList این کار را میکنن؟

پ و :
البته کار نشد نداره ولی زمانی که راه بهتری هست باید از اونا استفاده کرد
در پست قبلی راه بهتر توضیح داده شده

hamed jalili
جمعه 04 آبان 1386, 06:39 صبح
ArrayList ها SafeCode نیستند و کد های Unsafe تولیدمی کنند


دوست عزیز میشه بیشتر توضیح بدین که کد Safe چیه ؟






برای لیست پیوندی از LinkedList<T> استفاده بشه
به جای T میتونین نوع دلخواه خودتون را بذارین




LinkedList<int> LList = newLinkedList<int>();
LinkedListNode<int> newNode = newLinkedListNode<int>(10);
LList.AddFirst(newNode);
LList.AddAfter(newNode, 20);





AddFirst و AddAfter ؛ میشه در موردشون بیشتر توضیح بدین که اصلا چه جوری میشه با اینها یه درخت و که نمی دونیم که هر Child (برگ ) بست داده میشه یا نمیشه یااگه بشه تا چه عمق ی بست داده میشه رو با LinkedList پیاده سازی کرد . :متفکر:

ممنون









.

Mahdi.Kiani
جمعه 04 آبان 1386, 13:06 عصر
دوست عزیز میشه بیشتر توضیح بدین که کد Safe چیه ؟

به پست شماره 4 اینجا (http://barnamenevis.org/forum/showthread.php?t=78971&highlight=arraylist) رجوع شود (یه دقت بخونیدش)

[quote]
AddFirst و AddAfter ؛ میشه در موردشون بیشتر توضیح بدین



از اسمشون مشخصه
AddAFter یک گره بع از گره مشخص شده در آرگومان اول ایجاد میکنه
AddFirst هم یک گره در ابتدای لیست ایجاد میکنه




منظورتون را نفهمیدم بیشتر توضیح بدین

sinpin
جمعه 04 آبان 1386, 13:30 عصر
1) Arraylist هیچ ربطی به لیست های پیوندی نداره
دلیل : ساختمان داده این دو با هم فرق می کنند
2)Arraylist در دات نت 2 با وجود Generic ها شدیدا توصیه میشه که استفاده نشه
دلیل : ArrayList ها SafeCode نیستند و کد های Unsafe تولیدمی کنند (خواستید بگین تا بیشتر توضیح بدم)


دوست عزیز میشه بیشتر توضیح بدین که کد Safe چیه ؟

احتمالا منظور ایشون همون type safety بوده ! :بامزه:

Generics allow type safety to be achieved with a single implementation where traditionally a different implementation would have been needed for each type, or compile-time type safety would have been lost.

type safety دارد یعنی اینکه شما نمیتوانید هر تایپی رو در run-time در اون add کنید چون در compile-time تایپ مورد نظرتون رو باید مشخص میکنید. (پس جلوی خیلی از اشتباهات و exception ها رو میگیره)


The non-generic ArrayList type is always backed by an object[] - an array of references to any old object. That means that if you want to store value types in the list, they have to be boxed first. When you retrieve the value, if you want it back as a value type again you need to unbox it. This boxing and unboxing can be expensive if you do a lot of it - both in processor time and especially in memory. Each value requires an extra object to be created, so a list of 100,000 bytes creates 100,000 objects (each with the overhead of being an object) as well as a reference to each of those objects. Generics allow the List<T> type to be backed by an array of the appropriate type - so a List<byte> is backed by a byte[]. No boxing or unboxing is required, giving a massive boost in memory and processor efficiency when adding to and accessing the list
منبع :
http://www.yoda.arachsys.com/csharp/csharp2/generics.html

و از طرفی نسبت به نوع غیر generic بازدهی بهتری دارند : چون نوع غیر generic جهت انعطاف با تایپ object کار میکند که نیاز به boxing و unbonxing دارد اما انواع generic به این سربار نیازی ندارند.


List<T> offers generally better performance than ArrayList as well as type safety. We recommend using List<T> over ArrayList always if T is a reference type. If T is a value type there is additional cost assocated with creating a specialized version of List<T> for that value type. When T would be a value type we recommend List<T> if the savings in boxing is greater than the cost of the additional code -- this tends to happen if you store about 500 elements across all your List<T> objects. (http://msdn2.microsoft.com/en-us/library/6sh2ey19.aspx)

sinpin
جمعه 04 آبان 1386, 14:03 عصر
بسمه تعالی
با سلام خدمت دوستان
می شه نحوه پیاده سازی لیست پیوندی در سی شارپ رو توضح بدید؟

The LinkedList<T> class in the .NET framework is considered a doubly linked list. This is because each node in the linked list contains a pointer to both the previous node and the next node in the linked list. Figure 4-1 shows what a doubly linked list looks like diagrammed on paper. Each node in this diagram represents a single
LinkedListNode<T> object.
http://en.csharp-online.net/images/0/00/CSC2fig4-1.jpg (http://en.csharp-online.net/Image:CSC2fig4-1.jpg)

http://en.csharp-online.net/CSharp_Generics_Recipes%E2%80%94Implementing_a_Lin ked_List

hamed jalili
جمعه 04 آبان 1386, 19:06 عصر
AddFirst هم یک گره در ابتدای لیست ایجاد میکنه



فرض کنیم :

A ---> B ----> C -----> D

حالا فرض کنیم که C به عنوان Nod جاری فعال ه ؛ با AddFirst به کجای این لیست یه Nod اضافه میشه ؟ به قبل C با قبل A ؟


اگه به قبل C اضافه نمیشه در اون صورت ، این کار چه طور انجام میشه ؟









.

Mahdi.Kiani
جمعه 04 آبان 1386, 22:14 عصر
فرض کنیم :

A ---> B ----> C -----> D

حالا فرض کنیم که C به عنوان Nod جاری فعال ه ؛ با AddFirst به کجای این لیست یه Nod اضافه میشه ؟ به قبل C با قبل A ؟



.

همونطور که گفتم با Addlist به ابتدای لیست گره اضافه میشه
پس بعد از اضافه کردن گره ای مانند E در با متد AddFirst شکل لیست به این صورت در میاد




E ---> A ----> B ----->C ----->D








اگه به قبل C اضافه نمیشه در اون صورت ، این کار چه طور انجام میشه ؟



چه ربطی داره به پرتغال فروش یا پرتغال ها ؟؟:بامزه:

hamed jalili
شنبه 05 آبان 1386, 07:54 صبح
چه ربطی داره به پرتغال فروش یا پرتغال ها ؟؟:بامزه:



یعنی نمیشه به قبل C ، نودی اضافه کرد ؟





و :




LinkedList<int> LList = newLinkedList<int>();
LinkedListNode<int> newNode = newLinkedListNode<int>(10);
LList.AddFirst(newNode);
LList.AddAfter(newNode, 20);



در این کد که شما زحمتشو کشیدین ، به Node اسم newNode دادین ؛ در این درختی که من می خواهم با این کلاس پیاده کنم ، تعداد Node ها مشخص نیست !!!! به همین خاطر نمیشه از قبل Node ها رو تعریف کرد !!!
تولید Node ها باید در داخل یه حلقه باشه که هر وقت که لازم شد در هر کجای درخت که لازم باشه ، یه Node اضافه بشه ، یا وسط چند Node یا بعد آخرین Node یا ... خوب حالا من چه طور می تونم از این کلاس به این نحو استفاده کنم ؟








.

Mahdi.Kiani
شنبه 05 آبان 1386, 12:48 عصر
یعنی نمیشه به قبل C ، نودی اضافه کرد ؟



.
ببخشین ولی اگه یکم به خودتون زحمت میدادین میدیدن که کلاس Linkedlist غیر از متد های AddFirst و AddAfter متد های دیگه ای و قابلیت های دیگه ای هم داره مثلا متد AddBefore که یک گره جدید را قبل از هر گره ای که بخواین می تونین بذارین (همون چیزی که 2 روزه خودتون را الافش کردین تا من بهتون جواب بدم)

من نمیتونم که کل برنامه را براتون بنویسیم و آپ کنم
یکم بیشتر همت کنین
به خدا اونوقت که ما میخواستیم اینا را یاد بگیریم آرزو داشتیم یکی یه سر نخ به ما بده تا باقیش را خودمون بریم
ولی شما حتی یه زحمت نکسیدین ببینی که این کلاس linkedList چه قابلیت های دیگه ای داره؟




تولید Node ها باید در داخل یه حلقه باشه که هر وقت که لازم شد در هر کجای درخت که لازم باشه ، یه Node اضافه بشه ، یا وسط چند Node یا بعد آخرین Node یا ..


خوب تولید گره ها را در حلقه بذارین و با متد های AddFirst و AddLast و AddBefore و AddAFter و .......
هر کاری که میخواین بکنین

hamed jalili
شنبه 05 آبان 1386, 13:06 عصر
ببخشین ولی اگه یکم به خودتون زحمت میدادین میدیدن که کلاس Linkedlist غیر از متد های AddFirst و AddAfter متد های دیگه ای و

دوست عزیز
من استفاده از اون متودارو می تونم یاد بگیرم ولی بلد نیستم که چه طور می تونم بگم که بعد از مثلا گره 5 یه گره ایجا کنه یا بعد از گره جاری یه گره ایجا کنه (البته نه از MSDN پیدا کردم نه از خود کلاس چیزی در این مورد دستگیرم شد ) !!!!







خوب تولید گره ها را در حلقه بذارین و با متد های AddFirst و AddLast و AddBefore و AddAFter و .......



اسم نود ها رو چی کار کنم پس ؟!






.

emad_67
شنبه 05 آبان 1386, 14:07 عصر
چه طور می تونم بگم که بعد از مثلا گره 5 یه گره ایجا کنهبرای این کار باید گره 5 ام رو داشته باشی که اونو به تابع AddAfter بدی تا گره جدید بعد از اون add بشه.

اسم نود ها رو چی کار کنم پس ؟!
برای مثال اینو ببین


LinkedList<int> list = new LinkedList<int>();
LinkedListNode<int> node;
for (int i = 0; i < 10; i++)
{
node = new LinkedListNode<int>(i);
list.AddLast(node);
}
ابتدا یه ارجاعی به کلاس LinkedListNode<int> باید بسازی و بعد در حلقه تخصیص حافظه بکنی.

hamed jalili
شنبه 05 آبان 1386, 14:40 عصر
دوستان شرمنده ، من مبتدی هستم و با راهنمایی های شما نتونستم درختی رو که می خواستم رو کامل پیاده کنم !!
شکل درخت و کدی که خودم تا جایی رو که با کمک های شما نوشتم رو اینجا می گذارم ، اگه ممکن باشه شما در کامل کردنش بهم کمک کنید .



http://img.majidonline.com/pic/124230/Barnamenevis.jpg





LinkedList<int> MainTree = newLinkedList<int>();

LinkedListNode<int> A = newLinkedListNode<int>(123);
MainTree.AddFirst(A);

LinkedListNode<int> B = newLinkedListNode<int>(22);
MainTree.AddAfter(A, B);

LinkedListNode<int> C = newLinkedListNode<int>(33);
MainTree.AddAfter(A, C);

LinkedListNode<int> D = newLinkedListNode<int>(44);
MainTree.AddAfter(A, D);

LinkedListNode<int> E = newLinkedListNode<int>(55);
MainTree.AddAfter(B, E);

LinkedListNode<int> F = newLinkedListNode<int>(66);
MainTree.AddAfter(E, F);

LinkedListNode<int> G = newLinkedListNode<int>(77);
MainTree.AddAfter(E, G);

LinkedListNode<int> H = newLinkedListNode<int>(88);
MainTree.AddAfter(D, H);

LinkedListNode<int> I = newLinkedListNode<int>(99);
MainTree.AddAfter(D, I);






1- Node ها رو درست تعریف کردم ؟

2- چه طور بگم ، Parent ، مثلا Node E رو پیدا کن ؟

3- چه طور فاصله Node مثلا I از A را پیدا کنم ؟

4- فرض کنیم که می خواهیم به Node H یه Node جدید اضافه کنیم ، اسم Node H رو نداریم برای پیدا کردن او از مقدار اون ( مقدار تمام Node ها منحصر به فرد ه ) استفاده می کنیم به این صورت :


Problem8Tree.Find(CurrentNodeFlage);

خوب حالا چه طور یه Node به این Node اضافه کنیم ؟






ممنون .

rohullah
شنبه 05 آبان 1386, 15:23 عصر
من تو c# مبتدیم و در حضور اساتید چیزی نمیتونم بگم ولی توی درس ساختمان داده که ما پاس کردیم توی ساخنمان یک درخت هر نود دوتا لینک نگه می داشت یکی برای فرزند و یکی برای برادر راست.من توی c++ بلدم کدشو بنویسم ولی اینجا اساتید باید بگن.چون این چیزی که من میبینم فقط یه لینک به نود فرزند داره.

PC2st
شنبه 05 آبان 1386, 20:27 عصر
با راهنمایی های شما نتونستم درختی رو که می خواستم رو کامل پیاده کنم !!
فکر نمیکنم بشه اینطور با LinkedList رفتار کرد، بلکه شبیه به شکلی خواهد بود که در پست شماره 15 (توسط sinpin) گذاشته شده.

hamed jalili
یک شنبه 06 آبان 1386, 06:50 صبح
فکر نمیکنم بشه اینطور با LinkedList رفتار کرد، بلکه شبیه به شکلی خواهد بود که در پست شماره 15 (توسط sinpin) گذاشته شده.



:متفکر::متفکر::متفکر::متفکر:

خوب پس برای پیاده سازی درخت ، اون هم درختی که معلوم نیست چند تا گره داره ، باید چی کار کرد ؟






.

sinpin
یک شنبه 06 آبان 1386, 07:46 صبح
:متفکر::متفکر::متفکر::متفکر:

خوب پس برای پیاده سازی درخت ، اون هم درختی که معلوم نیست چند تا گره داره ، باید چی کار کرد ؟
.

چرا شما خودتون یک کلاس ژنزیک برای درختتون ایجاد نمیکنید؟ اینجا چندتا مثال هست :
http://www.codeproject.com/csharp/treecollection2.asp
http://www.codeproject.com/useritems/Trees.asp
http://www.codeproject.com/csharp/phSharpTree.asp

Mahdi.Kiani
یک شنبه 06 آبان 1386, 08:15 صبح
:متفکر::متفکر::متفکر::متفکر:

خوب پس برای پیاده سازی درخت ، اون هم درختی که معلوم نیست چند تا گره داره ، باید چی کار کرد ؟






.

پس بهتر بود عنوان تاپیک را یکی از عنوان های زیر انتخاب می کردین

1 ) پیاده سازی ساختمان داده درخت در سی شارپ
یا
2) پیاده سازی درخت توسط لیست های پیوندی

PC2st
یک شنبه 06 آبان 1386, 16:41 عصر
2) پیاده سازی درخت توسط لیست های پیوندی
البته لیست پیوندی و درخت، مفاهیمی جداگانه هستند.

Mahdi.Kiani
یک شنبه 06 آبان 1386, 22:16 عصر
البته لیست پیوندی و درخت، مفاهیمی جداگانه هستند.

من هم نگفتم که درخت و لیست پیوندی یک مفهوم هستند
بلکه گفتم پیاده سازی درخت توسط لیست های پیوندی
یکی از راه های پیاده سازی درخت ها توسط لیست های پیوندی می باشد که در هر گره لیست پیوندی شامل سه بخش Data و LeftChildLink و EightChildLink می باشد.
جهت اطلاعات بیشتر به کتاب های Data Structures مراجعه شود!!

hamed jalili
یک شنبه 06 آبان 1386, 22:17 عصر
1 ) پیاده سازی ساختمان داده درخت در سی شارپ



این تاپیک و من درست نکردم سرچ کردم و چون تقریبا شبیه به چیزی بود که من می خواستم سوالمو اینجا مطرح کردم ،

خوب حالا به نظر شما نمیشه به این روش درخت رو پیاده کرد ؟






.

PC2st
یک شنبه 06 آبان 1386, 23:55 عصر
من هم نگفتم که درخت و لیست پیوندی یک مفهوم هستند
بلکه گفتم پیاده سازی درخت توسط لیست های پیوندی
گفتن جمله : "پیاده سازی درخت توسط لیست پیوندی" مناسب نیست، چون:

+ مفاهیم متفاوتی دارند (و این رو قبول دارید).

+ node (گره) فقط مخصوص لیست پیوندی نیست.
پس وقتی در درخت از node استفاده کردیم، به معنای این نیست که : درخت توسط لیست پیوندی پیاده سازی شده است.

* شاید منظورتون استفاده از لیست پیوندی برای ذخیره زیر گره ها است؟

hamed jalili
دوشنبه 07 آبان 1386, 06:05 صبح
پس بهتر بود عنوان تاپیک را یکی از عنوان های زیر انتخاب می کردین
1 ) پیاده سازی ساختمان داده درخت در سی شارپ

بنا به فرموده دوستمون ، من تاپیک زیر رو درست کردم ، میشه لطف کنید و اجازه بدید ادامه بحث رو به اونجا منتقل کنیم ؟

http://barnamenevis.org/forum/showthread.php?p=413726#post413726