tailieunhanh - 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. | Chươ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ú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 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ới và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ẳng hạn phần tử của vectơ A kí hiệu là Ai hoặ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ần tử 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 n chiều. II. CẤU TRÚC LƯU TRỮ CỦA MẢNG 1. 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ần tử 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 truy cậ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ực tiếp ra địa chỉ. Địa chỉ này được gọi là địa chỉ được tính computer address . Cách nà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 theo . Cách thứ hai là lưu trữ các địa chỉ cần thiết ở một chỗ qui