Dữ liệu kiểu mảng là gì là một trong những keyword được search nhiều nhất trên Google về chủ đề dữ liệu kiểu mảng là gì. Trong bài viết này, hoclamweb.vn sẽ viết bài viết Dữ liệu kiểu mảng là gì? Tại sao chúng ta lại sử dụng dữ liệu kiểu mảng?
Dữ liệu kiểu mảng là gì? Tại sao chúng ta lại sử dụng dữ liệu kiểu mảng?
I / định nghĩa :
II/ phương pháp khai báo mảng 1 chiều : Có hai cách khai báo :
TYPE Tên_Kiểu_Mảng = ARRAY[chỉ_số_đầu . . Chỉ_số_cuối] of Kiểu_Phần_tử ;
VAR Tên_biến_Mảng : Tên_Kiểu_Mảng ;
phương pháp 2 :
VAR Tên_biến_Mảng : ARRAY[chỉ_số_đầu . . Chỉ_số_cuối] of Kiểu_Phần_tử ;
lưu ý :
Khi truyền dữ liệu kiểu mảng vào trong chương trình con bắt buộc phải sử dụng phương pháp 1
III / mẹo khai báo mảng 2 chiều :
hướng dẫn 1 :
TYPE Tên_Kiểu_Mảng = ARRAY[m1 . . M2,n1 . . N2] of Kiểu_Phần_tử ;
VAR Tên_biến_Mảng : Tên_Kiểu_Mảng ;
hướng dẫn 2 :
VAR Tên_biến_Mảng : ARRAY[m1 . . M2,n1 . . N2] of Kiểu_Phần_tử ;
note : m1 là chỉ số thể loại đầu và m2 chỉ số dạng cuối
n1 là chỉ số cột đầu và n2 chỉ số cột cuối
IV / mẹo truy nhập Mảng
Kí hiệu mảng 2 chiều có M dạng ,N cột A(M,N) . Số phần tử là MxN Kí hiệu phần tử ở thể loại i ( 1 <= i <= M ) , cột j ( 1 <= j <= N ) của mảng là A[i,j] . Chỉ số i gọi là chỉ số loại , chỉ số j gọi là chỉ số cột . quan tâm chỉ số dòng viết trước.
Trong chương trình , A[i,j] có vai trò giống như một biến ,mang giá trị của ô nhớ tương ứng với phần tử ở dòngi , cột j của mảng . Vậy muốn truy nhập (lấy ra hoặc đặt lại ) trị giá của phần tử này chỉ cần truy nhập qua A[i,j] .
V / chuyển đổi mảng 2 chiều vào mảng 1 chiều :
B[k] := A[i,j] với không := (i – 1) * N + j ( 1<=i<=M ; 1<=j <= N )
VI / click thước của mảng :
+ cách 2 : click thước Mảng = click thước 1 phần tử * số lượng phần tử .
VII / chủ đề mảng và tự điển :
hình 1
1 2 3 4
8 7 6 5
ảnh 2
4 1 2 3
5 8 7 6
ảnh 3
4 8 1 3
5 7 2 6
rạch ròi có 8! = 40.320 Bảng giống như vậy . Bài toán đặt ra là :
Nếu xếp các ô cạnh nhau theo chiều mũi tên giống như trên hình vẽ sẽ được 1 số nguyên kiểu LongInt : 12345678 ( ảnh 1 ) hoặc 41236785 ( hình 2 ) hoặc 48136275 ( ảnh 3 ).Giá trị của số này gọi là trị giá của bảng .
Hãy sắp đặt 40.320 bảng này theo thứ tự tăng nghĩa là bố trí 40.320 số kiểu LongInt .Không thể sử dụng mảng có kiểu Array[1.. 40320] Of LongInt để lưu trữ các bảng này .
Vậy hướng khắc phục như thế nào ? Ta sẽ xây dựng 1 “Tự điển “ sắp xếp tăng các số này (nhưng không cần lưu trữ) .Mỗi số gọi là 1 từ trong tự điển .
Mỗi từ tạo thành giống như phương pháp trên có những đặc trưng gì ? Nếu lần lượt tạo các chữ số từ trái qua phải , chữ số ở vị trí thứ i ( 0<= i <= 8 ) có k*(8-i)! Số được tạo ra trước nó ; k là số các chữ số nhỏ hơn chữ số ở vị trí i mà chưa được dùng sử dụng các chữ số trước i . Vậy từ ở vị trí thứ i là 1 cặp số ( i,k) ,trong tự điển nó đứng ở vị trí thứ :
8
VT = ki * (8-i)! + 1 ( 1≪=i<=
i=1
Thí dụ Bảng nêu ở ảnh 1 có VT = 1 vì ki =0 trong cả 8 số hạng .
Bảng nêu ở hình 2 có VT = 3*7! + 3! + 2! + 1! + 1 = 5049 …
Vậy chỉ cần các mảng sau :
+ Mảng M có 8 phần tử kiểu Word chứa 8 trị giá (8-i)! ( 1≪= i <= 8 )
+ Mảng P để đánh dấu các chữ số nào đang được dùng đứng trước chữ số thứ i , suy ra không là số các chữ số nhỏ hơn i , vừa mới được dùng đứng trước chữ số thứ i
+ Mảng A có kiểu Array[1..8] of Byte để chứa 1 bảng .
Mỗi khi nhận được 1 bảng , ta có thể tìm được vị trí của nó trong tự điển , và ngược lại .
Uses Crt;
Const M : Array[0..7] of Word =(1,1,2,6,24,120,720,5040);
Type KX = Array[1..8] of Byte;
Var A : KX; i , j : Word;
Function Vitri(X : KX) : Word;
Var T : LongInt;
i,j : Byte;
D : KX;
Begin
T := 0;
FillChar(D,Sizeof(D),0);
For i:=1 to 8 do
Begin
For j:= X[i]-1 downto 1 do
If D[j]=0 then T := T + M[8-i];
D[X[i]] := 1;
End;
Vitri := T + 1;
End;
Procedure Timso(T : Word;Var X : KX);
Var i,j,k : Byte; D : KX;
Begin
FillChar(D,Sizeof(D),0);
Dec(T);
For i:=1 to 8 do
Begin
không := T div M[8-i] + 1 ; T := T mod M[8-i];
j := 0;
While (k>0) do
Begin
While D[j+1]=1 do Inc(j);
Inc(j);Dec(k);
End;
X[i] := j; D[j] := 1;
End;
End;
BEGIN
Clrscr;
For i:=1 lớn 8 do
Begin
Write(‘A[‘,i,’] = ‘);
Readln(A[i]);
End;
j := vitri(A);
Writeln(j);
Timso(j,A);
For i:=1 lớn 8 do Write(A[i]);
Readln
END.
VIII / Một số thao tác trên mảng :
1 ) Duyệt mảng :
a ) Đếm số phần tử thoả mãn 1 thuộc tính nào đó ( thường dùng 1 biến đếm ) .
b ) check các phần tử của mảng xem vừa mới được sử dụng vào một giai đoạn nào đó của bài toán chưa , phần tử nào đã được xem xét thì được đánh dấu bằng cách gán cho nó 1 trị giá đặc biệt .( Hoặc có thể dùng kèm theo 1 mảng phụ để đánh dấu ) .
c ) cải thiện lại trị giá của 1 số phần tử có tính chất chung .
d ) Tìm một dãy con các phần tử liên tiếp nhau thoả mãn 1 tính chất nào đó .
e ) Xoá bỏ một số phần tử ( Thường sử dụng kèm theo 1 mảng đánh dấu ) .
g ) Duyệt mảng cùng lúc dồn mảng sau khi xoá bỏ 1 số phần tử , hoặc chèn thêm vào 1 số phần tử .
h) xử lý trên mảng vòng ( Hai cách thức chính – Các bài tập 5,21,23.. Sẽ đề cập )
2 ) sắp đặt tăng trưởng , giảm :
+ BubbleSort
+ ShellSort
+ QuickSort
+ HeapSort
+ Đổi chỗ trực tiếp
a ) Bubble Sort Phương pháp nổi bọt
Uses Crt;
Const N = 10000;
Type M1 = Array[1..N] of Integer;
Var A : M1;
i,j,x : Integer;
Begin
Clrscr;
Randomize;
For i:=1 to N do A[i] := Random(10);
For i:=1 lớn N do Write(A[i]:4);
For i:=2 lớn N do
For j:=N downto i do
If A[j-1] > A[j] then
Begin
x := A[j-1];
A[j-1] := A[j];
A[j] := x;
End;
Writeln;
For i:=1 to N do Write(A[i]:4);
Readln;
End.
b ) Shell Sort Chèn trực tiếp với độ dài giảm dần , có biến đóng vai trò lính canh
Uses Crt;
Const N = 10000;
Type M1 = Array[1..N] of Integer;
M2 = Array[1..4] of Integer;
Var A : M1;
H : M2;
i,j,m,k,s,x : Integer;
Begin
Clrscr;
Randomize;
For i:=1 to N do A[i] := Random(10);
For i:=1 lớn N do Write(A[i]:4);
H[1] := 1; H[2] := 3; H[3] := 5; H[4] := 9;
For m := 1 lớn 4 do
Begin
không := H[m];
S := -k;
For i:=K+1 to N do
Begin
x := A[i];
j := i-k;
If s=0 then s := -k;
Inc(s);
A[s] := x;
While x Begin
A[j+k] := A[j];
Dec(j,k);
End;
A[j+k] := x;
End;
End;
For i:=1 lớn N do Write(A[i]:4);
Readln;
End.
c ) QuickSort
$S-
Uses Crt; Sắp xếp bằng phân hoạch
Const Max= 15000; Nếu sử dụng đệ qui , k dùng 2 mảng DP,CP , thì Max ->32000
Type Chiso = 1..Max;
đưa = Array[Chiso] of Integer;
Var A : Mang;
Procedure Taomang; Tạo ngẫu nhiên Mảng A(N)
Procedure QuickSort;
Var s,D,C,i,j : Word;
coc,x : Integer;
dP,cP : Array[Chiso] of Chiso;
Begin
s:=1;
dP[s]:=1;
cP[s]:=Max;
Repeat
D:=dP[s]; Chỉ số đầu của phân hoạch thứ s
C:=cP[s]; Chi số cuối của phân hoạch thứ s
Dec(s);
Repeat
i:=D;
j:=C;
x:= A[(D+C) div 2];
Repeat
While A[i] < x do inc(i);
While x < A[j] do dec(j);
If i<=j then
Begin
coc:=A[i]; A[i]:=A[j]; A[j]:=coc;
Inc(i);
Dec(j);
End;
Until i>j;
If i Begin
Inc(s);
dP[s]:=i;
cP[s]:=C;
End;
C:=j;
Until D>=C;
Until s=0;
End;
Procedure Hien(X : Mang); Hiện Mảng
BEGIN
Repeat
Clrscr;
Taomang;
QuickSort;
Hien(A);
Write(‘ESC to Quit.Press any key to Continue…’);
Until ReadKey=#27;
END.
d) MergeSort Đổi chỗ trực tiếp . Phương pháp này it dùng trên mảng vì tốn bộ nhớ
e ) HeapSort Phương pháp vun đống + Đệ qui sẽ học sau
3 )Tạo mảng vòng :
phương pháp 2 : Nhân đôi mảng
i chạy từ 1 đến N để tạo các điểm
bắt đầu không giống nhau của J
A(N) : 1 2 …….i ……….. ……………..N 1 2 3 ………..(i+N-1) ……………………2xN
J đi từ i tới i+N-1 là duyệt xong mảng A(N)
4 ) Biến định vị :
Thí dụ : Bài toán tìm dãy con dài nhất gồm các phần tử liên tiếp to hơn x :
( xem lời giải chi tiết ở trang 122 )
+ Chương trình sẽ sử dụng 1 biến i làm nghĩa vụ duyệt mảng , 4 biến định vị : đ,c,Lđ,Lc
Biến đ : chốt điểm đầu của dãy con mới xây dựng
Biến c : chốt điểm cuối của dãy con mới xây dựng
Biến Lđ : chốt điểm đầu của dãy con dài nhất trước dãy con mới thiết lập
Biến Lc : chốt điểm cuối của dãy con dài nhất trước dãy con mới thiết lập
+ Khởi trị : Đ := 1;C := 1; LĐ := 1; LC:=1;
+ Biến i duyệt mảng bắt đầu từ 1 ,
* Nếu A[i] > x thì C chốt tới giá trị i này, i liên tục tiến trình “thăm dò “ của mình , * Nếu A[i]<= x thì phải so sánh C-Đ với LC-LĐ .
-Nếu C-Đ > LC-LĐ thì dãy con mới thiết lập dài hơn nên LC nhận giá trị mới là C , LĐ nhận trị giá mới là Đ . đồng thời Đ và C lên giữ chốt mới là i, để khởi đầu thiết lập một dãy con không giống
-Nếu C-Đ < = LC-LĐ thì chỉ xảy ra Đ và C lên giữ chốt mới là i, để bắt đầu xây dựng một dãy con không giống