Bài giảng cấu trúc dữ liệu và giải thuật (3/5)

Tìm kiếm Bài giảng

Gốc > Cao đẳng - Đại học > Công nghệ thông tin >

0 / 0

Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả

(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Tứ Hải
Ngày gửi: 11h:29' 11-01-2026
Dung lượng: 533.5 KB
Số lượt tải: 1

Số lượt thích: 0 người

Chương 3:
MẢNG, DANH SÁCH
VÀ CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG

1. Mảng
* Khai báo mảng 1 chiều:
Cú pháp:
[Số phần tử tối đa của mảng];

Ví dụ: int a[10];
Ý nghĩa: Khai báo mảng a gồm 10 phần tử, mỗi phần tử có
kiểu int

* Khai báo mảng 2 chiều:
Cú pháp:
[Số phần tử hàng][Số phần tử cột];

Ví dụ: int a[5][10];
Ý nghĩa: Khai báo mảng a gồm 5 x 10=50 phần tử, mỗi
phần tử có kiểu int

a

* Truy xuất mảng 1 chiều
Sau khi mảng được khai báo, mỗi phần tử trong mảng đều
có chỉ số để tham chiếu. Chỉ số bắt đầu từ 0 đến n-1 (với n
là kích thước mảng). Trong ví dụ trên, ta khai báo mảng
10 phần tử thì chỉ số bắt đầu từ 0 đến 9.

a[2]

a[7]

=> Muốn truy xuất đến phần tử nào, ta viết:
tên mảng[chỉ số]
VD: a[0]=max; (gán phần tử a[0] là max)

• Nhập dữ liệu cho mảng 1 chiều

• In mảng 1 chiều

* Truy xuất mảng 2 chiều
Sau khi được khai báo, mỗi phần tử trong mảng 2 chiều đều
có 2 chỉ số để tham chiếu, chỉ số hàng và chỉ số cột. Chỉ
số hàng bắt đầu từ 0 đến số hàng – 1 và chỉ
số cột bắt đầu từ 0 đến số cột – 1. Tham chiếu
đến một phần tử trong mảng 2 chiều a: a[chỉ
số hàng][chỉ số cột]
a
0
1 2 int
3 a[5][10];
4 5 6 7 8 9

a[3][2]

a[1][5]

a[4][8]

• Nhập dữ liệu cho mảng 2 chiều
for (i=0;i<5;i++)
//vòng for có giá trị i chạy từ 0 đến 4 cho
hàng

for (j=0;j<10;j++) //vòng for có giá trị j chạy từ 0 đến 9 cho cột
{
printf(“Nhap vao phan tu thu a[%d][%d]: “,i+1,j+1);
scanf(“%d”,&a[i][j]);
}

Thứ tự nhập dữ liệu vào mảng 2 chiều

• In mảng 2 chiều

for (i=0;i<5;i++)
{

for (j=0;j<10;j++)
printf(“%3d”,a[i][j]);
printf(“\n”); // xuống dòng để in hàng kế tiếp
}

2. Danh sách liên kết
Một danh sách liên kết (Linked List) là một dãy các cấu trúc
dữ liệu được kết nối với nhau thông qua các liên kết (link).
Hiểu một cách đơn giản thì danh sách liên kết là một cấu
trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành
một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến
nút kế tiếp trong chuỗi.

Các thuật ngữ trong Danh sách liên kết
• Liên kết (Link) - Mỗi liên kết của danh sách được liên
kết có thể lưu trữ một dữ liệu được gọi là một phần tử
• Tiếp theo (Next) - Mỗi liên kết của danh sách được
liên kết chứa một liên kết đến liên kết tiếp theo được gọi
là Next
• LinkedList - Danh sách được liên kết chứa liên kết kết
nối đến liên kết đầu tiên được gọi là First

Biểu diễn Danh sách liên kết
Danh sách được liên kết có thể được hình dung như một
chuỗi các nút, nơi mọi nút đều trỏ đến nút tiếp theo

• Danh sách được Liên kết chứa một phần tử liên kết
được gọi là đầu tiên
• Mỗi liên kết mang (các) trường dữ liệu và một trường
liên kết được gọi là tiếp theo
• Mỗi liên kết được liên kết với liên kết tiếp theo của
nó bằng cách sử dụng liên kết tiếp theo của nó
• Liên kết cuối cùng mang một liên kết là null để đánh
dấu phần cuối của danh sách

Các loại Danh sách liên kết
 Danh sách liên kết đơn:
Danh sách được liên kết đơn chứa các nút có trường dữ liệu
(data) cũng như trường 'tiếp theo' (next), trỏ đến nút tiếp
theo trong chuỗi các nút.

Các loại Danh sách liên kết

 Danh sách liên kết kép
Trong 'danh sách được liên kết kép', mỗi nút chứa, ngoài
liên kết nút tiếp theo, một trường liên kết thứ hai trỏ đến
nút 'trước đó' trong chuỗi các nút. Hai liên kết có thể
được gọi là 'chuyển tiếp' (forward) và 'quay lại'
(backwards), hoặc' tiếp theo' (next) và 'trước'
(prev/previous).

Các loại Danh sách liên kết
 Danh sách liên kết móc vòng
Trong nút cuối cùng của danh sách, trường liên kết thường
chứa tham chiếu rỗng, một giá trị đặc biệt được sử dụng
để chỉ ra việc thiếu các nút tiếp theo. Một quy ước ít phổ
biến hơn là làm cho nó trỏ đến nút đầu tiên của danh
sách; trong trường hợp đó, danh sách được cho là 'vòng
tròn' hoặc 'liên kết móc vòng'; nếu không, nó được cho là
'mở' hoặc 'tuyến tính'. Nó là một danh sách mà con trỏ
cuối cùng trỏ đến nút đầu tiên

Các thao tác cơ bản trên Danh sách liên kết
• Chèn - Thêm một phần tử vào đầu danh sách
• Duyệt - Duyệt qua lần lượt các phần tử trong danh sách.
VD Thao tác hiển thị danh sách đầy đủ các phần tử
• Xóa - Xóa một phần tử ở đầu danh sách
• Xóa - Xóa một phần tử bằng cách sử dụng khóa đã cho
• Tìm kiếm - Tìm kiếm một phần tử bằng cách sử dụng
khóa đã cho

Triển khai Danh sách liên kết
• Danh sách liên kết đơn hoặc danh sách liên kết móc vòng

• Danh sách liên kết kép

Thêm phần tử và đầu của Danh sách liên kết
Để thêm một phần tử (Node/Element) mới vào trong danh
sách liên kết đơn, chúng ta thực hiện các bước như sau:
•Cấp phát bộ nhớ cho phần tử mới
•Gán thuộc tính data của phần tử mới cho giá trị cần thêm
vào

• Gán thuộc tính next của phần tử mới cho phần tử đầu tiên

• Gán phần tử đầu tiên của danh sách cho phần tử mới

Mã nguồn ngôn ngữ C cho thao tác thêm phần tử vào đầu
danh sách:

• value: là giá trị cần thêm mới vào danh sách
• head: là địa chỉ phần tử đầu tiên của danh sách

3. Các kiểu dữ liệu trừu tượng
- Kiểu dữ liệu trừu tượng là một kiểu dữ liệu do
chúng ta định nghĩa ở mức khái niệm, nó chưa được
cài đặt cụ thể bằng một ngôn ngữ lập trình.
- Khi cài đặt một kiểu dữ liệu trừu tượng trên một
ngôn ngữ lập trình cụ thể, chúng ta phải thực hiện hai
nhiệm vụ:
1. Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc
dữ liệu hoặc một kiểu dữ liệu trừu tượng khác đã được
cài đặt.
2. Viết các chương trình con thực hiện các phép toán
trên kiểu dữ liệu trừu tượng mà ta thường gọi là cài
đặt các phép toán.