Lập Trình C: Bài 14 - Danh Sách Liên Kết Kép - Nguyễn Văn Quân

Nội dung

• 1 Cài đặt danh sách
• 2 Khởi tạo và kiểm tra rỗng
• 3. Độ dài danh sách
• 4. Tạo 1 Node P chứa thông tin
• 5. Chèn phần tử vào vị trí đầu tiên
• 6. Chèn phần tử vào cuối danh sách tương tự như đầu danh sách
• 7. Chèn phần tử vào vị trí k
• 8. Xóa phần tử đầu, cuối danh sách
• 9. Xóa phần tử ở vị trí k
• 10. Tìm phần tử x trong DS
• 11. Xóa phần tử x trong DS
• 12. Chương trình hoàn chỉnh

Danh sách liên kết kép cũng là một dạng danh sách liên kết nhưng mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách

1 Cài đặt danh sách

Cấu trúc của 1 Node trong danh sách liên kết kép tương đối giống với DSLKD nhưng có thêm một con trỏ trỏ về Node trước nó

typedef int item; typedef struct Node //cau truc 1 Node { item Data; //du lieu cua Node Node *Left; //Con tro trai Node *Right; //con tro phai }; typedef struct DList //cau truc Cua List { Node *Head; //con tro dau Node *Tail; //con tro cuoi };

Cấu trúc của DSLKK không như DSLKD có 1 Con trỏ trỏ đến đầu DS, nhưng DSLKK ngoài con trỏ trỏ đến đầu danh sách còn có thêm 1 con trỏ trỏ đến Node cuối của danh sách

2 Khởi tạo và kiểm tra rỗng

Khởi tạo ta cho 2 con trỏ đầu và cuối trỏ vê NULL, Khi kiểm tra rỗng thi chỉ cần xem con trỏ đầu có trỏ về NULL không là đủ

