لیست پیوندی

[fond]

با سلام

خب من یه چیزهایی رو پاک کردم که خوندن کد راحتتر بشه. هنوز خیلی از توابع رو پیاده سازی نکردم چون هنوز نتوستم تابع ()insert رو بنویسم. این کدی بود که من نوشتم اما اون طور که انتظار دارم کار نمی‌کنه:

تابع ()print قراره لیست رو چاپ کنه. تابع ()addfirst یه چیزی رو به اول لیست اضافه می‌کنه و تابع ()insert یک چیزی رو در یک جای خاص از لیست قرار می‌دهد و تابع ()getnode هم یک node میگیره.

فایل list.h

کد: [انتخاب]

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

typedef struct node node;

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

node *getnode();
void addfirst(node**,int);
void print(node *);
void insert(node **, int, int);

فایل list.c

کد: [انتخاب]

#include "list.h"


int main()
{
        node *list;

        insert(&list, 0, 5);
        insert(&list, 1, 10);
        insert(&list, 2, 15);
        insert(&list, 3, 20);

        print(list);

        return 0;
}

node *getnode()
{
        node* temp;
        temp = (node*) malloc( sizeof(node) );

        if( temp != NULL )
                return temp;

        abort();
}

void addfirst( node **ptr, int val )
{
        node *temp = getnode();
        temp -> value = val;
        temp -> next = *ptr;
        (*ptr) = temp;
}

void print( node *ptr )
{
        while( ptr )
        {
                printf("%d\n", ptr -> value );
                ptr = ptr -> next;
        }
}

void insert(node **ptr, int index, int val)
{


        if(index == 0)
        {
                addfirst(ptr, val);
        }
        else
        {
                node *temp = getnode();
                temp -> value = val;

                int j;

                for(j=1; j < index; j++)
                {
                        (*ptr) = (*ptr) -> next;
                }

                temp -> next = (*ptr) -> next;
                (*ptr) -> next = temp;
        }

}

خیلی ممنونم

[فاراب]

من نفهمیدم دقیقا مشکل چیه. اما کتاب ساختمان داده‌ها هم کد و هم توضیح رو داره. فکر میکنم اینجوری بهتر باشه. در ضمن کد آماده هم خیلی راحت گیر میاد گوگل کنید. وقتی قبلا نوشته شده چه نیازی به نوشتن مجدد کد هست. . اگر جایی مشکل داشتید بفرمایید.

[fond]

حقیقتش قصدم فقط یادگیری هست. درسته که قبلا توی کتابخانه stl و همینطور جاهای دیگه پیاده سازی شده اما من فقط هدفم یادگیری هست. من دارم از روی کتاب ساختمان داده‌های هوریتز پیش میرم. از بین اون توابعی که قرار دادم، همگی به جز ()insert کار می‌کنن. برنامه هم اصلا اجرا نمیشه و coredump میشه.

خیلی ممنون که توجه کردید

[فاراب]

لیست پیوندی بیشتر با ++C پیاده میشه. اما شما انگار با C کار میکنید.
کد زیر بصورت کامل تست شده است و بجای insert از enter استفاده میکنه. تمام حقوقش هم متعلق به Sundown از سایت http://barnamenevis.org/ هست. امیدوارم به کارتون بیاد:

کد: [انتخاب]


/*//////////////////////////////
Structure In C
*///////////////////////////////

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>     
#include <ctype.h>
#define  TRUE  1
#define NIL (struct Employee *)NULL
struct Employee {
       char name[30] ;
       int ID ;
       char JobTittle[30] ;
   char Addres[30];
       struct Employee *next ;
} ;
struct Employee *first , *last , *node ;
void enter ();
void list ();
void del ();
void FindByID();
int main ()
{   
char  s[10] ;
    first = NIL ;
    while (TRUE) {


     printf("E:\tEnter New Employee\n");

     printf("R:\tRemove a Employee\n");

     printf("L:\tList All Of The Employee\n");

printf("F:\tFind Employee By ID\n");

     printf("Q:\tQuit The Program\n") ;

     printf("Make Your Choice :  ");
     printf("( E R L F Q) :   ") ;
     gets(s) ;
     *s = toupper(*s) ;
     switch (*s) {
   case 'E' :
       enter() ;
       break ;
   case 'L' :
       list() ;        
       break ;
   case 'R' :
       del() ;
       break ;
   case 'F':
   FindByID();
   break;
   case 'Q' :
       exit(0) ;
     }
   }
return 0;
}
//********************
void enter ()
  {
   char numstr[30] ;
   node = (struct Employee *)malloc(sizeof(struct Employee));
   node -> next = NIL ;
   if (first == NIL)
       first = last = node ;
   else  {

   last -> next = node ;

last = node ;
   }
   printf("\n Enter name of Employee:");
   gets(last -> name) ;

   printf("\n Enter Employee ID :");
   gets(numstr) ;
   last -> ID = atoi(numstr) ;

   printf("\n Enter Employee JobTittle :");   
   gets(last -> JobTittle) ;

   printf("\n Enter Addres :");   
   gets(last -> Addres) ;

}
//********************
void list ( )
{
     printf("\n\n\n\n");
int i ;
     if (first == NIL) {
printf("\n<< the list is empty .>>") ;
getch() ;
return ;
     }
     last = first ;


     printf("\t\tName\t\tNumber\t\tJobTittle\tAddres\n");

      printf("\t\t----\t\t------\t\t--------\t---------") ;
      i = 6 ;
  printf("\n\n");
      do {

printf("\t\t");
   printf("%s", last -> name) ;

   printf("\t\t");
   printf("%d", last -> ID) ;

   printf("\t\t");
   printf("%s", last -> JobTittle) ;

   printf("\t\t");
   printf("%s",last -> Addres);
   i ++ ;
   last=last -> next ;
   printf("\n\n");
      } while (last != NIL) ;

  printf("\n\n\n\n");
      printf("\t\t********************************************") ;     

      printf("\npress a key to continue...");  
      getch() ;
  printf("\n\n");
}
//*******************
void del ()
{
    int stnumber ;

    printf("Enter Employee ID for delete:");
    scanf("%d", &stnumber) ;
    last = node = first ;
    while (last != NIL)
    {
     if (last -> ID!=stnumber)  {
  node = last ;
  last = last -> next ;
  continue ;
     }
     else
{
if (last == first)
{
first=last -> next ;
free(last) ;
free(node) ;
break ;
}
else
{
     node -> next=last -> next;
     free(last) ;
break ;
}
     }
    }
}

//*******************
void FindByID()
{
    int stnumber ;
  if (first == NIL) {
printf("\n<< the list is empty .>>") ;
getch() ;
return ;
     }
last = first ;
    printf("\n\nEnter Employee ID To Search It : ");
    scanf("%d", &stnumber) ;
   
  printf("\n\n\t\tName\t\tNumber\t\tJobTittle\tAddres\n");

      printf("\t\t----\t\t------\t\t--------\t---------") ;     
  printf("\n\n");

do
{

if (last -> ID==stnumber)

{
printf("\t\t");
printf("%s", last -> name) ;

printf("\t\t");
printf("%d", last -> ID) ;

printf("\t\t");
printf("%s", last -> JobTittle) ;

printf("\t\t");
printf("%s",last -> Addres);


printf("\n\n");
}
last=last -> next ;
      } while (last != NIL) ;

  printf("\n\n\n\n");
      printf("\t\t********************************************") ;     

      printf("\npress a key to continue...");  
      getch() ;
  printf("\n\n");


}





[کیان]

جزییات بیشتری به عنوان تاپیک اضافه کن!

[fond]

خیلی ممنون به خاطر اون برنامه. توی ++c با کلاسها میشه خیلی راحت لیست رو پیاده سازی کرد. حتی یه پیاده سازی از لیست دو طرفه هم توی کتابخانه stl وجود داره.

اون برنامه به نظر من چند تا اشکال داره:

اول اینکه اون برنامه از متغیرهای سراسری استفاده می‌کنه که این خوب نیست. بهتره اطلاعات رو از طریق پارامترها به توابع بفرستیم که کد پرتابل تر بشه و اشکالزدایی هم راحت‌تر بشه (تا جایی که ممکنه نباید از متغیر سراسری استفاده کرد)
دوم اینکه اون برنامه طوری نوشته شده که بتونه با کاربر به صورت تعاملی رفتار کنه. اما معمولا لیست پیوندی باید توسط برنامه نویس استفاده بشه.

من تابع ()insert رو بدین صورت بازنویسی کردم و همه چیز درست شد:

کد: [انتخاب]

void insert(node **head, int index, int val)
{
        node *ptr = (*head);

        if(index == 0)
        {
                addfirst(head, val);
        }
        else
        {
                node *temp = getnode();
                temp -> value = val;

                int j;

                for(j=1; j < index; j++)
                {
                        ptr = ptr -> next;
                }

                temp -> next = ptr -> next;
                ptr -> next = temp;
        }
   
}


[فاراب]

خیلی ممنون به خاطر اون برنامه. توی ++c با کلاسها میشه خیلی راحت لیست رو پیاده سازی کرد. حتی یه پیاده سازی از لیست دو طرفه هم توی کتابخانه stl وجود داره.

اون برنامه به نظر من چند تا اشکال داره:

اول اینکه اون برنامه از متغیرهای سراسری استفاده می‌کنه که این خوب نیست. بهتره اطلاعات رو از طریق پارامترها به توابع بفرستیم که کد پرتابل تر بشه و اشکالزدایی هم راحت‌تر بشه (تا جایی که ممکنه نباید از متغیر سراسری استفاده کرد)
دوم اینکه اون برنامه طوری نوشته شده که بتونه با کاربر به صورت تعاملی رفتار کنه. اما معمولا لیست پیوندی باید توسط برنامه نویس استفاده بشه.

من تابع ()insert رو بدین صورت بازنویسی کردم و همه چیز درست شد:

کد: [انتخاب]

