Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương III: Mảng và Danh sách

Cấu trúc dữ liệu và Giải thuật

Chương III: Mảng và Danh sách

Mảng và Danh sách

Nội dung

– Cấu trúc dữ liệu Mảng

z Lưu trữ Mảng 1 chiều

z Lưu trữ Mảng 2 chiều

z Các phép toán trên cấu trúc Mảng

– Danh sách tuyến tính

z Lưu trữ kế tiếp

z Lưu trữ móc nối

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

1

Cấu trúc dữ liệu và Giải thuật

Kiểu dữ liệu trừu tượng Mảng

z Đối tượng của Mảng:

– Một tập các cặp (index, item)

– Với mỗi giá trị của index sẽ có một giá trị tương ứng

của item.

– Index là một tập có thứ tự có một chiều hoặc nhiều

chiều

z Index 1 chiều : {0, 1, 2, …, n-1}

z Index 2 chiều : {(0,0) , (0,1), (0,2), …,(0,n), (1,0), (1,1) ….}

Kiểu dữ liệu trừu tượng Mảng

z Các phép toán

– Create(j, list) : tạo mảng có j chiều, list là một j-bộ với

phần tử thứ k của list là kích thước chiều thứ k của

mảng.

– Retrieve(A,i) : Trả ra giá trị của phần tử nhận chỉ số i

nếu có

– Store(A,i,x) : Trả ra một mảng giống như mảng A đã

cho ban đầu, chỉ khác là một cặp (i,x) đã được bổ

sung vào vị trí đúng

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

2

Cấu trúc dữ liệu và Giải thuật

Cấu trúc dữ liệu Mảng

z Mảng là dãy các phần tử được đánh chỉ số

z Khi cài đặt trong máy tính, mảng được lưu trữ

trong một dãy các ô nhớ liên tiếp trong bộ nhớ

z Kích thước của mảng được xác định khi khởi tạo

và không thay đổi

z Mỗi phần tử trong mảng có một chỉ số xác định

z Truy xuất vào các phần tử của mảng sử dụng chỉ

số của phần tử

Mảng trong các ngôn ngữ lập trình

– Tập chỉ số của mảng có thể khác nhau

z C, Java : chỉ số là số nguyên, liên tục, bắt đầu từ 0

z Pascal : chỉ số có thể có giá trị rời rạc

z Perl: cho phép chỉ số không phải là số

– Mảng có thể là thuần nhất hoặc không thuần nhất

– Mảng có thể có thêm các thông tin bổ sung ngoài các

phần tử

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

3

Cấu trúc dữ liệu và Giải thuật

Mảng 1 chiều

– Khởi tạo

z Cần chỉ ra số phần tử của mảng

z Khai báo mảng trong C:

<kiểu dữ liệu của phần tử ><tên biến>[size]

– int list[5];

– char word[25];

– Tham chiếu

z Các phần tử trong mảng 1 chiều được tham chiếu đến sử

dụng địa chỉ được tính

– int list [5] Æ

list[0]

list[1]

list[2]

list[3]

list[4]

địa chỉ cơ sở = α

α + sizeof(int)

α + 2*sizeof(int)

α + 3*sizeof(int)

α + 4*sizeof(int)

Mảng 1 chiều

int list[] = {0, 1, 2, 3, 4};

int *ptr; int rows = 5;

int i; ptr = list;

Address

Value

1228

1230

1232

1234

1236

0

1

2

3

4

printf(“Address Value\n”);

for (i=0; i < rows; i++)

printf(“%8u%5d\n”, ptr+i, *(ptr+i));

printf(“\n”);

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

4

Cấu trúc dữ liệu và Giải thuật

Mảng 2 chiều

– Khai báo

z Cần chỉ ra số hàng, số cột

z Trong C : <kiểu phần tử> <tên biến> [size1] [size2]

– int table[4][5];

z Truy xuất một phần tử

– table[i][j]

– Lưu trữ mảng 2 chiều trong bộ nhớ máy tính

z Theo thứ tự ưu tiên hàng

z Theo thứ tự ưu tiên cột

Mảng 2 chiều

– Lưu trữ mảng 2 chiều theo thứ tự ưu tiên hàng

a₀₀

a₁₀

a₂₀

a₃₀

a₀₁

a₁₁

a₂₁

a₃₁

a₀₂

a₁₂

a₂₂

a₃₂

Từ mảng 2 chiều lưu trữ

