# برنامه نویسی با محصولات مایکروسافت > برنامه نویسی مبتنی بر Microsoft .Net Framework > C#‎‎ >  لیست پیوندی در سی شارپ

## hassan_kahrizy

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

----------


## shahab_ss

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

میتونی یک کلاس که عضو قبل و بعدش رو بشناسه تعریف کنی دیگه مشکل اشاره گر و دردسر هاش رو هم ندازی من یک درخت اینجوری پیاده سازی کردم برای پروژه هوش مصنوعی

----------


## hassan_kahrizy

بسمه تعالی
با سلام
می شه یک مثال بزنید
با تشکر

----------


## Artz_6

در #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

دوست عزیز با وجود کلاس arraylist دیگر نیاز به لیستهای پیوندی نیست این کلاس یک ارایه با طول متغییر است و کار با ان هم خیلی راحت است

----------


## hamed jalili

من از MSDN نتونستم چیزی راجع به ArryList پیدا کنم ، 
میشه شما یه مثال بزنین ؟ 
ممنون .











.

----------


## ghafoori

System.Collections.ArrayList array = new System.Collections.ArrayList();
            array.Add("ali");
                        array.RemoveAt(0);

----------


## hamed jalili

هیچ محدودیتی در این کلاس وجود نداره ؟ 
یعنی به هر طول دلخواه میشه اونو ادامه داد ؟


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







.

----------


## Mahdi.Kiani

> دوست عزیز با وجود کلاس 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

> دوست عزیز با وجود کلاس 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

> 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

[quote=hamed jalili;412514]دوست عزیز میشه بیشتر توضیح بدین که کد Safe چیه ؟

به پست شماره 4 اینجا رجوع شود (یه دقت بخونیدش)




> AddFirst و AddAfter ؛ میشه در موردشون بیشتر توضیح بدین


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




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

----------


## sinpin

> 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/.../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.

----------


## sinpin

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


 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/CSharp_G..._a_Linked_List

----------


## hamed jalili

> AddFirst هم یک گره در ابتدای لیست ایجاد میکنه


فرض کنیم :

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

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


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









.

----------


## Mahdi.Kiani

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


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


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






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


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

----------


## hamed jalili

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


یعنی نمیشه به قبل 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

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


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

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




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


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

----------


## hamed jalili

> ببخشین ولی اگه یکم به خودتون زحمت میدادین میدیدن که کلاس Linkedlist غیر از متد های AddFirst و AddAfter متد های دیگه ای و


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







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


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






.

----------


## emad_67

> چه طور می تونم بگم که بعد از مثلا گره 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

دوستان شرمنده ، من مبتدی هستم و با راهنمایی های شما نتونستم درختی رو که می خواستم رو کامل پیاده کنم !! 
شکل درخت و کدی که خودم تا جایی رو که با کمک های شما نوشتم رو اینجا می گذارم ، اگه ممکن باشه شما در کامل کردنش بهم کمک کنید . 







 
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

من تو C#‎ مبتدیم و در حضور اساتید چیزی نمیتونم بگم ولی توی درس ساختمان داده که ما پاس کردیم توی ساخنمان یک درخت هر نود دوتا لینک نگه می داشت یکی برای فرزند و یکی برای برادر راست.من توی C++‎ بلدم کدشو بنویسم ولی اینجا اساتید باید بگن.چون این چیزی که من میبینم فقط یه لینک به نود فرزند داره.

----------


## PC2st

> با راهنمایی های شما نتونستم درختی رو که می خواستم رو کامل پیاده کنم !!


فکر نمیکنم بشه اینطور با LinkedList رفتار کرد، بلکه شبیه به شکلی خواهد بود که در پست شماره 15 (توسط sinpin) گذاشته شده.

----------


## hamed jalili

> فکر نمیکنم بشه اینطور با LinkedList رفتار کرد، بلکه شبیه به شکلی خواهد بود که در پست شماره 15 (توسط sinpin) گذاشته شده.


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

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






.

----------


## sinpin

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


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

----------


## Mahdi.Kiani

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


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

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

----------


## PC2st

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


البته لیست پیوندی و درخت، مفاهیمی جداگانه هستند.

----------


## Mahdi.Kiani

> البته لیست پیوندی و درخت، مفاهیمی جداگانه هستند.


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

----------


## hamed jalili

> 1 ) پیاده سازی ساختمان داده درخت در سی شارپ


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

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






.

----------


## PC2st

> من هم نگفتم که درخت و لیست پیوندی یک مفهوم هستند
> بلکه گفتم پیاده سازی درخت توسط لیست های پیوندی


گفتن جمله : "پیاده سازی درخت توسط لیست پیوندی" مناسب نیست، چون:

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

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

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

----------


## hamed jalili

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


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

https://barnamenevis.org/showth...726#post413726

----------