void Init(DList &L) { L.Head = NULL; // Con tro dau tro den NULL L.Tail = NULL; // Con tro cuoi tro den NULL } int Isempty (DList L) //kiem tra DS rong { return (L.Head == NULL); }

3. Độ dài danh sách

Để tìm độ dài của DSLKK ta hoàn toàn có thể làm giống như DSLKD, tức dùng con trỏ duyệt từ đầu đến cuối, nhưng trong DSLKK ta có thể dùng 2 con trỏ ở đầu và cuối để đếm

int Len (DList L) // Do dai danh sach { Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L int i = 0; //bien dem if (PH != NULL) i = 1; while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam) { if (PH == PT) break; PH = PH->Right; //cho PH tro den Node tiep theo i++; if (PH == PT) break; PT = PT->Left; //cho PT tro den Node truoc do i++; } return i; //tra lai so Node cua L }

4. Tạo 1 Node P chứa thông tin

Node *Make_Node (item x) //tao 1 Node P chua thong tin la x { Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P P->Data = x; //Ghi du lieu vao Data P->Left = NULL; P->Right = NULL; return P; }

5. Chèn phần tử vào vị trí đầu tiên

Trước khi chèn vào đầu danh sách cần kiểm tra xem danh sách rỗng hay không. Nếu danh sách rỗng ta cho Head và Tail đều trỏ đến P. Nếu không rỗng thực hiện chèn.

void Insert_first (DList &L, item x) //Chen x vao vi tri dau tien trong danh sach { Node *P; P = Make_Node(x); //tao 1 Node P if (Isempty(L)) //Neu danh sach rong { L.Head = P; L.Tail = P; } else { P->Right = L.Head; L.Head->Left = P; L.Head = P; } }

6. Chèn phần tử vào cuối danh sách tương tự như đầu danh sách

void Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach { Node *P; P = Make_Node(x); //tao 1 Node P if (Isempty(L)) //Neu danh sach rong { L.Head = P; L.Tail = P; } else { L.Tail->Right = P; //ket noi voi danh sach P->Left = L.Tail; //P tro ve Node truoc L.Tail = P; //luu lai vi tri cuoi } }

7. Chèn phần tử vào vị trí k

Trước khi chèn vào vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách. Nếu chèn vào giữa danh sách ta thực hiện theo 4 bước

void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach { Node *PH = L.Head, *PT, *R; int i=1, l = Len(L); if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien else { R = Make_Node(x); //tao 1 Node P if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien else if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi else //chen vao vi tri 1<k<l+1 { while (PH != NULL && i != k-1) //duyet den vi tri k-1 { i++; PH = PH->Right; } PT = PH->Right; //xac dinh vi tri k R->Right = PT; //(1) R->Left = PH; //(2) PH->Right = R; //(3) PT->Left = R; //(4) } } }

8. Xóa phần tử đầu, cuối danh sách

// Lay gia tri can xoa ra, sau do bo qua 1 Node dau tien void Del_first (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Head->Data; //lay gia tri ra neu can dung L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach } } // Lay gia tri can xoa ra, sau do bo qua 1 Node cuoi void Del_last (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Tail->Data; L.Tail = L.Tail->Left; L.Tail->Right = NULL; } }

9. Xóa phần tử ở vị trí k

Trước khi xóa ở vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách hay ở giữa

void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach { Node *PH = L.Head, *PT; int i=1, l = Len(L); if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien else { if (k == 1) Del_first(L,x); //xoa vi tri dau tien else if (k == l) Del_last(L,x); //xoa vi tri cuoi else //xoa vi tri 1<k<l+1 { while (PH != NULL && i != k-1) //duyet den vi tri k-1 { i++; PH = PH->Right; } x = PH->Right->Data; PT = PH->Right->Right; //xac dinh vi tri k+1 PH->Right = PT; PT->Left = PH; } } }

10. Tìm phần tử x trong DS

int Search (DList L, item x) //tim x trong danh sach { Node *P=L.Head; int i=1; while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach { P = P->Right; i++; } if (P != NULL) return i; //tra ve vi tri tim thay else return 0; //khong tim thay }

11. Xóa phần tử x trong DS

void Del_x (DList &L, item x) //xoa phan tu x trong danh sach { int l = Search(L,x); while (l) { Del_k (L,x,l); //trong khi van tim thay x thi van xoa l = Search(L,x); } }

12. Chương trình hoàn chỉnh

#include <stdlib.h> #include <stdio.h> typedef int item; typedef struct Node //cau truc 1 Node { item Data; //du lieu cua Node Node *Left; //Con tro trai Node *Right; //con tro phai }; typedef struct DList //cau truc Cua List { Node *Head; //con tro dau Node *Tail; //con tro cuoi }; void Init(DList &L); int Isempty (DList L); //kiem tra DS rong int Len (DList L); // Do dai danh sach Node *Make_Node (Node *P, item x); //tao 1 Node P chua thong tin la x void Insert_first (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach void Insert_last (DList &L, item x); //Chen x vao vi tri dau tien trong danh sach void Insert_k (DList &L, item x, int k); //chen x vao vi tri k trong danh sach void Del_first (DList &L, item &x); //Xoa phan tu dau tien void Del_k (DList &L, item &x, int k); //Xoa Node k trong danh sach int Search (DList L, item x); //tim x trong danh sach void Del_x (DList &L, item x); //xoa phan tu x trong danh sach void Input (DList &L); //nhap danh sach void Output (DList L); //xuat danh sach void Init(DList &L) { L.Head = NULL; // Con tro dau tro den NULL L.Tail = NULL; // Con tro cuoi tro den NULL } int Isempty (DList L) //kiem tra DS rong { return (L.Head == NULL); } int Len (DList L) // Do dai danh sach { Node *PH = L.Head, *PT = L.Tail; //tao Node PH (con tro duyet tu dau DS) và PT (con tro duyet tu cuoi DS) de duyet danh sach L int i = 0; //bien dem if (PH != NULL) i = 1; while (PH != NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam) { if (PH == PT) break; PH = PH->Right; //cho PH tro den Node tiep theo i++; if (PH == PT) break; PT = PT->Left; //cho PT tro den Node truoc do i++; } return i; //tra lai so Node cua L } Node *Make_Node (item x) //tao 1 Node P chua thong tin la x { Node *P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P P->Data = x; //Ghi du lieu vao Data P->Left = NULL; P->Right = NULL; return P; } void Insert_first (DList &L, item x) //Chen x vao vi tri dau tien trong danh sach { Node *P; P = Make_Node(x); //tao 1 Node P if (Isempty(L)) //Neu danh sach rong { L.Head = P; L.Tail = P; } else { P->Right = L.Head; L.Head->Left = P; L.Head = P; } } //Chen vao cuoi danh sach cung tuong tu void Insert_last (DList &L, item x) //Chen x vao vi tri cuoi trong danh sach { Node *P; P = Make_Node(x); //tao 1 Node P if (Isempty(L)) //Neu danh sach rong { L.Head = P; L.Tail = P; } else { L.Tail->Right = P; //ket noi voi danh sach P->Left = L.Tail; //P tro ve Node truoc L.Tail = P; //luu lai vi tri cuoi } } void Insert_k (DList &L, item x, int k) //chen x vao vi tri k trong danh sach { Node *PH = L.Head, *PT, *R; int i=1, l = Len(L); if (k<1 || k> l+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien else { R = Make_Node(x); //tao 1 Node P if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien else if (k == l+1) Insert_last(L,x); //chen vao vi tri cuoi else //chen vao vi tri 1<k<l+1 { while (PH != NULL && i != k-1) //duyet den vi tri k-1 { i++; PH = PH->Right; } PT = PH->Right; //xac dinh vi tri k R->Right = PT; //(1) R->Left = PH; //(2) PH->Right = R; //(3) PT->Left = R; //(4) } } } void Del_first (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Head->Data; //lay gia tri ra neu can dung L.Head = L.Head->Right; //Cho L tro den Node thu 2 trong danh sach } } void Del_last (DList &L, item &x) //Xoa phan tu dau tien { if (!Isempty(L)) { x = L.Tail->Data; L.Tail = L.Tail->Left; L.Tail->Right = NULL; } } void Del_k (DList &L, item &x, int k) //Xoa Node k trong danh sach { Node *PH = L.Head, *PT; int i=1, l = Len(L); if (k<1 || k> l) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien else { if (k == 1) Del_first(L,x); //xoa vi tri dau tien else if (k == l) Del_last(L,x); //xoa vi tri cuoi else //xoa vi tri 1<k<l+1 { while (PH != NULL && i != k-1) //duyet den vi tri k-1 { i++; PH = PH->Right; } x = PH->Right->Data; PT = PH->Right->Right; //xac dinh vi tri k+1 PH->Right = PT; PT->Left = PH; } } } int Search (DList L, item x) //tim x trong danh sach { Node *P=L.Head; int i=1; while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach { P = P->Right; i++; } if (P != NULL) return i; //tra ve vi tri tim thay else return 0; //khong tim thay } void Del_x (DList &L, item x) //xoa phan tu x trong danh sach { int l = Search(L,x); while (l) { Del_k (L,x,l); //trong khi van tim thay x thi van xoa l = Search(L,x); } } void Input (DList &L) //nhap danh sach { int i=0; item x; do { i++; printf ("Nhap phan tu thu %d : ",i); scanf("%d",&x); if (x != 0) Insert_k(L,x,Len(L)+1); } while(x != 0); //nhap 0 de ket thuc } void Output (DList L) //xuat danh sach { Node *P=L.Head; while (P != L.Tail->Right) { printf("%5d",P->Data); P = P->Right; } printf("\n"); } int main() { DList L; Init(L); Input(L); Output(L); int lua_chon; printf("Moi ban chon phep toan voi DS LKD:"); printf("\n1: Kiem tra DS rong"); printf("\n2: Do dai DS"); printf("\n3: Chen phan tu x vao vi tri k trong DS"); printf("\n4: Tim mot phan tu trong DS"); printf("\n5: Xoa phan tu tai vi tri k"); printf("\n6: XOa phan tu x trong DS"); printf("\n7: Thoat"); do { printf("\nBan chon: "); scanf("%d",&lua_chon); switch (lua_chon) { case 1: { if (Isempty(L)) printf("DS rong !"); else printf ("DS khong rong !"); break; } case 2: printf ("Do dai DS la: %d.",Len(L));break; case 3: { item x; int k; printf ("Nhap phan tu can chen vao DS: "); scanf("%d",&x); printf ("Nhap vi tri can chen: "); scanf ("%d",&k); Insert_k (L,x,k); printf ("DS sau khi chen:\n"); Output(L); break; } case 4: { item x; printf ("Moi ban nhap vao phan tu can tim: "); scanf("%d",&x); int k=Search(L,x); if (k) printf ("Tim thay %d trong DS tai vi tri thu: %d",x,k); else printf ("Khong tim thay %d trong danh sach !",x); break; } case 5: { int k; item x; printf ("Nhap vi tri can xoa: "); scanf ("%d",&k); Del_k (L,x,k); printf ("DS sau khi xoa:\n"); Output(L); break; } case 6: { item x; printf ("Nhap phan tu can xoa: "); scanf ("%d",&x); Del_x (L,x); printf ("DS sau khi xoa:\n"); Output(L); break; } case 7: break; } }while (lua_chon !=7); return 0; }

[rps-include post=”2703″ shortcodes=”false”]

Bạn có thể sẽ thích: