Page 1
goupee.vn goupee.com Phần 3: Cấu trúc dữ liệu và giải thuật Chương 9: Các cấu trúc tuyến tính Phần A: Cấu trúc Mảng cuu duong than cong . com fb.com/goupee.vn 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Contenu du document
Page 2
goupee.vnCác nội dung chính goupee.com 1. Cấu trúc mảng Mô tả Cấu trúc lưu trữ tuần tự Cài đặt mảng bằng cấu trúc lưu trữ tuần tự Hàm địa chỉ 2. Cấu trúc danh sách Mô tả Cấu trúc vào sau ra trước (LIFO) (Stack-Ngăn xếp) Cấu trúc vào trước ra trước (cuu duong than cong . comFIFO) (Queue-Hàng đợi) Một số ứng dụng của ngăn xếp và hàng đợi fb.com/goupee.vn 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 3
goupee.vn1. Cấu trúc mảng goupee.com Mô tả cấu trúc Mảng (Array) là một tập cố định các phần tử và cùng kiểu dữ liệu. Tính chất đặc trưng Số chiều: số chiều của mảng tương ứng với số chiều của thông tin cần được biểu diễn. Một mảng bao giờ cũng ít nhất một chiều. Kích thước mỗi chiều: phải là một giá trị cố định. Ta có thể dễ dàng suy ra kích thước của mảng bằng cách lấy tích tất cả các kích thước của tất cả các chiều. Kiểu phần tử mảng: đó là kiểu dữ liệu cho mỗi phần tử của mảng. Kiểu mảng có thể được khái quát bằng khai báo như sau: ARRAY : <name>[dimension, len 1, len 2,..., len n] OF datatype; Khi đó, kích cuu duong than cong . comthước của mảng name kí hiệu LEN(name) được tính bằng công thức: LEN(name) = len 1 x len 2 x ... = (len i) (với i=1,2,..,n) fb.com/goupee.vn 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 4
goupee.vn1. Cấu trúc mảng goupee.com Mô tả - Ví dụ: Khai báo mảng 1 chiều: ARRAY: vector [1, N] OF integer ; Khai báo mảng hai chiều: ARRAY: matran[2, M, N] OF integer; hay tương đương ARRAY: matran[1, M] OF vector; Khai báo mảng N chiều: ARRAY : a[N, L , L ,..., Ln] OF integer; (2.1) 1 2 Từ việc khai báo mảng như trên ta có thể dễ dàng suy ra mảng hai chiềucuu duong than cong . comlà mảng một chiều của các mảng một chiều, mảng ba chiều là mảng 1 chiều của các mảng 2 chiều,..., mảng N chiều là mảng 1 chiều của các mảng N-1 chiều. fb.com/goupee.vn 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 5
goupee.vn1. Cấu trúc mảng goupee.com Mô tả - Ví dụ: Chúng ta có thể mô tả hình thức như sau: ARRAY: an[N, L , L ,..., Ln] OF datatype ; 1 2 ARRAY: an-1[N-1, L ,..., Ln] OF datatype ; AND 2 ARRAY: an[1, L ] OF an-1 ; (2.2) 1 Trong C/C++, các mảng trên được khai báo như sau: int vector [0..N-1] ; int matran [0..M-1][0..N-1] ; hay vector matran [0..M-1]; Lưu ý trong C/C++ quycuu duong than cong . comước: Kích thước mỗi chiều = chỉ số trên + 1 fb.com/goupee.vn 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 6
goupee.vn1. Cấu trúc mảng goupee.com Các thao tác cơ bản Thao tác khởi tạo: thao tác khởi tạo cấu trúc, xác định các đặc trưng của cấu trúc này. Thao tác này luôn được tiến hành trước tiên. Trong các ngôn ngữ lập trình, thao tác này tương ứng với việc khai báo kiểu dữ liệu mới. Thao tác truy nhập vào các phần tử của mảng: truy nhập vào các phần tử của mảng để sử dụng các phần tử này như: lấy giá trị, cập nhật giá trị. Để truy nhập vào một phần tử của mảng, ta dùng một chỉ số (index) gắn với phần tử đó. Mỗi phần tử của mảng có một chỉ số duy nhất, có vai trò như địa chỉ của phần tử trong mảng.cuu duong than cong . com Nếu mảng có N chiều như được khai báo ở (2.1) thì cấu trúc chỉ số của mỗi phần tử như sau: [i ,i ,...,in], với ij (j = 1..N) là các số nguyên 1 2 thoả mãn: 1 ij Lj. fb.com/goupee.vn 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 7
goupee.vnVí dụ về các thao tác goupee.com Khi truy nhập vào một phần tử thứ i của vector (mảng 1 chiều) ta có: vector[i] Khi truy nhập vào một phần tử ở hàng i, cột j của ma trận (mảng 2 chiều) ta có: matran[i,j]. Ta sẽ tìm hiểu sâu hơn về ý nghĩa của chỉ số ở phần sau, khi ta học về khái niệm hàm địa chỉ. cuu duong than cong . com fb.com/goupee.vn 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 8
goupee.vnCấu trúc lưu trữ tuần tự goupee.com Mô tả A0 a1 a2 … ai … an-1 an c A0 là địa chỉ bắt đầu của cấu trúc lưu trữ, cũng là địa chỉ của ô nhớ chứa phần tử đầu tiên. Kích thước mỗi ô nhớ là như nhau, là một hằng số cố định được kí hiệu là c (đơn vị tính thường là byte). Hàm địa chỉ:cuu duong than cong . com Địa chỉ của ai: Loc (ai) = A0 + c* (i-1) Hàm địa chỉ: fi = c * (i-1) (address function) fb.com/goupee.vn 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 9
goupee.vnCấu trúc lưu trữ tuần tự goupee.com Đặc điểm Cấu trúc tương đối đơn giản, dễ sử dụng Kích thước luôn cố định. Việc cấp phát vùng nhớ cho CTLT này được thực hiện đúng một lần, và cũng được giải phóng đúng một lần khi CTLT này không cần dùng nữa (như sau khi ra khỏi một thủ tục hay kết thúc chương trình có sử dụng CTLT này). Việc truy nhập vào các phần tử nhanh và đồng đều (truy nhập trực tiếp) do địa chỉ mỗi phần tử có thể tính trực tiếp. Ta sẽ tìm hiểu cách tính này ở phần sau. Vì cấu trúc mảng có kích thước cố định, gồm các phần tửcuu duong than cong . com có cùng kiểu dữ liệu, nên nó thường được cài đặt bằng cấu trúc lưu trữ tuần tự. fb.com/goupee.vn 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 10
goupee.vnCài đặt mảng bằng cấu trúc lưu trữ tuầngoupee.com tự Cài đặt mảng một chiều: ARRAY : a [1, N] OF datatype ; 1 Thứ nhất, xác định các đặc trưng của cấu trúc lưu trữ: Số ô nhớ : bằng N, là số phần tử của mảng, tức là kích thước của mảng. Kích thước mỗi ô nhớ: là một hằng số c cố định mà bằng kích thước của kiểu dữ liệu datatype của mỗi phần tử của mảng. Cần dành ra một khối nhớ liên tục có kích thước c.N, có địa chỉ đầu tiên là Acuu duong than cong . comđể lưu trữ cho mảng này. 0 fb.com/goupee.vn 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 11
goupee.vnCài đặt mảng 1 chiều goupee.com Cài đặt mảng một Kiểu DL Kích thước chiều: char 1 ARRAY : a [1, N] OF 1 datatype ; int 2 Bảng 2.1: Kích thước một số kiểu dữ liệu cơ long, float 4 bản trong C/C++ double 8 cuu duong than cong . comchar[N] N fb.com/goupee.vn 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 12
goupee.vnCài đặt mảng 1 chiều goupee.com ARRAY : a [1, N] OF datatype ; 1 Thứ hai, bố trí các phần tử của mảng vào CTLT đã chọn: Bố trí lần lượt các phần tử của mảng vào trong các ô nhớ của CTLT tuần tự, có nghĩa là phần tử thứ i của mảng sẽ được lưu trữ ở ô nhớ thứ i (1 i N, với N là kích thước của mảng). Địa chỉ tuyệt đối của phần tử thứ i, a1[i]: Ai = A0 + c (i-1) A0 cuu duong than cong . com a1[1] a1[2] … a1[i] … a1[n-1] a1[n] c fb.com/goupee.vn 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 13
goupee.vnCài đặt mảng 2 chiều goupee.com Cài đặt mảng hai chiều: ARRAY : a [2,M,N] OF datatype ; 2 Với các mảng hai hay nhiều chiều hơn, cấu trúc mảng và cấu trúc lưu trữ tuần tự có sự khác biệt đáng kể. Khi CTDL mảng là đa chiều thì cấu trúc lưu trữ tuần tự chỉ có một chiều. Do đó, chúng ta cần phải có một phương pháp để chuyển đổi từ cấu trúc đa chiều sang cấu trúc một chiều và ngược lại. Thứ nhất, xác định các đặc trưng của CTLT tuần tự: Số ô nhớ : bằng M*N, là kích thước của mảng. Kích thước mỗicuu duong than cong . comô nhớ : là kích thước của datatype. Ta cần dành ra một khối nhớ liên tục có kích thước c.M.N, có địa chỉ đầu tiên là A để lưu trữ cho mảng này. 0 fb.com/goupee.vn 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 14
goupee.vnCài đặt mảng 2 chiều goupee.com Cài đặt mảng hai chiều: ARRAY : a [2,M,N] OF datatype ; 2 Thứ hai, bố trí các phần tử: có hai phương pháp bố trí: Theo thứ tự ưu tiên hàng: trong phương pháp này, các phần tử của mảng sẽ được bố trí lần lượt theo từng hàng, hết hàng nọ đến hàng kia theo thứ tự các hàng từ trên xuống dưới. Theo thứ tự ưucuu duong than cong . comtiên cột: trong phương pháp này, các phần tử của mảng lại được bố trí theo từng cột, hết cột nọ đến cột kia theo thứ tự các cột từ trái sang phải. fb.com/goupee.vn 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 15
goupee.vnCài đặt mảng hai chiều: 2 cách bố trígoupee.com A mt[1,1] mt[1,2] … mt[i,j] … mt[m,n-1] mt[m,n] 0 Theo thứ tự ưu tiên hàng mt[1,1] mt[1,2] c mt[2,1] mt[2,2] mt[3,1] mt[3,2] ... ... Theo thứ tự ưu tiên cột A mt[1,1] mt[2,1]cuu duong than cong . com… mt[i,j] … mt[m-1,n] mt[m,n] 0 Các phương pháp lưu trữ mảng hai chiều fb.com/goupee.vn 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 16
goupee.vnCài đặt mảng 2 chiều goupee.com Cài đặt mảng hai chiều: ARRAY : a [2,M,N] OF datatype ; 2 Với phương pháp lưu trữ theo thứ tự ưu tiên hàng, phần tử a [i,j] 2 của mảng được lưu trữ ở ô nhớ thứ z tính theo công thức: z = N*(i-1) + j (2.3) Công thức này được gọi là hàm địa chỉ cho mảng hai chiều a khi 2 các phần tử được bố trí theo thứ tự ưu tiên hàng. Ngược lại, ở ô nhớ z sẽ lưu trữ phần tử a [i,j] với i và j được tính 2 theo công thức:cuu duong than cong . com i = (z -1) DIV N +1 và j = (z-1) MOD N +1 (2.4) fb.com/goupee.vn 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 17
goupee.vnCài đặt mảng 2 chiều goupee.com Cài đặt mảng hai chiều: ARRAY : a [2,M,N] OF datatype ; 2 Với phương pháp lưu trữ theo thứ tự ưu tiên cột, phần tử a [i,j] 2 của mảng được lưu trữ ở ô nhớ thứ z được tính theo công thức : z = M*(j-1) + i (2.5) Đây là hàm địa chỉ cho mảng hai chiều a khi các phần tử được 2 bố trí theo thứ tự ưu tiên cột. Ngược lại, ở ô nhớ z sẽ lưu trữ phần tử a [i,j] với i và j được tính 2 theo công thứccuu duong than cong . com: i = (z -1) MOD M +1 và j = (z-1) DIV M +1 (2.6) fb.com/goupee.vn 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 18
goupee.vnCài đặt mảng nhiều hơn 2 chiều goupee.com Đối với mảng nhiều hơn hai chiều, ta nhớ lại cách chuyển đổi tương đương trong phần trước, là cách chuyển đổi từ các mảng nhiều chiều sang các mảng ít chiều hơn. Cụ thể, mảng 3 chiều là một mảng một chiều của các mảng hai chiều. Mà cách lưu trữ mảng 1 chiều và mảng hai chiều ta đã tìm hiểu ở phần trên, nên việc lưu trữ mảng 3 chiều không gặp khó khăn gì. Từ cách cài đặt được mảng 3 chiều, chúng ta dễcuu duong than cong . com dang suy ra cách cài đặt các mảng 4, 5,..., N chiều. fb.com/goupee.vn 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 19
goupee.vnCấu trúc mảng – Hàm địa chỉ goupee.com Khái niệm Hàm địa chỉ có dạng: f : X Y (2.7) Với : X là tập các phần tử của một mảng Y là địa chỉ các ô nhớ của cấu trúc lưu trữ tuần tự Một số quy ước đã sử dụng: c là một số nguyên dương để chỉ kích thước của một ô nhớ cuu duong than cong . com A là một số nguyên dương để chỉ địa chỉ đầu tiên của 0 khối lưu trữ, cũng là địa chỉ của ô nhớ đầu tiên. fb.com/goupee.vn 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 20
goupee.vnCấu trúc mảng – Hàm địa chỉ goupee.com Tính chất Hàm địa chỉ: phụ thuộc vào các đặc trưng của cấu trúc mảng như số chiều, kích thước mảng, kiểu dữ liệu của các phần tử, nhưng đặc trưng số chiều là cơ bản nhất. Chúng ta sẽ thấy rõ hơn về điều này khi xây dựng hàm địa chỉ cho các mảng có số chiều khác nhau. cuu duong than cong . com fb.com/goupee.vn 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !