Lập trình C: Bài 14 – Danh sách liên kết kép
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”]
Anh Quân ơi, ghi file trong code của anh ra màn hình như thé nào ạ?
Mình không hiểu cái ghi trong file là thế nào.
cho em hỏi trong chỗ thêm cuối, tại sao lại phải L.Tail = P; //luu lai vi tri cuoi ạ?
Mình có comment đó. Lệnh đó để lưu lại vị trí cuối, vì khi xóa cuối thì xon trỏ L.Tail sẽ không trỏ về đâu, mình cần trỏ nó về vị trí mới.
A oi cho e hoi la con tro L.tail-> right phai tro ve null the con tro L.head-> left cung phai tro ve null dung khong a khong thi no se tro linh tinh? E cam on a
E nham la L.head-> left phai tro ve null a
Đúng rồi bạn
– Ở mục số 8 (Xóa phần tử đầu cuối danh sách) em nghĩ dòng số 8 a phải cho L.head->left=NULL.
– Ở mục số 9 (Xóa phần tử ở vị trí k) em nghĩ nên cắt đứt liên kết giữa phần tử muốn xóa với danh sách(cho trỏ đến NULL hoặc delete luôn) .
– Vì mình dùng cấp phát động nên em nghĩ mình nên có 1 mục delete.
Đúng rồi bạn. Trong loạt bài này mình đã bỏ qua phần giải phóng bộ nhớ. Cảm ơn bạn góp ý nhé.
Cho em hỏi tại sao vòng while ở:
– Mục 7 dòng 14.
– Mục 9 dòng 13.
Có kiểm tra PH != NULL để làm gì ạ? Em cảm ơn.
Kiểm tra nó khác Null để biết đến cuối danh sách chưa, khi khác null thì chưa tới, lúc đó ta mới có PH->right được, nếu ko sẽ lỗi.
trang web rất hữu ích. cám ơn bạn rất nhiều
Cảm ơn bạn, Hãy chia sẻ cho bạn bè nhé.
anh cho em hỏi là ở hàm make_node khi anh khai báo nguyên mẫu là có truyền vào node *p, mà sao khi gọi lại nó chỉ có mỗi item x trong hàm vậy ạ ?
Hàm của mình viết là thế này:
Node *Make_Node (item x)
Do vậy truyền vào x là đúng rồi.
vâng, mà anh cho em hỏi thêm dấu ! đặt trong lệnh if(isempty(L)) ở 2 hàm del_first và del_last là có nghĩa gì thế ạ ?, tại sao không phải là != ,
! có nghĩa là phủ định.
isEmpty(L) là kiểm tra danh sách có rỗng không. Thì !isEmpty(L) là phủ định của nó.
đây là code trên C hay C++ ạ sao e copy về dev-C++ lưu dưới định dạng .c mà ko chạy ạ,em cảm ơn!
Code C xen lẫn cú pháp C++ nhé. Bạn đặt tên file đuôi cpp là ok.
Anh ơi, ko có bài nói về danh sách liên kết vòng hả anh.
Ukm, a ko có bài nói về cái đó.
anh ơi cho em hỏi mk muốn thay thế dãy số bằng danh sách sinh viên với các thuộc tính thì áp dụng sao ạ
Thi nhập xuất chỗ nào em thay thành nhập xuất của struct thôi e,
anh oi nhập xuất dữ liệu từ file này có khác gì ko hay cứ lm như bt thôi em chạy lấy dữ liệu ở file nó xuất lỗi hoài ạ
làm bình thường thôi e. Trước printf 1 số thì giờ printf nhiều số hoặc chuỗi thôi.