Cài đặt stack bằng danh sách liên kết đơn

em mới tìm hiểu về stack , anh chị cho em hỏi cài stack bằng mảng có gì khác với danh sách liên kết đơn vậy ạ , ưu và nhược điểm của mỗi loại là gì vậy ạ .
em cảm ơn

Nội dung chính Show

(1) Khởi tạo ngăn xếp rỗng
void create(struct node *s){ s = NULL;}(2) Kiểm tra ngăn xếp rỗngint Empty(struct node *s){ return (s == NULL);}
void Push(struct node *s, item x){
struct node *p; p= new node; p->infor= x; p->next= NULL; if (s==NULL) s= p; else{ p->next = s; s= p; }}
(4) Loại bỏ một phần tử ở đỉnh ngăn xếp:
int Pop(struct Stack *s, item &x){ else{ p= s; x= s->infor; delete p; return 1;} struct node *p; if (Empty(s) ) return 0; p= new node; s= s->next; }
QUEUE - HÀNG ĐỢI:\ a)Khái niệm - Hàng đợi là kiểu danh sách tuyến tính, trong đó phép bổ sung một phần tử được thực hiện ở một đầu gọi là lối sau (rear) và phép loại bỏ một phần tử được thực hiện ở đầu kia gọi là lối trước (front) của hàng đợi. - Hàng đợi là kiểu danh sách dạng FIFO (First In-First Out).
nCấu trúc dữ liệu của hàng đợi:
//Khai báo kiểu Item (nếu cần)
struct node{ Item infor; struct node *rear; struct queue q; node *next; }; struct queue{ struct node *front; };
(3) Thêm một phần tử x vào lối sau của hàng đợi: void Push(struct queue *q, item x){ struct node *p; p= new node; p->infor= x; p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } }
(4) Loại bỏ một phần tử ở lối trước của hàng đợi: int Pop(struct queue *q, item &x){ struct node *p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } }
Ngoài ra các bạn có thẻ tham khảo code mấu, bài tập và slide ở dưới

Thế bạn đã biết mảng và dslk đơn khác gì nhau chưa

3 Likes

Cuong_Nguyen_Huu:

mảng có gì khác với danh sách liên kết đơn

Kết quả ở trang đầu tiên

2 Likes

Home Categories FAQ/Guidelines Terms of Service Privacy Policy

Yêu cầu:

Minh họa cài đặt stack bằng danh sách liên kết. Mỗi phần tử của stack sẽ chứa 1 số nguyên. Do vậy mỗi node của danh sách liên kết sẽ gồm 1 trường dữ liệu kiểu int, 1 con trỏ next. Thao tác loại bỏ (pop()) hay bổ sung (push()) sẽ thực hiện với ô đầu tiên của danh sách liên kết.

Các phép toán cơ bản: 1. Khởi tạo 2. Kiểm tra ngăn xếp rỗng: 3. Nạp vào : nạp phần tử vào đầu ngăn xếp 4. Lấy ra : trả lại giá trị của phần tử ở đầu ngăn xếp và xóa bỏ phần tử đó khỏi ngăn xếp

5. Hiển thị các phần tử của ngăn xếp

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /* * File: khoa.cpp * Author: KHOA * * Created on August 26, 2016, 9:16 AM */ #include <iostream> #include<stdio.h> #include<stdio.h> using namespace std; struct Node { int data; Node *next; }; struct List { Node *head; Node *tail; }; // khoi tao stack void Init(List &s) { s.head = s.tail = NULL; } // kiem tra stack co rong khong bool isEmpty(List &s) { if (s.head == NULL) return true; else return false; } // tao Node Node *creat_Node(int x) { Node *p = new Node; if (p != NULL) { p->data = x; p->next = NULL; } else return NULL; } // Push vao stack void push(List &s, int x) { Node *p = creat_Node(x); if (isEmpty(s)) { s.head = s.tail = p; // neu stack rong thi ta gan p la phan tu dau va cuoi } else { p->next = s.head; // cho phan tu ke tiep bang phan tu dau s.head = p; // cap nhat phan tu dau la phan tu moi them vao } } // Pop phan tu ra khoi stack void pop(List &s) { Node *p = s.head; if (!isEmpty(s)) { s.head = p->next; delete p; } else { cout << "\nDanh sach da rong! "; } } // tim kiem phan tu trong stack Node *search_Node(List &s, int x) { Node *q = s.head; while (q != NULL) { if (q->data == x) { return q; } else { q = q->next; } } return NULL; } // Nhap du lieu cho Stack void nhap(List &s) { int n; cout << "nhap so luong phan tu cho stack: "; cin>>n; for (int i = 1; i <= n; i++) { int x; cout << "Phan tu " << i << ": "; cin>>x; push(s, x); } } // xuat cac phan tu trong stack void xuat(List &s) { Node *p = s.head; while (p != NULL) { cout << " " << p->data; p = p->next; } } int main() { List s; Init(s); nhap(s); xuat(s); int x; int lc; do { cout << "\n_ _ _CHUONG TRINH STACK_ _ _"; cout << endl; cout << " 1.Push Stack" << "\n 2.Pop Stack" << "\n 3.Tim phan tu" << "\n 4.Thoat"; cout << "\nNhap thong tin can kiem tra: "; cin>>lc; switch (lc) { case 1: cout << "Nhap phan tu can Push: "; cin>>x; push(s, x); break; case 2: cout << "Pop phan tu trong Stack "; pop(s); cout << "\n"; break; case 3: cout << "Nhap phan tu can tim kiem: "; cin>>x; if (search_Node(s, x) != NULL) cout << "Tim thay phan tu!\n"; else cout << "khong tim thay!\n"; break; case 4: break; default: cout << "Ban nhap sai "; } xuat(s); cout << "\n"; } while (lc != 4); return 0; }

