تو مجید آنلاین یادم نمیاد کد C در مورد لیست پیوندی نوشته باشم، اما از آرشیو کد هایی که در فروم دانشگاهی
iaun (دیگه وجود نداره) نوشته بودم اینها رو پیدا کردم :
این کد توابع replace برای تعویض کردن مقدار، add برای اضافه کردن عنص به لیست، clear برای حذف کردن کل لیست
و print برای نمایش محتویات لیست رو داره :
کد:
#include <stdio.h>
#include <conio.h>
struct item
{
int value;
item *next;
};
typedef item *list;
list node(list l, int n)
{
if (n < 1)
return 0;
list p = l;
for (int i = 1; (i < n) && (p); i++)
p = p->next;
return p;
}
void replace(list &l, int m, int n)
{
list node1 = node(l, m);
list node2 = node(l, n);
list pnode1 = node(l, m - 1);
list pnode2 = node(l, n - 1);
list temp;
if ((!node1) || (!node2) || (node1 == node2))
return;
if (pnode1)
pnode1->next = node2;
else
l = node2;
if (pnode2)
pnode2->next = node1;
else
l = node1;
temp = node1->next;
node1->next = node2->next;
node2->next = temp;
}
void add(list &l, int value)
{
list p;
if (l)
{
p = l;
while (p->next)
p = p->next;
p->next = new item;
p = p->next;
p->value = value;
p->next = 0;
}
else
{
l = new item;
l->value = value;
l->next = 0;
}
}
void clear(list &l)
{
list p = l, q;
while (p)
{
q = p->next;
delete p;
p = q;
}
l = 0;
}
void print(list l)
{
list p;
p = l;
while (p)
{
printf("%d > ", p->value);
p = p->next;
}
printf("null\n");
}
void main()
{
list mylist = 0;
add(mylist, 1);
add(mylist, 2);
add(mylist, 3);
add(mylist, 4);
add(mylist, 5);
print(mylist);
replace(mylist, 2, 4);
print(mylist);
clear(mylist);
getch();
}
این کد هم علاوه بر توابع add و clear و print، تابع length برای محاسبه کردن طول لیست و تابع ins رو برای ادغام کردن
دو لیست پیوندی ارائه می کنه :
کد:
#include <stdio.h>
#include <conio.h>
struct item
{
int value;
item *next;
};
typedef item *list;
list node(list l, int n)
{
if (n < 1)
return 0;
list p = l;
for (int i = 1; (i < n) && (p); i++)
p = p->next;
return p;
}
int length(list &l)
{
int count = 0;
list p = l;
while (p)
{
count++;
p = p->next;
}
return count;
}
void ins(list &list1, int i1, list &list2, int i2, int len)
{
if ((i1 > length(list1) + 1)
|| (i2 + len - 1 > length(list2))
|| (i1 < 1) || (i2 < 1))
{
printf("\nError : operation failed.\n");
return;
}
list node1 = node(list1, i1 - 1);
list node2 = node(list2, i2);
list p = node1;
list q = node(list1, i1);
for (int i = 0; i < len; i++)
{
if (p)
{
p->next = new item;
p = p->next;
}
else
{
p = new item;
list1 = p;
}
p->value = node2->value;
node2 = node2->next;
}
p->next = q;
}
void add(list &l, int value)
{
list p;
if (l)
{
p = l;
while (p->next)
p = p->next;
p->next = new item;
p = p->next;
p->value = value;
p->next = 0;
}
else
{
l = new item;
l->value = value;
l->next = 0;
}
}
void clear(list &l)
{
list p = l, q;
while (p)
{
q = p->next;
delete p;
p = q;
}
l = 0;
}
void print(list l)
{
list p;
p = l;
while (p)
{
printf("%d > ", p->value);
p = p->next;
}
printf("null\n");
}
void main()
{
list list1 = 0;
list list2 = 0;
add(list1, 1);
add(list1, 2);
add(list1, 3);
add(list1, 4);
add(list1, 8);
add(list2, 5);
add(list2, 6);
add(list2, 7);
print(list1);
print(list2);
ins(list1, 5, list2, 1, 3);
print(list1);
clear(list1);
clear(list2);
getch();
}
این کد هم رشته ها رو بجای آرایه یک بعدی بصورت لیست پیوندی پیاده سازی کرده.
تابع strcmp برای مقایسه کردن محتویات دو لیست (رشته)، تابع strvrfy برای مشخص کردن تعداد کاراکتر های مشابه،
تابع strcnvcl برای تبدیل کردن لیست به آرایه رشته ای یا برعکس و توابع clear و print داره :
کد:
#include <stdio.h>
#include <conio.h>
struct item
{
char ch;
item *next;
};
typedef item *list;
int strcmp(list l1, list l2)
{
list p1 = l1;
list p2 = l2;
while ((p1) && (p2))
{
if ((p1->ch) > (p2->ch))
return 1;
if ((p1->ch) < (p2->ch))
return -1;
p1 = p1->next;
p2 = p2->next;
}
return 0;
}
int strvrfy(list l1, list l2)
{
list p1 = l1;
list p2 = l2;
int i = 0;
while ((p1) && (p2))
{
i++;
if ((p1->ch) != (p2->ch))
break;
p1 = p1->next;
p2 = p2->next;
}
return i;
}
void strcnvcl(list l, char str[])
{
list p = l;
int i = 0;
while (p)
{
str[i] = p->ch;
p = p->next;
i++;
}
}
list strcnvcl(char str[])
{
list l = new item;
l->ch = str[0];
l->next = 0;
list p = l;
for (int i = 0; str[i]; i++)
{
p->next = new item;
p = p->next;
p->ch = str[i + 1];
p->next = 0;
}
return l;
}
void clear(list &l)
{
list p = l, q;
while (p)
{
q = p->next;
delete p;
p = q;
}
l = 0;
}
void print(list l)
{
list p = l;
while (p)
{
printf("%c", p->ch);
p = p->next;
}
printf("\n");
}
void main()
{
char mystr[80];
list mylist1 = strcnvcl("this is a test");
list mylist2 = strcnvcl("this is not a test");
print(mylist1);
strcnvcl(mylist1, mystr);
printf("%s\n", mystr);
printf("%d\n", strvrfy(mylist1, mylist2));
printf("%d\n", strcmp(mylist1, mylist2));
clear(mylist1);
clear(mylist2);
getch();
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int cid=0;
struct employ
{
int id;
char name[20];
char occupation[20];
char location[20];
struct employ *idnext,*nnext,*occnext,*lnext;
}*idhead=NULL,*nhead=NULL,*occhead=NULL,*lhead=NULL;
struct employ *idtail=NULL,*ntail=NULL,*occtail=NULL,*ltail=NULL;
struct employ *NEW=NULL,*idnow=NULL,*nnow=NULL,*occnow=NULL,*lnow=NULL;
struct employ *idp=NULL,*np=NULL,*occp=NULL,*lp=NULL;
void main()
{
char key;
void create_node(void);
void add_node(void);
void display(void);
void del_node(void);
for(;;)
{
clrscr();
gotoxy(25,10);
printf("Enter C For Create New Node\n");
gotoxy(25,11);
printf("Enter D For Delete One of Nodes\n");
gotoxy(25,12);
printf("Enter V For Veiw List\n");
gotoxy(25,13);
printf("Enter Q For Quiet Program");
key=getch();
if(key=='c')
{
create_node();
add_node();
}
else if(key=='v')
{
display();
}
else if(key=='d')
{
del_node();
}
else if(key=='q')
{
break;
}
else
{
printf("\nYour Entered Key Is Wrong.Please Try Again");
}
}
}
void create_node()
{
NEW=(struct employ *)malloc(sizeof(struct employ));
clrscr();
NEW->id=cid++;
gotoxy(25,10);
printf("Enter Your Name:");
gets(NEW->name);
gotoxy(25,11);
printf("Enter Your Occupation at Office:");
gets(NEW->occupation);
gotoxy(25,12);
printf("Enter Your Location(Only City):");
gets(NEW->location);
NEW->nnext=NULL;
NEW->idnext=NULL;
NEW->occnext=NULL;
NEW->lnext=NULL;
}
void add_node()
{
if(idhead==NULL&&nhead==NULL&&occhead==NULL&&lhead==NULL)
{
idhead=NEW;
nhead=NEW;
occhead=NEW;
lhead=NEW;
idtail=NEW;
ntail=NEW;
occtail=NEW;
ltail=NEW;
}
else
{
idnow=idhead;
nnow=nhead;
occnow=occhead;
lnow=lhead;
idtail->idnext=NEW;
idtail=NEW;
while(nnow!=NULL)
{
if(strcmp(nnow->name,NEW->name)<0)
{
np=nnow;
nnow=nnow->nnext;
}
else
{
break;
}
}
if(nnow==nhead)
{
NEW->nnext=nhead;
nhead=NEW;
}
else if(nnow==NULL)
{
ntail->nnext=NEW;
ntail=NEW;
}
else
{
NEW->nnext=nnow;
np->nnext=NEW;
}
while(occnow!=NULL)
{
if(strcmp(occnow->occupation,NEW->occupation)<0)
{
occp=occnow;
occnow=occnow->occnext;
}
else
{
break;
}
}
if(occnow==occhead)
{
NEW->occnext=occhead;
occhead=NEW;
}
else if(occnow==NULL)
{
occtail->occnext=NEW;
occtail=NEW;
}
else
{
NEW->occnext=occnow;
occp->occnext=NEW;
}
while(lnow!=NULL)
{
if(strcmp(lnow->location,NEW->location)<0)
{
lp=lnow;
lnow=lnow->lnext;
}
else
{
break;
}
}
if(lnow==lhead)
{
NEW->lnext=lhead;
lhead=NEW;
}
else if(lnow==NULL)
{
ltail->lnext=NEW;
ltail=NEW;
}
else
{
NEW->lnext=lnow;
lp->lnext=NEW;
}
}
}
void display()
{
char v;
clrscr();
lbl1:
if(idhead==NULL&&nhead==NULL&&occhead==NULL&&lhead==NULL)
{
gotoxy(25,10);
printf("You Do not have any thing to veiw!");
getch();
}
else
{
gotoxy(25,10);
printf("Enter I For See List order by ID");
gotoxy(25,11);
printf("Enter N For See List order by Name");
gotoxy(25,12);
printf("Enter O For See List order by Occupation");
gotoxy(25,13);
printf("Enter L For See List order by Location");
v=getch();
if(v=='i')
{
idnow=idhead;
clrscr();
while(idnow!=NULL)
{
printf("\nID:%d\nName:%s\nOccupation:%s\nLocation:%s\n",idnow->id,idnow->name,idnow->occupation,idnow->location);
idnow=idnow->idnext;
}
}
else if(v=='n')
{
nnow=nhead;
clrscr();
while(nnow!=NULL)
{
printf("\nName:%s\nID:%d\nOccupation:%s\nLocation:%s\n",nnow->name,nnow->id,nnow->occupation,nnow->location);
nnow=nnow->nnext;
}
}
else if(v=='o')
{
occnow=occhead;
clrscr();
while(occnow!=NULL)
{
printf("\nOccupation:%s\nID:%d\nName:%s\nLocation:%s\n",occnow->occupation,occnow->id,occnow->name,occnow->location);
occnow=occnow->occnext;
}
}
else if(v=='l')
{
lnow=lhead;
clrscr();
while(lnow!=NULL)
{
printf("\nLocation:%s\nID:%d\nName:%s\nOccupation:%s\n",lnow->location,lnow->id,lnow->name,lnow->occupation);
lnow=lnow->lnext;
}
}
else
{
clrscr();
goto lbl1;
}
getch();
}
}
void del_node()
{
int nudeid=0;
char find='f';
clrscr();
idnow=idhead;
nnow=nhead;
occnow=occhead;
lnow=lhead;
if(idhead==NULL)
{
printf("\nYou Do Not have any thing for Delete!");
getch();
}
else
{
gotoxy(25,10);
printf("Enter Node Id That You Want To Delete Him:");
scanf("%d",&nudeid);
while(idnow!=NULL)
{
if(nudeid!=idnow->id)
{
idp=idnow;
idnow=idnow->idnext;
find='f';
}
else
{
find='t';
break;
}
}
if(find=='t')
{
while(nnow!=NULL)
{
if(nudeid!=nnow->id)
{
np=nnow;
nnow=nnow->nnext;
}
else
{
break;
}
}
while(occnow!=NULL)
{
if(nudeid!=occnow->id)
{
occp=occnow;
occnow=occnow->occnext;
}
else
{
break;
}
}
while(lnow!=NULL)
{
if(nudeid!=lnow->id)
{
lp=lnow;
lnow=lnow->lnext;
}
else
{
break;
}
}
if(idhead->idnext==NULL)
{
idhead=NULL;
nhead=NULL;
occhead=NULL;
lhead=NULL;
idtail=NULL;
ntail=NULL;
occtail=NULL;
ltail=NULL;
}
else
{
if(idnow==idhead)
{
idhead=idhead->idnext;
}
else if(idnow==idtail)
{
idtail=idp;
idtail->idnext=NULL;
}
else
{
idp->idnext=idnow->idnext;
}
if(nnow==nhead)
{
nhead=nhead->nnext;
}
else if(nnow==ntail)
{
ntail=np;
ntail->nnext=NULL;
}
else
{
np->nnext=nnow->nnext;
}
if(occnow==occhead)
{
occhead=occhead->occnext;
}
else if(occnow==occtail)
{
occtail=occp;
occtail->occnext=NULL;
}
else
{
occp->occnext=occnow->occnext;
}
if(lnow==lhead)
{
lhead=lhead->lnext;
}
if(lnow==ltail)
{
ltail=lp;
ltail->lnext=NULL;
}
else
{
lp->lnext=lnow->lnext;
}
}
gotoxy(27,11);
printf("Success Delete!");
getch();
}
else
{
gotoxy(25,11);
printf("You Entered id is Wrong!");
getch();
}
}
}
البته من نمیخوام در این حد اصلا برنامه ای رو نمیخوام فقط میخوام در مورد لیست پیوندی توضیح بدین
و اگه خواستم یه برنامه ساده بنویسم چطوری باهاش کار کنم همین راستی در مورد کدی که گذاشتم به نظرت درست عمل میکنه
یک بخش زیادی از کد هایی که از لیست پیوندی استفاده می کنند مربوط به خود لیست پیوندی نیست، مربوط به
داده ای است که در لیست پیوندی ذخیره شده. مثلا در این کدی که شما قرار دادید، بخش عمده کد مربوط به
مشخصات شاغلین (نام و شغل و شهر) است و به خود ساختار لیست پیوندی ارتباطی نداره. فرضا اگر در لیست
پیوندی بجای اطلاعات شاغلین، اطلاعات دفترچه تلفن ذخیره می شد بخش زیادی از کد تغییر می کرد.
کد هایی که من نوشتم به این جهت ساده تر هستند که فقط یک داده ساده داخل لیست پیوندی ذخیره می کنند.
ساختار یک لیست پیوندی اینطوریه که ابتدا عنصر (گره) لیست پیوندی رو تعریف می کنیم :
کد:
struct item
{
int value;
item *next;
};
اسم این ساختار رو در مثال بالا item قرار دادیم که یک اسم اختیاری است. value داده ای است که در عنصر ذخیره میشه و جزو موارد اختیاری است، ممکنه در یک مثال بجای یک داده چند داده ذخیره بشه و یا نوع داده اش بجای int
نوع دیگه ای باشه. اما next جزو موارد ساختاری لیست پیوندی است و حتما باید باشه. next موقعیت عنصر بعدی
رو در لیست پیوندی مشخص می کنه و چون بصورت اشاره گر به عنصر بعدی اشاره می کنه با کاراکتر * اشاره گر ها تعریف میشه. نوع اشاره گر اش هم item است، یعنی دقیقا از نوع خود عنصر (گره)
در لیست پیوندی هر عنصر می دونه که عنصر بعدی چیه، در مورد عنصر انتهای لیست پیوندی هم در next مقدار 0
(معادل null) ذخیره میشه تا مشخص بشه که عنصر انتهایی لیست پیوندی است و عنصر بعدی وجود نداره.
هر لیست پیوندی باید یک اشاره گر برای مشخص کردن عنصر آغازین اش داشته باشه :
کد:
typedef item *list;
list mylist = 0;
در مثال بالا ابتدا برای اشاره گری که شروع لیست رو مشخص می کنه یک نوع داده تعریف کردیم به نام list
و سپس از نوع داده list یک متغیر به نام mylist معرفی کردیم. اکنون mylist مشخص کننده شروع یک لیست پیوندی
است که البته چون لیست هیچ عنصری ندارد و خالی است مقدار 0 دارد.
در مثال زیر سه لیست پیوندی خالی (بدون عنصر) ایجاد شده اند :
کد:
typedef item *list;
list listA = 0;
list listB = 0;
list listC = 0;
اضافه کردن عنصر به لیست پیوندی و یا حذف کردن عنصر از آن یا پیمایش کردن (برای جستجو کردن یک مقدار،
محاسبه کردن طول لیست، ادغام کردن چند لیست پیوندی و ...) بر اساس الگوریتم هایی انجام می شود که
در همه کتاب های ساختمان داده هست و در همه کد ها یکسانه. تنها چیزی که باعث تغییر میشه همون
داده یا داده هایی است که در عنصر ذخیره میشه. البته توضیحی که از ساختار لیست پیوندی نوشتم مربوط به
لیست پیوندی ساده یکطرفه است، در لیست پیوندی دو طرفه علاوه بر next یک back هم تعریف میشه تا
عنصر قبلی رو هم مشخص کنه، یعنی هر عنصر هم عنصر بعدی و هم عنصر قبلی خودش رو بشناسه.
یک بخش زیادی از کد هایی که از لیست پیوندی استفاده می کنند مربوط به خود لیست پیوندی نیست، مربوط به
داده ای است که در لیست پیوندی ذخیره شده. مثلا در این کدی که شما قرار دادید، بخش عمده کد مربوط به
مشخصات شاغلین (نام و شغل و شهر) است و به خود ساختار لیست پیوندی ارتباطی نداره. فرضا اگر در لیست
پیوندی بجای اطلاعات شاغلین، اطلاعات دفترچه تلفن ذخیره می شد بخش زیادی از کد تغییر می کرد.
کد هایی که من نوشتم به این جهت ساده تر هستند که فقط یک داده ساده داخل لیست پیوندی ذخیره می کنند.
ساختار یک لیست پیوندی اینطوریه که ابتدا عنصر (گره) لیست پیوندی رو تعریف می کنیم :
کد:
struct item
{
int value;
item *next;
};
اسم این ساختار رو در مثال بالا item قرار دادیم که یک اسم اختیاری است. value داده ای است که در عنصر ذخیره میشه و جزو موارد اختیاری است، ممکنه در یک مثال بجای یک داده چند داده ذخیره بشه و یا نوع داده اش بجای int
نوع دیگه ای باشه. اما next جزو موارد ساختاری لیست پیوندی است و حتما باید باشه. next موقعیت عنصر بعدی
رو در لیست پیوندی مشخص می کنه و چون بصورت اشاره گر به عنصر بعدی اشاره می کنه با کاراکتر * اشاره گر ها تعریف میشه. نوع اشاره گر اش هم item است، یعنی دقیقا از نوع خود عنصر (گره)
در لیست پیوندی هر عنصر می دونه که عنصر بعدی چیه، در مورد عنصر انتهای لیست پیوندی هم در next مقدار 0
(معادل null) ذخیره میشه تا مشخص بشه که عنصر انتهایی لیست پیوندی است و عنصر بعدی وجود نداره.
هر لیست پیوندی باید یک اشاره گر برای مشخص کردن عنصر آغازین اش داشته باشه :
کد:
typedef item *list;
list mylist = 0;
در مثال بالا ابتدا برای اشاره گری که شروع لیست رو مشخص می کنه یک نوع داده تعریف کردیم به نام list
و سپس از نوع داده list یک متغیر به نام mylist معرفی کردیم. اکنون mylist مشخص کننده شروع یک لیست پیوندی
است که البته چون لیست هیچ عنصری ندارد و خالی است مقدار 0 دارد.
در مثال زیر سه لیست پیوندی خالی (بدون عنصر) ایجاد شده اند :
کد:
typedef item *list;
list listA = 0;
list listB = 0;
list listC = 0;
اضافه کردن عنصر به لیست پیوندی و یا حذف کردن عنصر از آن یا پیمایش کردن (برای جستجو کردن یک مقدار،
محاسبه کردن طول لیست، ادغام کردن چند لیست پیوندی و ...) بر اساس الگوریتم هایی انجام می شود که
در همه کتاب های ساختمان داده هست و در همه کد ها یکسانه. تنها چیزی که باعث تغییر میشه همون
داده یا داده هایی است که در عنصر ذخیره میشه. البته توضیحی که از ساختار لیست پیوندی نوشتم مربوط به
لیست پیوندی ساده یکطرفه است، در لیست پیوندی دو طرفه علاوه بر next یک back هم تعریف میشه تا
عنصر قبلی رو هم مشخص کنه، یعنی هر عنصر هم عنصر بعدی و هم عنصر قبلی خودش رو بشناسه.
سلام خسته نباشید اگر بنده بخوام یک لیست پیوندی حلقوی یک طرفه با داده لخواه فرقی نمیکنه ایجاد کنم که امکاننات درج و حذف و نمایش لیست رو داشته باشه باید کد هارو به چه شکل بنویسم ممنون میشم اگر بنده رو راهنمای کنید
سلام خسته نباشید اگر بنده بخوام یک لیست پیوندی حلقوی یک طرفه با داده لخواه فرقی نمیکنه ایجاد کنم که امکاننات درج و حذف و نمایش لیست رو داشته باشه باید کد هارو به چه شکل بنویسم ممنون میشم اگر بنده رو راهنمای کنید
In data structures, a circular linked list is a linked list in which the last node stores the address of the first node. A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element.
