Bài 14: Danh sách liên kết kép

Posted on by adminChuyên mục:Kiến thức Internet

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ép

1 Cài đặt danh sách

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 thành phần liên kết với thành phần đứng trước và sau nó trong danh sáchCấ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 thành phần vào vị trí tiên phong

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 thi 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 thành phần vào cuối danh sách tương tự như 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 thành phần vào vị trí k

Trước khi chèn vào vị trí k cần kiểm tra vị trí k có tương thích, 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 triển khai theo 4 bước
Chè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 1Right;
				}
				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 thành phần đầ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 thành phần ở 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 1Right;
				}
				x = PH->Right->Data;
				PT = PH->Right->Right; //xac dinh vi tri k+1
				PH->Right = PT; 	
				PT->Left = PH;	
			}
    }
}

10. Tìm thành phần 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 thành phần 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 hảo

#include 
#include 
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 1Right;
				}
				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 1Right;
				}
				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 hoàn toàn có thể sẽ thích :

admin