Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Danh sách liên kết vòng (Circular Linked List)

  1. #1
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    168

    Mặc định Danh sách liên kết vòng (Circular Linked List)

    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.
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		350px-Circularly-linked-list_svg.png
Lần xem:	2
Size:		9.0 KB
ID:		7955

    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.
    C Code:
    1. int listsize(NODEPTR *plist)
    2. {
    3.      NODEPTR p;
    4.    int i;
    5.    if(empty(plist))
    6.        return (0);
    7.    p = (*plist->next);
    8.    i = 1;
    9.    while(p != *plist)
    10.    {
    11.         i++;
    12.       p = p->next;
    13.    }
    14. }
    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.

    C Code:
    1. struct node
    2. {
    3.       int info;
    4.             struct node *next;
    5. };
    6. //khai bao kieu con tro chi den nut
    7. typedef 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:
    C Code:
    1. NODEPTR getnode(void)
    2. {
    3.       NODEPTR p;
    4.    p = (NODEPTR) malloc(sizeof(struct node));
    5.    return (p);
    6. };
    Tác vụ freenode
    Giải phóng biến động đã cấp phát trước đó.
    C Code:
    1. void freenode(NODEPTR p)
    2. {
    3.       free(p);
    4. }
    Tác vụ initialize:
    Khởi động danh sách liên kết vòng:
    C Code:
    1. void initialize(NODEPTR *plist)
    2. {
    3.      *plist = NULL;
    4. }
    Tác vụ empty:
    Kiểm tra danh sách liên kết vòng có rỗng không.
    C Code:
    1. int empty(NODEPTR *plist)
    2. {
    3.        return(*plist == NULL ? true : false);
    4. }
    Tác vụ listsize
    Đếm số nút có trong danh sách liên kết vòng:
    C Code:
    1. int listsize(NODEPTR *plist)
    2. {
    3.      NODEPTR p;
    4.    int i;
    5.    if(empty(plist))
    6.        return (0);
    7.    p = (*plist->next);
    8.    i = 1;
    9.    while(p != *plist)
    10.    {
    11.         i++;
    12.       p = p->next;
    13.    }
    14.    return (i);
    15. }
    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
    C Code:
    1. NODEPTR nodepointer(NODEPTR *plist, int i)
    2. {
    3.       NODEPTR p;
    4.       int vitri;
    5.       if(i < 0 || i >= listsize(plist))
    6.            return(null);
    7.       p = (*plist)->next; //p chi nut dau dslk vong
    8.       for(vitri = 0;vitri < i;vitri++)
    9.           p = p->next;
    10.       return(p);
    11. }
    Tác vụ push
    Thêm một nút vào đầu danh sách liên kết vòng.
    C Code:
    1. void push(NODEPTR *plist, int x)
    2. {
    3.       NODEPTR p;
    4.    p = getnode();
    5.    p->info = x;
    6.    if(empty(plist) == true)
    7.        *plist = p;
    8.    else
    9.        p->next = (*plist)->next;
    10.    (*plist)->next = p;
    11. };
    Tác vụ insend
    Thêm nút vào cuối danh sách liên kết vòng.

    C Code:
    1. void insend(NODEPTR *plist, int x)
    2. {
    3.     NODEPTR p;
    4.     p = getnode();
    5.     p->info = x;
    6.     if(empty(plist) == true)
    7.         p->next = p;
    8.     else
    9.     {
    10.          p->next = (*plist)->next;
    11.       (*plist)->next = p;
    12.     }
    13.     *plist = p;
    14. };
    Tác vụ pop
    Xóa nút ở đầu danh sách liên kết vòng.
    C Code:
    1. int pop(NODEPTR *plist)
    2. {
    3.       NODEPTR p;
    4.    int x;
    5.    if(empty(plist))
    6.        printf("Danh sach bi rong");
    7.    else
    8.    {
    9.         p = (*plist)->next; // p la nut can xoa
    10.       x = p->info;
    11.       if(p == *plist) // truong hop ds chi co mot nut
    12.           *plist = NULL;
    13.       else
    14.           (*plist)->next = p->next;
    15.       freenode(p);
    16.       return (x);
    17.    }
    18. };
    Tác vụ dellast
    Xóa nút ở cuối danh sách liên kết vòng.
    C Code:
    1. int dellast(NODEPTR *plist)
    2. {
    3.      NODEPTR p;
    4.    int x;
    5.    if(empty(plist))  // truong hop danh sach bi rong
    6.        printf("Danh sach bi rong");
    7.    else
    8.    {
    9.         if((*plist)->next == plist) // truong hop cho co mot nut
    10.            {
    11.               p = *plist;
    12.                x = p->info;
    13.              *plist = NULL;
    14.               freenode(p);
    15.               return(x);
    16.          }
    17.          p = *plist;    // p la nut can xoa
    18.          x = p->info;
    19.          *plist = nodepointer(plist, listsize(plist) - 2);
    20.          (*plist)->next = p->next;
    21.          freenode(p);
    22.          return (x);
    23.    }
    24. }
    Tác vụ traverse:
    Duyệt danh sách liên kết vòng từ nút đầu đến nút cuối.
    C Code:
    1. void traverse(NODEPTR *plist)
    2. {
    3.      NODEPTR p;
    4.    if(*plist == NULL)
    5.        printf("Danh sach rong")
    6.    else
    7.    {
    8.         p = (*plist)->next; //p chi nut dau
    9.       printf("%d", p->info);
    10.       p = p->next;        //p chi nut thu hai
    11.       while(p != (*plist)->next)
    12.       {
    13.            printf("%d",p->info);
    14.          p = p->next;
    15.       }
    16.    }
    17. }
    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.

  2. #2
    Ngày gia nhập
    03 2013
    Bài viết
    1

    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
    C Code:
    1.       #include"conio.h"
    2.       #include"stdio.h"
    3.       #include"ctype.h"
    4.       typedef struct sv
    5.       {
    6.      char ht[35];
    7.      char gt[10];
    8.      char qq[20];
    9.      float d;
    10.       };
    11.       typedef struct ds
    12.       {
    13.      sv info;
    14.      ds*next;
    15.       } ds;
    16.  
    17.       ds *taonut()
    18.       {
    19.        ds *p=new ds();
    20.        printf("\nNhap ho ten: ") ;  fflush(stdin);gets(p->info.ht);
    21.        printf("Nhap gioi tinh: ");  fflush(stdin);gets(p->info.gt);
    22.        printf("Nhap que quan: ");  fflush(stdin);gets(p->info.qq);
    23.        float tg;
    24.        printf("Nhap diem trung binh: "); scanf("%f",&tg);p->info.d=tg;
    25.        p->next=NULL;
    26.        return p;
    27.       }
    28.       ds *nhap(ds*l)
    29.       {  char ch;
    30.      int i=1;
    31.      ds*q,*p;
    32.      l=new ds();
    33.      l->next=l;
    34.      do
    35.      {
    36.       printf("\nNhap thong tin sinh vien thu %d:",i);     i++;
    37.       p=taonut();
    38.       p->next=l;
    39.       if(l->next==l) l->next=p;
    40.       else q->next=p;
    41.       q=p;
    42.       printf("\n ban co nhap nua khong?(c/k) "); fflush(stdin);
    43.       scanf("%c",&ch);
    44.      }while(toupper(ch)!='K');
    45.       return l;
    46.      }
    47.  
    48.      void ht(ds*l)
    49.      {
    50.       ds *p=l->next;
    51.       int i=1;
    52.       while(p!=l)
    53.        {
    54.      printf("\n%d) %-30s %-6s %-20s %-5.2f",i,      p->info.ht,p->info.gt,p->info.qq,p->info.d);
    55.      p=p->next;
    56.      i++;
    57.        }
    58.      }
    59. //Dua ra nhung sinh vien co diem trung binh lon nhat
    60. void diemln(ds *l)
    61. {
    62.  ds *p=l->next;
    63.  float max=0;
    64.  while(p!=l)
    65.       {
    66.        if(max < p->info.d) max=p->info.d;
    67.        p=p->next;
    68.       }
    69. //Khi thoat khoi vong while ben tren p=l
    70.  printf("\n\nDanh sach sinh vien co diem trung binh lon nhat la:");
    71.  p=p->next;
    72.  while(p!=l)
    73.       {
    74.        if(p->info.d ==max)
    75.      printf("\n%25s%8s%13s%5.2f",p->info.ht,        p->info.gt,p->info.qq,p->info.d);
    76.        p=p->next;
    77.       }
    78. }
    79. //Sap xep danh sach sinh vien theo thu tu tang dan cua diem trung binh
    80. ds *sxdiemtd(ds *l)
    81. {
    82.  sv tg;
    83.  ds *p=l->next;
    84.  while(p!=l)
    85.       {
    86.        ds *q=p->next;
    87.        while(q!=l)
    88.         {
    89.          if(p->info.d > q->info.d)
    90.            {
    91.         tg=p->info;
    92.         p->info=q->info;
    93.         q->info=tg;
    94.            }
    95.          q=q->next;
    96.         }
    97.        p=p->next;
    98.       }
    99.  return l;
    100. }
    101. //bo sung mot nut p vao dau danh sach l
    102. ds *bsdau(ds *l, ds *p)
    103. {
    104.  p->next=l->next;
    105.  l->next=p;
    106.  return l;
    107. }
    108. //Bo sung mot nut p vao cuoi danh sach l
    109. ds *bscuoi(ds *l,ds *p)
    110. {
    111.  ds *q=l->next;
    112.  while(q->next!=l) q=q->next;
    113.  p->next=l;
    114.  q->next=p;
    115.  return l;
    116. }
    117. //Chen mot nut p vao vi tri thu k trong danh sach co HEAD la l
    118. ds *chen(ds *l,ds *p,int k)
    119. {
    120.  int d=0;
    121.  ds *q=l;
    122. //Tim den nut truoc nut thu k, tuc la tim den nut thu (k-1)
    123.  while(q->next!=l&&d<k-1)
    124.       {
    125.        d++;
    126.        q=q->next;
    127.       }
    128.  if(q->next==l || k<=0)
    129.    {
    130.     printf("\nKHONG CHEN DUOC! KHONG CO VI TRI THU %d",k);
    131.     return l;
    132.    }
    133.  else
    134.      {
    135.       p->next=q->next;
    136.       q->next=p;
    137.      }
    138.  return l;
    139. }
    140. //Xoa nut dau danh sach
    141. ds *delfirst(ds *l)
    142. {
    143.  if(l->next==l) return l;
    144.  ds *p=l->next;
    145.  l->next=p->next;
    146.  delete p;
    147.  return l;
    148. }
    149. //Xoa nhung sinh vien co diem trung binh <5
    150. ds *xoaduoitb(ds *l)
    151. {
    152.  if(l->next==l) return l;
    153.  ds *q=l,*p=l->next;
    154.  while(p!=l)
    155.       {
    156.        if(p->info.d <5)
    157.      {
    158.       ds *t=p;
    159.       q->next=p=p->next;
    160.       delete t;
    161.      }
    162.        else
    163.        {
    164.         q=p;
    165.         p=p->next;
    166.        }
    167.       }
    168.  return l;
    169. }
    170. /*Tach danh sach l thanh 2 danh sach: 1 danh sach gom nhung
    171. sinh vien co diem >5, 1 danh sach gom nhung sinh vien co diem <=5 */
    172. ds *tach(ds *l,ds*HEAD)
    173. {
    174.  HEAD->next=HEAD;
    175.  ds *q=l,*p=l->next;
    176.  while(p!=l)
    177.       {
    178.        if(p->info.d <=5)
    179.      {
    180.       ds *c,*t=p;
    181.       q->next=p=p->next;
    182.       if(HEAD->next==HEAD) HEAD->next=t;
    183.       else c->next=t;
    184.       c=t;
    185.       c->next=HEAD;
    186.      }
    187.        else
    188.        {
    189.         q=p;
    190.         p=p->next;
    191.        }
    192.       }
    193.  return l;
    194. }
    195. /*ghep 2 danh sach thanh 1 danh sach. Ket qua cho ra chi 1 danh sach_la
    196. danh sach duoc liet ke truoc trong thu tu tham so cua ham, danh sach kia
    197. chi con lai nut dau_cung phai bi thu hoi khong gian nho*/
    198. ds *gheptruoc(ds *HEAD,ds*l)
    199. {
    200.  if(l->next==l)
    201.    {
    202.     delete l;
    203.     return HEAD;
    204.    }
    205.  ds *p=l,*q=HEAD;
    206.  while(p->next!=l) p=p->next;
    207.  while(q->next!=HEAD) q=q->next;
    208.  q->next=l->next;
    209.  p->next=HEAD;
    210.  delete l;
    211.  return HEAD;
    212. }
    213.      void main()
    214.      { clrscr();
    215.        ds *l;
    216.        l=nhap(l);
    217.        printf("\n Danh sach vua nhap la:");
    218.        ht(l);
    219.        diemln(l);
    220.      l=sxdiemtd(l);
    221.      printf("\n danh sach sau khi sap xep la:");
    222.      ht(l);
    223.      int k;
    224.      printf("\n\nNhap vi tri can chen k= ") ; scanf("%d",&k);
    225.      printf("Nhap thong tin sinh vien can chen vao vi tri thu %d trong danh sach:",k);
    226.      ds*p=taonut();
    227.      l=chen(l,p,k);
    228.      printf("\nDanh sach sau khi chen vao vi tri thu %d la:",k);
    229.      ht(l);
    230.        l=delfirst(l);
    231.        printf("\n\nDanh sach sau khi xoa sinh vien dau tien la:");
    232.        ht(l);
    233.        l=xoaduoitb(l);
    234.        printf("\n\nDanh sach sau khi xoa nhung sinh vien co diem trung binh <5 la:");
    235.        ht(l);
    236.        ds *L;
    237.        printf("\n\nTa tach thanh 2 danh sach sinh vien nhu sau:");
    238.        tach(l,L);
    239.        printf("\nDanh sach sinh vien co diem trung binh >5 la: ");
    240.        if(l->next==l) printf("danh sach rong");
    241.        else ht(l);
    242.        printf("\nDanh sach sinh vien co diem trung binh <=5 la: ");
    243.        if(L->next==L) printf("danh sach rong");
    244.        else ht(L);
    245.      L=gheptruoc(L,l);
    246.      printf("\n\nTa ghep hai danh sach thanh mot danh sach nhu sau:");
    247.      ht(L);
    248.      getch();
    249.      }
    250.  
    251.     int menu()
    252.      {
    253.       int n;
    254.       do
    255.       {
    256.         printf("\n               MENU CHUONG TRINH          ");
    257.         printf("\n      Nhan 1 De tao danh sach: ");
    258.         printf("\n      Nhan 2 De Tim lon nhat ");
    259.         printf("\n      Nhan 3 De Sap xep");
    260.         printf("\n      Nhan 4 De Chen  ");
    261.         printf("\n      Nhan 5 De Xoa dau ");
    262.         printf("\n      Nhan 6 Xoa nho hon TB");
    263.         printf("\n      Nhan 7 Tach Ghep ");
    264.         printf("\n      Nhan 0 De thoat: ");
    265.         scanf("%d",&n);
    266.        }while(n<0||n>7);
    267.       return n;
    268.      }
    269.       void main()
    270.      { clrscr();
    271.        ds *l;
    272.        int chucnang;
    273.        do
    274.        {
    275.     chucnang=menu();
    276.     switch(chucnang)
    277.     {
    278.         case 0:
    279.         printf(" Nhan 1 phim bat ki de thoat: ");
    280.         exit(1);
    281.         case 1:
    282.         printf("\n Tao danh sach:");
    283.         l=nhap(l);
    284.         printf("\n Danh sach vua nhap la:");
    285.         ht(l);
    286.         clrscr();
    287.         break;
    288.         case 2:
    289.         printf("\Diem lon nhat") ;
    290.         diemln(l);
    291.         getch();
    292.         clrscr();
    293.         break;
    294.         case 3:
    295.         l=sxdiemtd(l);
    296.         printf("\n danh sach sau khi sap xep la:");
    297.         ht(l);
    298.         getch();
    299.         clrscr();
    300.         break;
    301.         case 4:
    302.         int k;
    303.         printf("\n\nNhap vi tri can chen k= ");scanf("%d",&k);
    304.         printf("Nhap thong tin sinh vien can chen vao vi tri thu %d trong danh sach:",k);
    305.         ds*p=taonut();
    306.         l=chen(l,p,k);
    307.         printf("\nDanh sach sau khi chen vao vi tri thu %d la:",k);
    308.         ht(l);
    309.         getch();
    310.         clrscr();
    311.         break;
    312.         case 5:
    313.            l=delfirst(l);
    314.            printf("\n\nDanh sach sau khi xoa sinh vien dau tien la:");
    315.            ht(l);
    316.            getch();
    317.            clrscr();
    318.            break;
    319.         case 6:
    320.            l=xoaduoitb(l);
    321.            printf("\n\nDanh sach sau khi xoa nhung sinh vien co diem trung binh <5 la:");
    322.            ht(l);
    323.            getch();
    324.            clrscr();
    325.            break;
    326.        case 7:
    327.            ds *L;
    328.            printf("\n\nTa tach thanh 2 danh sach sinh vien nhu sau:");
    329.            tach(l,L);
    330.            printf("\nDanh sach sinh vien co diem trung binh >5 la: ");
    331.            if(l->next==l) printf("danh sach rong");
    332.            else ht(l);
    333.            printf("\nDanh sach sinh vien co diem trung binh <=5 la: ");
    334.            if(L->next==L) printf("danh sach rong");
    335.            else ht(L);
    336.            L=gheptruoc(L,l);
    337.            printf("\n\nTa ghep hai danh sach thanh mot danh sach nhu sau:");
    338.            ht(L);
    339.            getch();
    340.            clrscr();
    341.            break;
    342.     }
    343. }while(chucnang!=0);
    344. }

  3. #3
    Ngày gia nhập
    02 2014
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    1

    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 ý !
    Code:
     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.}

Các đề tài tương tự

  1. Danh sách liên kết cơ bản | Linked list basic
    Gửi bởi Kevin Hoang trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 20-11-2016, 10:26 PM
  2. vấn đề liên quan giữa Tree và Linked List.!!
    Gửi bởi nhocconan.91 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 14-11-2010, 02:44 PM
  3. tạo 1 danh sách liên kết đơn(Linked List) mới ntn???
    Gửi bởi nhocconan.91 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 15-10-2010, 06:36 AM
  4. linked list | Danh sách liên kết | Lỗi do đâu?
    Gửi bởi xai1lanroibo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 03-05-2009, 03:01 PM
  5. In ra danh sách rỗng khi đã nhập danh sách - Linked List trong lập trình C++
    Gửi bởi dieucay555 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 05-03-2008, 11:38 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn