Danh sách liên kết vòng (Circular Linked List)

[iamvtn]

Danh sách liên kết vòng (Circular Linked List).

Danh Sách liên kết vòng là danh sách liên kết nhưng trướng next của nút cuối chỉ nút đầu tiên trong danh sách.


Không nói dài dòng chúng ta sẽ nghiên cứu luôn về cách cài đặt danh sách liên kết vòng bằng biến động.

int listsize(NODEPTR *plist){     NODEPTR p;   int i;   if(empty(plist))       return (0);   p = (*plist->next);   i = 1;   while(p != *plist)   {        i++;      p = p->next;   }}

1. Khai báo cấu trúc một nút strong danh sách liên kết vòng.
Khai báo một nút là một mẫu tin (struct) có hai trường là info và next.

• Trường info: chứa nội dung của nút.
• Trường next: là con trỏ chỉ nút, dùng chỉ nút kế trong danh sách liên kết vòng.

struct node{      int info;            struct node *next;};//khai bao kieu con tro chi den nuttypedef struct node *NODEPTR;

Chúng ta quản lý danh sách liên kết vòng qua con trỏ plist chỉ nút cuối của danh sách. Con trỏ plist có thể khai báo toàn cục hay cụ bộ.


2. Các tác vụ trên danh sách liên kết vòng:

Tác vụ getnode:
Cấp phát một biến động làm cho nút một danh sách liên kết vòng:

NODEPTR getnode(void){      NODEPTR p;   p = (NODEPTR) malloc(sizeof(struct node));   return (p);};

Tác vụ freenode
Giải phóng biến động đã cấp phát trước đó.

void freenode(NODEPTR p){      free(p);}

Tác vụ initialize:
Khởi động danh sách liên kết vòng:

void initialize(NODEPTR *plist){     *plist = NULL;}

Tác vụ empty:
Kiểm tra danh sách liên kết vòng có rỗng không.

int empty(NODEPTR *plist){       return(*plist == NULL ? true : false);}

Tác vụ listsize
Đếm số nút có trong danh sách liên kết vòng:

int listsize(NODEPTR *plist){     NODEPTR p;   int i;   if(empty(plist))       return (0);   p = (*plist->next);   i = 1;   while(p != *plist)   {        i++;      p = p->next;   }   return (i);}

Tác vụ nodepointer
Trả về con trỏ nút thứ i (i = 0,1,2,....) trong danh sách liên kết vòng

