Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Mảng và danh sách. Chương này có nội dung trình bày về: khái niệm, phân loại, các phép toán diễn đạt, cài đặt của mảng, danh sách, ngăn xếp, hàng đợi. Mời các bạn cùng tham khảo!
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Mảng và danh sách
- 8/4/2020
1.2.2 Ngôn ngữ diễn đạt giải thuật
#include void main()
#include {
#include int n,*a;
printf("nhap so phan tu:"); scanf("%d",
int max(int *x,int n) &n);
{ int result = x[0]; a=(int*)malloc(n*sizeof(int));
for (int i=1;i
- 8/4/2020
2.1 Mảng (Array)
2.1.1 Khái niệm
2.1.2 Một số phép toán trên mảng
2.1.3 Cài đặt mảng 1 và 2 chiều
Cấu trúc dữ liệu và giải thuật 41
2.1.1 Khái niệm
❖Khái niệm: mảng là một tập có thứ tự gồm một số cố
định các phần tử cùng kiểu dữ liệu
→ là một cấu trúc dữ liệu
❖Mỗi phần tử được xác định và truy cập bởi tên mảng và
chỉ số của phần tử đó (là thứ tự của phần tử)→truy cập
ngẫu nhiên
❖Kiểu dữ liệu mảng: 1chiều, nhiều chiều
❖Ví dụ: vectơ, ma trận
Cấu trúc dữ liệu và giải thuật 42
21
- 8/4/2020
2.1.1 Khái niệm
❖Cấu trúc lưu trữ mảng: là hình thức lưu trữ kế
tiếp
▪ Địa chỉ các phần tử liên tiếp nhau
▪ Các phần tử được sắp xếp theo hàng
▪ Bộ nhớ cố định
❖Đặc điểm:
▪ Cấu trúc đơn giản, truy cập nhanh
▪ Thiếu mềm dẻo trong các phép toán như xóa, chèn
Cấu trúc dữ liệu và giải thuật 43
2.1.2 Một số phép toán trên mảng
❖Tạo lập mảng
❖Nhập/xuất mảng
❖Cập nhập phần tử mảng
❖Duyệt mảng (tìm kiếm một phần tử của mảng)
❖Không có phép toán thêm/bớt phần tử
( Sinh viên tự cài đặt)
Cấu trúc dữ liệu và giải thuật 44
22
- 8/4/2020
2.1.3 Cài đặt mảng 1 chiều và 2 chiều
#define N 10
void main() { // cài đặt một mảng có kích thước cho
trước
clrscr();
int a[N];// khai bao mang kich thuoc N
for(int i=0; i
- 8/4/2020
2.2 Danh sách (List)
2.2.1 Khái niệm
2.2.2 Phân loại danh sách
2.2.4 Cài đặt danh sách liên kết
2.2.5 Các phép toán trên danh sách liên kết
Cấu trúc dữ liệu và giải thuật 47
2.2.1 Khái niệm
❖Khái niệm : danh sách là tập có thứ tự các phần tử cùng
kiểu
▪ Số phần tử biến động
▪ Các phần tử được sắp xếp theo thứ tự trước – sau
❖Danh sách tuyến tính: thể hiện quan hệ lân cận giữa các
phần tử
▪ Hoặc là danh sách rỗng hoặc có dạng (a1, a2, …, an)
▪ n: độ dài / kích thước của danh sách
▪ Mỗi phần tử thường là một bản ghi bao gồm một hoặc nhiều
trường (field)
❖Ví dụ: danh sách sinh viên, danh mục điện thoại
Cấu trúc dữ liệu và giải thuật 48
24
- 8/4/2020
2.2.1 Khái niệm
❖ Danh sách con: gồm các phần tử liên tiếp từ ai đến aj của
danh sách
▪ Nếu i=1 gọi là phần đầu (prefix)
▪ Nếu j=n gọi là phần cuối (postfix).
❖ Dãy con: là một DS tạo thành bằng cách loại từ DS một số
phần tử.
❖ Ví dụ: DS = (a,b,c,d,e,f). Khi đó:
▪ (c,d,e) là một danh sách con của DS
▪ (a, b) là một phần đầu của DS
▪ (c,d,e,f) là một phần cuối của DS
▪ (a,c,f) là một dãy con của DS
Cấu trúc dữ liệu và giải thuật 49
2.2.2 Phân loại danh sách
❖Theo mối quan hệ giữa các phần tử
▪ Danh sách tuyến tính
▪ Danh sách phi tuyến
❖Theo cách thức liên kết giữa các phần tử trong
lưu trữ
▪ Danh sách liên kết đơn
▪ Danh sách liên kết vòng
▪ Danh sách liên kết kép
Cấu trúc dữ liệu và giải thuật 50
25
- 8/4/2020
2.2.3 Cài đặt bằng danh sách liên kết
Các cách cài đặt
Cài đặt bằng mảng: (lưu trữ kế tiếp)
Ưu điểm:
Truy cập nhanh, ngẫu nhiên, như nhau đối với mọi phần tử
Thao tác tìm kiếm dễ dàng
Nhược điểm:
Kích thước mảng trong mọi ngôn ngữ lập trình đều cố định còn
kích thước ds luôn biến động → lãng phí hoặc thiếu vùng nhớ
Việc thêm bớt khó khăn do phải dịch chuyển nhiều phần tử
→lãng phí thời gian
Cấu trúc dữ liệu và giải thuật
2.2.3 Cài đặt bằng danh sách liên kết
❖Cài đặt bằng danh sách liên kết: lưu trữ móc nối
❖Khái niệm: danh sách liên kết đơn (linked list) là DS
các phần tử (gọi là nút) được móc nối với nhau theo một
chiều.
❖Mỗi phần tử là một Struct (bản ghi)
▪ Một trường con trỏ chứa thông tin liên kết đến nút tiếp
theo (next)
▪ Các trường chứa thông tin (data) A
Data Next
Cấu trúc dữ liệu và giải thuật 52
26
- 8/4/2020
2.2.3 Cài đặt danh sách liên kết
Head: con trỏ trỏ tới nút đầu tiên → để truy cập vào các
phần tử của danh sách
Trường Next của nút cuối cùng chứa giá trị NULL- là địa
chỉ đặc biệt để đánh dấu nút kết thúc danh sách
Head
…
a0 a1 an-1
Cấu trúc dữ liệu và giải thuật 53
2.2.3 Cài đặt danh sách liên kết
❖Định nghĩa:
typedef struct node{
typeData data;
struct node *next;
}node;
❖Tạo nút mới:
node* p=malloc(sizeof(node));
❖Giải phóng nút:
free(p);
❖Khai báo một con trỏ:
node *head;
Cấu trúc dữ liệu và giải thuật 54
27
- 8/4/2020
2.2.3 Cài đặt danh sách liên kết
❖Chú ý:
▪ Head là con trỏ trỏ tới nút đầu tiên, khi con trỏ rỗng thì
Head=NULL
▪ Sử dụng Head để truy cập toàn bộ danh sách
▪ Khi truyền danh sách vào hàm thì chỉ cần truyền Head
▪ Nếu hàm làm thay đổi vị trí nút đầu của danh sách (thêm
hoặc xóa nút đầu) thì Head không trỏ vào đầu danh sách
nữa
→ Nên truyền Head theo dạng tham biến (hoặc trả lại con
trỏ mới)
Cấu trúc dữ liệu và giải thuật 55
2.2.4 Một số phép toán trên danh sách
❖Tìm kiếm nút có giá trị là v trong danh sách
▪ Nếu tìm được thì trả lại vị trí của phần tử, ngược lại trả
về giá trị 0. hoặc nếu tìm được thì trả lại con trỏ trỏ vào
phần tử cần tìm, nếu không tìm thấy thì trả lại con trỏ
NULL .
▪ Giải thuật: Dùng con trỏ q chạy từ đầu danh sách, qua
lần lượt các phần tử của danh sách và dừng lại ở phần tử
có giá trị v.
Cấu trúc dữ liệu và giải thuật 56
28
- 8/4/2020
2.2.4 Một số phép toán trên danh sách
Thêm một phần tử có giá trị dữ liệu là v
→Bốn tình huống: Thêm vào danh sách rỗng/ đầu/giữa
và cuối danh sách
Thêm vào danh sách rỗng
Giải thuật:
Tạo một nút mới: khai báo và cấp phát bộ nhớ
Móc nối nút mới vào danh sách:
Head
▪ Gán trường dữ liệu của nút bằng v
▪ Gán trường Next trỏ tới NULL
▪ Gán con trỏ Head trỏ tới nút mới v
Cấu trúc dữ liệu và giải thuật 57
2.2.4 Một số phép toán trên danh sách
❖Thêm vào đầu danh sách
❖Giải thuật:
▪Tạo một nút mới: khai báo và cấp phát bộ nhớ
▪Móc nối nút mới vào danh sách:
• Gán trường dữ liệu của nút bằng v
• Gán trường Next trỏ tới đầu danh sách (head)
• Gán con trỏ Head trỏ tới nút mới Head X
v
Cấu trúc dữ liệu và giải thuật
NewNode 58
29
- 8/4/2020
2.2.4 Một số phép toán trên danh sách
❖Thêm vào giữa/cuối danh sách/ Thêm một nút mới
vào danh sách sau nút index. Nếu thành công trả lại nút
được thêm, ngược lại trả lại NULL
CurrNode
X
▪ Giải thuật: v
▪ Tìm nút thứ index – currNode
NewNode
▪ Tạo nút mới
▪ Móc nối nút mới vào danh sách
Cấu trúc dữ liệu và giải thuật 59
2.2.4 Một số phép toán trên danh sách
❖Xóa nút có giá trị v trong danh sách
❖Giải thuật:
▪ Tìm nút có giá trị v
▪ Thiết lập nút trước của nút cần xóa móc nối đến nút
sau của nút cần xóa: sử dụng hai con trỏ để duyệt
danh sách và xác định nút trước của nút cần xóa.
▪ Giải phóng bộ nhớ được cấp phát cho nút cần xóa
❖2 tình huống:
▪ Nút cần xóa ở đầu / giữa hoặc cuối danh sách
Cấu trúc dữ liệu và giải thuật 60
30
- 8/4/2020
2.2.4 Một số phép toán trên danh sách
❖Xóa nút có giá trị v
Head X a0 X a1 …
P
Head
a0 a1 X v X a3 …
q P
Cấu trúc dữ liệu và giải thuật 61
2.3 Ngăn xếp (Stack)
2.3.1 Khái niệm
2.3.2 Cài đặt danh sách
2.3.3 Ứng dụng
Cấu trúc dữ liệu và giải thuật 62
31
- 8/4/2020
2.3.1 Khái niệm
❖Khái niệm: Ngăn xếp là một kiểu danh sách mà việc
thêm và bớt phần tử được thực hiện chỉ tại một đầu danh
sách gọi là đỉnh
❖Hoạt động theo nguyên tắc “Vào trước ra sau” (LIFO)
❖Hình ảnh minh họa: chồng sách, chồng máy tính, hộp
chứa đạn súng trường
Cấu trúc dữ liệu và giải thuật 63
2.3.1 Khái niệm
❖Các thao tác cơ bản
▪ Thêm phần tử (Push)
▪ Bớt phần tử (pop)
▪ Kiểm tra danh sách rỗng/đầy
▪ Phần tử đỉnh Push Pop
Đỉnh
Đáy
Cấu trúc dữ liệu và giải thuật 64
32
- 8/4/2020
2.3.2 Cài đặt ngăn xếp
❖Cài đặt bằng mảng
❖Cài đặt bằng danh sách liên kết
→ Yêu cầu: sinh viên cài đặt
Cấu trúc dữ liệu và giải thuật 65
2.3.3 Ứng dụng
❖Trình thông dịch
❖Một số bài toán tìm đường đi trong lý thuyết đồ
thị
❖Khử đệ quy: bài toán đổi cơ số, bài toán in xâu
đảo ngược
❖Bài toán ký pháp trung/hậu tố (ký pháp Balan)
Cấu trúc dữ liệu và giải thuật 66
33
- 8/4/2020
2.4 Hàng đợi (Queue)
2.4.1 Khái niệm
2.4.2 Cài đặt hàng đợi
2.4.3 Ứng dụng
Cấu trúc dữ liệu và giải thuật 67
2.4.1 Khái niệm
❖Khái niệm: Hàng đợi là kiểu danh sách mà thao
tác thêm phần tử được thực hiện ở một đầu còn
thao tác lấy ra phần tử được thực hiện ở đầu kia
của danh sách.
❖Hoạt động theo nguyên tắc “vào trước – ra
trước” (FIFO)
❖Ví dụ minh họa: Hàng đợi thanh toán, soát vé
Cấu trúc dữ liệu và giải thuật 68
34
- 8/4/2020
2.4.1 Khái niệm
❖Các thao tác cơ bản
▪ Thêm phần tử vào cuối danh sách
▪ Lấy ra phần tử ở đầu danh sách
▪ Trả lại phần tử đầu danh sách
▪ Trả lại phần tử cuối danh sách
Cấu trúc dữ liệu và giải thuật 69
2.4.2 Cài đặt hàng đợi
❖Cài đặt bằng mảng
❖Cài đặt bằng danh sách liên kết
→ Yêu cầu: sinh viên cài đặt
Cấu trúc dữ liệu và giải thuật 70
35
- 8/4/2020
2.4.3 Ứng dụng
❖Bộ đệm
❖Xử lý lệnh trong máy tính
❖Hàng đợi các chương trình chờ xử lý
❖Bài toán quản lý kho hàng
Cấu trúc dữ liệu và giải thuật 71
2.2.4 Cài đặt bởi mảng
a) Chèn
❖ Giải thuật: Dồn các phần tử từ vị trí p đến
cuối sang phải một vị trí
A B C D E F G H I J K
p
- Đặt v vào vị trí P
- Tăng n lên 1
Cấu trúc dữ liệu và giải thuật 72
36
- 8/4/2020
2.2.4 Cài đặt bởi mảng
b) Xóa
- Mảng ban đầu P
A B C D E F G H I J K L
- Giải thuật: Chuyển tất cả các phần tử từ vị trí p+1 đến
cuối sang trái 1 vị trí, Giảm n đi 1
A B C D E F H I J K L
- Nếu không cần bảo lưu thứ tự các phần tử sau khi xóa thì
chỉ cần tráo đổi giá trị phần tử cần xóa cho phần tử cuối
cùng và giảm n đi 1.
❖Các trường hợp đặc biệt với 2 thao tác chèn và xóa
73
2.2.4 Cài đặt bởi mảng
❖Cài đặt trong C:
▪ Giả sử độ dài tối đa của danh sách là MaxSize, các
phần tử của danh sách có kiểu dữ liệu là TypeItem
(kiểu cơ sở hoặc cấu trúc).
▪ Danh sách được biểu diễn bởi cấu trúc gồm 2 trường.
▪ Trường thứ nhất là mảng các phần tử, phần tử thứ i của
danh sách được lưu giữ trong thành phần thứ i của
mảng.
▪ Trường thứ hai ghi chỉ số của thành phần mảng lưu giữ
thành phần cuối cùng của danh sách
Cấu trúc dữ liệu và giải thuật 74
37
- 8/4/2020
2.2.4 Cài đặt bởi mảng
Khai báo kiểu danh sách
struct TypeList {
TypeItem Elem[MaxSize];
int size; } ;
TypeList L;
Lưu ý:
Để khởi tạo một danh sách rỗng ta dùng lệnh gán
L.size=0;
Nếu L.size=MaxSize thì danh sách đầy.
Cấu trúc dữ liệu và giải thuật 75
2.2.4 Cài đặt bởi mảng
Chèn vào sau vị trí p
void InsertAfter(int v,TypeItem x, TypeList *L){
int i;
if (IsEmpty(*L)==1)
{ L->size++; L->Elem[L->size] = x; }
else
if(IsFull(*L)==0)
{ L->size++; i=L->size - 1;
while (i>v+1) {
L->Elem[i]=L->Elem[i-1]; i--;
printf("\n %d",i); }
L->Elem[i] = x;
}
else printf("\n Danh sach day"); }
Cấu trúc dữ liệu và giải thuật 76
38
- 8/4/2020
2.2.4 Cài đặt bởi mảng
Chèn vào trước vị trí p
void InsertBefore(int v, TypeItem x, TypeList *L)
{
int i;
if (IsEmpty(*L)==1)
{ (L->size)++; L->Elem[L->size - 1] = x; }
else
if(IsFull(*L)==0)
{ (L->size)++; i=L->size - 1;
while (i>v)
{ L->Elem[i]=L->Elem[i-1]; i--; }
L->Elem[i] = x;
}
else printf("\n Danh sach day");
}
Cấu trúc dữ liệu và giải thuật 77
2.2.4 Cài đặt bởi mảng
Xóa phần tử ở vị trí p
void Remove(int v, TypeofList *L)
{
int i;
if (IsEmpty(*L)==0)
{
for (i=v;isize-1;i++)
L->Elem[i]=L->Elem[i+1];
L->size--;
}
else
printf("\n Danh sach rong");
}
Cấu trúc dữ liệu và giải thuật 78
39
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