void insert(node **head, int index, int val)
{
        node *ptr = (*head);

        if(index == 0)
        {
                addfirst(head, val);
        }
        else
        {
                node *temp = getnode();
                temp -> value = val;

                int j;

                for(j=1; j < index; j++)
                {
                        ptr = ptr -> next;
                }

                temp -> next = ptr -> next;
                ptr -> next = temp;
        }
   
}


کاملا درسته. امیدوارم همیشه توی برنامه نویسی موفق باشید.

[fond]

خب نسخه تقریبا کامل شدش رو اینجا میذارم تا شاید بدرد دوستان دیگه هم بخوره. البته این بیشتر شبیه یه شبه کده و خوب باید خودتون تغییرش بدید.

کد: [انتخاب]

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

typedef struct node node;

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

node *getnode();
void addfirst(node**, int);
int getfirst(node**);
void print(node *);
int get(node*, int);
void deletelist(node**);
void insert(node **, int, int);
void del(node **, int);
int search(node *, int val);



node *
getnode()
{
node* temp;
temp = (node*) malloc( sizeof(node) );

if( temp != NULL )
{
temp -> next = NULL;
return temp;
}

exit(EXIT_FAILURE);
}

void
addfirst( node **ptr,
int val )
{
node *temp = getnode();
temp -> value = val;
temp -> next = *ptr;

(*ptr) = temp;

}

int
getfirst(node **ptr)
{
node *temp = *ptr;
*ptr = (*ptr) -> next;

free(*ptr);

return temp -> value;
}

void
print( node *ptr )
{
while( ptr )
{
printf("%d\n", ptr -> value );
ptr = ptr -> next;
}
}

int
get(node *head,
int i)
{
        node *ptr = head;

        while( --i )
        {
                ptr = ptr -> next;
        }
   
        return (ptr -> value);
}


void
deletelist( node **head )
{
        node *ptr = *head;
node *next;

        while( ptr )
        {
next = ptr -> next;
free(ptr);
ptr = next;
        }
}

void
insert(node **head,
int index,
int val)
{
node *ptr = (*head);

if(index == 0)
{
addfirst(head, val);
}

else
{
node *temp = getnode();
temp -> value = val;

int j;

for(j=1; j < index; j++)
{
ptr = ptr -> next;
}


temp -> next = ptr -> next;
ptr -> next = temp;

}

}


void
del( node **head,
int index )
{

if( index == 0 )
{
node *ptr = (*head);

(*head) = ptr -> next;

free(ptr);

}

else
{
node *preptr = (*head);
node *ptr = preptr -> next;

int j;

for(j=1; j < index; j++)
{
preptr = preptr -> next;
ptr = preptr -> next;
}

preptr -> next = ptr -> next;

free(ptr);

}


}

int
search(node *head,
int val)
{
int i = 0;

node *ptr = head;

while( ptr )
{
if( (ptr -> value) == val )
return i;
i++;

ptr = ptr -> next;
}

return (-1);
}


[fond]

شاید بهتر باشه یه توضیح مختصری هم بدم. هر چند برنامه سادست و قابل فهمه اما خوب شاید این توضیحات برای دوستانی که قصد یادگیری دارند مناسب باشه:

این عمل یه لیست خالی ایجاد می‌کنه:

کد: [انتخاب]

node *list1 = getnode()
این عمل هم یه مقدار جدید رو به ابتدای لیست اضافه می‌کنه (همون push):

کد: [انتخاب]

void addfirst(node **head, int value);

اولین عنصر لیست رو برمیگردونه و بعدش اونو از لیست حذف می‌کنه (همون pop):

کد: [انتخاب]

int getfirst(node **head);

 لیست رو چاپ می‌کنه:

کد: [انتخاب]

void print(node *head);
یه عنصر رو از هر جای دلخواهی از لیست بازیابی می‌کنه اما اون رو حذف نمیکنه:

کد: [انتخاب]

int get(node *head, int index);
که index اندیس همون عنصری هست که می‌خوایم بازیابی بشه.

لیست رو کامل حذف می‌کنه:

کد: [انتخاب]

void deletelist(node **head);
یه عنصری رو به هر جای لیست اضافه می‌کنه:

کد: [انتخاب]

void insert(node **head, int index, int val);
که index مکانی هست که می‌خوایم val اضافه بشه.

این یکی هم یه عنصر رو از هر جای لیست حذف می‌کنه:

کد: [انتخاب]

void del(node **head, int index);
برای جستجوی یک مقدار در لیست:

کد: [انتخاب]

int search(node *head, int val);
اگر اشکالی داره خواهش می‌کنم بهم بگید تا تصحیح کنم.

[vandu]

ممنون. کد کاملی شده. فقط فکر می‌کنم در تابع get توی شرط حلقه بجای ‎--i‎ باید نوشته بشه ‎i--‎ . چون اندیس‌ها از صفر شروع میشن. البته اگه اشتباه نکنم...

[fond]

بله حق با شماست. الان تست کردم متوجه شدم تابع ()print هم یه صفر اضافه چاپ می‌کنه.