Mảng và danh sách

Trong khóa học java này sẽ có các phần chính như sau:

Mảng(array) và danh sách(list)
Cây
stack và queue

1.Các khái niệm:

1.Mảng(array) là tập có thứ tự, các phần tử cố định.
Các phép thực hiện trên mảng:

• Tạo lập(creat) mảng
• Tìm kiếm mảng
• Cập nhật 1 phần tử mảng

Trong mảng không có phép bổ sung và loại bỏ phần tử.
Mỗi phần tử trong mảng được đặc trưng bởi một chỉ số thể hiện vị trí của phần tử đó trong mảng.

2. Danh sách(líst) tập có thứ tự, phần tử biến động.

Các phép thực hiện trên danh sách rất nhiều:

• Bổ sung và loại bỏ phần tử.
• ghép
• Tách
• Sao chép
• Cập nhật
• Sắp xếp
• Tìm kiếm

Phần tử trong danh sách gồm 1 hoặc nhiều trường(fields)
MÌnh để mình nói về bộ nhớ trong cho các bạn dễhình dung vì noi về cấu trúc dữ liệu sẽ đề cập đến nhiều bộ nhớ trong, bộ nhớ trong coi chúng là các từ máy liên tiếp, mỗi từ máy(word) gồm 8-64 bit và mỗi từ máy đề có địa chỉ riêng biệt. Muốn xác định địa chỉ của các từ máy chúng ta dùng con trỏ.

3.Cách lưu trữ của mảng:

Cách lưu trữ đơn giản nhất là ta dùng cách lưu trữ kế tiếp:
nếu mảng A có n phần tử mà mỗi phần tử ai (1< i < n) chiếm x từ máy thì ta cần xn từ máy kế tiếp để lưu trữ mảng A
Địa chỉ của phần tử ai sẽ đc tính theo công thức:
Loc(ai) = L0 + x*(i-1)
với L0 là địa chỉ của từ máy đầu tiên trong miền nhớ dành cho vector A . Nếu b < i < n thì trong ngoặc sẽ là i-b
Đối với mảng nhiều chiều thì ta cũng dùng lưu trữ kế tiếp dành cho mảng, có hai kiểu lưu trữ:
Lưu trữ theo cột:

• Cấc phần tử sẽ ưu tiên theo côt, thứ tự sẽ là a11 a21 a31..., xong cột thứ nhất sang đến cột thứ 2 a21,a22,a23...
• ta có công thưc tính vị trí của phần tư aij cuả mảng n hàng m cột:Loc(aij) = L0 + x*((j-1)*n+(i-1))

Lưu trữ theo hàng: ta sẽ lưu trữ hết hàng này đến hàng khác

• Loc(aij) = L0 + x*((i-1)*m+(j-1))

Tổng quát lên ta có:

mảng n chiều A[a1,a2...an] với bi<ai<ci(i=1,2,3....n), và xét theo thứ tự ưu tiên hàng ta có địa chỉ của mỗi phần tử mảng đc tính bởi công thức sauvới x là số từ máy:
n n
Loc(A[a1,a2..an]) =L0+(∑pi(bi-ci) với pi=π (bk-ck+1))*x
i=1 k=i+1 

• Cách lưu trữ kế tiếp cho ta tốc độ truy cập, tìm kiếm rất nhanh và đồng đều với mọi phần tử
• Lưu trữ này dẫn đến nhiều trường hợp rất phí bộ nhớ, và bị giớ hạn khi lưu trữ.

Với danh sách tuyến tính hay biến đổi việc lưu trữ này rất khó khăn khi phải dồn dã liên tục bộ nhớ nếu không sẽ phí tổn không gian, với danh sách tuyến tính ta sẽ xét các lưu trữ khác.

4.Lưu trữ móc nối:

Ý tưởng của việc lưu trữ móc nối là thế này: mỗi phần tử của danh sách được chứa trong một số từ máy kế tiếp ta chia làm 2 phần:

1. info: chứa thông tin của phần tử
2. link: chứa vị trí của phần tử kế tiếp.

ở cuối danh sách không còn phần tử tiếp theo thì phần link sẽ là không có gì.
Ta sẽ có một con trỏ L trỏ vào phần tử đầu tiên đánh dấu vị trí đó, nếu L=null thì danh sách sẽ là rỗng.
Dưới đây ta sẽ thực hiện 2 phép toán bổ sung và loại bỏ với danh sách nối đơn trên.
L là vị trí của phần tử đầu danh sách, M là vị trí của một phần tử bất kì
Ý tưởng của phép bổ sung danh sách 1 phần tử A vào vị trí sau M: link(M) sẽ chỉ vào A tức là ta gán A vào link M: link(M)=A, còn link(A) sẽ phải chỉ vào phần tử sau phần tử M tức là link(A)=link(M)
thuật toán sau đây sẽ làm rõ vấn đề:
if L=null then
L=A
link(A)=null
end
else link(A)=link(M)
link(M)=A (đổi thứ tự câu lệnh thì se phải thêm biến trung gian để lưu giá trị của link(M))
end
Với phép loại bỏ phần tử M thì ý tưởng sẽ là tìm đến ptu trước M vd là phần tử A thì ta sẽ gán link(A)=link(M) và có một phép riêng biệt loại bỏ phần tử gọi là dispose(M)(mình tạm thời không đề cập ở đây)
if L=null then
returrn
else
A=L
while(link(A) # M) do A= link(A) (A sẽ băng phần tử đc trỏ băng link( A)) (tìm phần tử trước M)
Link(A)=link(M)
call dispose(M)(loại bỏ M)

Bài tập:

1. Viết thuật toán ghép 2 danh sách nối đơn, mình gợi ý tìm đến nút cuối của một danh sách A sau đó link của nút này sẽ chỉ vào Phần tử đầu của nút B.Nhớ xét đầy đủ các trường hợp.
2.vecto là mảng 1 chiều, vậy phân biệt giữa vector và danh sách tuyến tính như thế nào?
3. Cho mảng A=Aijk với -2<i<7, -7<j<3, 2<k<9 tính địa chỉ A[3,7,4] biết rằng mảng được lưu trữ theo thứ tự ưu tiên hàng và địa chỉ của từ máy đầu tiên là 300, mỗi phần tử chiếm 2 từ máy.
4.Một vấn đề của lưu trữ kế tiếp là tốn bộ nhớ. Ta có một ma trận vuông có phần tử của đường chéo chính và phần tử của 2 đường chéo sát đường chéo chính là khác 0 giống như ma trận ở hình dưới.
 

Để tiết kiệm ta sẽ lưu trữ các phần tử khác không này theo thứ tự ưu tiên hàng A[1;1] lưu tại B[1] A[1,2] lưu tại B[2] ,A[2,1] lưu tại B [3]......Lập giải thuật xác định đc giá trị A[i;j] từ B khi biết i,j ví dụ i=1, j=1 thì A[1;1] đc xác định qua B[1] vậy A[i;j] thì xác định qua vto B[?].