sang bộ nhớ kế tiếp sử dụng

thứ tự ưu tiên hàng

a₀₀

a₀₁

a₀₂

a₁₀

a₁₁

a₁₂

a₂₀

a₂₁

a₂₂

a₃₀

a₃₁

a₃₂

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

5

Cấu trúc dữ liệu và Giải thuật

Mảng 2 chiều

– Lưu trữ mảng 2 chiều theo thứ tự ưu tiên cột

a₀₀

a₁₀

a₂₀

a₃₀

a₀₁

a₁₁

a₂₁

a₃₁

a₀₂

a₁₂

a₂₂

a₃₂

Từ mảng 2 chiều lưu trữ

sang bộ nhớ kế tiếp sử dụng

thứ tự ưu tiên cột

a₀₀

a₁₀

a₂₀

a₃₀

a₀₁

a₁₁

a₂₁

a₃₁

a₀₂

a₁₂

a₂₂

a₃₂

Danh sách tuyến tính

– Danh sách là một tập hợp có thứ tự gồm một số biến

động các phần tử cùng kiểu {a₁, a₂, …., a_n-1, a_n}

– a_ilà phần tử ở vị trí i trong danh sách

– a₁là phần tử đầu tiên, a_nlà phần tử cuối cùng của

danh sách

– n là độ dài của danh sách tại 1 thời điểm

– Trường hợp n =0 ta có danh sách rỗng

– Trong danh sách tuyến tính, thứ tự trước sau của các

phần tử được xác định rõ ràng.

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

6

Cấu trúc dữ liệu và Giải thuật

Các cách cài đặt danh sách tuyến tính

– Dùng Mảng:

z Lưu trữ các phần tử của danh sách trong một vector lưu trữ

bao gồm các ô nhớ liên tiếp

– Dùng Con trỏ:

z Các phần tử được lưu trữ trong các ô nhớ ở các vị trí tùy ý

trong bộ nhớ

z Các phần tử liên kết với nhau bằng con trỏ

– Dùng địa chỉ gián tiếp

z Các phần tử được lưu trữ trong các ô nhớ ở các vị trí tùy ý

trong bộ nhớ

z Có một mảng địa chỉ trong đó phần tử thứ i của mảng chứa

địa chỉ của phần tử thứ i trong danh sách

Lưu trữ kế tiếp đối với danh sách

– Danh sách lưu trữ trong một phần bộ nhớ bao gồm

các ô nhớ liên tiếp

z Các phần tử liền kề nhau được lưu trữ trong những ô nhớ

liền kề nhau

z Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ

tự được lưu trữ trong vector

z Có một chỉ số last dùng để xác định chỉ số của phần tử cuối

cùng trong danh sách

A

max

1 2 3

last

i

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

7

Cấu trúc dữ liệu và Giải thuật

Lưu trữ kế tiếp đối với danh sách

– Khai báo danh sách sử dụng lưu trữ kế tiếp trong C

#define max 100

typedef etype integer

typedef struct LIST{

etype elements[max];

int last;

} LISTTYPE

Lưu trữ kế tiếp đối với danh sách

– Ưu điểm của cách lưu trữ kế tiếp

z Tốc độ truy cập vào các phần tử của danh sách nhanh

– Nhược điểm của cách lưu trữ kế tiếp

z Cần phải biết trước kích thước tối đa của danh sách

– Tại sao?

z Thực hiện các phép toán bổ sung các phần tử mới và loại bỏ

các phần tử cũ khá tốn kém

– Tại sao?

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

8

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách kế tiếp

– Bổ sung một phần tử vào vị trí p trong danh sách

A

3

1 2

last

p

A

1 2 3

x

p

Các thao tác trên danh sách kế tiếp

Procedure INSERT-LIST(L, x, p)

Begin

{ L là danh sách được lưu trữ dưới dạng mảng, x là giá trị phần tử mới, p là vị trí

phần tử mới, L có số tối đa là max phần tử , last là chỉ số phần tử cuối cùng trong

danh sách }

1. {Danh sách đã đầy} if (last > max) then ERROR;

2. {Kiểm tra giái trị p} else if (p > last ) OR (p < 1) then ERROR;

3. else

begin {Dịch chuyển các phần tử, tạo ô trống để bổ sung}

for i = last down to p do L[i+1] = L[i];

{Lưu giá trị mới vào vị trí p} L[p] = x;

last = last+1; {Số lượng phần tử trong danh sách tăng thêm 1}

end.

End

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

9

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách kế tiếp

– Loại bỏ một phần tử trong danh sách

A

x

p

1 2 3

last

1

3

p

2

A

1 2 3

last

p

Các thao tác trên danh sách kế tiếp

Procedure DELETE-LIST(L, p)

Begin

{ Loại bỏ phần tử ở vị trí p trong danh sách kế tiếp L.

L có tối đa max phần tử , hiện tại phần tử cuối cùng ở vị trí last}

1. {Kiểm tra p} if (p > last ) OR (p <1) then ERROR;

2. {Dồn các phần tử ở đuôi danh sách lên trên 1 vị trí}

for i:= p to last-1 do

S[i] := S[i+1];

last:= last-1;

3. End.

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

10

Cấu trúc dữ liệu và Giải thuật

Lưu trữ móc nối đối với danh sách

z Danh sách móc nối đơn ( Singly Linked-List)

– Một phần tử trong danh sách = một nút

– Một nút có hai thành phần

z INFO: chứa thông tin (nội dung, giá trị) ứng với phần tử

z NEXT: chứa địa chỉ của nút tiếp theo

– Để thao tác được trên danh sách, cần nắm được địa chỉ của

nút đầu tiên trong danh sách Ù biết được con trỏ L trỏ tới đầu

danh sách

Danh sách móc nối đơn

Hình ảnh danh sách móc nối đơn

L

e1

e2

e3

e4

e5

NIL

Ví dụ danh sách móc nối đơn

Data 4320

Structure 2000

And 1000

Algorithm 3000

Course

5000

Địa chỉ bộ nhớ của các phần tử tiếp theo

Địa chỉ nút đầu

danh sách

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

11

Cấu trúc dữ liệu và Giải thuật

Danh sách móc nối đơn

z Danh sách rỗng là danh sách không có chứa nút nào, lúc

đó L = NULL

z Tham chiếu đến các thành phần của một nút có địa chỉ p

(trỏ bởi con trỏ p)

– INFO(p): Tham chiếu vào giá trị

z INFO(p) = 234 ÅÆ giá trị dữ liệu lưu trữ tại nút trỏ bởi

p là 234;

– NEXT(p)

z NEXT(p) = 234 ÅÆ Ô nhớ chứa phần tử sau nút trỏ

bởi p có địa chỉ là 234

z Cấp phát một nút trống sẽ được trỏ bởi p

Câu lệnh trong giả ngôn ngữ : call New(p)

z Thu hồi một nút trỏ bởi p

Câu lệnh trong giả ngôn ngữ: call Dispose(p)

Danh sách móc nối đơn

– Khai báo trong ngôn ngữ C

typedef <kiểu dữ liệu của phần tử> element_type;

struct node{

element_type info;

struct node * next;

} ;

typedef struct node LISTNODE;

typedef LISTNODE *LISTNODEPTR;

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

12

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách nối đơn

z Duyệt danh sách nối đơn:

.

Procedure TRAVERSE(L)

{Đầu vào của giải thuật là một LISTNODEPTR L}

Begin

p:= L;

while p <> NULL do

begin

writeln(INFO(p));

p:= NEXT(p);

end;

End

Các thao tác trên danh sách nối đơn

– Bổ sung một phần tử mới vào danh sách

z Hãy bổ sung thêm một nút mới có thông tin là X vào sau

một nút trong danh sách được trỏ tới bởi con trỏ P

P

L

B

C

G

H

P

L

C

G

B

H

X

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

13

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách nối đơn

– Bổ sung một phần tử mới vào danh sách

Procedure INSERT(L, X, P)

Begin

1. { Tạo nút mới chứa giá trị X, được trỏ đến bới con trỏ Temp}

Call New(Temp) ;

INFO(Temp) = X;

2. { Gắn nút mới vào vị trí cần chèn}

NEXT(Temp) = NEXT(P);

NEXT(P) = Temp;

End

Các thao tác trên danh sách nối đơn

Sau khi khởi tạo nút mới và gán giá trị cho phần tử mới

P

L

B

C

G

H

X

Temp

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

14

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách nối đơn

Sau khi thực hiện NEXT(Temp) = NEXT(P);

NEXT(P)

P

L

B

C

G

H

X

Temp

Các thao tác trên danh sách nối đơn

Sau khi thực hiện NEXT(P) = Temp;

P

L

B

C

G

H

X

Temp

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

15

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách nối đơn

– Loại bỏ nút xác định trước:

z Hãy loại bỏ nút đằng sau nút trỏ bởi con trỏ P cho trước

P

L

B

C

G

H

P

L

C

G

B

H

Các thao tác trên danh sách nối đơn

Procedure DELETE(L, p)

Begin

{Trường hợp tổng quát}

1. Temp = NEXT(p) ;

2. Next(p) = Next(Temp);

3. call Dispose(Temp);

End.

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

16

Cấu trúc dữ liệu và Giải thuật

Minh họa thao tác trong NNLT C

– Cho một danh sách chứa các số nguyên, được sắp

xếp theo chiều tăng dần

z Viết đoạn chương trình C thực hiện bổ sung một nút mới có

giá trị x cho trước vào danh sách

z Viết đoạn chương trình C thực hiện việc loại bỏ một nút có

giá trị biết trước

Minh họa thao tác trong NNLT C

– Khai báo danh sách

struct node{

int info;

struct node * next;

} ;

typedef struct node LISTNODE;

typedef LISTNODE *LISTNODEPTR;

void insert(LISTNODEPTR *, int );

int delete(LISTNODEPTR *, int);

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

17

Cấu trúc dữ liệu và Giải thuật

void INSERT_ORDER( LISTNODEPTR *startPtr, int value){

/* Chương trình bổ sung một nút vào danh sách có sắp xếp theo chiều tăng dần

của giá trị các phần tử */

LISTNODEPTR temp, current, previous ;

temp = malloc(sizeof(LISTNODE));

if (temp!= NULL) {

1.

temp->info = value; temp->next = NULL;

previous = NULL; current = *startPtr;

while (current != NULL && value >current->info) {

previous = current; current = current->next;

}

2.

3.

4.

if (previous = NULL) {

temp->next = *startPtr;

*startPtr = temp;

}

else { previous->next = temp; temp->next = current; }

}

int DELETE_ORDER( LISTNODEPTR *startPtr, int value){

/* Chương trình bổ sung một nút vào danh sách có sắp xếp theo chiều tăng dần

của giá trị các phần tử */

LISTNODEPTR temp, current, previous ;

if (value == (* startPtr) -> info ) {

temp = *startPtr; *startPtr = (* startPtr) -> next; free(temp);

return value;

}else {

previous = *startPtr; current = (*startPtr) -> next;

while(current != NULL && current->info != value){

previous = current; current = current->next;

}

if (current != NULL) { temp = current; previous->next = current->next;

free(temp) ; return value;

}

return ‘\0’;

}

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

18

Cấu trúc dữ liệu và Giải thuật

Danh sách nối kép

z Qui cách của nút trong danh sách nối kép

prev next

info

nút

– Trường PREV của nút đầu tiên và trường NEXT của nút

cuối cùng đều có giá trị NULL

– Cần nắm được hai con trỏ, con trỏ L trỏ tới nút cực trái, con

trỏ R trỏ tới nút cực phải của danh sách

– Với danh sách rỗng , L = R = NULL

R

L

B

C

G

H

Danh sách nối kép

– Khai báo danh sách nối kép trong C

struct dlnode{

int info;

struct dlnode *next;

struct dlnode *prev;

} ;

typedef struct dlnode DLNODE;

typedef DLNODE *DLNODEPTR;

DLNODEPTR left, right;

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

19

Cấu trúc dữ liệu và Giải thuật

Các thao tác trên danh sách nối kép

Bổ sung một phần tử vào sau một nút được trỏ bởi con trỏ M biết trước

R

L

B

C

G

H

M

R

B

C

G

H

L

X

M

R

B

C

G

H

L

X

Các thao tác trên danh sách nối kép

z Giải thuật bổ sung một phần tử mới vào danh sách nối kép

Procedure INSERT-DOUBLE (L, R, M, X)

{Bổ sung một phần tử chứa dữ liệu X vào sau phần tử trỏ bởi M}

1. {Tạo lập nút mới}

call New(p) ; {xin cấp phát một nút mới có địa chỉ là p}

INFO(p) := X;

2. {Danh sách rỗng}

if L = R= NULL then begin

PREV(p):= NEXT(p) := NULL;

L:= R:=p;

return;

end;

(Còn tiếp)

Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN

20

Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương III: Mảng và Danh sách - Đỗ Bích Diệp