NGăn xếp Stack cài đặt bằng con trỏ code C/C++

0
3092
ngan xep stack cai dat bang con tro c

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.

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.

stack ngan xep cai dat bang con tro c

Vào code cụ thể 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 ngữ C để viết nhé. Nếu bạn viết bằng C++, chỉ cần thay đổi 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ó phần tử 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 phần tử của ngăn xếp, dùng trong việc chèn thêm phần tử vào ngăn xếp. Chúng ta sẽ sử dụng số lượng để xác định vị trí phần tử.

// 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 phần tử 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 ) để liên kết với đầu danh sách. Sau đó gán S.Top = P ( Lúc này P sẽ là phần tử ở đầ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 phần tử ra khỏi đầu ngăn xếp. Hàm sẽ trả về giá trị item x. Dùng cho nhiều mục đích 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ị 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 giải quyết 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 dữ liệu từ bàn phím và xuất ra màn hình.

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 một số nguyên từ bàn phím. Trả về kết quả 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<stdio.h>
#include<stdlib.h>

// 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;
}

LEAVE A REPLY

Please enter your comment!
Please enter your name here