C3phalex1n_0x
دوشنبه 24 شهریور 1393, 14:04 عصر
سلام به همه دوستان عزیز گرامی و اساتید صاحب قلم در وب سایت برنامه نویس. اورگ
پیرو قرآن کریم، کلام پروردگار دانا : ذکات علم نشر آن است و همچنین مطابق با حرف امام یازدهم ما شیعیان، امام حسن عسگری (ع) : بهترین کار در دنیا دانش اندوزی و نشر آن به برادران است.
بنده خیلی علاقمند بودم آموزشی در رابطه با لیست های پیوندی آماده کنم و آن را در این قسمت از وب سایت برنامه نویس به اشتراک بگذارم. همانطور که می دانید، مفهوم لیست پیوندی بسیار مهم هست و یادگیری آن هم در ابتدا کمی مشکل و ترسناک می باشد. در این آموزش که بنده آنرا آماده کرده ام (البته عمده قسمت های این مقاله ترجمه یا کپی است) قصد دارم شما را گام به گام با پیاده سازی، طراحی و مفهوم لیست های پیوندی آشنا کنم. همچنین از آنجایکه بنده استاد نیستم و یک تازه کار بیش نمی باشم، انتظار دارم اگر در جایی استادی از من ایراد و اشتباهی دید آن را برای من رفع کرده تا از ادامه اشتباهات من جلوگیری کند. به هر حال، امیدوارم این مقاله کوچک، راهنمای تمامی دوستان و برادران من باشد.
مباحثی که در این مقاله مورد بررسی قرار خواهد گرفت:
اشاره گرها چی هستند و چرا از آن ها در برخی موقعیت ها استفاده می شود؟
اشاره گر ها در C و سی پلاس پلاس به چه شکل هستند؟!
ساختارها (Structure) موجود در زبان برنامه نویسی C چه هستند؟!
کلاس ها (Classes) در زبان برنامه نویسی سی پلاس پلاس چه هستند؟!
فرق بین کلاس ها و ساختارها در چیست؟
لیست پیوندی چیست و فرق آن با آرایه ها در چه می باشد؟
نحوه ذخیره سازی عناصر لیست پیوندی و آرایه ها در حافظه به چه شکل است؟
چرا باید از لیست پیوندی استفاده کنیم؟!
کاربرد لیست پیوندی در عمل چیست؟!
الگوریتم چیست و الگوریتم پیاده سازی لیست پیوندی به چه شکل است؟
پیاده سازی لیست پیوندی با ساختار ها به صورت غیر پویا
پیاده سازی لیست پیوندی با ساختار ها به صورت پویا
پیاده سازی تابع افزودن عنصر به لیست پیوندی
پیاده سازی تابع حذف عنصر از لیست پیوندی
پیاده سازی تابع نمایش عناصر موجود در لیست پیوندی
پیاده سازی لیست پیوندی با کلاس ها در زبان برنامه نویسی سی پلاس پلاس
خلاصه مقاله
منابع استفاده شده در نگاشت مقاله
http://upcity.ir/images2/68807010627099788353.jpg
اگر واقعا می خواهید یک برنامه نویس C حرفه ای شوید، نیاز دارید بدانید که C چگونه حافظه را کنترل می کند. زبان برنامه نویسی C بر سر اینکه برنامه شما چگونه از حافظه استفاده کند، کنترل بسیار زیادی به شما ارائه می دهد. در این قسمت شما خواهید فهمید که هنگامی که یک متغیر را تعریف می کنید در حافظه چه اتفاقی می افتد و در حالت کلی با نحوه کنترل حافظه آشنا خواهید شد. شایان ذکر است، به منظور اینکه اشاره گر ها را به درستی یاد بگیرید، باید با نحوه مدیریت اشیاء و داده ها در حافظه آشنایی دقیق و کاملی داشته باشید که در قسمت اول این مقاله به این موضوع خواهیم پرداخت.
اشاره گر ها در C
اشاره گرها یکی از اساسی ترین مفاهیم موجود در زبان برنامه نویسی C هستند که داشتن فهم دقیقی از آنها برای تمامی برنامه نویسان به این زبان الزامی است. اما خب، واقعا اشاره گر ها چه هستند؟! در جواب این سوال به سادگی می توان گفت، یک اشاره گر در واقع یک متغیر است که می تواند آدرس دیگر متغییر ها را در خودش نگه دارد. اشاره گر ها در C به دلایل مختلفی استفاده می شوند که برخی از آنها را در این مقاله با هم بررسی خواهیم کرد.
http://upcity.ir/images2/31824595417338855386.jpg
دلیل اول : در برخی شرایط هنگام برنامه نویسی، نیاز دارید کپی از داده ها موجود در برنامه را به یک تابع از برنامه عبور دهید. این عمل باعث اتلاف حافظه و پایین آمدن راندمان کار برنامه می شود. با این حال، به منظور رفع کردن این مشکل، شما می توانید به سادگی آدرس آن داده های را با استفاده از اشاره گر ها به تابع خود عبور دهید و از اتلاف حافظه و پایین آمدن سرعت کار برنامه جلوگیری کنید.
http://upcity.ir/images2/96748519627214928423.png
دلیل دوم : گاهی اوقات شما نیاز دارید دو تابع به صورت همزمان بر روی قسمتی از داده های برنامه شما کار کنند، در این موقعیت می توانید از اشاره گر ها و آدرس آن قطعه داده استفاده کنید.
http://upcity.ir/images2/61767029443816734656.png
اشاره گر ها به شما کمک می کنند دو مورد ذکر شده در بالا را به سادگی انجام بدهید، یعنی از کپی کردن داده ها در برنامه خود جلوگیری کنید و داده های درون برنامه را به اشتراک بگذارید. اما اگر اشاره گر ها فقط آدرس ها هستند، چرا بعضی ها آن را گیج کننده در میابند؟ دلیل این موضوع این است که اشاره گر ها یک فرم غیر مستقیم (indirection) از دستورالعمل ها می باشند. اگر شما دقت در عمل نداشته نباشید به سرعت دنباله اشاره گرها را در حافظه از دست خواهید داد و این موجب می شود برنامه شما کرش کند و یا کدنویسی بسیار پیچیده شود. با این حال راه فهم دقیق اشاره گر ها این است که به آرامی شروع به یادگیری آن کنید.
نکته ای درباره اشاره گرها و چند نکته پزشکی: اشاره گر ها در واقع یک ایده ساده هستند اما به منظور اینکه آن را کامل یاد بگیرید، باید وقت بسیار زیادی صرف کنید. همچنین به منظور بالا بردن راندمان یادگیری به صورت مداوم استراحت کنید، آب زیاد بنوشید و اگر خیلی خسته شدید یک دوش بگیرید و در هنگام فعالیت ذهنی کم غذا بخورید و در هر 3 ساعت یک فنجان قهوه با یک حبه قند بخورید و برای اینکه استرس خودتان را کاهش بدهید، چایی سبز و لیمو مصرف کنید.
ورود به درون حافظه
همانطور که قبلا اشاره کردم، به منظور اینکه بتوانید اشاره گر ها را به صورت دقیق متوجه شوید، شما نیاز خواهید داشت به درون حافظه کامپیوتر وارد شوید و آن را با دقت مورد بررسی قرار بدهید.
شایان ذکر است، هرگاه که شما یک متغیر تعریف می کنید، کامپیوتر برای آن در قسمتی از حافظه یک فضا ایجاد می کند. به عنوان مثال، اگر شما یک متغیر درون یک تابع مانند main() تعریف کنید، کامپیوتر آن را در یک قسمت از حافظه به نام پشته (Stack) ذخیره می سازد و اما اگر متغیر را در خارج از توابع تعریف کنید، آن متغیر درون قسمت عمومی (Globals) و همچنین اگر متغیری را به شکل ثابت تعریف کنید آن در قسمت ثابت (Constant) حافظه ذخیره خواهد شد. در تصویر زیر، به صورت بصری این موضوع نمایش داده شده است.
http://upcity.ir/images2/32409924367201993851.png
این نکته را هم به خاطر بسپارید، عملا کامپیوتر با حروف کار نمی کند. اساس کار کامپیوتر با اعداد و آدرس ها است (البته حروف هم معادل عددی دارند :ی ). مثلا هنگامی که شما یک متغیر با نام x در برنامه خود تعریف می کنید (کد نمایش داده شده در تصویر بالا را در نظر بگیرید)، کامپیوتر برای آن در آدرس 4.100.000 حافظه می گیرد، در نتیجه هر بار که به آن رجوع شود، در واقع به آدرس آن متغیر رجوع می شود و هنگامی که مقداری در آن متغییر ذخیره می گردد، در واقع مقداری در آدرس 4100000 ذخیره می شود.
به عبارت کلی تر، نام یک متغیر در واقع نامی هست که شما به یک قسمت از حافظه اختصاص می دهید تا به آن ساده تر دسترسی بگیرید. با این حال، اگر در موقعیتی نیاز داشتید که آدرس یک متغیر را درون حافظه بدست آورید، می توانید از عملوند & استفاده کنید. این عملوند باعث می شود آدرس یک قطعه داده یا در مفهوم شی گرایی (Object Oriented) آدرس یک شی (Object) بازگشت داده شود.
http://upcity.ir/images2/16287734334430871155.png
همانطور که در قطعه کد بالا مشاهده می کنید، ما توانستیم با استفاده از عملوند & و با استفاده از تابع printf آدرس متغیر در حافظه را به سادگی به دست آوریم.
نکته : خیلی مواقع مشاهده می کنم دانشجوهای گرامی با درک واژه شی (Object) کمی مشکل دارند و اساتید در دانشگاه با مثال زدن های بصری مانند آجر و دیوار و ماشین سعی در انتقال مفهوم شی موجود در علوم کامپیوتر را دارند که به نظر بنده بی سواد اشتباه است. طبق تعریف شی در ویکیپدیا و کورس Introduction to Programing دانشگاه کارنگی ملون (اسم استادش رو یادم رفته) شی در واقع چیزی در حافظه است که شامل داده (Data) و یک شناسه (Identifier) می شود که می توانند مجموعه ای از عملیات ها را انجام بدهند (البته به شکل خیلی خلاصه گفتم، شما هم بهتر است همین دید را فعلا نسبت به شی داشته باشید).
http://upcity.ir/images2/79231341616290823173.png
این آموزش ادامه خواهد داشت.
پیرو قرآن کریم، کلام پروردگار دانا : ذکات علم نشر آن است و همچنین مطابق با حرف امام یازدهم ما شیعیان، امام حسن عسگری (ع) : بهترین کار در دنیا دانش اندوزی و نشر آن به برادران است.
بنده خیلی علاقمند بودم آموزشی در رابطه با لیست های پیوندی آماده کنم و آن را در این قسمت از وب سایت برنامه نویس به اشتراک بگذارم. همانطور که می دانید، مفهوم لیست پیوندی بسیار مهم هست و یادگیری آن هم در ابتدا کمی مشکل و ترسناک می باشد. در این آموزش که بنده آنرا آماده کرده ام (البته عمده قسمت های این مقاله ترجمه یا کپی است) قصد دارم شما را گام به گام با پیاده سازی، طراحی و مفهوم لیست های پیوندی آشنا کنم. همچنین از آنجایکه بنده استاد نیستم و یک تازه کار بیش نمی باشم، انتظار دارم اگر در جایی استادی از من ایراد و اشتباهی دید آن را برای من رفع کرده تا از ادامه اشتباهات من جلوگیری کند. به هر حال، امیدوارم این مقاله کوچک، راهنمای تمامی دوستان و برادران من باشد.
مباحثی که در این مقاله مورد بررسی قرار خواهد گرفت:
اشاره گرها چی هستند و چرا از آن ها در برخی موقعیت ها استفاده می شود؟
اشاره گر ها در C و سی پلاس پلاس به چه شکل هستند؟!
ساختارها (Structure) موجود در زبان برنامه نویسی C چه هستند؟!
کلاس ها (Classes) در زبان برنامه نویسی سی پلاس پلاس چه هستند؟!
فرق بین کلاس ها و ساختارها در چیست؟
لیست پیوندی چیست و فرق آن با آرایه ها در چه می باشد؟
نحوه ذخیره سازی عناصر لیست پیوندی و آرایه ها در حافظه به چه شکل است؟
چرا باید از لیست پیوندی استفاده کنیم؟!
کاربرد لیست پیوندی در عمل چیست؟!
الگوریتم چیست و الگوریتم پیاده سازی لیست پیوندی به چه شکل است؟
پیاده سازی لیست پیوندی با ساختار ها به صورت غیر پویا
پیاده سازی لیست پیوندی با ساختار ها به صورت پویا
پیاده سازی تابع افزودن عنصر به لیست پیوندی
پیاده سازی تابع حذف عنصر از لیست پیوندی
پیاده سازی تابع نمایش عناصر موجود در لیست پیوندی
پیاده سازی لیست پیوندی با کلاس ها در زبان برنامه نویسی سی پلاس پلاس
خلاصه مقاله
منابع استفاده شده در نگاشت مقاله
http://upcity.ir/images2/68807010627099788353.jpg
اگر واقعا می خواهید یک برنامه نویس C حرفه ای شوید، نیاز دارید بدانید که C چگونه حافظه را کنترل می کند. زبان برنامه نویسی C بر سر اینکه برنامه شما چگونه از حافظه استفاده کند، کنترل بسیار زیادی به شما ارائه می دهد. در این قسمت شما خواهید فهمید که هنگامی که یک متغیر را تعریف می کنید در حافظه چه اتفاقی می افتد و در حالت کلی با نحوه کنترل حافظه آشنا خواهید شد. شایان ذکر است، به منظور اینکه اشاره گر ها را به درستی یاد بگیرید، باید با نحوه مدیریت اشیاء و داده ها در حافظه آشنایی دقیق و کاملی داشته باشید که در قسمت اول این مقاله به این موضوع خواهیم پرداخت.
اشاره گر ها در C
اشاره گرها یکی از اساسی ترین مفاهیم موجود در زبان برنامه نویسی C هستند که داشتن فهم دقیقی از آنها برای تمامی برنامه نویسان به این زبان الزامی است. اما خب، واقعا اشاره گر ها چه هستند؟! در جواب این سوال به سادگی می توان گفت، یک اشاره گر در واقع یک متغیر است که می تواند آدرس دیگر متغییر ها را در خودش نگه دارد. اشاره گر ها در C به دلایل مختلفی استفاده می شوند که برخی از آنها را در این مقاله با هم بررسی خواهیم کرد.
http://upcity.ir/images2/31824595417338855386.jpg
دلیل اول : در برخی شرایط هنگام برنامه نویسی، نیاز دارید کپی از داده ها موجود در برنامه را به یک تابع از برنامه عبور دهید. این عمل باعث اتلاف حافظه و پایین آمدن راندمان کار برنامه می شود. با این حال، به منظور رفع کردن این مشکل، شما می توانید به سادگی آدرس آن داده های را با استفاده از اشاره گر ها به تابع خود عبور دهید و از اتلاف حافظه و پایین آمدن سرعت کار برنامه جلوگیری کنید.
http://upcity.ir/images2/96748519627214928423.png
دلیل دوم : گاهی اوقات شما نیاز دارید دو تابع به صورت همزمان بر روی قسمتی از داده های برنامه شما کار کنند، در این موقعیت می توانید از اشاره گر ها و آدرس آن قطعه داده استفاده کنید.
http://upcity.ir/images2/61767029443816734656.png
اشاره گر ها به شما کمک می کنند دو مورد ذکر شده در بالا را به سادگی انجام بدهید، یعنی از کپی کردن داده ها در برنامه خود جلوگیری کنید و داده های درون برنامه را به اشتراک بگذارید. اما اگر اشاره گر ها فقط آدرس ها هستند، چرا بعضی ها آن را گیج کننده در میابند؟ دلیل این موضوع این است که اشاره گر ها یک فرم غیر مستقیم (indirection) از دستورالعمل ها می باشند. اگر شما دقت در عمل نداشته نباشید به سرعت دنباله اشاره گرها را در حافظه از دست خواهید داد و این موجب می شود برنامه شما کرش کند و یا کدنویسی بسیار پیچیده شود. با این حال راه فهم دقیق اشاره گر ها این است که به آرامی شروع به یادگیری آن کنید.
نکته ای درباره اشاره گرها و چند نکته پزشکی: اشاره گر ها در واقع یک ایده ساده هستند اما به منظور اینکه آن را کامل یاد بگیرید، باید وقت بسیار زیادی صرف کنید. همچنین به منظور بالا بردن راندمان یادگیری به صورت مداوم استراحت کنید، آب زیاد بنوشید و اگر خیلی خسته شدید یک دوش بگیرید و در هنگام فعالیت ذهنی کم غذا بخورید و در هر 3 ساعت یک فنجان قهوه با یک حبه قند بخورید و برای اینکه استرس خودتان را کاهش بدهید، چایی سبز و لیمو مصرف کنید.
ورود به درون حافظه
همانطور که قبلا اشاره کردم، به منظور اینکه بتوانید اشاره گر ها را به صورت دقیق متوجه شوید، شما نیاز خواهید داشت به درون حافظه کامپیوتر وارد شوید و آن را با دقت مورد بررسی قرار بدهید.
شایان ذکر است، هرگاه که شما یک متغیر تعریف می کنید، کامپیوتر برای آن در قسمتی از حافظه یک فضا ایجاد می کند. به عنوان مثال، اگر شما یک متغیر درون یک تابع مانند main() تعریف کنید، کامپیوتر آن را در یک قسمت از حافظه به نام پشته (Stack) ذخیره می سازد و اما اگر متغیر را در خارج از توابع تعریف کنید، آن متغیر درون قسمت عمومی (Globals) و همچنین اگر متغیری را به شکل ثابت تعریف کنید آن در قسمت ثابت (Constant) حافظه ذخیره خواهد شد. در تصویر زیر، به صورت بصری این موضوع نمایش داده شده است.
http://upcity.ir/images2/32409924367201993851.png
این نکته را هم به خاطر بسپارید، عملا کامپیوتر با حروف کار نمی کند. اساس کار کامپیوتر با اعداد و آدرس ها است (البته حروف هم معادل عددی دارند :ی ). مثلا هنگامی که شما یک متغیر با نام x در برنامه خود تعریف می کنید (کد نمایش داده شده در تصویر بالا را در نظر بگیرید)، کامپیوتر برای آن در آدرس 4.100.000 حافظه می گیرد، در نتیجه هر بار که به آن رجوع شود، در واقع به آدرس آن متغیر رجوع می شود و هنگامی که مقداری در آن متغییر ذخیره می گردد، در واقع مقداری در آدرس 4100000 ذخیره می شود.
به عبارت کلی تر، نام یک متغیر در واقع نامی هست که شما به یک قسمت از حافظه اختصاص می دهید تا به آن ساده تر دسترسی بگیرید. با این حال، اگر در موقعیتی نیاز داشتید که آدرس یک متغیر را درون حافظه بدست آورید، می توانید از عملوند & استفاده کنید. این عملوند باعث می شود آدرس یک قطعه داده یا در مفهوم شی گرایی (Object Oriented) آدرس یک شی (Object) بازگشت داده شود.
http://upcity.ir/images2/16287734334430871155.png
همانطور که در قطعه کد بالا مشاهده می کنید، ما توانستیم با استفاده از عملوند & و با استفاده از تابع printf آدرس متغیر در حافظه را به سادگی به دست آوریم.
نکته : خیلی مواقع مشاهده می کنم دانشجوهای گرامی با درک واژه شی (Object) کمی مشکل دارند و اساتید در دانشگاه با مثال زدن های بصری مانند آجر و دیوار و ماشین سعی در انتقال مفهوم شی موجود در علوم کامپیوتر را دارند که به نظر بنده بی سواد اشتباه است. طبق تعریف شی در ویکیپدیا و کورس Introduction to Programing دانشگاه کارنگی ملون (اسم استادش رو یادم رفته) شی در واقع چیزی در حافظه است که شامل داده (Data) و یک شناسه (Identifier) می شود که می توانند مجموعه ای از عملیات ها را انجام بدهند (البته به شکل خیلی خلاصه گفتم، شما هم بهتر است همین دید را فعلا نسبت به شی داشته باشید).
http://upcity.ir/images2/79231341616290823173.png
این آموزش ادامه خواهد داشت.