Chương III: Mảng và Danh sách (p2) Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng

Chương III: Mảng và Danh sách (p2) Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học

 

11 6 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu (CTDL02)

Trường: Trường Đại học Bách khoa, Đại học Đà Nẵng

Thông tin:

28 trang 1 tháng trước

Tác giả:

Profile Kim Oanh
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 1
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
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 2
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
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 3
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 rố có thể có giá trị ờ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ử
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 4
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] địa chỉ c sơ ở = α
list[1] α + sizeof(int)
list[2] α + 2*sizeof(int)
list[3] α + 3*sizeof(int)
list[4] α + 4*sizeof(int)
Mảng 1 chiều
Address Value
1228 0
1230 1
1232 2
1234 3
1236 4
int list[] = {0, 1, 2, 3, 4};
int *ptr; int rows = 5;
int i; ptr = list;
printf(“Address Value\n”);
for (i=0; i < rows; i++)
printf(“%8u%5d\n”, ptr+i, *(ptr+i));
printf(“\n”);
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 5
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
32
a
31
a
30
a
22
a
21
a
20
a
12
a
11
a
10
a
02
a
01
a
00
a
32
a
31
a
30
a
22
a
21
a
20
a
12
a
11
a
10
a
02
a
01
a
00
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
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 6
Mảng 2 chiều
– Lưu trữ mảng 2 chiều theo thứ tự ưu tiên cột
a
32
a
31
a
30
a
22
a
21
a
20
a
12
a
11
a
10
a
02
a
01
a
00
a
32
a
22
a
12
a
02
a
31
a
21
a
11
a
01
a
30
a
20
a
10
a
00
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
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
1 2 n
, a , …., a
n-1
, a }
– a
i
là phần tử ở vị trí i trong danh sách
– a
1
là phần tử đầu tiên, a
n
là 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 ngợp n =0 ta có danh sách rỗ
– 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.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 7
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 kưu trữ ế 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
1 2 3 last
i
max
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 8
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?
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 9
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
1 2 3 last
p
A
1 2 3 last
p
A
1 2 3 last
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 mưu giá trị ớ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
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 10
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
1 2 3 last
p
A
1 2 3 last
x
p
A
1 3 last
p
2
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.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 11
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
L
e1 e2 e5 NILe4e3
5000
Data 4320
Structure
2000 CourseAlgorithm 3000And 1000
Hình ảnh danh sách móc nối đơn
Ví dụ danh sách móc n nối đơ
Địa chỉ nút đầu
danh sách
Địa chỉ bộ nhớ của các phần tử tiếp theo
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 12
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;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 13
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
L
B C G H
L
B
C G
H
P
X
P
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 14
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
L
B C G H
P
X
Temp
Sau khi khởi tạo nút mớ ầi và gán giá trị cho ph n tử mới
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 15
Các thao tác trên danh sách nối đơn
L
B C G H
P
X
Temp
NEXT(P)
Sau khi thực hiện NEXT(Temp) = NEXT(P);
Các thao tác trên danh sách nối đơn
L
B C G H
P
X
Temp
Sau khi thực hiện NEXT(P) = Temp;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 16
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
L
B C G H
L
B
C G
H
P
P
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.
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 17
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);
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 18
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;
2. while (current != NULL && value >current->info) {
previous = current; current = current->next;
}
3. if (previous = NULL) {
temp->next = *startPtr;
*startPtr = temp;
}
4. 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’;
}
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 19
Danh sách nối kép
z Qui cách của nút trong danh sách nối kép
– 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
L
B C G H
R
prev next
info
nút
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;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 20
Các thao tác trên danh sách nối kép
L
B C G H
R
X
M
L
B C G H
R
X
M
L
B C G H
R
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
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)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 21
Các thao tác trên danh sách nối kép
z Bổ sung vào danh sách nối kép (tiếp)
3. {Trường hợp M là nút cực phải}
if M = R then begin
NEXT(p) := NULL; PREV(p) := M; NEXT(M) := p;
R:= p;
end;
4. { Bổ sung vào giữa}
PREV(p) := M; NEXT(p) := NEXT(M);
PREV(NEXT(M)) := p;
NEXT(M) := p;
5. return.
Các thao tác trên danh sách nối kép
z Loại bỏ một phần tử
L
B C G H
R
L
B C G H
R
M
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 22
Các thao tác trên danh sách nối kép
z Giải thuật loại bỏ một phần tử khỏ ối danh sách n i kép
Procedure DELETE-DOUBLE (L, R, M)
{Loại bỏ phần tử trỏ bởi M }
1. {Danh sách rỗng}
if L= R= NULL then return;
2. {Loại bỏ}
if L= R and L = M then L:=R:= NULL;
else if M = L then begin L:= NEXT(L); PREV(L) := NULL; end;
else if M = R then begin R:= PREV(R); NEXT(R) := NULL; end;
else begin NEXT(PREV(M)) :=NEXT(M); PREV(NEXT(M)) := PREV(M);
end;
call Dispose(M);
3. return.
Biểu diễn đa thức sử dụng danh sách
– Bài toán cộng hai đa thức
z Dạng tổng quát của một đa thức
z Viết giải thuậ ổ đt tìm t ng 2 a thức trên
01
1
1
...)( axaxaxaxP
n
n
n
n
++++=
−
−
24678
278
8256)(
74352)(
xxxxxxB
xxxxxA
−+−+=
−++−=
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 23
Cách tiếp cận sử dụng danh sách kế tiếp
z Biểu diễ đn a thức sử dụng danh sách lưu trữ kế tiếp
– Mỗi số hạng của đa thứ ứ ớc ng v i một phần tử của vector
lưu trữ
– Một vector có kích thước n có các phần tử đánh số từ 1
đến n thì lưu trữ được mộ đt a thức có số ũm tố đi a là n-1
– Phần hệ ốs a
i
của một số hạng được lưu trong chính phần
tử của vector lưu trữ
– Phần số ũm i của một số hạng thì ẩn trong thứ ựt của phần
tử lưu trữ
– Phần tử ứth i trong vector lưu trữ lưu thông tin về ốs hạng
a
i-1
x
i-1
z Phần tử ứth 1 lưu trữ thông tin a
0
z Phần tử ứth 2 lưu trữ thông tin về a
1
z …
Cách tiếp cận sử dụng lưu trữ kế tiếp
– Ví dụ:
2-5000034-7
A[9]A[8]A[7]A[6]A[5]A[4]A[3]A[2]A[1]
65-2010-800
B[9]B[8]B[7]B[6]B[5]B[4]B[3]B[2]B[1]
24678
278
8256)(
74352)(
xxxxxxB
xxxxxA
−+−+=
−++−=
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 24
Cách tiếp cận sử dụng lưu trữ kế tiếp
– Giải thuật cộ đng hai a thức lưu trữ trên vector
Procedure ADD-POLY1(A,m, B, n, C)
Begin
{A, B là hai vector lưu trữ hai đa thứ đc ã cho;
m,n lần lượt là kích thước của A,B, giả sử m <= n ;
C là vector lưu trữ kết quả}
for i:= 1 to n do begin
if i<= m then
C[i] := A[i] + B[i] ;
else
C[i] := B[i] ;
end.
End
Cách tiếp cận sử dụng lưu trữ móc nối
z Biểu diễ đn a thức sử dụng lưu trữ móc nối
– Một đa thức được biểu diễn dưới dạ ống danh sách n i đơn
– Quy cách của 1 nút
– Ví dụ:
LINKEXPCOEF
24678
278
8256)(
74352)(
xxxxxxB
xxxxxA
−+−+=
−++−=
A
2 8 - 5 7
6 8 5 7
3 2 4 1
-7 0
- 2 6
1 4
-8
2
B
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 25
Cách tiếp cận sử dụng lưu trữ móc nối
Procedure ADD-POLY2(A, B, C)
Begin
1. p:= A; q:=B;
2. call New(C) ; d:= C; {d trỏ vào nút cuối cùng của C}
3. while p <> NULL and q <> NULL do
case
EXP(p) = EXP(q): x := COEF(p) + COEF(q) ;
if x<>0 then call ATTACH(x, EXP(p), d) ;
p:= LINK(p) ; q:= LINK(q);
EXP(p) > EXP(q): call ATTACH(COEF(p), EXP(p),d);
p:= LINK(p);
EXP(p) < EXP(q): call ATTACH(COEF(q), EXP(q),d);
q:= LINK(q);
end case; {Còn tiếp}
Cách tiếp cận sử dụng lưu trữ móc nối
4. {Trường hợp A kế ắt thúc trước, A ng n hơn}
while q <> NULL do begin
call ATTACH(COEF(q), EXP(q),d); q:= LINK(q);
end ;
5. {Trường hợp B kết thúc trước}
while p <> NULL do begin
call ATTACH(COEF(p), EXP(p), d) ; p := LINK(p);
end ;
6. {Kết thúc danh sách tổng} LINK(d) := NULL;
7. {Cho con trỏ C trỏ tới danh sách tổng}
t:= C; C:= LINK(t); call dispose(t);
8. return.
| 1/28
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Cấu trúc dữ liệu và Giải thuật
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 nh ề i 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 ch ề i 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 g ố i 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: [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] địa chỉ cơ sở = α list[1] α + sizeof(int) list[2] α + 2*sizeof(int) list[3] α + 3*sizeof(int) list[4] α + 4*sizeof(int) Mảng 1 chiều int list[] = {0, 1, 2, 3, 4}; Address Value int *ptr; int rows = 5; 1228 0 int i; ptr = list; 1230 1
printf(“Address Value\n”); 1232 2 for (i=0; i < rows; i++) 1234 3
printf(“%8u%5d\n”, ptr+i, *(ptr+i)); 1236 4 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 : [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 00 01 02 a a a 10 11 12 a a a
Từ mảng 2 chiều lưu trữ 20 21 22
sang bộ nhớ kế tiếp sử dụng a a a 30 31 32 thứ tự ưu tiên hàng a a a a a a a a a a a a 00 01 02 10 11 12 20 21 22 30 31 32
Đỗ 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 00 01 02 a a a 10 11 12 a a a
Từ mảng 2 chiều lưu trữ 20 21 22
sang bộ nhớ kế tiếp sử dụng a a a 30 31 32 thứ tự ưu tiên cột a a a a a a a a a a a a 00 10 20 30 01 11 21 31 02 12 22 32
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 {a1, a2, …., an-1, an}
– ai là phần tử ở vị trí i trong danh sách
– a1 là phần tử đầu tiên, an là 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ử t ứ h i của mảng chứa
địa chỉ của phần tử t ứ h 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 1 2 3 i last max
Đỗ 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 1 2 3 p last A 1 2 3 p last A x 1 2 3 p last
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 1 2 3 p last A 1 3 p 2 last A 1 2 3 p last
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ỉ nút đầu
Địa chỉ bộ nhớ của các phần tử tiếp theo 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ữ : cal New(p)
z Thu hồi một nút trỏ bởi p
Câu lệnh trong giả ngôn ngữ: cal Dispose(p)
Danh sách móc nối đơn
– Khai báo trong ngôn ngữ C typedef 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 L P B C G H L P B C G 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 p ầ h n tử mới L P 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); L P NEXT(P) 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; L P 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 t ỏ r P cho trước L P B C G H L P B C G 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; 2.
while (current != NULL && value >current->info) {
previous = current; current = current->next; } 3. if (previous = NULL) { temp->next = *startPtr; *startPtr = temp; } 4.
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 t ỏ r , con trỏ L t ỏ r 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 L B C G H R 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 L B C G H R M L B C G H R X M L B C G H R 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
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
z Bổ sung vào danh sách nối kép (tiếp)
3. {Trường hợp M là nút cực phải} if M = R then begin
NEXT(p) := NULL; PREV(p) := M; NEXT(M) := p; R:= p; end; 4. { Bổ sung vào giữa}
PREV(p) := M; NEXT(p) := NEXT(M); PREV(NEXT(M)) := p; NEXT(M) := p; 5. return.
Các thao tác trên danh sách nối kép
z Loại bỏ một phần tử L B C G H R M L B C G H R
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 21
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
z Giải thuật loại bỏ một phần tử khỏi danh sách ố n i kép
Procedure DELETE-DOUBLE (L, R, M)
{Loại bỏ phần tử trỏ bởi M } 1. {Danh sách rỗng} if L= R= NULL then return; 2. {Loại bỏ}
if L= R and L = M then L:=R:= NULL;
else if M = L then begin L:= NEXT(L); PREV(L) := NULL; end;
else if M = R then begin R:= PREV(R); NEXT(R) := NULL; end;
else begin NEXT(PREV(M)) :=NEXT(M); PREV(NEXT(M)) := PREV(M); end; call Dispose(M); 3. return.
Biểu diễn đa thức sử dụng danh sách
– Bài toán cộng hai đa thức
z Dạng tổng quát của một đa thức n n−1 P(x) =a x + + + + n an− x ... a x a 1 1 0 8 7 2 ( A )x =2 x 5 − x +3 x +4 x −7 8 7 6 4 2 (
B )x =6 x +5 x −2 x + x −8 x
z Viết giải thuật tìm ổ t ng 2 đa thức trên
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 22
Cấu trúc dữ liệu và Giải thuật
Cách tiếp cận sử dụng danh sách kế tiếp
z Biểu diễn đa thức sử dụng danh sách lưu trữ kế tiếp
– Mỗi số hạng của đa thức ứng ớ
v i một phần tử của vector lưu trữ
– Một vector có kích thước n có các phần tử đánh số từ 1
đến n thì lưu trữ được một đa thức có số mũ tối đa là n-1
– Phần hệ số a của một số hạng được lưu trong chính phần i tử của vector lưu trữ
– Phần số mũ i của một số hạng thì ẩn trong thứ tự của phần tử lưu trữ
– Phần tử thứ i trong vector lưu trữ lưu thông tin về ố s hạng a xi-1 i-1
z Phần tử thứ 1 lưu trữ thông tin a0
z Phần tử thứ 2 lưu trữ thông tin về a1 z …
Cách tiếp cận sử dụng lưu trữ kế tiếp – Ví dụ: 8 7 2 (
A )x = 2 x −5 x + 3 x + 4 x− 7 8 7 6 4 2 (
B )x = 6 x + 5 x − 2 x + x − 8x A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] -7 4 3 0 0 0 0 -5 2 B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9] 0 0 -8 0 1 0 -2 5 6
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 23
Cấu trúc dữ liệu và Giải thuật
Cách tiếp cận sử dụng lưu trữ kế tiếp
– Giải thuật cộng hai đa thức lưu trữ trên vector
Procedure ADD-POLY1(A,m, B, n, C) Begin
{A, B là hai vector lưu trữ hai đa thức đã cho;
m,n lần lượt là kích thước của A,B, giả sử m <= n ;
C là vector lưu trữ kết quả} for i:= 1 to n do begin if i<= m then C[i] := A[i] + B[i] ; else C[i] := B[i] ; end. End
Cách tiếp cận sử dụng lưu trữ móc nối
z Biểu diễn đa thức sử dụng lưu trữ móc nối
– Một đa thức được biểu diễn dưới dạng danh sách ố n i đơn – Quy cách của 1 nút COEF EXP LINK – Ví dụ: 8 7 2 ( A ) x = 2 x −5 x +3x + 4x − 7 8 7 6 4 2 ( B )
x = 6 x + 5 x − 2 x + x − 8x A 2 8 - 5 7 3 2 4 1 -7 0 B 6 8 5 7 - 2 6 1 4 -8 2
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 24
Cấu trúc dữ liệu và Giải thuật
Cách tiếp cận sử dụng lưu trữ móc nối Procedure ADD-POLY2(A, B, C) Begin 1. p:= A; q:=B;
2. call New(C) ; d:= C; {d trỏ vào nút cuối cùng của C}
3. while p <> NULL and q <> NULL do case
EXP(p) = EXP(q): x := COEF(p) + COEF(q) ;
if x<>0 then call ATTACH(x, EXP(p), d) ; p:= LINK(p) ; q:= LINK(q);
EXP(p) > EXP(q): call ATTACH(COEF(p), EXP(p),d); p:= LINK(p);
EXP(p) < EXP(q): call ATTACH(COEF(q), EXP(q),d); q:= LINK(q); end case; {Còn tiếp}
Cách tiếp cận sử dụng lưu trữ móc nối
4. {Trường hợp A kết thúc trước, A ngắn hơn}
while q <> NULL do begin
call ATTACH(COEF(q), EXP(q),d); q:= LINK(q); end ;
5. {Trường hợp B kết thúc trước}
while p <> NULL do begin
call ATTACH(COEF(p), EXP(p), d) ; p := LINK(p); end ;
6. {Kết thúc danh sách tổng} LINK(d) := NULL;
7. {Cho con trỏ C trỏ tới danh sách tổng}
t:= C; C:= LINK(t); call dispose(t); 8. return.
Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 25