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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 3 - Danh sách đặc (mảng) Chương 3 Danh sách đặc (Mảng) 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.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 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 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;i3.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;i3.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 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;i3.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 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 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 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 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 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 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 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 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 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 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é ...