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

Đề tài: Danh sách liên kết kép

  1. #1
    Ngày gia nhập
    10 2009
    Nơi ở
    Close All
    Bài viết
    993

    Mặc định Danh sách liên kết kép

    -Hẳn các bạn ai cũng fai học qua môn Cấu trúc dữ liệu.Trong đó danh sách liên kết là 1 cấu trúc dữ liệu động rất phổ biến .
    Hôm nay mình cũng bon chen viết bài về danh sách liên kết kép.Mình demo với trường data của 1 nút là kiểu dữ liệu int nha.
    -Danh sách lien kết kép thực ra cũng giống với DSLKD thôi.chỉ khác là mỗi nút có thêm con trỏ prev để trỏ tới phần tử trước nó trong DSLKK thôi,thay vì chỉ có mỗi pnext đối với DSLKD.
    Cách khai báo,cài đặt DSLKK cũng như DSLKD thôi:
    C Code:
    1. typedef struct DNode
    2. {
    3.     int value;
    4.     struct DNode *pnext,*prev;
    5. }DNODE;//Cấu trúc của 1 nút
    6. typedef struct DList
    7. {
    8.     DNODE *phead,*ptail;
    9. }DLIST; //Cài đặt structure để quản lí DLIST

    -Tới đây ắt hẳn các bạn sẽ hỏi lệnh typedef để làm j?Thực ra typedef có nhiệm vụ định nghĩa 1 kiểu dữ liệu từ 1 kiểu đã có.Nếu ở đây không có typedef thì :

    C Code:
    1. struct DNode
    2. {
    3.     int value;
    4.     struct DNode *pnext,*prev;
    5. };
    6. struct DList
    7. {
    8.     DNODE *phead,*ptail;
    9. };
    lúc bạn khai báo biến fai có thêm struct (trong C thôi,C++ không cần)
    VD: struct DNode a;




    -Điều đầu tiên :Khi chúng ta thao tác với danh sách liên kết thì chúng ta phải đảm bảo rằng mọi thành phần kết nối ( pnext,prev) đều hợp lý và chính xác.
    --Các bạn có thể thấy khi mình muốn add thêm 1 nút vào đầu Danh sách liên kết kép: Thì sẽ có 2 trường hợp cơ bản mà chúng ta cần xét:danh sách rỗng và danh sách không rỗng.
    VD: Thêm nút A1 nào đó vào đầu danh sách liên kết kép L nha:
    +TH Danh sách rỗng (L.phead=NULL):Khi danh sách rỗng thì các con trỏ đến phần tử đầu và cuối danh sách đều bằng null( nghĩa là danh sách chưa có cái j trong đó hết,rỗng tuếch).


    - add A1 vào đầu danh sách.:thì lúc này danh sách chỉ có 1 phần tử và phần kết nối (prev,pnext) đều bằng NULL.vì đằng trước và đằng sau A1 đâu còn thằng nào nữa đâu mà trỏ tới nhỉ. Cập nhật lại giá trị con trỏ phead và ptail.Trường hợp này phần tử đầu danh sách trùng với cuối danh sách nên phead và ptail cùng trỏ tới A1( trỏ tới cùng 1 vùng nhớ trong bộ nhớ chính).
    +TH Danh sách không rỗng (L.phead!=NULL)

    Khi add A1 vào đâu danh sách thì ta phải chú ý đến thành phần kết nối(prev,pnext)

    Ý tưởng:
    Lúc đầu L.phead=A //đầu danh sách là A
    A1->pnext=L.phead; ///cái thằng đứng sau nút A1 là nút A
    L.phead->prev=A1 ;//chỉnh lại: vì A1 mới đc thêm vào đầu danh sách nên thằng đứng trước nút A là A1,chư không phải là NULL.
    //Bây giờ phần tử đầu danh sách là A1 chứ không phải A nữa nên phải chỉnh lại con trỏ phead thôi pà con ui!!!
    L.phead=A1;

    *Còn việc add thêm nút vào cuối danh sách hay add sau 1 nút thì ý tưởng cơ bản cũng gần gần giống như add vào đầu danh sách thôi.Chỉ cần chú ý chỉnh sửa những thành phần kết nối( prev,pnext) có lien quan thôi nha.Không liên quan thì làm lơ nó.I don’t care)

    *Xóa phần tủ ở đầu danh sách nè:
    +Nếu danh sách rỗng thì khỏi cần xét làm gì đúng không pà con (cái này không biết đúng không………hihihihi)
    +Giờ chỉ cần xét trường hợp danh sách khác rỗng thôi:

    Muốn hủy phần tử đầu xâu thì ta phải hủy các mối liên hệ của nó trước: (giống như ngày xưa sát thủ giết vua,guan lại,phải giết hết mấy thằng lính ,người bên cạnh nó trước thì lúc đó giết nó mới dễ đúng không nào) .
    Đầu tiên:
    X=L.phead;// ghi nhớ mục tiêu tiêu diệt là A
    L.phead=X->pnext; //lúc này thằng đầu danh sách là thằng đứng sau A,vì thằng A sắp bị mạng ra chém rồi còn gì( thằng B lên nắm quyền làm BOSS).
    If(L.phead!=NULL) L.phead->prev=NULL;
    + //Nếu B tồn tại ( danh sách không rỗng khi hủy thằng A) thì trước thằng B phải là NULL.Nếu chúng ta không làm điều này:L.phead->prev=NULL(B->prev=NULL) thì sau khi thằng A bị hủy thì thằng B vẫn cứ nhớ là đằng trước nó còn thằng A(B->prev==A);
    --Cuối cùng mang X (A) ra chém bay đầu cho ta: delete a;
    Xóa 1 phần tử cuối danh sách cũng tương tự như thế này thôi.

    C Code:
    1. /*
    2.  Coder:tauit_dnmd
    3.  */
    4. #include<stdio.h>
    5. #include<conio.h>
    6. typedef struct DNode
    7. {
    8.     int value;
    9.     struct DNode *pnext,*prev;
    10. }DNODE;
    11. DNODE* InitDNode(int x)
    12. {
    13.     DNODE* temp=new DNODE;
    14.     if(temp==NULL) return NULL;
    15.     temp->value=x;
    16.     temp->prev=temp->pnext=NULL;
    17.     return temp;
    18. }
    19. typedef struct DList
    20. {
    21.     DNODE *phead,*ptail;
    22. }DLIST;
    23. void InitDList(DLIST &L)
    24. {
    25.     L.phead=L.ptail=NULL;
    26. }
    27. void AddHead(DLIST &L,DNODE *p)
    28. {
    29.     if(p==NULL) return;
    30.     if(L.phead==NULL)
    31.     {
    32.         p->pnext=p->prev=NULL;
    33.         L.phead=p;
    34.         L.ptail=L.phead;
    35.        
    36.     }
    37.     else
    38.     {
    39.         p->prev=NULL;
    40.         p->pnext=L.phead;
    41.         L.phead=p;
    42.     }
    43. }
    44. void AddTail(DLIST &L,DNODE *p)
    45. {
    46.     if(p==NULL) return;
    47.     if(L.phead==NULL)
    48.     {
    49.         p->pnext=p->prev=NULL;
    50.         L.phead=p;
    51.         L.ptail=L.phead;
    52.        
    53.     }
    54.     else
    55.     {
    56.         p->prev=L.ptail;
    57.         p->pnext=NULL;
    58.         L.ptail->pnext=p;
    59.         L.ptail=p;
    60.     }
    61. }
    62. int AddAt(DLIST &L,int x,int pos) //them x vao sau Node co gia tri ==pos  dau tien
    63. {
    64.     if(L.phead==NULL) return 0;
    65.     DNODE *p=L.phead;
    66.     while(p!=NULL)
    67.     {
    68.         if(p->value==pos) break;
    69.         p=p->pnext;
    70.     }
    71.     if(p!=NULL)
    72.     {
    73.         DNODE *temp=InitDNode(x);
    74.         temp->pnext=p->pnext;
    75.         temp->prev=p;
    76.         p->pnext=temp;
    77.         if(p==L.ptail) L.ptail=temp;
    78.         return 1;
    79.     }
    80.     return 0;
    81. }
    82. void RemoveHead(DLIST &L)
    83. {
    84.     DNODE *x;
    85.     if(L.phead==NULL) return;
    86.     x=L.phead;
    87.     L.phead=L.phead->pnext;
    88.     if(L.phead!=NULL) L.phead->prev=NULL;
    89.     delete x;
    90. }
    91. void RemoveTail(DLIST &L)
    92. {
    93.     DNODE *p,*q;
    94.     if(L.phead==NULL) return;
    95.     p=L.ptail;
    96.     if(p->prev==NULL){ RemoveHead(L);return;}
    97.     q=p->prev;
    98.     q->pnext=NULL;
    99.     L.ptail=q;
    100.     delete p;  
    101. }
    Thiếu sót chỗ nào anh em bỏ qua cho mình nha.Cái này code lâu lắm ùi

  2. #2
    Ngày gia nhập
    10 2009
    Bài viết
    86

    Bạn ơi chỉnh hình dùm mình nha, đọc mà o thấy gì hết

  3. #3
    Ngày gia nhập
    09 2012
    Bài viết
    2

    Bài viết rất hay, nhờ nó mình đã hiểu được phần nào

  4. #4
    Ngày gia nhập
    07 2007
    Bài viết
    1

    Bài viết rất sáng sủa, và dễ đọc. Cám ơn bạn

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

  1. Hướng dẫn Biểu diễn thích hợp bằng danh sách liên kết đơn hoặc danh sách liên kết kép
    Gửi bởi maitrung trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 04-08-2012, 08:01 PM
  2. Cấu trúc dữ liệu Cách tạo danh sách liên kết mới từ danh sách liên kết đã cho như thế nào?
    Gửi bởi giacmo1612 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 2
    Bài viết cuối: 30-11-2011, 04:43 PM
  3. Nhập và xuất danh sách liên kết lồng danh sách liên kết?
    Gửi bởi nvluong_it trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 22-04-2011, 11:30 AM
  4. Lập trình C Danh sách liên kết - Xử lý danh sách liên kết trong lập trình C
    Gửi bởi phucduan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 08-11-2010, 10:25 PM
  5. Danh sách liên kết, code nhập danh sách sinh viên có lỗi làm sao sửa?
    Gửi bởi acmilan trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 10-04-2009, 08:24 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