Cấu trúc dữ liệu và giải thuật - Chương 2

CẤU TRÚC MẢNG (ARRAY)Cấu trúc dữ liệu đầu tiên mà ta nói tới là cấu trúc Mảng , đây là 1 cấu trúc rất quen thuộc, nó có mặt ở hầu hết các ngôn ngữ lập trình. I. ĐỊNH NGHĨA Mảng là một tập hợp có thứ tự, bao gồm 1 số xác định n phần tử (n được gọi là độ dài hay kích thước của mảng). Ngoài giá trị, mỗi phần tử của mảng còn dược đặt trưng bởi chỉ số (index), thể hiện thứ tự của phần tử đó tron mảng. Các giá trị của phần...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 2Chương II. CẤU TRÚC MẢNG (ARRAY) Cấu trúc dữ liệu đầu tiên mà ta nói tới là cấu trúc Mảng , đây là 1 cấu trúcrất quen thuộc, nó có mặt ở hầu h ết các ngôn ngữ lập trình.I. ĐỊNH NGHĨA Mảng là một tập hợp có thứ tự, bao gồm 1 số xác định n phần tử (n đ ược gọ ilà độ dài hay kích th ước củ a mảng). Ngoài giá trị, mỗi phần tử của mảng còn dượcđặt trưng b ởi chỉ số (index), th ể h iện thứ tự của phần tử đó tron mảng. Các giá trịcủa ph ần tử mảng đ ều cùng một loại. Đối với mảng thường gặp các phép toán : - Tạo lập một mảng . - Duyệt qua các phần tử của mảng. - Tìm kiếm một phần tử của mảng. - Sắp xếp các ph ần tử trong mảng theo một thứ tự nhất đ ịnh. Vì số phần tử của mảng là cố đ ịnh, nên không có phép bổ sung ph ần tử mớivào mảng hoặc loại bỏ mộ t ph ần tử ra khỏi mảng. Vectơ là mảng một chiều, mỗi ph ần tử của nó ứng với một chỉ số. Chẳnghạn: phần tử của vectơ A, kí hiệu là Ai h oặc A[i] với i là chỉ số . Ma trận là mảng hai chiều, mỗ i ph ần tử của nó ứng với 2 chỉ số, ví dụ : ph ầntử của ma trận B, kí hiệu là Bij ho ặc B[i, j] với i gọ i là chỉ số hàng, j gọ i là chỉ sốcột. Tương tự người ta cũ ng mở rộng : mảng 3 chiều ,mảng 4 chiều,…. Mảng nchiều.II. CẤU TRÚC LƯU TRỮ CỦA MẢNG1. Khái quát về cách lưu trữ Mộ t cách đơn giản, có thể hình dung bộ nh ớ của MTĐT là một dãy các ph ầntử cơ sở được đ ánh số kế tiếp nhau (kể từ số 0). Số thứ tự đó được gọi là đ ịa chỉ ,một ph ần tử nhớ cơ sở, có địa chỉ đượ gọ i là từ máy. Một ph ần tử dữ liệu có thểđược lưu trữ trong máy bởi một ô nh ớ bao gồm mộ t ho ặc nhiều từ máy. Việc truycập vào ô nhớ dó sẽ được xác định bởi địa ch ỉ của từ máy đ ầu tiên tạo nên ô nhớđó. Th ường có 2 cách để xác định đ ược địa chỉ. Cách th ứ hất là d ựa vào những đặt tả của việc lư u trữ dữ liệu đ ể tính trựctiếp ra địa chỉ. Địa chỉ n ày được gọi là địa chỉ đ ược tính (computer address). Cáchnày thương hay được sử dụng trong chương trình d ịch củ a các ngôn ngữ lập trìnhđể tính địa chỉ các phần tử của mảng, tính địa ch ỉ các lệnh th ực hiện tiếp theov.v… Cách thứ h ai là lưu trữ các địa ch ỉ cần thiết ở một chỗ qui đ ịnh, khi cần xácđịnh sẽ lấy từ đó ra. Lo ại địa ch ỉ này được gọi là (pointer) họăc mối nối (link). Địachỉ quay lui của chương trình con đ ể quay trở về chỗ có lời gọ i trong chương trìnhchính, khi kết thúc việc thự c hiện chương trình con đó, chính là loại đ ịa chỉ này. Cũng có mộ t số cấu trúc lưu trữ sử dụng phố i hợp cả hai cách xác đ ịnh địachỉ nói trên.2. Lưu trữ kế tiếp đối với mảng Thông thường mảng được lưu trữ trong máy dưới dạng mộ t vectơ, mà ngườita gọ i là vectơ lưu trữ. Đó là một dãy các từ máy kế tiếp nhau (vì vậy người ta gọ ilà lưu trữ kế tiếp - sequential storage allocation). Giả sử, ta xét việc lưu trữ kế tiếp đối với mảng 1 chiều, hay 1 vectơ A, màcác phần tử của nó là A[i] với 1≤i≤n. Nếu mỗi ph ần tử của vectơ đuợc lưu trữtrong một ô nh ớ gồm có một từ máy thì đ ể lưu trữ vectơ A, phải dành ra trong bộnhớ n từ máy kế tiếp nhau, đó chính là n phần tử củ a vectơ lưu trữ V : Phần tử V[i] của vectơ đang xét. Nếu mỗ i ph ần tử của vectơ lưu trũ V (mỗi ô nh ớ của V) phải gồm ω từ máymới chứa được một phần tử A[i] thì lúc đó V phải bao gồm n ∗ ω từ máy kế tiếp.Địa chỉ mỗi ô nh ớ, nghĩa là mỗi phần tử nhớ V[i] , bây giờ là đ ịa chỉ của từ máyđầu tiên củ a ô nhớ đó. Ví d ụ: Nếu ω = 3 mà đ ịa chỉ của V [1] là 1000 thì địa ch ỉcủa V[2] là 1003, của V[3] là 1006. V[1] V[2] V[3] V[n] V A[1] A[2] A[3] ……… A[n] ω Lo Hình 2.1 Địa chỉ củ a V[1] được gọi là địa chỉ g ốc (base address), ký hiệu là Lo. Như vậy việc xác đ ịnh đ ịa chỉ của V[i], hay nói một cách khác: Việc xácđịnh địa ch ỉ của A[i] sẽ được tính ra theo công thứ c: LOC (A[i] ) = Lo + ω ∗ ( i-1) Trong ngôn ngữ C , cận dưới củ a chỉ số không nh ất thiết phải là 1 mà có thểlà mộ t số n guyên b nào đó. Khi ấy địa ch ỉ của A[i] được tính b ởi: LOC (A[i] ) = Lo + ω ∗ ( i-b) Đối với mảng 2 chiều hay ma trận, việc lưu trữ các phần tử cũng được thựchiện bởi mộ t vectơ lưu trữ như trên. Gọi B là một ma trận có m hàng, n cột, B sẽ được lưu trữ trong bộ nh ớ bởivectơ lưu trữ V b ao gồm m∗n∗ω từ máy ( m ỗi phần tử củ a V gồm ω từ máy) Với ngôn ngữ PASCAL, nếu giả sử B có 3 hàng, 4 cộ t (m=3, n=4) thì cácphần tử của nó sẽ được lưu trữ như hình sau:V B11 B12 B13 B14 B21 B22 B23 B24 B31 B32 B33 B34 V[1] V[5] V[9] V[12] Phần tử ở hàng 1 Ph ần tử ở hàng 2 Phần tử ở h àng 3 Hình 2.2 Như ...