Programming C: Posts 14 – Doubly linked list
Content
- 1 Install list
- 2 Initialization and check empty
- 3. The length of the list
- 4. Create 1 Node P contains information
- 5. Insert element into the first position
- 6. Insert the end of the list elements similar to the list
- 7. Insert element into position k
- 8. Remove the first element, end of list
- 9. Remove the element at position k
- 10. Find element x in DS
- 11. Remove element x in DS
- 12. Complete program
Doubly linked list is a linked list format, but each element associated with the element preceding and following it in the list
1 Install list
The structure of 1 Node doubly linked list similar to DSLKD but more a pointer to Node before it
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
};
The structure of such DSLKD DSLKK not have 1 Pointer to the first DS, but DSLKK outside pointer to the list still further 1 Node pointer to end of list
2 Initialization and check empty
It is initialized to 2 start and end pointers return NULL, When test execution just see an empty head pointer NULL pointer is not enough
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. The length of the list
To find the length of DSLKK we absolutely can do like DSLKD, Instant approval pointers from start to finish, but we can use DSLKK 2 cursor at the beginning and end of counting
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. Create 1 Node P contains information
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. Insert element into the first position
Before insertion into the top of the list to check if the list is empty or not. If we empty list for Head and Tail are pointing to P. If not perform insert empty.
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. Insert the end of the list elements similar to the list
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. Insert element into position k
Before inserting in place to check the position k k matches, Is the end of the list or lists. If inserted between the list I follow 4 Steps
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. Remove the first element, end of list
// 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. Remove the element at position k
Before deleting in place to check the position k k matches, Is the end of the list or lists, or in the middle
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. Find element x in 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. Remove element x in 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. Complete program
#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”]
My Anh Quan, His record in the code file to the screen as How A?
I do not understand what is written in the file how.
I asked for more space for the end, why must L.Tail = P; //Save the end position ạ?
I have commented that. Command to save the last position, since the end of the cantilever deleting pointer will not point to where L.Tail, I need to point it to a new location.
A oi cho e hoi la con tro L.tail-> right phai tro ve null the con tro L.head-> provision must return null left khong dung khong then it becomes a miscellaneous? E cam on a
E nham la L.head-> left phai tro ve null a
Yeah you
– In item # 8 (Remove terminal element list) I think the line number 8 a must for L.head->left=NULL.
– In item # 9 (Remove the element at position k) I think they should cut off the link between the element you want to delete the list(to point to NULL or delete always) .
– Because I use dynamically allocated, so I thought I should have 1 delete items.
Yeah you. In this series I had to skip the memory release. Thank you comment offline.
Let me ask why the while loop:
– Ink 7 current 14.
– Ink 9 current 13.
Check PH != NULL to do sir? I thank.
Check it different to the last known Null list yet, while others are less null, then will we be T-> right are, if not will be sorry.
useful websites. thank you very much
Thank you, Please share with your friends offline.
he asked me as he is at make_node function prototype declaration is passed to the node * p, but why call it only every item x in the function so sir ?
Its function is written like this:
Node *Make_Node (item x)
Thus passed x is right.
yes, he let me ask Forums ! put in an if statement(isempty(The)) in 2 del_first function and what is meant del_last sir ?, why not != ,
! mean negative.
isEmpty(The) the check list is empty. then !isEmpty(The) is its negative.
Here is the code in C or C ++ sir Star e-C ++ dev copy of saving it as .c without running sir,thank you!
C code syntax C ++ mixed nhé. Cpp file name extension you are ok.
Waiter, no talk about the list of links within Bro.
Sme, a no talk about it.
Honey, can I ask if I want to replace the number sequence with a student list with attributes, how do I apply
Entry and exit test where you change to the entry and exit of struct only e,
Is it different if you import and export data from this file or just keep running, I ran to get the data in the file, it always output error
just do normal e. Before printf 1 printf time numbers are multiple numbers or strings.