Ngăn xếp stack cài đặt bằng con trỏ trong C/C++ là nội dung của bài viết mình muốn chia sẻ cho các bạn. Bài tập Ứng dụng ngăn xếp viết hàm đổi số thập phân sang nhị phân.
Tóm Tắt
Cách cài đặt ngăn xếp bằng con trỏ
Về nội dung lý thuyết như định nghĩa, cách cài đặt stack bằng bạn có thể tham khảo tại bài viết trước của mình nhé!
Nắm vững nguyên lý là vào ra dữ liệu đểu ở một đầu của ngăn xếp, vậy là ok.
Ưu điểm của cách này là bạn sẽ tối ưu bộ nhớ. Không bị giới hạn các phần tử có trong ngăn xếp. Ngoài ra còn có nhiều điểm mạnh khác.
Vào code đơn cử thôi nào .
1. Khai báo ngăn xếp bằng con trỏ
Trong bài mình sẽ dùng ngôn từ C để viết nhé. Nếu bạn viết bằng C + +, chỉ cần đổi khác câu lệnh nhập xuất. Câu lệnh cấp bộ nhớ cho con trỏ là được .
// Cai dat Stack bang con tro
typedef int item;
struct Node{ // Khai bao node du lieu
item Data; // Du lieu
Node *Next; // con tro lien ket
};
typedef struct Stack{ // Dinh nghia kieu stack
Node * Top;
}Stack;
Trong đoạn code trên. Chúng ta sẽ khai báo một Node chứa Data và con trỏ Next dùng để liên kết với các phần tử phía dưới.
Ngăn xếp sẽ gồm tập hợp các node *Top. Khi áp dụng, các con trỏ Top sẽ trỏ tới các node ở phía dưới.
2. Các hàm cần thiết
Chú ý: web đang bị lỗi hiển thị kí tự & thành & amp;
Hàm khởi tạo stack
// Ham khoi tao stack
void Newstack(Stack & S){
S.Top=NULL;
}
Hàm này giúp xóa đi bộ nhớ đệm, tạo vùng nhớ cho con trỏ Top. Khởi tạo vùng nhớ cho Stack
Hàm kiểm tra stack rỗng
// Ham kiem tra Stack rong
int Isnull(Stack & S){
return (S.Top == NULL);
}
Nếu S.Top = = NULL, tức là đỉnh của ngăn xếp không có thành phần nào, như vậy ngắn xếp đó rỗng .
Hàm kiểm tra độ dài ngăn xếp
Hàm này sẽ cho biết số lượng thành phần của ngăn xếp, dùng trong việc chèn thêm thành phần vào ngăn xếp. Chúng ta sẽ sử dụng số lượng để xác lập vị trí thành phần .
// Ham kiem tra do dai Stack
int Lenstack(Stack S){
Node *P = S.Top; // Khai bao con tro P tro toi S
int i = 0;
while (P!=NULL){
i++;
P=P->Next;
}
return i;
}
3. Hàm tạo một node
Hàm này dùng để tạo một thành phần của ngăn xếp, gán giá trị cho nó !
Giá trị cần truyền vào là x, như vậy P->Data = x;
P -> Next = NULL; ( vì chưa liên kết với phần tử nào)
// Ham Tao mot Node
Node *Make_Node(item x){
Node *P = (Node*)malloc(sizeof(Node)); // CAp phat bo nho cho Node
// Code C++: Node *P = new Node;
P->Data=x;
P->Next= NULL;
return P;
}
4. Hàm Push và POP – Thêm phần tử và lấy phần tử khỏi đầu stack
Đối với hàm Push. Chúng ta chỉ cần tạo một node bằng cách dùng hàm make node bên trên. Gán P -> Next = S.Top ( vị trí đầu stack ) để link với đầu list. Sau đó gán S.Top = P ( Lúc này P. sẽ là thành phần ở đầu ngăn xếp )
// Ham Push - Them vao dau danh sach
void Push(Stack & S, item x){
Node * P = Make_Node(x); // Tao node P chua gia tri x
P->Next = S.Top;
S.Top = P;
}
Hàm POP : Hàm dùng để lấy thành phần ra khỏi đầu ngăn xếp. Hàm sẽ trả về giá trị item x. Dùng cho nhiều mục tiêu khác nhau .
Nếu S.Top khác rỗng, thì x = S.Top -> Data ( gán x = Data ). Sau đó giảm ngăn xếp đi một đơn vị chức năng bằng cách gán nó thành phần tử phía sau nó !
// Ham Pop - Lay gia tri phan tu dau danh sach
item Pop(Stack & S){
if(S.Top!=NULL){
item x = S.Top->Data;
S.Top=S.Top->Next;
return x;
}
}
5. Hàm chèn phần tử x vào vị trí k bất kì trong ngăn xếp
Chèn vào đầu thì sử dụng hàm Push, vậy làm cách nào để chèn vào vị trí bất kỳ mà không phá vỡ cấu trúc của nó ?
Tư tưởng xử lý của mình là :
- Dùng hàm Push, Pop, lấy các phần tử từ vị trí k cho vào một ngăn xếp khác ( Temp);
Xác định vị trí bằng cách dùng hàm kiểm tra độ dài ngăn xếp. - Dùng hàm Push, thên phần tử cần chèn vào vị chí k.
- Cuối cùng Push lại các phần tử từ ngăn xếp temp
// Ham chen gia tri x vao vi tri k bat ki
void Insert_k(Stack & S, item x, int k){
if(k<1 || k > Lenstack(S))
printf("\nVi tri chen khong hop le");
else{
Stack Temp;
Newstack(Temp);
int t = Lenstack(S)-k; // Truoc vi tri k co k phan tu
// printf("\nDo dai la %d", Lenstack(S));
while(t>=0){
Push(Temp,Pop(S)); // Chuyen phan tu sang stack Temp t+1 lần
t--;
}
Push(S,x);
while(Temp.Top!=NULL){ // Trong khi Temp còn phần tử
Push(S, Pop(Temp)); // Push tro lai stack S
}
}
}
6. Hàm nhập xuất dữ liệu cho Stack
Mình sẽ dùng hàm này để nhập tài liệu từ bàn phím và xuất ra màn hình hiển thị .
Hàm Input:
Điều kiện để kết thúc nhập là do bạn tự xác định. Ở đây mình cho nếu x = 0 thì kết thúc. Sử dụng vòng lặp while cho tới khi điêu kiện sai thì ngừng nhập. Mỗi lần nhập sẽ thêm phần tử vào đầu ngăn xếp. Đúng cấu trúc của kiểu dữ liệu nhé!
Hàm Output: Cũng lấy từng phần tử từ đầu ngăn xếp cho tới khi không còn phần tử nào trong stack ( S.Top == NULL)
// Nhap nhap Input
void Input(Stack & S){
printf("\nNhap phan tu cho stack: \nNhap 0 de ket thuc\n");
item x;
do{
scanf("%d",&x);
if(x!=0)
Push(S,x);
}
while (x!=0);
}
// Ham xuat
void Output(Stack S){
printf("\n");
while(S.Top !=NULL)
printf(" %d",Pop(S));
}
7. Ứng dụng ngăn xếp, đổi một số nguyên x từ hệ thập phân sang hệ nhị phân
Đề bài : Nhập vào 1 số ít nguyên từ bàn phím. Trả về tác dụng là dạng nhị phân của số đó
Về thuật toán: Chúng ta sẽ chia số nguyên x cho 2, lấy phần dư ( kể cả 0 hoặc 1) Push vào một stack Binary.
Sau mỗi lần chia thì gán x = x/2 ( Giảm dần đi ). Nếu bạn đã biết cách đổi số nhị phân bằng tay thì điều này rất dễ hiểu.
// Ham doi thap phan sang nhi phan
void Convertbinary(int x){
Stack Binary;
int temp;
Newstack(Binary);
while(x!=0){
Push(Binary,(x%2));
x=x/2;
}
printf("\nKet qua: ");
while(Binary.Top!= NULL)
printf("%d",Pop(Binary));
}
8. Code hoàn chỉnh stack ngăn xếp cài đặt bằng con trỏ
Ngoài bài code này, các bạn có thể tham khảo thêm các bài viết về cấu trúc dữ liệu và thuật toán khác tại đây.
// //Code by tailieu.pro - https://github.com/duongdinh24 // Stack pointer #include#include // Cai dat Stack bang con tro typedef int item; struct Node{ // Khai bao node du lieu item Data; // Du lieu Node *Next; // con tro lien ket }; typedef struct Stack{ // Dinh nghia kieu stack Node * Top; }Stack; // Ham khoi tao stack void Newstack(Stack & S){ S.Top=NULL; } // Ham kiem tra Stack rong int Isnull(Stack & S){ return (S.Top == NULL); } // Ham kiem tra do dai Stack int Lenstack(Stack S){ Node *P = S.Top; // Khai bao con tro P tro toi S int i = 0; while (P!=NULL){ i++; P=P->Next; } return i; } // Ham Tao mot Node Node *Make_Node(item x){ Node *P = (Node*)malloc(sizeof(Node)); // CAp phat bo nho cho Node // Code C++: Node *P = new Node; P->Data=x; P->Next= NULL; return P; } // Ham Push - Them vao dau danh sach void Push(Stack & S, item x){ Node * P = Make_Node(x); // Tao node P chua gia tri x P->Next = S.Top; S.Top = P; } // Ham Pop - Lay gia tri phan tu dau danh sach item Pop(Stack & S){ if(S.Top!=NULL){ item x = S.Top->Data; S.Top=S.Top->Next; return x; } } // Ham chen gia tri x vao vi tri k bat ki void Insert_k(Stack & S, item x, int k){ if(k<1 || k > Lenstack(S)) printf("\nVi tri chen khong hop le"); else{ Stack Temp; Newstack(Temp); int t = Lenstack(S)-k; // printf("\nDo dai la %d", Lenstack(S)); while(t>=0){ Push(Temp,Pop(S)); t--; } Push(S,x); while(Temp.Top!=NULL){ Push(S, Pop(Temp)); } } } // Nhap nhap Input void Input(Stack & S){ printf("\nNhap phan tu cho stack: \nNhap 0 de ket thuc\n"); item x; do{ scanf("%d",&x); if(x!=0) Push(S,x); } while (x!=0); } // Ham xuat void Output(Stack S){ printf("\n"); while(S.Top !=NULL) printf(" %d",Pop(S)); } // Ham doi thap phan sang nhi phan void Convertbinary(int x){ Stack Binary; int temp; Newstack(Binary); while(x!=0){ Push(Binary,(x%2)); x=x/2; } printf("\nKet qua: "); while(Binary.Top!= NULL) printf("%d",Pop(Binary)); } int main(){ Stack S; Newstack(S); Input(S); Insert_k(S,14,4); printf("\nStack sau khi chen 14 : \n"); Output(S); Convertbinary(218); return 0; }
Source: https://final-blade.com
Category: Kiến thức Internet
