در توسینسو تدریس کنید

و

با دانش خود درآمد کسب کنید

آموزش برنامه نویسی C قسمت 27 : لیست پیوندی (Linked List)

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

1- اندازه یک آرایه همیشه در طول برنامه ثابت است و نمیتوان تغییرش داد. ولی لیست پیوندی را میتوان بنا بر نیاز گسترش داد و یا از طولش کم کرد.

2- خانه های آرایه در فضاهای پشت سر هم در حافظه ذخیره میشوند در حالی که خانه های لیست پیوندی در هر جای فضای حافظه میتوانند ذخیره شوند و این خانه های پراکنده را با اشاره گر هایی بهم متصل میکنیم.

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

خانه های لیست پیوندی چطور در حافظه ذخیره میشوند ؟

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

struct test_struct
{
    int value;
    struct test_struct *next;
};

این structure از یک مقدار value و یک اشاره گر ساخته شده است. نوع value هرچیزی میتواند باشد. اشاره گر next هم به خانه بعدی لیست پیوندی اشاره میکند. پس با این اشاره گر ها میتوان لیست پیوندی را پیمایش کرد و از یکی یه دیگری رفت. به شکل زیر دقت کنید. این یک "لیست پیوندی ساده یک طرفه" است.

آموزش برنامه نویسی C  قسمت 27 : لیست پیوندی (Linked List)

چطور یک نود لیست پیوندی ایجاد میشود؟

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

struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));

تابع malloc قطعه ای از حافظه را به مقدار یا ساختاری که به عنوان آرگومان به او دادیم را اختصاص میدهد. در اینجا گفتیم به اندازه ( size of ) ساختار test_struct قطعه ای از حافظه را جدا کن. فقط باید دقت داشته باشید که malloc یک اشاره گر void برمیگرداند. پس خروجی آن را باید cast کنیم. عبارت داخل پرانتز قبل از malloc این کار را میکند. خروجی malloc را به یک اشاره گر از جنس struct تبدیل میکند که بتوانیم آنرا داخل ptr بریزیم. بعد از اینکه نود بوجود آمد، میتوان مقادیری را به آن اختصاص داد تا نگه دارد. اگر هم آخرین نود ما باشد به اشاره گر خانه بعدی آن مقدار null را اختصاص میدهیم. کد زیر:

ptr->value = my_value;
ptr->next = NULL;

چطور یک لیست پیوندی را پیمایش کنیم؟

پیمایش و جستجو در لیست پیوندی یعتی دنبال یک محتوای خاص در لیست پیوندی باشیم. روش کار خیلی ساده است. از خانه اول شروع کرده و دونه دونه جلو میرویم و مقدار مورد نظر را با مقدار ذخیره شده در لیست ها مطابقت میدهیم. این کار را تا موقعی که به انتهای لیست نرسیده ایم ادامه میدهیم. به کد زیر دقت کنید.

 while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            ptr = ptr->next;
        }
    }

یک نود چطور در لیست پیوندی پاک میشود؟

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

کد زیر یک مثال جامع برای اضافه کردن نود، جستجوی نود و حذف نود است.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

struct test_struct
{
    int val;
    struct test_struct *next;
};

struct test_struct *head = NULL;
struct test_struct *curr = NULL;

struct test_struct* create_list(int val)
{
    printf("\n creating list with headnode as [%d]\n",val);
    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    head = curr = ptr;
    return ptr;
}

struct test_struct* add_to_list(int val, bool add_to_end)
{
    if(NULL == head)
    {
        return (create_list(val));
    }

    if(add_to_end)
        printf("\n Adding node to end of list with value [%d]\n",val);
    else
        printf("\n Adding node to beginning of list with value [%d]\n",val);

    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    if(add_to_end)
    {
        curr->next = ptr;
        curr = ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}

struct test_struct* search_in_list(int val, struct test_struct **prev)
{
    struct test_struct *ptr = head;
    struct test_struct *tmp = NULL;
    bool found = false;

    printf("\n Searching the list for value [%d] \n",val);

    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(true == found)
    {
        if(prev)
            *prev = tmp;
        return ptr;
    }
    else
    {
        return NULL;
    }
}

int delete_from_list(int val)
{
    struct test_struct *prev = NULL;
    struct test_struct *del = NULL;

    printf("\n Deleting value [%d] from list\n",val);

    del = search_in_list(val,&prev);
    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
            prev->next = del->next;

        if(del == curr)
        {
            curr = prev;
        }
        else if(del == head)
        {
            head = del->next;
        }
    }

    free(del);
    del = NULL;

    return 0;
}

void print_list(void)
{
    struct test_struct *ptr = head;

    printf("\n -------Printing list Start------- \n");
    while(ptr != NULL)
    {
        printf("\n [%d] \n",ptr->val);
        ptr = ptr->next;
    }
    printf("\n -------Printing list End------- \n");

    return;
}

int main(void)
{
    int i = 0, ret = 0;
    struct test_struct *ptr = NULL;

    print_list();

    for(i = 5; i<10; i++)
        add_to_list(i,true);

    print_list();

    for(i = 4; i>0; i--)
        add_to_list(i,false);

    print_list();

    for(i = 1; i<10; i += 4)
    {
        ptr = search_in_list(i, NULL);
        if(NULL == ptr)
        {
            printf("\n Search [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n Search passed [val = %d]\n",ptr->val);
        }

        print_list();

        ret = delete_from_list(i);
        if(ret != 0)
        {
            printf("\n delete [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n delete [val = %d]  passed \n",i);
        }

        print_list();
    }

    return 0;
}

دقت داشته باشید که :

1- اولین نود از طریق یک اشاره گر سراسری به نام head مشخص میشود.

