Cài đặt mạng và danh sách

Mảng và danh sách

Quang Hưng

Mảng là một tập có thứ tự gồm mộtsố cố định các phần tử. Không có phép bổ sung phần tử

hoặc loại bỏ phần tử đượcthực hiện đối với mảng. Thường chỉ có các phép tạo lập mảng,

tìm kiếm một phầntử của mảng, lưu trữ một phần tử của mảng. Ngoài giá trị, một phần tử

của mảngcòn được đặc trưng bởi chỉ số (index) thể hiện thứ tự của phần tử đó trongmảng.

Vector là mảng một chiều, mỗiphần tử ai của nó ứng với một chỉ số i. Ma trận là mảng hai

chiều, mỗi phần tửaij ứng với hai chỉ số i và j.

Tương tự, người ta mở rộng ra:mảng ba chiều,...,mảng n chiều.

Danh sách có hơi khác với mảng ởchỗ: nó là một tập hợp có thứ tự nhưng bao gồm một số

biến động các phần tử.Phép bổ sung và phép loại bỏ một phần tử là phép thường xuyên tác

động lên danhsách. Tập hợp các người đến khám bệnh cho ta hình ảnh một danh sách. Họ

sẽ đượckhám theo một thứ tự. Số người có lúc tăng lên (do có người mới đến), có lúcgiảm

đi (do bỏ về vì không chờ được). Một danh sách mà quan hệ lân cận giữa cácphần tử được

hiển thị ra thì được gọi là danh sách tuyến tính. Như vậy, danhsách tuyến tính là một danh

sách hoặc rỗng (không có phần tử nào) hoặc có dạng(a1, a2,..., an) với ai (1≤ i ≤ n) làcác

dữ liệu nguyên tử. Trong danh sách tuyến tính luôn tồn tại một phần tử đầu a1, phần tử

cuối an. Đối với mỗi phần tử ai bất kỳ với 1≤ i ≤ n-1 thì có một phần tử ai + 1 gọi là phần

tử sau của ai và với 2 ≤ i ≤ n thì có một phần tửai-1 gọi là phần tử trước ai. ai được gọi là

phần tử thư i của danh sách tuyến tính n, n được gọi là độ dài hoặc kích thước của danh

sách và nó có giá trị thay đổi.

Mỗi phần tử trong một danh sáchthường là một bản ghi (gồm một hoặc nhiều trường). Ví

dụ: danh mục điện thoạilà một danh sách tuyến tính, mỗi phần tử của nó ứng với một đơn

vị thuê bao, nógồm ba trường:

-Tên đơn vị hoặc tên chủ hộ thuêbao.

-Địa chỉ

-Số điện thoại

Mỗi một phần tử được xác địnhbằng địa chỉ của chúng trong bộ nhớ trong. Thường thì có

hai cách để xác địnhđược địa chỉ của một phần tử trong danh sách. Cách thứ nhất là dựa

vào nhữngđặc tả của dữ liệu cần tìm. Địa chỉ thuộc loại này được gọi là địa chỉ tínhđược

(computed ađress). Cách này thường hay được sử dụng trong các ngôn ngữlập trình để tính

địa chỉ các phần tử của vector, của ma trận để tính địa chỉlệnh thực hiện tiếp theo trong quá

trình thực hiện chương trình đích. Cách thứhai là lưu trữ các địa chỉ cần thiết đó ở một chỗ