آموزش تصویری برنامه نویسی ++C و C – تابع QSort و لیست های پیوندی

قسمت اول این فیلم آموزشی در مورد تابع QSort و همچنین قسمت دوم این فیلم آموزشی در مورد لیست های پیوندی‌(Linked List) می باشد.

قبل از معرفی تابع Qsort می خواهیم ابتدا روش مرتب سازی Quicksort را در موردش توضیح دهیم تا شما بتوانید تابع QSort را راحت تر درک کنید.

روش مرتب‌سازی سریع (Quick Sort) :

یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

۱- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) – به عنوان مثال عنصر اول – انتخاب می‌شود.

۲- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.

۳- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.

تابع QSort:

یک تابع استاندارد در زبان برنامه نویسی C می باشد که با استفاده از الگوریتم Quicksort شروع به مرتب سازی لیست ها و آرایه های می کند.

نحوه استفاده از این تابع به صورت زیر می باشد.

/* 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;
}

/* 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) می باشد.

لیست پیوندی:

فهرست پیوندی یا لیست پیوندی (Linked list) ساختاری شامل دنباله‌ای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است. فهرست پیوندی از جملهٔ ساده‌ترین و رایج‌ترین داده‌ساختارها است و در پیاده‌سازی از داده‌ساختارها پشته (Stack)، صف (Queue) و جدول درهم‌سازی (Hash table) استفاده می‌شود. مزیت مهم فهرست پیوندی نسبت به آرایه‌ها این است که ترتیب قرار گرفتن داده‌ها در آن با ترتیب قرار گرفتن آن‌ها در حافظه متفاوت است. به همین دلیل فهرست پیوندی دارای این ویژگی است که درج و حذف گره‌ها در هر نقطه‌ای از فهرست، با تعداد ثابتی از عملیات امکان‌پذیر است. از طرف دیگر فهرست پیوندی اجازه دستیابی تصادفی به داده یا هرگونه اندیس گذاری را نمی‌دهد. در نتیجه بسیاری از اعمال ابتدایی نظیر به دست آوردن آخرین عنصر فهرست، پیدا کردن عنصر شامل داده مورد نظر، یا مشخص کردن مکان درج یک عنصر جدید ممکن است نیازمند بررسی اکثر عناصر فهرست باشد.

نمونه کد در مورد لیست پیوندی

#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;
}

#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;

}

با تشکر فراوان از استاد “کیارش بازرگان ”

دانلود این فیلم آموزشی

پیروزباشید، طراح باشی

پیروز باشید!
طراح باشی

آموزش تصویری برنامه نویسی ++C و C – تابع QSort و لیست های پیوندی

آموزش تصویری برنامه نویسی ++C و C – تابع QSort و لیست های پیوندی

درباره نویسنده

طراح‌باشی

نوشتن دیدگاه

لغو پاسخ

مشترک خبرنامه شوید

نوشته‌های تازه

پربازدیدها

آموزش تصویری برنامه نویسی ++C و C – تابع QSort و لیست های پیوندی

ممکن است دوست داشته باشید

درباره نویسنده

طراح‌باشی

نوشتن دیدگاه

مشترک خبرنامه شوید

نوشته‌های تازه

پربازدیدها