آیا امکان تعریف ساختمان داده نامتناهی وجود دارد؟
لیست پیوندی هم محدودیت سایز دارد پس چه الویتی نسبت به آرایه دارد (غیر از وجود اشاره گرها)؟
آیا امکان تعریف ساختمان داده نامتناهی وجود دارد؟
لیست پیوندی هم محدودیت سایز دارد پس چه الویتی نسبت به آرایه دارد (غیر از وجود اشاره گرها)؟
لیست پیوندی (و هر ساختمان داده دیگری که بر این اساس ساخته می شود مانند درخت ،لیست و پشته) یک ساختمان داده نامتناهی محسوب می شود! شما در این ساختمان داده ها می بایست مدیریت حافظه را خود بر عهده بگیرید و تا جاییکه حافظه شما اجازه دهید می توانید این ساختمان داده را بزرگ کنید.
شما نباید محدودیت حافظه را در ساختمان داده دخیل کنید ،چون تعریف ساختمان داده یک مفهوم انتزاعی است و مستقل از سخت افزار می باشد.
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
سلام
اکثر ساختمان های داده رو میشه طوری طراحی کرد که محدودیت اندازه از لحاظ ساختاری نداشته باشه
ولی اگه که منظور شما اینه که مثلا به یک لیست پیوندی بی نهایت مقدار (یا شی ء ) رو اضافه کنیم و هیچ اتفاقی نیفته که باید عرض کنم این مساله مربوط به مدیریت پردازش ها ( و اختصاص حافظه به اونها) میشه که با سیستم عامل مرتبط هست نه ساختار ساختمان داده .
موفق باشید
لیست پیوندی ساختمان داده ای است که فقط با یک اشاره گر به ابتدای لیست مشخص می شود ، شما نیازی نیست که سایز آنرا مشخص کنید. در اکثر زبانهای برنامه نویسی این امکان به برنامنه نویس داده می شود که به هر تعدادی که مورد نیاز است حافظه در اختیار بگیردموقع تعریف لیست در یک برنامه باید سایز آن را مشخص کرد پس چطور می توان محدودیت حافظه را در ساختمان داده دخیل نکرد ؟
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
مثلا در زبان سی چگونه باید لیست را تعریف کنیم؟مگر نباید از آرایه ها استفاده کنیم! که برای آرایه هم باید سایز را از اول مشخص کنیم؟
خیر. هیچ نیازی به استفاده از آرایه نیست. توصیه می کنم یک کتاب ساختمان داده را بخوانید ولی بطور مختصر:
مثلا در زبان Cpp برای ایجاد لیست پیوندی یک کلاس می نویسید که در آن داده هایی که می خواهید در لیست شما وجود داشته باشد را تعریف می کنید بعلاوه یک اشاره گر به شی از همین کلاس. می بینید که تا اینا هیچ اسمی از آرایه برده نشده است.
برای استفاده هم یک شی از این کلاس تعریف می کنید. از این به بعد نقطه دسترسی شما به لیست از طریق همین شی و دنبال کردن لینکها می باشد.
برای گسترش لیست هم کافی است یک شی جدید از آن کلاس تعریف کنید و آدرس آنرا در فیلد لینک شی که می خواهید قبل از این عنصر باشد قرار دهید.
به این ترتیب مشاهده می کنید که در ابتدا لیست ما یک عتصر دارد و به مرور و بر حسب نیاز شما می توانید لیست را بطور دلخواه رشد دهید بدون اینکه از اول بگویید لیست چقدر بزرگ خواهد شد.
اگر متوجه نشدید به کتابی مثل کتاب هرویتس مراجعه کنید.
همانطور که قبلا اشاره کردم ساختمان داده یک دید انتزاعی است و مستقل از پیاده سازی می باشد، یکی از روش های تعریف لیست پیوندی آرایه است اما نمی توان آنرا بصورت نامتناهی در زبان C تعریف کرد(زبانهایی هستند که می توانند آرایه های نامتناهی داشته باشند) شما برای تعریف لیست پیوندی نامتناهی در C از توابعی برای تخصیص حافظه مانند malloc استفاده کنید،برای اطلاعات بیشتر در مورد لیست های پیوندی به اینجا مراجعه کنید
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
از لینکتون ممنون
این که می گید میشه با آرایه پیاده کرد درست ولی این کار خیلی غیرمعقول به نظر می رسه چون هم مزایای آرایه را از دست می دیم و تا حدی هم مزایای لیست را. در کل همانطور که در ویکی پدیا گفته بود تعریف اصلی لیست پیوندی با توجه به مفهوم اشاره گر به همان نوع است و تا زبان مورد نظر از مفاهیم تجرد داده حمایت می کنه نیازی نیست بریم سراغ آرایه
البته در C هیچ نیازی به استفاده ار آرایه نیست چون از struct پشتیبانی میکنه.
لیست پیوندی رو جایی استفاده می کنند که نخوان مثل آرایه ها سایز اون رو از قبل مشخص کرد.
اگه مجبور نیستید از اون استفاده نکنید چون فضای زیادی استفاده می کنند.
اصولا یه چیزی شبیه تسبیهه . باید مواظب پیچیدگیهاش باشی.
از لحاظ تئوری نا محدوده ولی از لحاظ عملی ...
تو همین سایت هم برای تعریف لیست پیوندی از آرایه ها استفاده کرده که این باعث میشه نتونیم یک لیست نامتناهی تعریف کنیم!
چون کد رو همین جا نوشتم و کامپایل نکردم ممکنه خطا داشته باشه. اما فکر کنم بتونی ایده بگیری ازش. این یه لیست هست که فقط توی هر گره یه 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 میخوای. اگر به زبون دیگه ای میخوای، بگو کجاش رو نمیتونی تبدیل کنی
ضمنا اینم میتونه کمکت کنه: http://en.wikipedia.org/wiki/Linked_list