2- آخرین نود در لیست هم با اشاره گر curr مشخص میشود، حتی اگر نود آخر هم پاک شود، نود قبل آن نود پایانی میشود.

3- هر بار که نودی به لیست اضافه میشود، چک میکند که آیا لیست خالی است یا خیر که آگر خالی باشد آنرا به عنوان نود head در نظر بگیرد.

خروجی :

 -------Printing list Start------- 

 -------Printing list End------- 

 creating list with headnode as [5]

 Adding node to end of list with value [6]

 Adding node to end of list with value [7]

 Adding node to end of list with value [8]

 Adding node to end of list with value [9]

 -------Printing list Start------- 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Adding node to beginning of list with value [4]

 Adding node to beginning of list with value [3]

 Adding node to beginning of list with value [2]

 Adding node to beginning of list with value [1]

 -------Printing list Start------- 

 [1] 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [1] 

 Search passed [val = 1]

 -------Printing list Start------- 

 [1] 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [1] from list

 Searching the list for value [1] 

 delete [val = 1]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [5] 

 Search passed [val = 5]

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [5] from list

 Searching the list for value [5] 

 delete [val = 5]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [9] 

 Search passed [val = 9]

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [9] from list

 Searching the list for value [9] 

 delete [val = 9]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 -------Printing list End-------

خوب دوستان خسته نباشید، من که خسته شدم. فکر میکنم در حد مقدماتی و برای راه افتادن کافیه این مباحث. یادمه مبانی ترم یک و برنامه نویسی پیشرفته ترم 2 رو هم انقدر محتوا نداشت!!! از ساختمان داده ترم 3 هم یه چیزایی گفتیم. اگر بخوایم بحث رو ادامه بدیم واقعا نمیدونم چند قسمت دیگه باید بنویسم، ولی فک کنم برای بخش اولش کافیه از اینجا به بعد یکم مباحث پیشرفته تر میشه. بهتره تو یه بخش جدا باشه ولی قول میدم بزودی ادامه بدم C رو، الان خودمم یکم به تنوع نیاز دارم !!! دوست دارم درمورد مباحث دیگه هم مطلب بزارم، اونجا همدیگرو میبینیم، بزودی در دوره بعدی C هم همدیگرو میبینیم. :)))

قسمت آخر بخش مقدماتی

نویسنده : سید محمد باقر موسوی

منبع : جزیره برنامه نویسی وب سایت توسینسو

هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی است

#برنامه_نویسی_به_زبان_c #نوشتن_shell_script_در_لینوکس #زبان_برنامه_نویسی_c_در_لینوکس #برنامه_نویسی_c_در_محیط_لینوکس #برنامه_نویسی_به_زبان_c_در_لینوکس #لیست_پیوندی #آموزش_گام_به_گام_برنامه_نویسی_c #برنامه_نویسی_c_در_linux #آموزش_برنامه_نویسی_c_در_لینوکس
عنوان
1 آموزش برنامه نویسی C قسمت 1 : نصب محیط برنامه نویسی رایگان
2 آموزش برنامه نویسی C قسمت 2 : Hello World رایگان
3 آموزش برنامه نویسی C قسمت 3 : Data Types رایگان
4 آموزش برنامه نویسی C قسمت 4 : Data Types رایگان
5 آموزش برنامه نویسی C قسمت 5 : اشاره گر ها رایگان
6 آموزش برنامه نویسی C قسمت 6 : آرایه ها رایگان
7 آموزش برنامه نویسی C قسمت 7 : ساختار شرط IF رایگان
8 آموزش برنامه نویسی C قسمت 8 : حلقه for رایگان
9 آموزش برنامه نویسی C قسمت 9 : حلقه While رایگان
10 آموزش برنامه نویسی C قسمت 10 : Struct رایگان
11 آموزش برنامه نویسی C قسمت 11 : تابع دریافت ورودی scanf رایگان
12 آموزش برنامه نویسی C قسمت 12 : فایل های متنی و باینری رایگان
13 آموزش برنامه نویسی C قسمت 13 : توابع رایگان
14 آموزش برنامه نویسی C قسمت 14 : توابع اشاره گر رایگان
15 آموزش برنامه نویسی C قسمت 15 : argc argv رایگان
16 آموزش برنامه نویسی C قسمت 16 : Multiple Source Files رایگان
17 آموزش برنامه نویسی C قسمت 17 : String Functions & Operations رایگان
18 آموزش برنامه نویسی C قسمت 18 : Char Pointers VS Array Char رایگان
19 آموزش برنامه نویسی C قسمت 19 : Binary & Unary Operations رایگان
20 آموزش برنامه نویسی C قسمت 20 : Type Casting رایگان
21 آموزش برنامه نویسی C قسمت 21 : readdir & opendir functions رایگان
22 آموزش برنامه نویسی C قسمت 22 : Fork Function رایگان
23 آموزش برنامه نویسی C قسمت 23 : Thread رایگان
24 آموزش برنامه نویسی C قسمت 24 : Switch Case Statement رایگان
25 آموزش برنامه نویسی C قسمت 25 : qsort رایگان
26 آموزش برنامه نویسی C قسمت 26 : Socket Programming رایگان
27 آموزش برنامه نویسی C قسمت 27 : لیست پیوندی (Linked List) رایگان
زمان و قیمت کل 0″ 0
0 نظر

هیچ نظری ارسال نشده است! اولین نظر برای این مطلب را شما ارسال کنید...

نظر شما
برای ارسال نظر باید وارد شوید.
از سرتاسر توسینسو
تنظیمات حریم خصوصی
تائید صرفنظر
×

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