intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu: Chương 3 - Danh sách đặc (mảng)

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:53

Thêm vào BST
Báo xấu
104
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ; mảng có thể một chiều hay nhiều chiều. Và để hiểu rõ hơn về mảng mời các bạn tham khảo bài giảng Cấu trúc dữ liệu: Chương 3 - Danh sách đặc (mảng) sau đây.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 3 - Danh sách đặc (mảng)

  1. Chương 3 Danh sách đặc (Mảng)
  2. 3.1. Định nghĩa • Mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. • Mảng có thể một chiều hay nhiều chiều. • Mảng hai chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. 16/11/2008 Cấu trúc dữ liệu 1 2
  3. 3.1. Định nghĩa • Mảng 1 chiều được khai báo như sau: []; VD: int a[100]; Hoặc vừa khai báo vừa gán giá trị khởi động cho mảng: int a[5] = {1, 7, -2, 8, 19}; Hoặc: int a[]= {1, 7, -2, 8, 19}; 16/11/2008 Cấu trúc dữ liệu 1 3
  4. 3.1. Định nghĩa Tương tự, có thể khai báo mảng 2 chiều hay nhiều chiều như sau: [][]...; VD: int a[100][150]; Hoặc: int a[][] = {{1, 7, -3, 8, 19}, {4, 5, 2, 8, 9}, {21, 7, -45, -3, 4}}; 16/11/2008 Cấu trúc dữ liệu 1 4
  5. 3.2. Các phép toán trên mảng 3.2.1. Khởi tạo mảng void khoi_tao(int a[], int &n) { int i; coutn; for(i=0;i
  6. 3.2. Các phép toán trên mảng 3.2.2. Xuất mảng void xuat(int a[],int n) { for(int i=0;i
  7. 3.2. Các phép toán trên mảng 3.2.3. Chèn một phần tử vào mảng Khi thêm một phần tử vào vị trí thứ k (0 ≤ k < n) thì các phần tử từ a[k+1] đến a[n-1] được di chuyển ra sau một vị trí void chen(int a[], int &n) { int i,k,x; coutx; coutk; for(i=n-1;i>=k-1;i--) a[i+1]=a[i]; a[k-1]=x; n++; } 16/11/2008 Cấu trúc dữ liệu 1 7
  8. 3.2. Các phép toán trên mảng 3.2.4. Xóa một phần tử của mảng Khi xóa một phần tử tại vị trí thứ k (0 ≤ k < n) thì các phần tử từ a[k+1] đến a[n-1] được di chuyển về trước một vị trí void xoa(int a[], int &n) { int i,k; coutk; for(i=k;i
  9. 3.3. Ưu và khuyết điểm của mảng 3.3.1. Ưu điểm • Dễ cài đặt và truy nhập các phần tử dữ liệu • Tốc độ truy nhập đến một vị trí bất kỳ trên mảng nhanh, hiệu quả 16/11/2008 Cấu trúc dữ liệu 1 9
  10. 3.3. Ưu và khuyết điểm của mảng 3.3.2. Khuyết điểm • Cần phải xác định trước số phần tử mảng trước khi sử dụng ⇒không phù hợp với các bài toán chưa biết trước số lượng các phần tử. • Khó khăn trong các thao tác chèn và xóa một phần tử bất kỳ trong mảng. Nếu bài toán mà việc chèn phần tử và xóa phần tử diễn ra liên tục ⇒ tốc độ xử lý sẽ rất chậm. 16/11/2008 Cấu trúc dữ liệu 1 10
  11. 3.4. Stack và Queue • Hàng đợi (QUEUE) và ngăn xếp (STACK) là 2 cấu trúc dữ liệu khá phổ biến. • Chúng thể hiện cách thức lưu trữ và xử lý dữ liệu theo một trình tự đã được quy ước. 9Hàng đợi: Nguyên tắc hoạt động: FIFO (First In First Out) 9Ngăn xếp: Nguyên tắc hoạt động: LIFO (Last In First Out) 16/11/2008 Cấu trúc dữ liệu 1 11
  12. 3.4. Stack và Queue 3.4.1. Stack Định nghĩa Stack là một kiểu danh sách tuyến tính đặc biệt mà phép thêm vào (PUSH) và phép lấy ra (POP) đều thực hiện ở cùng một đầu gọi là đỉnh (TOP) của stack. Do đó stack hoạt động theo nguyên tắc “vào sau ra trước” LIFO. Stack có thể rỗng hoặc chứa một số phần tử. 16/11/2008 Cấu trúc dữ liệu 1 12
  13. 3.4. Stack và Queue 3.4.1. Stack Định nghĩa Biểu diễn stack bằng mô hình mảng với các hàm: - Push theo chế độ tăng trước - Pop theo chế độ giảm sau input output top 3 2 1 16/11/2008 Cấu trúc dữ liệu 1 13
  14. 3.4. Stack và Queue 3.4.1. Stack Cài đặt Các thao tác chính: - isEmpty: Kiểm tra rỗng - isFull: Kiểm tra đầy - Push: Thêm 1 phần tử - Pop: Lấy ra 1 phần tử 16/11/2008 Cấu trúc dữ liệu 1 14
  15. 3.4. Stack và Queue 3.4.1. Stack Cài đặt struct Stack { int data[100]; int top; }; void Initial(Stack &s) { s.top = -1; } 16/11/2008 Cấu trúc dữ liệu 1 15
  16. 3.4. Stack và Queue 3.4.1. Stack Cài đặt int isEmpty(Stack s) { return (s.top==-1); } int isFull(Stack s) { return (s.top>=99); } 16/11/2008 Cấu trúc dữ liệu 1 16
  17. 3.4. Stack và Queue 3.4.1. Stack Cài đặt void Push(Stack &s,int k) { if (isFull(s)) return; s.data[++s.top]=k; } 16/11/2008 Cấu trúc dữ liệu 1 17
  18. 3.4. Stack và Queue 3.4.1. Stack Cài đặt int Pop(Stack &s) { if (isEmpty(s)) return -1; return s.data[s.top--]; } 16/11/2008 Cấu trúc dữ liệu 1 18
  19. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan Cú pháp của biểu thức: có 3 dạng 1. Trung tố (infix): Ký hiệu phép toán được viết giữa hai toán hạng. VD: (4 + 5)*(8 - (4 – 1)) Khuyết điểm: - Chỉ dùng được cho các phép toán có hai toán hạng - Nếu bỏ các dấu ngoặc tròn thì phải có: + Quy định về độ ưu tiên thứ tự thực hiện phép toán + Trong trường hợp các phép toán có cùng độ ưu tiên thì phải quy định thứ tự thực hiện các phép toán (từ trái sang phải hay từ phải sang trái) 16/11/2008 Cấu trúc dữ liệu 1 19
  20. 3.4. Stack và Queue 3.4.1. Stack Định giá biểu thức số học theo ký pháp hậu tố Ba Lan 2. Tiền tố (prefix): Ký hiệu phép toán được viết trước danh sách các toán hạng. Có 3 dạng tiền tố cụ thể: - Dạng tiền tố thường (ordinary prefix): danh sách các toán hạng được đặt trong hai dấu ngoặc tròn và có các dấu phẩy ngăn cách các toán hạng. VD: *(+(1,5),-(8,-(4,1))) - Dạng tiền tố Cambridge Polish (Cambridge Polish prefix): giống như dạng tiền tố thường nhưng dấu ngoặc bên trái của danh sách các toán hạng được mang ra ngoài, bao cả ký hiệu phép toán, và dấu phẩy ngăn cách các toán hạng được loại bỏ. VD: (*(+1 5)(-8 (-4 1))) 16/11/2008 Cấu trúc dữ liệu 1 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2