Một số bài tập Lập trình C
1.1 Khởi tạo Queue rỗng. Để khởi tạo Queue rỗng ta cần đưa vị trí Front về 0, Rear về -1, cout về 0. code by nguyenvanquan7826 1 2 3 4 5 6 void Init (Queue &Q) //khoi tao Queue rong { Q.Front = 0; //phan tu dau Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q) Q.count = 0; //so phan tu bang 0 }
Bạn đang xem trước 20 trang tài liệu Một số bài tập Lập trình C, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
nh sach day !");
return 0;
}
if (k(*L).size+1) //kiem tra dieu kien vi tri chen
{
printf("Vi tri chen khong hop le !\n");
return 0;
}
printf ("Nhap thong tin: ");
x = init_x(); //gan x = ham khoi tao x
int i;
//di chuyen cac phan tu ve cuoi danh sach
for (i = (*L).size; i >= k; i--)
(*L).Elems[i] = (*L).Elems[i-1];
(*L).Elems[k-1]=x;//chen x vao vi tri k
(*L).size++;//tang size len 1 don vi.
return 1;
}
void Input (List *L)
{
int n;
printf("Nhap so phan tu cua danh sach: ");
scanf("%d",&(*L).size);
int i;
for (i=0; i<(*L).size; i++)
{
printf("Nhap phan tu thu %d : ",i+1);
(*L).Elems[i] = init_x();
}
}
void Output (List L)
{
printf("Danh sach: \n");
int i;
for (i=0; i<L.size; i++)
printf("%5d",L.Elems[i]);
printf("\n");
}
int Search (List L, item x)
{
int i;
for (i=0; i<L.size; i++)
if (L.Elems[i] == x)
return i+1;
return 0;
}
int Del_k (List *L, item *x, int k)
{
if (Isempty(*L))
{
printf("Danh sach rong !");
return 0;
}
if (k(*L).size)
{
printf("Vi tri xoa khong hop le !");
return 0;
}
*x=(*L).Elems[k-1]; //luu lai gia tri cua phan tu can xoa
int i;
for (i=k-1; i<(*L).size-1; i++) //don cac phan tu ve truoc
(*L).Elems[i]=(*L).Elems[i+1];
(*L).size--; //giam size
return 1;
}
int Del_x (List *L, item x)
{
if (Isempty(*L))
{
printf("Danh sach rong !");
return 0;
}
int i = Search(*L,x);
if (!i)
{
printf("Danh sach khong co %d",x);
return 0;
}
do
{
Del_k(L,&x,i);
i = Search(*L,x);
}
while (i);
return 1;
}
int main()
{
List 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.",L.size);break;
case 3:
{
item x;
int k;
printf ("Nhap vi tri can chen: ");
scanf ("%d",&k);
if (Insert_k(&L,x,k))
{
printf ("DS sau khi chen:\n"); //xuat danh sach 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);
if (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);
if (Del_x(&L,x))
{
printf ("DS sau khi xoa:\n");
Output(L);
}
break;
}
case 7: break;
}
}while (lua_chon !=7);
return 0;
}
Lập trình C: Bài 13 – Danh sách liên kết đơn cài bằng con trỏ
Nội dung
1. Cài đặt danh sách
2 Khởi tạo danh sách rỗng
3 Kiểm tra danh sách rỗng hay không
4 Tính độ dài danh sách
5 Tạo 1 Node trong danh sách
6 Chèn Node P vào vị trí đầu tiên
7. Chèn Node P vào vị trí k trong danh sách
8 Tìm phần tử co giá trị x trong danh sách
9 Xóa phần tử ở vị trí đầu tiên
10. Xóa phần tư ở vị trí k
11. Xóa phần tử có giá trị x
12. Chương trình hoàn chỉnh (full)
Danh sách liên kết có thể được cài đặt bằng mảng hoặc bằng con trỏ. Trong bài viết này mình sẽ hướng dẫn các bạn sử dụng con trỏ :), Loại danh sách này gọi tắt là danh sách liên kết đơn
Trong các bài trước mình viết code tất cả đều là chuẩn C, nhưng từ bây giờ mình sẽ xen lẫn chút cấu trúc của C++ nên code trong bài này bạn để trong file *.cpp nhé.
Danh sách liên kết có thể được mô tả như sau:
Danh sách liên kết đơn
Trong đó Data là dữ liệu của mỗi Node, có thể là Sinh viên, công nhân, (có kiểu item, và mình làm đơn giản với số nguyên), Next là con trỏ trỏ tới phần tử tiếp theo.
1. Cài đặt danh sách
code by nguyenvanquan7826
1
2
3
4
5
6
7
typedef int item; //kieu cac phan tu dinh nghia la item
typedef struct Node //Xay dung mot Node trong danh sach
{
item Data; //Du lieu co kieu item
Node *next; //Truong next la con tro, tro den 1 Node tiep theo
};
typedef Node *List; //List la mot danh sach cac Node
2 Khởi tạo danh sách rỗng
code by nguyenvanquan7826
1
2
3
4
void Init (List &L) // &L lay dia chi cua danh sach ngay khi truyen vao ham
{
L=NULL; //Cho L tro den NULL
}
Trong các bài trước để có thể thay đổi được giá trị của đối mà ta truyền vào hàm ta thưòng dùng biến con trỏ (*) và trong lời gọi hàm ta cần có & trước biến tuy nhiên khi chúng ta sử dụng cách truyền địa chỉ ngay khi khởi tạo hàm thì trong lời gọi hàm ta tiên hành truyền biến bình thưòng mà không phải lấy địa chỉ (thêm &) trước biến nữa.
(Đây là một cách truyền địa chỉ cho biến trong hàm ở C++.)
3 Kiểm tra danh sách rỗng hay không
Cái này khỏi giải thích nhiều:
code by nguyenvanquan7826
1
2
3
4
int Isempty (List L)
{
return (L==NULL);
}
4 Tính độ dài danh sách
Ta dùng 1 Node để duyệt từ đầu đến cuối, vừa duyệt vừa đếm
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
int len (List L)
{
Node *P=L; //tao 1 Node P de duyet danh sach L
int i=0; //bien dem
while (P!=NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
{
i++; //tang bien dem
P=P->next; //cho P tro den Node tiep theo
}
return i; //tra lai so Node cua l
}
5 Tạo 1 Node trong danh sách
Việc tạo 1 Node chứa thông tin trong danh sách sẽ giúp ta dễ dàng chèn, xóa và quản lý danh sách hơn. Trước tiên ta sẽ phải cấp phát vùng nhớ cho Node và sau đó gán Data vào là ok
code by nguyenvanquan7826
1
2
3
4
5
6
7
Node *Make_Node (Node *P, item x) //tao 1 Node P chua thong tin la x
{
P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
P->next = NULL; //Cho truong Next tro den NULL
P->Data = x; //Ghi du lieu vao Data
return P;
}
6 Chèn Node P vào vị trí đầu tiên
Để chèn P vào đầu danh sách trước tiên ta cho P trỏ đến L, sau đó chỉ việc cho L trỏ lại về P là ok
Chèn vào đầu danh sách liên két
code by nguyenvanquan7826
1
2
3
4
5
6
7
void Insert_first (List &L, item x) //Chen x vao vi tri dau tien trong danh sach
{
Node *P;
P = Make_Node(P,x); //tao 1 Node P
P->next = L; //Cho P tro den L
L = P; //L tro ve P
}
7. Chèn Node P vào vị trí k trong danh sách
Trước tiên ta kiểm tra vị trí chèn có hợp lệ không, nếu hợp lệ kiểm tra tiếp chèn vào vị trí 1 hay k >1 . Với k >1 ta thực hiện duyệt bằng Node Q đến vị trí k-1 sau đó cho P->Next trỏ đến Node Q->Next, tiếp đến cho Q->Next trỏ đến P
Chèn phàn tử vào vị trí k trong danh sách liên kết
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
void Insert_k (List &L, item x, int k) //chen x vao vi tri k trong danh sach
{
Node *P, *Q = L;
int i=1;
if (k len(L)+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
else
{
P = Make_Node(P,x); //tao 1 Node P
if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
else //chen vao k != 1
{
while (Q != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
Q = Q->next;
}
P->next = Q->next;
Q->next = P;
}
}
}
8 Tìm phần tử co giá trị x trong danh sách
Ta duyệt danh sách cho đến khi tìm thấy hoặc kết thúc và trả về vị trí nếu tìm thấy, ngược lại trả về 0
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
int Search (List L, item x) //tim x trong danh sach
{
Node *P=L;
int i=1;
while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
{
P = P->next;
i++;
}
if (P != NULL) return i; //tra ve vi tri tim thay
else return 0; //khong tim thay
}
9 Xóa phần tử ở vị trí đầu tiên
Trước tiên ta lưu giá trị của phần tử đầu tiên vào biến x, sau đó tiền hành cho L trỏ đến L->Next
Xóa phần tử đầu tiên trong danh sách
code by nguyenvanquan7826
1
2
3
4
5
void Del_frist (List &L, item &x) //Xoa phan tu dau tien
{
x = L->Data; //lay gia tri ra neu can dung
L = L->next; //Cho L tro den Node thu 2 trong danh sach
}
10. Xóa phần tư ở vị trí k
Dùng P duyệt đến vị trí k-1 và tiến hành cho P->Next trỏ đến phần tư kế tiếp k mà bỏ qua k. Lưu ý trong hình mình quên không lưu lại giá trị cần xóa tuy nhiên các bạn cần lưu lại như khi xóa ở vị trí đầu tiên.
Xóa phần tử thứ k trong danh sách liên kết
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
void Del_k (List &L, item &x, int k) //Xoa Node k trong danh sach
{
Node *P=L;
int i=1;
if (klen(L)) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
else
{
if (k==1) Del_frist(L,x); //xoa vi tri dau tien
else //xoa vi tri k != 1
{
while (P != NULL && i != k-1) //duyet den vi tri k-1
{
P=P->next;
i++;
}
P->next = P->next->next; //cho P tro sang Node ke tiep vi tri k
}
}
}
11. Xóa phần tử có giá trị x
Đon giản là ta tìm x trong danh sách bằng hàm Search và xóa tại vị trí tìm thấy mà ta nhận được
code by nguyenvanquan7826
1
2
3
4
void Del_x (List &L, item x) //xoa phan tu x trong danh sach
{
while (Search(L,x)) Del_k (L,x,Search(L,x)); //trong khi van tim thay x thi van xoa
}
12. Chương trình hoàn chỉnh (full)
click để xem chương trình hoàn chỉnh
click để xem chương trình hoàn chỉnh
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include
#include
typedef int item; //kieu cac phan tu dinh nghia la item
typedef struct Node //Xay dung mot Node trong danh sach
{
item Data; //Du lieu co kieu item
Node *next; //Truong next la con tro, tro den 1 Node tiep theo
};
typedef Node *List; //List la mot danh sach cac Node
void Init (List &L); //khoi tao danh sach rong
int len (List L); // Do dai danh sach
Node *Make_Node (Node *P, item x); //Tao 1 Node P voi thong tin chu trong no
void Insert_first (List &L, item x); //Chen phan tu vao dau danh sach
void Insert_k (List &L, item x, int k); //Chen phan tu vao vi tri k trong danh sach
void Input (List &L);//Nhap danh sach
void Output (List L);//Xuat danh sach
int Search (List L, item x); //Tim phan tu x trong danh sach, ham tre ve vi tri cua phan tu tim duoc
void Del_frist (List &L, item &x); //Xoa phan tu dau danh sach
void Del_k (List &L, item &x, int k); //Xoa phan tu vi tri k trong danh sach
void Del_x (List &L, item x);//Xoa phan tu co gia tri x trong danh sach
void Init (List &L) // &L lay dia chi cua danh sach ngay khi truyen vao ham
{
L=NULL; //Cho L tro den NULL
}
int Isempty (List L)
{
return (L==NULL);
}
int len (List L)
{
Node *P=L; //tao 1 Node P de duyet danh sach L
int i=0; //bien dem
while (P!=NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
{
i++; //tang bien dem
P=P->next; //cho P tro den Node tiep theo
}
return i; //tra lai so Node cua l
}
Node *Make_Node (Node *P, item x) //tao 1 Node P chua thong tin la x
{
P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
P->next = NULL; //Cho truong Next tro den NULL
P->Data = x; //Ghi du lieu vao Data
return P;
}
void Insert_first (List &L, item x) //Chen x vao vi tri dau tien trong danh sach
{
Node *P;
P = Make_Node(P,x); //tao 1 Node P
P->next = L; //Cho P tro den L
L = P; //L tro ve P
}
void Insert_k (List &L, item x, int k) //chen x vao vi tri k trong danh sach
{
Node *P, *Q = L;
int i=1;
if (k len(L)+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
else
{
P = Make_Node(P,x); //tao 1 Node P
if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
else //chen vao k != 1
{
while (Q != NULL && i != k-1) //duyet den vi tri k-1
{
i++;
Q = Q->next;
}
P->next = Q->next;
Q->next = P;
}
}
}
int Search (List L, item x) //tim x trong danh sach
{
Node *P=L;
int i=1;
while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
{
P = P->next;
i++;
}
if (P != NULL) return i; //tra ve vi tri tim thay
else return 0; //khong tim thay
}
void Del_frist (List &L, item &x) //Xoa phan tu dau tien
{
x = L->Data; //lay gia tri ra neu can dung
L = L->next; //Cho L tro den Node thu 2 trong danh sach
}
void Del_k (List &L, item &x, int k) //Xoa Node k trong danh sach
{
Node *P=L;
int i=1;
if (klen(L)) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
else
{
if (k==1) Del_frist(L,x); //xoa vi tri dau tien
else //xoa vi tri k != 1
{
while (P != NULL && i != k-1) //duyet den vi tri k-1
{
P=P->next;
i++;
}
P->next = P->next->next; //cho P tro sang Node ke tiep vi tri k
}
}
}
void Del_x (List &L, item x) //xoa phan tu x trong danh sach
{
while (Search(L,x)) Del_k (L,x,Search(L,x)); //trong khi van tim thay x thi van xoa
}
void Input (List &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 (List L) //xuat danh sach
{
Node *P=L;
while (P != NULL)
{
printf("%5d",P->Data);
P = P->next;
}
printf("\n");
}
int main()
{
List 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;
}
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
Danh 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ó
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
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à đủ
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
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
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
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
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
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.
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
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
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
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ép
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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 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
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
// 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
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 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
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
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
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
9
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
click để xem chương trình hoàn chỉnh
click để xem chương trình hoàn chỉnh
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#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 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 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;
}
Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack)
Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack
Trong bài này chúng ta tìm hiểu cách cài đặt Stack trên mảng và trên con trỏ
Nội dung
1. Stack cài đặt trên mảng
1.1 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, đầy
1.2 Thêm phần tử vào Stack (Push)
1.3 Lấy dữ liệu tại Top nhưng không xóa (Peak)
1.4 Xóa và lấy dữ liệu tại Top (Pop)
1.5 Code toàn bộ chương trình (full)
2. Stack cài đặt trên con trỏ
2.1 Xây dựng cấu trúc
2.2 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách
2.3 Tạo 1 Node
2.4 Chèn phần tử vào Stack (Push)
2.5 Lấy dữ liệu tại Top nhưng không xóa (Peak)
2.6 Xóa và lấy dữ liệu tại Top (Pop)
2.7 Chương trình hoàn chỉnh (full code)
3. Sử dụng Stack có sẵn trong C++
4. VÍ dụ về ứng dụng của Stack
1. Stack cài đặt trên mảng
code by nguyenvanquan7826
1
2
3
4
5
6
7
#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
int Top; //Dinh Top
item Data[Max]; //Mang cac phan tu
};
1.1 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, đầy
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = 0; //Stack rong khi Top la 0
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == 0);
}
int Isfull(Stack S) //kiem tra Stack day
{
return (S.Top == Max); //
}
1.2 Thêm phần tử vào Stack (Push)
Để chèn thêm phần tử vào Stack ta chèn vào vị trí Top, và tang Top lên 1 đơn vị
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
void Push(Stack &S, item x) //them phan tu vao Stack
{
if (!Isfull(S))
{
S.Data[S.Top] = x; //Gan du lieu
S.Top ++; //Tang Top len 1
}
}
1.3 Lấy dữ liệu tại Top nhưng không xóa (Peak)
code by nguyenvanquan7826
1
2
3
4
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Data[S.Top-1]; //Lay du lieu tai Top
}
1.4 Xóa và lấy dữ liệu tại Top (Pop)
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
S.Top --; //Giam Top
return S.Data[S.Top]; //Lay du lieu tai Top
}
}
1.5 Code toàn bộ chương trình (full)
click để xem chương trình hoàn chỉnh
link dự phòng
2. Stack cài đặt trên con trỏ
Stack trên con trỏ vẫn là stack bình thường nhưng link hoạt hơn vì nó dùng con trỏ để cấp phát và quản lý, không bị thừa hoặc thiếu gì cả.
2.1 Xây dựng cấu trúc
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
typedef int item; //kieu du lieu
struct Node
{
item Data; //du lieu
Node *Next; //link
};
typedef struct Stack
{
Node *Top;
};
2.2 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
void Init (Stack &S) //khoi tao Stack rong
{
S.Top = NULL;
}
int Isempty(Stack S) //kiem tra Stack rong
{
return (S.Top == NULL);
}
int Len (Stack S)
{
Node *P = S.Top;
int i=0;
while (P != NULL) //trong khi chua het Stack thi van duyet
{
i++;
P = P->Next;
}
return i;
}
2.3 Tạo 1 Node
code by nguyenvanquan7826
1
2
3
4
5
6
7
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
2.4 Chèn phần tử vào Stack (Push)
Để chèn phần tử vào Stack thì chỉ cần cho con trỏ Note đó trỏ và Top, rồi Top trỏ lại nó là xong
code by nguyenvanquan7826
1
2
3
4
5
6
void Push(Stack &S, item x) //them phan tu vao Stack
{
Node *P = MakeNode(x);
P->Next = S.Top;
S.Top = P;
}
2.5 Lấy dữ liệu tại Top nhưng không xóa (Peak)
code by nguyenvanquan7826
1
2
3
4
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
return S.Top->Data;
}
2.6 Xóa và lấy dữ liệu tại Top (Pop)
Ta chỉ cần cho con trỏ Top trỏ đến vị trí thứ 2 thôi.
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
9
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
if (!Isempty(S))
{
item x = S.Top->Data; //luu lai gia tri
S.Top = S.Top->Next; //Xoa phan tu Top
return x;
}
}
2.7 Chương trình hoàn chỉnh (full code)
click để xem chương trình hoàn chỉnh
link dự phòng
3. Sử dụng Stack có sẵn trong C++
Trong C++ đã xây dựng sẵn các phương thức (hàm) liên quan đến Stack, ta chỉ việc khai báo và sử dụng
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include // io
#include // use stack
using namespace std;
int main() {
stack S; // khai bao Stack voi kieu du lieu la int
for (int i = 0; i < 10; i++) {
S.push(i*78 + 26); // chen cac phan tu vao stack
}
cout << "Do dai stack: " << S.size() << "\n";
// xuat tat ca phan tu trong stack
while (!S.empty()) { // trong khi stack chua trong
int x = S.top(); // lay gia tri top
S.pop(); // loai bo khoi stack
cout << x << " ";
}
cout << "\n";
return 0;
}
4. VÍ dụ về ứng dụng của Stack
Stack có nhiều ứng dụng, sau đây là 1 ứng dụng trong chuyển đổi cơ số. Code sau sẽ chuyển số cơ số 10 sang cơ số x nhập từ bàn phím
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Lập trình C: Bài 16 – Xây dựng ngăn xếp (Queue)
Hàng đợi (Queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước” Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.
Nội dung
1. Queue cài đặt trên mảng
1.1 Khởi tạo Queue rỗng.
1.2 Kiểm tra Queue rỗng, đầy
1.3 Thêm phần tử vào cuối Queue (Push)
1.4 Xóa phần tử đầu Queue (Pop)
1.5 Xem thông tin phần tử đầu Queue
1.6 hàng đợi vòng (Queue Circular)
1.7 Chương trình hoàn chỉnh (full code)
2. Queue cài đặt bằng con trỏ
2.1 Xây dựng cấu trúc
2.2 Khởi tạo.
2.3. Kiểm tra rỗng
2.4 Tạo 1 Node P
2.5 Thêm phần tử vào cuối Queue
2.6 Xóa phần tử đầu Queue
2.7 Chương trình hoàn chỉnh (full code)
3. Sử dụng Quêu có sẵn trong C++
4. Ứng dụng của queue
1. Queue cài đặt trên mảng
Ở bài Stack, chúng ta có thể đếm số phần tử trong Stack bằng cách dùng 1 biến đếm (count) để cho dễ dàng, và ở phần Queue này tôi sẽ sử dụng biến đếm đó trong cấu trúc.
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
9
#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu
struct Queue
{
int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
item Data[Max]; //Mang cac phan tu
int count; //dem so phan tu cua Queue
};
1.1 Khởi tạo Queue rỗng.
Để khởi tạo Queue rỗng ta cần đưa vị trí Front về 0, Rear về -1, cout về 0.
code by nguyenvanquan7826
1
2
3
4
5
6
void Init (Queue &Q) //khoi tao Queue rong
{
Q.Front = 0; //phan tu dau
Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
Q.count = 0; //so phan tu bang 0
}
1.2 Kiểm tra Queue rỗng, đầy
Kiểm tra rỗng đầy chỉ cần kiểm tra count so với 0 và max
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
int Isfull (Queue Q) //kiem tra Queue day
{
if (Q.count == Max) //so phan tu = Max => day
return 1;
return 0;
}
1.3 Thêm phần tử vào cuối Queue (Push)
Tăng vị trí của Rear lên 1 và đưa data vào vị trí đó
code by nguyenvanquan7826
1
2
3
4
5
6
7
8
9
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
Q.count++; //tang so phan tu len
}
}
1.4 Xóa phần tử đầu Queue (Pop)
Trước tiên phải kiểm tra Queue rỗng không, nếu không rỗng ta thực hiện di chuyển các phần tử trong hàng về đầu hàng bằng vòng for (giống như xếp hàng khi mua hàng) sau đó giảm Rear và count xuống.
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q)) printf("Hang doi rong !");
else
{
item x = Q.Data[Q.Front];
for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
Q.Data[i] = Q.Data[i+1];
Q.Rear--; // giam vi tri phan tu cuoi xuong
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
}
1.5 Xem thông tin phần tử đầu Queue
code by nguyenvanquan7826
1
2
3
4
5
item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
if (Isempty(Q)) printf("Hang doi rong !");
else return Q.Data[Q.Front];
}
1.6 hàng đợi vòng (Queue Circular)
Như trên chúng ta xây dựng Queue dựa vào mảng, và thấy 1 điểm bất lợi là khi xóa phần tử đầu Queue chúng ta cần di chuyển tất cả các phần tử phía sau về trước. Để khắc phục điều này chúng ta có thể coi mảng đó như 1 mảng với các phân tử được xếp vòng tròn.
Khi đó ta có thể thêm, xóa các phần tử đơn giản, tuy nhiên cần lưu ý khi thêm và xóa phần tử mà Rear và Front ở cuối mảng (Max-1). Để khắc phục ta chia Front và Rear lây dư cho Max. Vậy là Nếu Front và Rear ở Max thì sẽ trở về vị trí 0.
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[(++Q.Rear) % Max] = x;
//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
Q.count++; //tang so phan tu len
}
}
int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
if (Isempty(Q)) printf("Hang doi rong !");
item x = Q.Data[Q.Front];
Q.Front = (Q.Front++) % Max; //tang vi tri phan dau tien len,neu dang o Max-1 thi ve 0
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
1.7 Chương trình hoàn chỉnh (full code)
click để xem chương trình hoàn chỉnh
link dự phòng
2. Queue cài đặt bằng con trỏ
2.1 Xây dựng cấu trúc
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
typedef int item; //kieu du lieu
struct Node
{
item Data;
Node * Next;
};
struct Queue
{
Node * Front, *Rear; //Node dau va Node cuoi
int count; //dem so phan tu
};
2.2 Khởi tạo.
Khởi tạo Queue ta cho Front và Rear cùng trỏ về NULL, count =0.
code by nguyenvanquan7826
1
2
3
4
5
void Init(Queue &Q)
{
Q.Front = Q.Rear = NULL;
Q.count = 0;
}
2.3. Kiểm tra rỗng
code by nguyenvanquan7826
1
2
3
4
5
6
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
2.4 Tạo 1 Node P
code by nguyenvanquan7826
1
2
3
4
5
6
7
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
2.5 Thêm phần tử vào cuối Queue
Để thêm phần tử, ta kiểm tra xem hàng có rỗng không, nếu hàng rỗng thì cho cả Front và Rear cùng trỏ về Node P mới tạo chứa phàn
tử x cần thêm. Nếu không rỗng ta trỏ Rear->Next về P và Rear trỏ về P. Tăng count lên 1
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
Node *P = MakeNode(x); //Neu Q rong
if (Isempty(Q))
{
Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
}
else //Khong rong
{
Q.Rear->Next = P;
Q.Rear = P;
}
Q.count ++ ; //tang so phan tu len
}
2.6 Xóa phần tử đầu Queue
Ta kiểm tra Queue có rỗng không, Nếu không rỗng kiểm tra xem có 1 hay nhiêu hơn 1 phần tử, nếu có 1 phần tử thì ta khởi tạo lại Queue, nếu có nhiều hơn ta cho Front trỏ đến tiếp theo. Giảm count xuống 1.
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q))
{
printf("Hang doi rong !");
return 0;
}
else
{
item x = Q.Front->Data;
if (Q.count == 1) //neu co 1 phan tu
Init(Q);
else
Q.Front = Q.Front->Next;
Q.count --;
return x; //tra ve phan tu lay ra
}
}
2.7 Chương trình hoàn chỉnh (full code)
click để xem chương trình hoàn chỉnh
link dự phòng
3. Sử dụng Quêu có sẵn trong C++
Giống như Stack trong C++, Queue cũng được xây dựng và ta chỉ việc dùng mà thôi.
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include
#include // su dung queue
using namespace std;
int main() {
queue Q; // khai bao queue co kieu nguyen
for (int i = 0; i < 10; i++) {
Q.push(i * 78 + 26); // them phan tu vao queue
}
cout << "So luong phan tu trong queue: " << Q.size() << "\n";
while (!Q.empty()) { // trong khi queue khong rong
int x = Q.front(); // lay gia tri dau hang
Q.pop(); // xoa gia tri dau hang
cout << x << " ";
}
cout << "\n";
return 0;
}
4. Ứng dụng của queue
Queue được dùng để khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn,
tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.
#include // io
#include // use stack
using namespace std;
int main() {
char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
stack S; // khai bao Stack voi kieu du lieu la int
int coSo, so, du;
cout << "Nhap so can chuyen: ";
cin >> so;
cout << "Nhap co so can chuyen: ";
cin >> coSo;
// chuyen doi bang cach dua vao Stack
while(so) {
du = so % coSo;
S.push(num[du]);
so /= coSo;
}
// Xuat ra
while(!S.empty()) {
cout << S.top();
S.pop();
}
return 0;
}
Các file đính kèm theo tài liệu này:
lap_trinh_c_hay_889.docx