NODEPTR nodepointer(NODEPTR *plist, int i){      NODEPTR p;      int vitri;      if(i < 0 || i >= listsize(plist))           return(null);      p = (*plist)->next; //p chi nut dau dslk vong      for(vitri = 0;vitri < i;vitri++)          p = p->next;      return(p);}

Tác vụ push
Thêm một nút vào đầu danh sách liên kết vòng.

void push(NODEPTR *plist, int x){      NODEPTR p;   p = getnode();   p->info = x;   if(empty(plist) == true)       *plist = p;   else       p->next = (*plist)->next;   (*plist)->next = p;};

Tác vụ insend
Thêm nút vào cuối danh sách liên kết vòng.

void insend(NODEPTR *plist, int x){    NODEPTR p;    p = getnode();    p->info = x;    if(empty(plist) == true)        p->next = p;    else    {         p->next = (*plist)->next;      (*plist)->next = p;    }    *plist = p;};

Tác vụ pop
Xóa nút ở đầu danh sách liên kết vòng.

int pop(NODEPTR *plist){      NODEPTR p;   int x;   if(empty(plist))       printf("Danh sach bi rong");   else   {        p = (*plist)->next; // p la nut can xoa      x = p->info;      if(p == *plist) // truong hop ds chi co mot nut          *plist = NULL;      else          (*plist)->next = p->next;      freenode(p);      return (x);   }};

Tác vụ dellast
Xóa nút ở cuối danh sách liên kết vòng.

int dellast(NODEPTR *plist){     NODEPTR p;   int x;   if(empty(plist))  // truong hop danh sach bi rong       printf("Danh sach bi rong");   else   {        if((*plist)->next == plist) // truong hop cho co mot nut           {              p = *plist;               x = p->info;             *plist = NULL;              freenode(p);              return(x);         }         p = *plist;    // p la nut can xoa         x = p->info;         *plist = nodepointer(plist, listsize(plist) - 2);         (*plist)->next = p->next;         freenode(p);         return (x);   } }

Tác vụ traverse:
Duyệt danh sách liên kết vòng từ nút đầu đến nút cuối.

void traverse(NODEPTR *plist){     NODEPTR p;   if(*plist == NULL)       printf("Danh sach rong")   else   {        p = (*plist)->next; //p chi nut dau      printf("%d", p->info);      p = p->next;        //p chi nut thu hai      while(p != (*plist)->next)      {           printf("%d",p->info);         p = p->next;      }   }}

Trên đây là vài tác vụ đơn giản hi vọng nó giúp được cho bạn (mình thì không rành lắm về C (chỉ nghiên cứu nhiều về C++ thôi)) nên có gì không hiểu hay thắc mắc thì cứ post lên anh em Cviet sẽ trả lời cho bạn.

[trongcktin13b1]

anh ơi giúp em sửa cái này dc chương trình lỗi ở voil main()
mà em không sao sửa dc

      #include"conio.h"      #include"stdio.h"      #include"ctype.h"      typedef struct sv      {     char ht[35];     char gt[10];     char qq[20];     float d;      };      typedef struct ds      {     sv info;     ds*next;      } ds;       ds *taonut()      {       ds *p=new ds();       printf("\nNhap ho ten: ") ;  fflush(stdin);gets(p->info.ht);       printf("Nhap gioi tinh: ");  fflush(stdin);gets(p->info.gt);       printf("Nhap que quan: ");  fflush(stdin);gets(p->info.qq);       float tg;       printf("Nhap diem trung binh: "); scanf("%f",&tg);p->info.d=tg;       p->next=NULL;       return p;      }      ds *nhap(ds*l)      {  char ch;     int i=1;     ds*q,*p;     l=new ds();     l->next=l;     do     {      printf("\nNhap thong tin sinh vien thu %d:",i);     i++;      p=taonut();      p->next=l;      if(l->next==l) l->next=p;      else q->next=p;      q=p;      printf("\n ban co nhap nua khong?(c/k) "); fflush(stdin);      scanf("%c",&ch);     }while(toupper(ch)!='K');      return l;     }      void ht(ds*l)     {      ds *p=l->next;      int i=1;      while(p!=l)       {     printf("\n%d) %-30s %-6s %-20s %-5.2f",i,      p->info.ht,p->info.gt,p->info.qq,p->info.d);     p=p->next;     i++;       }     }//Dua ra nhung sinh vien co diem trung binh lon nhatvoid diemln(ds *l){ ds *p=l->next; float max=0; while(p!=l)      {       if(max < p->info.d) max=p->info.d;       p=p->next;      }//Khi thoat khoi vong while ben tren p=l printf("\n\nDanh sach sinh vien co diem trung binh lon nhat la:"); p=p->next; while(p!=l)      {       if(p->info.d ==max)     printf("\n%25s%8s%13s%5.2f",p->info.ht,        p->info.gt,p->info.qq,p->info.d);       p=p->next;      }}//Sap xep danh sach sinh vien theo thu tu tang dan cua diem trung binhds *sxdiemtd(ds *l){ sv tg; ds *p=l->next; while(p!=l)      {       ds *q=p->next;       while(q!=l)        {         if(p->info.d > q->info.d)           {        tg=p->info;        p->info=q->info;        q->info=tg;           }         q=q->next;        }       p=p->next;      } return l;}//bo sung mot nut p vao dau danh sach lds *bsdau(ds *l, ds *p){ p->next=l->next; l->next=p; return l;}//Bo sung mot nut p vao cuoi danh sach lds *bscuoi(ds *l,ds *p){ ds *q=l->next; while(q->next!=l) q=q->next; p->next=l; q->next=p; return l;}//Chen mot nut p vao vi tri thu k trong danh sach co HEAD la lds *chen(ds *l,ds *p,int k){ int d=0; ds *q=l;//Tim den nut truoc nut thu k, tuc la tim den nut thu (k-1) while(q->next!=l&&d<k-1)      {       d++;       q=q->next;      } if(q->next==l || k<=0)   {    printf("\nKHONG CHEN DUOC! KHONG CO VI TRI THU %d",k);    return l;   } else     {      p->next=q->next;      q->next=p;     } return l;}//Xoa nut dau danh sachds *delfirst(ds *l){ if(l->next==l) return l; ds *p=l->next; l->next=p->next; delete p; return l;}//Xoa nhung sinh vien co diem trung binh <5ds *xoaduoitb(ds *l){ if(l->next==l) return l; ds *q=l,*p=l->next; while(p!=l)      {       if(p->info.d <5)     {      ds *t=p;      q->next=p=p->next;      delete t;     }       else       {        q=p;        p=p->next;       }      } return l;}/*Tach danh sach l thanh 2 danh sach: 1 danh sach gom nhungsinh vien co diem >5, 1 danh sach gom nhung sinh vien co diem <=5 */ds *tach(ds *l,ds*HEAD){ HEAD->next=HEAD; ds *q=l,*p=l->next; while(p!=l)      {       if(p->info.d <=5)     {      ds *c,*t=p;      q->next=p=p->next;      if(HEAD->next==HEAD) HEAD->next=t;      else c->next=t;      c=t;      c->next=HEAD;     }       else       {        q=p;        p=p->next;       }      } return l;}/*ghep 2 danh sach thanh 1 danh sach. Ket qua cho ra chi 1 danh sach_ladanh sach duoc liet ke truoc trong thu tu tham so cua ham, danh sach kiachi con lai nut dau_cung phai bi thu hoi khong gian nho*/ds *gheptruoc(ds *HEAD,ds*l){ if(l->next==l)   {    delete l;    return HEAD;   } ds *p=l,*q=HEAD; while(p->next!=l) p=p->next; while(q->next!=HEAD) q=q->next; q->next=l->next; p->next=HEAD; delete l; return HEAD;}     void main()     { clrscr();       ds *l;       l=nhap(l);       printf("\n Danh sach vua nhap la:");       ht(l);       diemln(l);     l=sxdiemtd(l);     printf("\n danh sach sau khi sap xep la:");     ht(l);     int k;     printf("\n\nNhap vi tri can chen k= ") ; scanf("%d",&k);     printf("Nhap thong tin sinh vien can chen vao vi tri thu %d trong danh sach:",k);     ds*p=taonut();     l=chen(l,p,k);     printf("\nDanh sach sau khi chen vao vi tri thu %d la:",k);     ht(l);       l=delfirst(l);       printf("\n\nDanh sach sau khi xoa sinh vien dau tien la:");       ht(l);       l=xoaduoitb(l);       printf("\n\nDanh sach sau khi xoa nhung sinh vien co diem trung binh <5 la:");       ht(l);       ds *L;       printf("\n\nTa tach thanh 2 danh sach sinh vien nhu sau:");       tach(l,L);       printf("\nDanh sach sinh vien co diem trung binh >5 la: ");       if(l->next==l) printf("danh sach rong");       else ht(l);       printf("\nDanh sach sinh vien co diem trung binh <=5 la: ");       if(L->next==L) printf("danh sach rong");       else ht(L);     L=gheptruoc(L,l);     printf("\n\nTa ghep hai danh sach thanh mot danh sach nhu sau:");     ht(L);     getch();     }     int menu()     {      int n;      do      {        printf("\n               MENU CHUONG TRINH          ");        printf("\n      Nhan 1 De tao danh sach: ");        printf("\n      Nhan 2 De Tim lon nhat ");        printf("\n      Nhan 3 De Sap xep");        printf("\n      Nhan 4 De Chen  ");        printf("\n      Nhan 5 De Xoa dau ");        printf("\n      Nhan 6 Xoa nho hon TB");        printf("\n      Nhan 7 Tach Ghep ");        printf("\n      Nhan 0 De thoat: ");        scanf("%d",&n);       }while(n<0||n>7);      return n;     }      void main()     { clrscr();       ds *l;       int chucnang;       do       {    chucnang=menu();    switch(chucnang)    {        case 0:        printf(" Nhan 1 phim bat ki de thoat: ");        exit(1);        case 1:        printf("\n Tao danh sach:");        l=nhap(l);        printf("\n Danh sach vua nhap la:");        ht(l);        clrscr();        break;        case 2:        printf("\Diem lon nhat") ;        diemln(l);        getch();        clrscr();        break;        case 3:        l=sxdiemtd(l);        printf("\n danh sach sau khi sap xep la:");        ht(l);        getch();        clrscr();        break;        case 4:        int k;        printf("\n\nNhap vi tri can chen k= ");scanf("%d",&k);        printf("Nhap thong tin sinh vien can chen vao vi tri thu %d trong danh sach:",k);        ds*p=taonut();        l=chen(l,p,k);        printf("\nDanh sach sau khi chen vao vi tri thu %d la:",k);        ht(l);        getch();        clrscr();        break;        case 5:           l=delfirst(l);           printf("\n\nDanh sach sau khi xoa sinh vien dau tien la:");           ht(l);           getch();           clrscr();           break;        case 6:           l=xoaduoitb(l);           printf("\n\nDanh sach sau khi xoa nhung sinh vien co diem trung binh <5 la:");           ht(l);           getch();           clrscr();           break;       case 7:           ds *L;           printf("\n\nTa tach thanh 2 danh sach sinh vien nhu sau:");           tach(l,L);           printf("\nDanh sach sinh vien co diem trung binh >5 la: ");           if(l->next==l) printf("danh sach rong");           else ht(l);           printf("\nDanh sach sinh vien co diem trung binh <=5 la: ");           if(L->next==L) printf("danh sach rong");           else ht(L);           L=gheptruoc(L,l);           printf("\n\nTa ghep hai danh sach thanh mot danh sach nhu sau:");           ht(L);           getch();           clrscr();           break;    }}while(chucnang!=0);}

[vitiit]

theo mình hàm duyệt danh sách vòng phải là như này ! nhất là chỗ sử dụng while thì phải là do - while thì mới đúng dk . :/ mong a e góp ý !

 1.int listsize(NODEPTR *plist){
 2.     NODEPTR p;
 3.   int i;
 4.   if(empty(plist))
 5.       return (0);
 6.   p = plist->next;
 7.   i = 1;
 8.  do
 9.   {
10.       i++;
11.     printf("%d\n",p->data)
12.     p = p->next;
13.  } while(p != plist->next)
14.}