ساختمان داده نامتناهی

[نغمه]

آیا امکان تعریف ساختمان داده نامتناهی وجود دارد؟
لیست پیوندی هم محدودیت سایز دارد پس چه الویتی نسبت به آرایه دارد (غیر از وجود اشاره گرها)؟

[whitehat]

لیست پیوندی (و هر ساختمان داده دیگری که بر این اساس ساخته می شود مانند درخت ،لیست و پشته) یک ساختمان داده نامتناهی محسوب می شود! شما در این ساختمان داده ها می بایست مدیریت حافظه را خود بر عهده بگیرید و تا جاییکه حافظه شما اجازه دهید می توانید این ساختمان داده را بزرگ کنید.
شما نباید محدودیت حافظه را در ساختمان داده دخیل کنید ،چون تعریف ساختمان داده یک مفهوم انتزاعی است و مستقل از سخت افزار می باشد.

[azmoodeh]

سلام

اکثر ساختمان های داده رو میشه طوری طراحی کرد که محدودیت اندازه از لحاظ ساختاری نداشته باشه

ولی اگه که منظور شما اینه که مثلا به یک لیست پیوندی بی نهایت مقدار (یا شی ء ) رو اضافه کنیم و هیچ اتفاقی نیفته که باید عرض کنم این مساله مربوط به مدیریت پردازش ها ( و اختصاص حافظه به اونها) میشه که با سیستم عامل مرتبط هست نه ساختار ساختمان داده .

موفق باشید

[نغمه]

لیست پیوندی یک ساختمان داده نامتناهی محسوب می شود! شما در این ساختمان داده ها می بایست مدیریت حافظه را خود بر عهده بگیرید و تا جاییکه حافظه شما اجازه دهید می توانید این ساختمان داده را بزرگ کنید.
شما نباید محدودیت حافظه را در ساختمان داده دخیل کنید ،چون تعریف ساختمان داده یک مفهوم انتزاعی است و مستقل از سخت افزار می باشد.

موقع تعریف لیست در یک برنامه باید سایز آن را مشخص کرد پس چطور می توان محدودیت حافظه را در ساختمان داده دخیل نکرد ؟

چطور می توان مدیریت حافظه را خود بر عهده بگیریم؟

[whitehat]

موقع تعریف لیست در یک برنامه باید سایز آن را مشخص کرد پس چطور می توان محدودیت حافظه را در ساختمان داده دخیل نکرد ؟
لیست پیوندی ساختمان داده ای است که فقط با یک اشاره گر به ابتدای لیست مشخص می شود ، شما نیازی نیست که سایز آنرا مشخص کنید. در اکثر زبانهای برنامه نویسی این امکان به برنامنه نویس داده می شود که به هر تعدادی که مورد نیاز است حافظه در اختیار بگیرد

[HAIdle]

موقع تعریف لیست در یک برنامه باید سایز آن را مشخص کرد پس چطور می توان محدودیت حافظه را در ساختمان داده دخیل نکرد ؟

چطور می توان مدیریت حافظه را خود بر عهده بگیریم؟

مطمئن هستید که لیست را درست متوجه شدید؟
چون همانطور که دوستمون گفتند در هنگام تعریف و استفاده از لیست هیچ نیازی به دانستن طول لیست نیست

[نغمه]

مثلا در زبان سی چگونه باید لیست را تعریف کنیم؟مگر نباید از آرایه ها استفاده کنیم! که برای آرایه هم باید سایز را از اول مشخص کنیم؟

[HAIdle]

خیر. هیچ نیازی به استفاده از آرایه نیست. توصیه می کنم یک کتاب ساختمان داده را بخوانید ولی بطور مختصر:
مثلا در زبان Cpp برای ایجاد لیست پیوندی یک کلاس می نویسید که در آن داده هایی که می خواهید در لیست شما وجود داشته باشد را تعریف می کنید بعلاوه یک اشاره گر به شی از همین کلاس. می بینید که تا اینا هیچ اسمی از آرایه برده نشده است.
برای استفاده هم یک شی از این کلاس تعریف می کنید. از این به بعد نقطه دسترسی شما به لیست از طریق همین شی و دنبال کردن لینکها می باشد.
برای گسترش لیست هم کافی است یک شی جدید از آن کلاس تعریف کنید و آدرس آنرا در فیلد لینک شی که می خواهید قبل از این عنصر باشد قرار دهید.
به این ترتیب مشاهده می کنید که در ابتدا لیست ما یک عتصر دارد و به مرور و بر حسب نیاز شما می توانید لیست را بطور دلخواه رشد دهید بدون اینکه از اول بگویید لیست چقدر بزرگ خواهد شد.
اگر متوجه نشدید به کتابی مثل کتاب هرویتس مراجعه کنید.

