Tạo bài viết
Đăng ký
01/10/2018, 22:40

Lập trình C: Bài 14 – Danh sách liên kết kép

Lập trình C: Bài 14 – Danh sách liên kết kép Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 19 responses 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 ...

Lập trình C: Bài 14 – Danh sách liên kết kép

Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 19 responses


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

Danh sách liên kết képDanh sách liên kết kép

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

Chèn x vào vị trí k trong danh sách liên kết képChèn x vào vị trí k trong danh sách liên kết kép 
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("
");
}

int main()
{
    DList L;
    Init(L);
    Input(L);
    Output(L);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("
1: Kiem tra DS rong");
    printf("
2: Do dai DS");
    printf("
3: Chen phan tu x vao vi tri k trong DS");
    printf("
4: Tim mot phan tu trong DS");
    printf("
5: Xoa phan tu tai vi tri k");
    printf("
6: XOa phan tu x trong DS");
    printf("
7: Thoat");
    do
    {
        printf("
Ban 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:
");
				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:
");
				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:
");
				Output(L);
				break;
			}
			case 7: break;
		}
	}while (lua_chon !=7);
	return 0;
}

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

Trần Trung Dũng

15 chủ đề

2610 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024