Bi 10: Mng v danh sỏch
10.1. Mng
10.1.1. Mng mt chiu, mng nhiu chiu
Khái niệm
Mng l mt tp hp cỏc phn t c nh cú cựng mt kiu, gi l kiu
phn t. Kiu phn t cú th l cú cỏc kiu bt k: ký t, s, chui ký t; cng
cú khi ta s dng kiu mng lm kiu phn t cho mt mng (trong trng h
p
ny ta gi l mng ca mng hay mng nhiu chiu).
Ta cú th chia mng lm 2 loi: mng 1 chiu v mng nhiu chiu.
Mng l kiu d liu c s dng rt thng xuyờn. Chng hn ngi ta
cn qun lý mt danh sỏch h v tờn ca khong 100 sinh viờn trong mt
lp. Nhn thy rng mi h v tờn lu tr ta cn 1 bin kiu chui, nh
vy 100 h v tờn thỡ cn khai bỏo 100 bin kiu chui. Nu khai bỏo nh
th ny thỡ on khai bỏo cng nh cỏc thao tỏc trờn cỏc h tờn s rt di
dũng v rc ri. Vỡ th, kiu d liu mng giỳp ớch ta trong trng hp
ny; ch cn khai bỏo 1 bin, bin ny cú th coi nh l tng ng vi
100 bin chui ký t; ú l 1 mng m cỏc phn t ca nú l chui ký t
Cấu trúc l-u trữ của mảng.
Cấu trúc dữ liệu đơn giản nhất dùng địa chỉ tính đ-ợc
để thực hiện l-u trữ và tìm kiếm phần tử, là mảng một
chiều hay véc tơ.
Thông th-ờng thì một số từ máy sẽ đ-ợc dành ra để
l-u trữ các phần tử của mảng. Cách l-u trữ này đ-ợc gọi
là cách
l-u trữ kế tiếp (sequential storage
allocation).
Tr-ờng hợp một mảng một chiều hay véc tơ có n phần
tử của nó có thể l-u trữ đ-ợc trong một từ máy thì cần
phải dành cho nó n từ máy kế tiếp nhau. Do kích th-ớc
1
. .
.
a
i
. .
.
a
n
f(i) = c * i gọi là hàm địa chỉ (address
function)
Đối với mảng nhiều chiều việc l-u trữ cũng t-ơng
tự nh- vậy nghĩa là vẫn sử dụng một véc tơ l-u trữ kế
tiếp nh- trên.
a
01
a
11
. .
.
a
ij
. .
.
a
nm
công thức tính địa chỉ nh- sau:
Loc(a
ij
) = L
0
+ (i - b
1
) * (u
2
- b
2
+ 1) + (j - b
2
)
vì mỗi hàng có (u
2
- b
2
+ 1) phần tử.
Ví dụ : Xét mảng ba chiều B có các phần tử b
ijk
với 1
i 2;
1 j 3; 1 k 4; đ-ợc l-u trữ theo thứ tự -u
tiên hàng thì các phần tử của nó sẽ đ-ợc sắp đặt kế
tiếp nh- sau:
b
111
, b
112
221
, b
222
, b
223
, b
224
, b
231
, b
232
, b
233
,
b
234
.
Công thức tính địa chỉ sẽ là :
Loc(a
ijk
) = L
0
+ (i - 1) *12 + (j - 1) * 4 + (k - 1)
VD Loc(b
223
) = L
0
+ 22.
Xét tr-ờng hợp tổng quát với mảng A n chiều mà các
i
)
với p
i
= (u
k
- b
k
+1)
đặc biệt p
n
= 1.
Chú ý :
n
n
k =i + 1
i = 1
1>
Khi mảng đ-ợc l-u trữ kế tiếp thì việc truy
nhập vào phần tử của mảng đ-ợc thực hiện trực
tiếp dựa vào địa chỉ tính đ-ợc nên tốc độ nhanh
và đồng đều đối với mọi phần tử.
2>
Mặc dầu có rất nhiều ứng dụng ở đó mảng có thể
x,y chỉ xử lý đ-ợc với đa thức bậc n-1 thôi.
VD : Với x
2
+ 4xy - y
2
+2x thì ta sẽ sử dụng ma
trận 5 ì 5 biểu diễn nó sẽ có dạng:
10.1.2. Cu trỳc lu tr mng trờn mt s ngụn ng lp trỡnh
I. GII THIU KIU D LIU KIU MNG TRONG C
. Hay nh lu tr cỏc t khúa ca ngụn ng lp trỡnh C, ta cng dựng
n mt mng lu tr chỳng.
Vớ d 1: Vit chng trỡnh cho phộp nhp 2 ma trn a, b cú m dũng n ct,
thc hin phộp toỏn cng hai ma trn a,b v in ma trn kt qu lờn mn hỡnh.
Trong vớ d ny, ta s s dng hm lm ngn gn hn chng trỡnh ca
ta. Ta s vit cỏc hm: nhp 1 ma trn t bn phớm, hin th ma trn lờn mn hỡnh,
cng 2 ma trn.
0
1
2
3
int i,j;
for(i=0;i<M;i++)
for(j=0; j<N; j++)
c[i][j]=a[i][j]+b[i][j];
}
int main()
{
int a[10][10], b[10][10], M, N;
int c[10][10];/* Ma tran tong*/
printf("So dong M= "); scanf("%d",&M);
printf("So cot M= "); scanf("%d",&N);
printf("Nhap ma tran A\n");
Nhap(a,M,N);
printf("Nhap ma tran B\n");
Nhap(b,M,N);
printf("Ma tran A: \n");
InMaTran(a,M,N);
printf("Ma tran B: \n");
InMaTran(b,M,N);
CongMaTran(a,b,M,N,c);
printf("Ma tran tong C:\n");
InMaTran(c,M,N);
getch();
return 0;
} Mảng trong C#
Array là một cấu trúc dữ liệu cấu tạo bởi một số biến được gọi là những phần tử
mảng. Tất cả các phần tử này đều thuộc một kiểu dữ liệu. Bạn có thể truy xuất
Làm việc với mảng (Working with Arrays) Ta có thể tìm được chiều dài của mảng sau nhờ vào thuộc tính Length thí dụ sau :
int arrayLength = integers.Length
Nếu các thành phần của mảng là kiểu định nghĩa trước (predefined types), ta có
thể sắp xếp tăng dần vào phương thức gọi là static Array.Sort() method:
Array.Sort(myArray);
Cuối cùng chúng ta có thể đảo ngược mảng đã có nhờ vào the static Reverse()
method:
Array.Reverse(myArray);
string[] artists = {"Leonardo", "Monet", "Van Gogh", "Klee"};
Array.Sort(artists);
Array.Reverse(artists);
foreach (string name in artists)
{
Console.WriteLine(name);
}
Mảng nhiều chiều (Multidimensional Arrays in C#)
Cú pháp :
type[,] array-name;
này phải đuợc khai báo từng mảng con một.
Thí dụ sau đây khai báo một mảng jagged hai chiều nghĩa là hai cặp [], gồm 3
hàng mỗi hàng là một mảng một chiều:
int[][] a = new int[3][];
a[0] = new int[4];
a[1] = new int[3];
a[2] = new int[1];
Khi dùng mảng jagged ta nên sử dụng phương thức GetLength() để xác định số
lượng cột của mảng. Thí dụ sau nói lên điều này:
using System;
namespace Wrox.ProCSharp.Basics
{
class MainEntryPoint
{
static void Main()
{
// Declare a two-dimension jagged array of authors' names
string[][] novelists = new string[3][];
novelists[0] = new string[] {
"Fyodor", "Mikhailovich", "Dostoyevsky"};
novelists[1] = new string[] {
"James", "Augustine", "Aloysius", "Joyce"};
novelists[2] = new string[] {
"Miguel", "de Cervantes", "Saavedra"};
10.2. Danh sỏch
10.2.1. Khỏi nim danh sỏch tuyn tớnh
Danh sách 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ử (x
1
, x
2
, . . ., x
n
)
nếu n = 0 ta có một danh sách rỗng.
Một danh sách mà quan hệ lân cận đ-ợc hiển thị gọi
là danh sách tuyến tính (linear list).
VD: Véc tơ chính là một tr-ờng hợp đặc biệt của danh
sách tuyến tính xét tại một thời điểm nào đấy.
Danh sá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 (a
1
, a
2
, . . ., a
n
)
với a
i
(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 a
1
, phần
tử cuối a
+ Phép ghép nối 2 hoặc nhiều danh sách.
+ Phép tách một danh sách thành nhiều danh sách.
+ Phép sao chép một danh sách.
+ Phép cập nhật (update) danh sách.
+ Phép sắp xếp các phần tử trong danh sách theo
thứ tự ấn định.
+ Phép tìm kiếm một phần tử trong danh sách theo
giá trị ấn định của một tr-ờng nào đó.
Trong đó phép bổ sung và phép loại bỏ là hai phép
toán th-ờng xuyên đ-ợc sử dụng trong danh sách.
Tệp cũng là một tr-ờng hợp của danh sách nó có
kích th-ớc lớn và th-ờng đ-ợc l-u trữ ở bộ nhớ ngoài.
Còn danh sách nói chung th-ờng đ-ợc xử lý ở bộ nhớ
trong.
Bộ nhớ trong đ-ợc hình dung nh- một dãy các từ
máy(words) có thứ tự, mỗi từ máy ứng với một địa chỉ.
Mỗi từ máy chứa từ 8 ữ 64 bits, việc tham khảo đến nội
dung của nó thông qua địa chỉ.
+ Cách xác định địa chỉ của một phần tử trong danh
sách: Có 2 cách xác định địa chỉ:
Cách 1: Dựa vào đặc tả của dữ liệu cần tìm . Địa
chỉ này gọi là địa chỉ tính đ-ợc (hay địa chỉ trực
tiếp).
VD: Xác định địa chỉ của các phần tử trong véc tơ,
ma trận thông qua các chỉ số.
Cách 2: L-u trữ các địa chỉ cần thiết ở trong bộ
nhớ, khi cần xác định sẽ lấy ở đó ra. Địa chỉ này đ-ợc
gọi là con trỏ (pointer) hay mối nối (link).
L-u trữ kế tiếp của danh sách tuyến tính.
Vi cỏc cu trỳc d liu c xõy dng t cỏc kiu c s nh: kiu thc, kiu
nguyờn, kiu ký t ... hoc t cỏc cu trỳc n gin nh mu tin, tp hp, mng ...
lp trỡnh viờn cú th gii quyt hu ht cỏc bi toỏn t ra. Cỏc i tng d li
u
c xỏc nh thuc nhng kiu d liu ny cú c im chung l khụng thay i
c kớch thc, cu trỳc trong quỏ trỡnh sng, do vy thng cng ngt, gũ bú
khin ụi khi khú din t c thc t vn sinh ng, phong phỳ. Cỏc kiu d liu
k trờn c gi l cỏc kiu d liu tnh.
Vớ d :
1. Trong thc t, mt s i tng cú th c
nh ngha qui, vớ d
mụ t i tng "con ngi" cn th hin cỏc thụng tin ti thiu nh :
H tờn
S CMND
Thụng tin v cha, m
é biu din mt i tng cú nhiu thnh phn thụng tin nh trờn cú th
s dng kiu bn ghi. Tuy nhiờn, cn lu ý cha, m ca mt ngi cng l
các đối tượng kiểu NGƯỜI, do vậy về nguyên tắc cần phải có định nghĩa
như sau:
typedef struct NGUOI{
char Hoten[30];
int So_CMND ;
NGUOI Cha,Me;
};
Nhưng với khai báo trên, các ngôn ngữ lập trình gặp khó khăn trong việc
cài đặt không vượt qua được như xác định kích thước của đối tượng kiểu
NGUOI.
2. Một số đối tượng dữ liệu trong chu kỳ sống của nó có thể thay đổi về
cấu trúc, độ lớn, như
danh sách các học viên trong một lớp học có thể tăng
1. Khởi tạo Stack
2. Thêm các phần tử vào Stack
3. Lấy các phần tử ra khỏi Stack
4. Thoát
Bài 2.
Hãy viết một chương trình hoàn chỉnh có menu cho người sử dụng để minh họa
các thuật toán sau:
1. Khởi tạo Queue
2. Thêm các phần tử vào Queue
3. Lấy các phần tử ra khỏi Queue
4. Thoát
Bài 3.
Dùng Stack để viết chương trình chuy
ển đổi một số từ hệ cơ số 10 sang hệ
cơ số nguyên a (0<a<10).
Bài 4.
Mô phỏng việc tạo buffer in một file ra máy in.
Buffer xem như là một hàng, khi ra lệnh in file máy tính sẽ thực hiện một cách lặp
quá trình sau cho đến hết file:
¾ Ðưa nội dung của tập tin vào buffer cho đến khi buffer đầy hoặc hết file.
¾ In nội dung trong buffer ra máy in cho tới khi hàng rỗng.
Hãy mô phỏng quá trình trên để in một file văn bản lên từng trang màn hình.
Bài 16: Danh sách nối kép (Double Linked List)
16.1. Định nghĩa và nguyên tắc tổ chức DS nối kép
Một số ứng dụng đòi hỏi chúng ta phải duyệt danh sách theo cả hai chiều một
cách hiệu quả. Chẳng hạn cho phần tử X cần biết ngay phần tử trước X và sau X
một cách mau chóng. Trong trường hợp này ta phải dùng hai con trỏ, một con trỏ
chỉ đến phần tử đứng sau (next), một con trỏ chỉ đến phần t
hơi khác với danh sách liên đơn. Trong cách cài đặt này, chúng ta không sử dụng ô
đầu mục như danh sách liên kết đơn mà sẽ quản lý danh sách một các trực tiếp
(header chỉ
ngay đến ô đầu tiên trong danh sách).
16.2. Các phép toán thao tác trên danh sách nối kép
Tạo danh sách liên kết kép rỗng
Giả sử DL là con trỏ quản lí danh sách liên kết kép thì khi khởi tạo danh sách rỗng
ta cho con trỏ này trỏ NULL (không cấp phát ô nhớ cho DL), tức là gán
DL=NULL.
void MakeNull_List (DoubleList *DL){
(*DL)= NULL;
}
Kiểm tra danh sách liên kết kép rỗng
Rõ ràng, danh sách liên kết kép rỗng khi và chỉ khi chỉ điểm đầu danh sách
không trỏ tới một ô xác định nào cả. Do đó ta sẽ kiểm tra DL = NULL.
int Empty (DoubleList DL){
return (DL==NULL);
}
Xóa một phần t
ử ra khỏi danh sách liên kết kép
Để xoá một phần tử tại vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta
phải chú ý đến các trường hợp sau:
- Danh sách rỗng, tức là DL=NULL: chương trình con dừng.
- Trường hợp danh sách khác rỗng, tức là DL!=NULL, ta phải phân biệt hai
trường hợp
Ô bị xoá không phải là ô được trỏ bởi DL, ta chỉ cần cập nhật lại các con
trỏ để nối kết ô trước p với ô sau p, các thao tác c
DL, ta cũng cần phân biệt mấy trường hợp sau:
Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm
đến giá trị của p. Để thêm một phầ
n tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá
trị x vào trường Element của ô nhớ này và cho hai con trỏ previous, next trỏ tới
NULL còn DL trỏ vào ô nhớ này, các thao tác trên có thể viết như sau:
DL=(Node*)malloc(sizeof(Node));
DL->Element = x;
DL->Previous=NULL;
DL->Next =NULL;
Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình 16.3
Copyright: Tài liệu đại học ©