[whitehat]

همانطور که قبلا اشاره کردم ساختمان داده یک دید انتزاعی است و مستقل از پیاده سازی می باشد، یکی از روش های تعریف لیست پیوندی آرایه است اما نمی توان آنرا بصورت نامتناهی در زبان C تعریف کرد(زبانهایی هستند که می توانند آرایه های نامتناهی داشته باشند) شما برای تعریف لیست پیوندی نامتناهی در C از توابعی برای تخصیص حافظه مانند malloc استفاده کنید،برای اطلاعات بیشتر در مورد لیست های پیوندی به اینجا (http://en.wikipedia.org/wiki/Linked_list)مراجعه کنید

[HAIdle]

از لینکتون ممنون
این که می گید میشه با آرایه پیاده کرد درست ولی این کار خیلی غیرمعقول به نظر می رسه چون هم مزایای آرایه را از دست می دیم و تا حدی هم مزایای لیست را. در کل همانطور که در ویکی پدیا گفته بود تعریف اصلی لیست پیوندی با توجه به مفهوم اشاره گر به همان نوع است و تا زبان مورد نظر از مفاهیم تجرد داده حمایت می کنه نیازی نیست بریم سراغ آرایه
البته در C هیچ نیازی به استفاده ار آرایه نیست چون از struct پشتیبانی میکنه.

[atilla snowman]

لیست پیوندی رو جایی استفاده می کنند که نخوان مثل آرایه ها سایز اون رو از قبل مشخص کرد.
اگه مجبور نیستید از اون استفاده نکنید چون فضای زیادی استفاده می کنند.
اصولا یه چیزی شبیه تسبیهه . باید مواظب پیچیدگیهاش باشی.
از لحاظ تئوری نا محدوده ولی از لحاظ عملی ...

[someCoder]

مثلا در زبان سی چگونه باید لیست را تعریف کنیم؟مگر نباید از آرایه ها استفاده کنیم! که برای آرایه هم باید سایز را از اول مشخص کنیم؟

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

[نغمه]

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

[someCoder]

http://www.functionx.com/cpp/articles/linkedlist.htm

[نغمه]

تو همین سایت هم برای تعریف لیست پیوندی از آرایه ها استفاده کرده که این باعث میشه نتونیم یک لیست نامتناهی تعریف کنیم!

[someCoder]

تو همین سایت هم برای تعریف لیست پیوندی از آرایه ها استفاده کرده که این باعث میشه نتونیم یک لیست نامتناهی تعریف کنیم!

اون آرایه برای ذخیره رشته است، شما بجاش یه int بذار.

[نغمه]

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

[someCoder]

میشه شما یک لیست پیوندی تعریف کنید
چون کد رو همین جا نوشتم و کامپایل نکردم ممکنه خطا داشته باشه. اما فکر کنم بتونی ایده بگیری ازش. این یه لیست هست که فقط توی هر گره یه int ذخیره شده.

// Define a node
struct nodeType {
int data;
nodeType *next;
};

// Make an empty list
nodeType *start = NULL;

// Make a node with some data
nodeType *myNewNode = new nodeType;
myNewNode->data = x;

// Add the node at the begining of the list
start->next = myNewNode;
start = myNewNode;


اینم از پیمایشش:


// Loop through data in list
nodeType *myIterator = start;
while(myIterator != NULL){
cout<<myIterator->data;

myIterator = myIterator->next;
}


ضمنا، من فرض کردم با ++C میخوای. اگر به زبون دیگه ای میخوای، بگو کجاش رو نمیتونی تبدیل کنی

[someCoder]

ضمنا اینم میتونه کمکت کنه: http://en.wikipedia.org/wiki/Linked_list

[نغمه]

مرسی از کمکتون تازه فهمیدم چی شد