STACK - HÀNG ĐỢI

a)Khái niệm

nNgăn xếp là một danh sách tuyến tính trong đó phép bổ sung và phép loại bỏ phần tử được thực hiện ở một đầu gọi là đỉnh (Top).

n Ngăn xếp là một danh sách kiểu LIFO (Last In - Firts Out).

n Hai phép toán chính của stack:

push() - thêm một nút ở đỉnh

pop() - lấy đi một nút ở đỉnh
nCấu trúc dữ liệu của ngăn xếp:

//Khai báo kiểu Item (nếu cần)

struct node{
Item infor;

node *next;

}

struct node *s;//khai báo stack S là con trỏ trỏ và đỉnh stack

(1) Khởi tạo ngăn xếp rỗng

void create(struct node *s){ s = NULL;}(2) Kiểm tra ngăn xếp rỗngint Empty(struct node *s){ return (s == NULL);}

(3) Thêm một phần tử x vào đỉnh ngăn xếp:

void Push(struct node *s, item x){
struct node *p; p= new node; p->infor= x; p->next= NULL; if (s==NULL) s= p; else{ p->next = s; s= p; }}

(4) Loại bỏ một phần tử ở đỉnh ngăn xếp:

int Pop(struct Stack *s, item &x){ else{ p= s; x= s->infor; delete p; return 1;} struct node *p; if (Empty(s) ) return 0; p= new node; s= s->next; }

QUEUE - HÀNG ĐỢI:\ a)Khái niệm - Hàng đợi là kiểu danh sách tuyến tính, trong đó phép bổ sung một phần tử được thực hiện ở một đầu gọi là lối sau (rear) và phép loại bỏ một phần tử được thực hiện ở đầu kia gọi là lối trước (front) của hàng đợi. - Hàng đợi là kiểu danh sách dạng FIFO (First In-First Out).

nCấu trúc dữ liệu của hàng đợi:

//Khai báo kiểu Item (nếu cần)

struct node{ Item infor; struct node rear; struct queue q; node next; }; struct queue{ struct node *front; };

(1) Khởi tạo hàng đợi rỗng:

void create(struct queue *q){

q->front = NULL;

q->rear= NULL;

}

(2) Kiểm tra hàng đợi rỗng:

int Empty(struct queue q){

return (q.front == NULL) ;

}

(3) Thêm một phần tử x vào lối sau của hàng đợi: void Push(struct queue q, item x){ struct node p; p= new node; p->infor= x; p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } }

(4) Loại bỏ một phần tử ở lối trước của hàng đợi: int Pop(struct queue q, item &x){ struct node p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } }

Ngoài ra các bạn có thẻ tham khảo code mấu, bài tập và slide ở dưới

CHU HẢI ĐĂNG
Học viện công nghẹ bưu chính viễn thông Hà Nội.
Phone: 01658991973
Email:
Facebook:http://www.facebook.com/HaiDangChu
y! : chu.haidang

Cài đặt stack bằng danh sách liên kết đơn

(1) Khởi tạo ngăn xếp rỗng

void create(struct node *s){ s = NULL;}(2) Kiểm tra ngăn xếp rỗngint Empty(struct node *s){ return (s == NULL);}

void Push(struct node *s, item x){

struct node *p; p= new node; p->infor= x; p->next= NULL; if (s==NULL) s= p; else{ p->next = s; s= p; }}

(4) Loại bỏ một phần tử ở đỉnh ngăn xếp:

int Pop(struct Stack *s, item &x){ else{ p= s; x= s->infor; delete p; return 1;} struct node *p; if (Empty(s) ) return 0; p= new node; s= s->next; }

nCấu trúc dữ liệu của hàng đợi:

//Khai báo kiểu Item (nếu cần)

struct node{ Item infor; struct node *rear; struct queue q; node *next; }; struct queue{ struct node *front; };

(3) Thêm một phần tử x vào lối sau của hàng đợi: void Push(struct queue *q, item x){ struct node *p; p= new node; p->infor= x; p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } }

(4) Loại bỏ một phần tử ở lối trước của hàng đợi: int Pop(struct queue *q, item &x){ struct node *p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } }

Ngoài ra các bạn có thẻ tham khảo code mấu, bài tập và slide ở dưới

Bài Viết Liên Quan

MỚI CẬP NHẬP

Xem Nhiều

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

void create(struct node s){ s = NULL;}(2) Kiểm tra ngăn xếp rỗngint Empty(struct node s){ return (s == NULL);}

int Pop(struct Stack s, item &x){ else{ p= s; x= s->infor; delete p; return 1;} struct node p; if (Empty(s) ) return 0; p= new node; s= s->next; }

struct node{ Item infor; struct node rear; struct queue q; node next; }; struct queue{ struct node *front; };

(3) Thêm một phần tử x vào lối sau của hàng đợi: void Push(struct queue q, item x){ struct node p; p= new node; p->infor= x; p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } }

(4) Loại bỏ một phần tử ở lối trước của hàng đợi: int Pop(struct queue q, item &x){ struct node p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } }