آموزش تصویری برنامه نویسی ++C و C – تابع QSort و لیست های پیوندی
قسمت اول این فیلم آموزشی در مورد تابع QSort و همچنین قسمت دوم این فیلم آموزشی در مورد لیست های پیوندی(Linked List) می باشد.
قبل از معرفی تابع Qsort می خواهیم ابتدا روش مرتب سازی Quicksort را در موردش توضیح دهیم تا شما بتوانید تابع QSort را راحت تر درک کنید.
روش مرتبسازی سریع (Quick Sort) :
یکی از الگوریتمهای مشهور مرتبسازی دادهها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن دادهها ارائه مینماید:
۱- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) – به عنوان مثال عنصر اول – انتخاب میشود.
۲- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده میشود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایههای چپ و راست نامیده میشوند.
۳- مرتبسازی بازگشتی: زیرآرایههای چپ و راست به روش مرتبسازی سریع مرتب میشوند.
تابع QSort:
یک تابع استاندارد در زبان برنامه نویسی C می باشد که با استفاده از الگوریتم Quicksort شروع به مرتب سازی لیست ها و آرایه های می کند.
نحوه استفاده از این تابع به صورت زیر می باشد.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/* qsort example */ #include <stdio.h> /* printf */ #include <stdlib.h> /* qsort */ int values[] = { 40, 10, 100, 90, 20, 25 }; int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main () { int n; qsort (values, 6, sizeof(int), compare); for (n=0; n<6; n++) printf ("%d ",values[n]); return 0; } |
لیست پیوندی:
فهرست پیوندی یا لیست پیوندی (Linked list) ساختاری شامل دنبالهای از عناصر است که هر عنصر دارای اشارهگری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ سادهترین و رایجترین دادهساختارها است و در پیادهسازی از دادهساختارها پشته (Stack)، صف (Queue) و جدول درهمسازی (Hash table) استفاده میشود. مزیت مهم فهرست پیوندی نسبت به آرایهها این است که ترتیب قرار گرفتن دادهها در آن با ترتیب قرار گرفتن آنها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گرهها در هر نقطهای از فهرست، با تعداد ثابتی از عملیات امکانپذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس گذاری را نمیدهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد.
نمونه کد در مورد لیست پیوندی
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include "Node.cpp" using namespace std; int main () { Node<char> *p,*q,*r; // Link the nodes with each other q = new Node<char>('B'); // here nxtptr is passed by a nullptr by default p = new Node<char>('A',q); r = new Node<char>('C'); // modify the list q->InsertAfter(r); /* Call the InsertAfter method that belongs to the object pointed by q, as paramater, pass to it the address contained in r. */ cout << "p:" << p->data << endl; // "A" will be printed out cout << "p_next:" << p->NextNode()->data << endl; // "B" will be printed out cout << "q:" << q->data << endl; // "B" will be printed out cout << "q_next:" << q->NextNode()->data << endl; // "C" will be printed out cout << "r:" << r->data << endl; // "C" will be printed out p = p->NextNode(); // p now points to the node coming after the node it was // previously pointing to. cout << endl; cout << "p:" << p->data << endl; // "B" will be printed out r = q->DeleteAfter(); // copy to r the address of the node pointed by //the node pointed by the node pointed by q, and remove that node from the list Node<char> *head; head = GetNode('A',GetNode('B',GetNode('C'))); /* Here above method, creates a list which has nodes having data A,B,C and each node pointing to the next one respectively. */ delete q; delete p; delete r; return 0; } |
با تشکر فراوان از استاد “کیارش بازرگان ”
دانلود این فیلم آموزشیپیروزباشید، طراح باشی
پیروز باشید!
طراح باشی
نوشتن دیدگاه