8/15/2017
Giới thiệu học phần
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Số tín chỉ: 3 Mục tiêu: Cung cấp
Các kiến thức cơ bản về cấu trúc dữ liệu và thuật toán Kỹ năng lựa chọn và xây dựng các cấu trúc dữ liệu và
thuật toán hợp lý
Bộ môn: Tin học Khoa Hệ thống Thông tin Kinh tế & Thƣơng mại điện tử
1
2
Tài liệu tham khảo
Giới thiệu học phần
Nội dung chính:
R. Sedgevick, Algorithms Addison-Wesley, Bản dịch
tiếng Việt: Cẩm nang thuật toán (tập 1, 2)
Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật
Lê Minh Hoàng, Bài giảng chuyên đề
Chương 1: Tổng quan về giải thuật và CTDL Chương 2: Một số cấu trúc dữ liệu cơ bản Chương 3: Cây và Cây tìm kiếm Chương 4: Một số giải thuật sắp xếp và tìm kiếm
Hồ Sỹ Đàm, Cấu trúc dữ liệu và giải thuật
3
4
1
8/15/2017
1.1 Cấu trúc dữ liệu (Data Structures)
Chƣơng 1. Tổng quan về giải thuật và CTDL
1.1 Cấu trúc dữ liệu 1.2 Giải thuật
1.1.1 Khái niệm chung 1.1.2 Vai trò của CTDL 1.1.3 Một số cấu trúc dữ liệu cơ bản
5
6
1.1.1 Khái niệm chung
Ví dụ
Cây phả hệ:
Mục tiêu của tin học?
Dữ liệu là gì? Kiểu dữ liệu ?
Khái niệm chung: CTDL là một cách thể hiện và tổ chức dữ liệu trong máy tính sao cho nó đƣợc sử dụng một cách có hiệu quả nhất.
Ông A lấy bà B có hai con trai C, D và một con gái E. Ông C kết hôn với cô F có hai con một trai G và một gái H. Ông D không lập gia đình. Cô E lấy ông I có hai gái K,L và một trai M. …
Khái niệm khác: CTDL là một dữ liệu phức hợp, gồm nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu cơ sở hoặc là một CTDL đã được xây dựng. Các thành phần dữ liệu tạo nên một CTDL được liên kết với nhau theo một cách nào đó.
7
8
2
8/15/2017
1.1.2 Các vấn đề liên quan
1.1.2 Vai trò của CTDL
Các tiêu chuẩn khi lựa chọn CTDL
CTDL phải biểu diễn được đầy đủ các thông tin của
bài toán ( phản ánh đúng thực tế).
Tầm quan trọng của việc lựa chọn CTDL Tổ chức dữ liệu: dữ liệu vào/ra/trung gian Xây dựng giải thuật
Cài đặt được trên máy tính và ngôn ngữ lập trình
đang sử dụng.
Các cách cài đặt khác nhau Thực hiện thao tác thuận lợi/khôngthuận lợi
CTDL thay đổi Thuật toán thay đổi
Phù hợp với các thao tác của thuật toán (đặc biệt thao tác được sử dụng nhiều) phát triển thuật toán đơn giản và đạt hiệu quả.
Tiết kiệm tài nguyên.
9
10
1.1.3 Một số cấu trúc dữ liệu cơ bản
Mảng (Array)
Mảng (array) Bản ghi (record)/cấu trúc (struct) Tập hợp (set) Tệp (file) Xâu (string) ….(danh sách liên kết, cây, bảng băm, …)
11
12
3
8/15/2017
1.2 Giải thuật (Algorithm)
Cấu trúc - Struct (structure)
1.2.1 Khái niệm chung 1.2.2 Ngôn ngữ diễn đạt giải thuật 1.2.3 Thiết kế và phân tích giải thuật 1.2.4 Giải thuật đệ quy
13
14
1.2.1 Khái niệm chung
Thuật toán là một dãy hữu hạn các bước được sắp xếp theo một trật tự xác định, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện, để giải quyết một vấn đề.
15
16
4
8/15/2017
1.2.1 Khái niệm chung
1.2.2 Ngôn ngữ diễn đạt giải thuật
Các tính chất (đặc trƣng) của thuật toán:
Cách liệt kê: liệt kê các bước cần thực hiện Sơ đồ khối: sử dụng các hình khối oval, chữ nhật,
hình thoi và mũi tên,…
Ngôn ngữ lập trình: dùng các ký hiệu và các quy
tắc của ngôn ngữ lập trình
Giả ngôn ngữ: kết hợp giữ cú pháp của ngôn ngữ
lập trình và ngôn ngữ tự nhiên
Tính vào (input) Tính ra (output) Tính đơn định (xác định / đơn nghĩa) Tính đúng đắn Tính dừng (tính kết thúc / tính đóng) Tính phổ dụng Tính khả thi/hiệu quả
17
18
1.2.2 Ngôn ngữ diễn đạt giải thuật
1,..., an.
1.2.2 Ngôn ngữ diễn đạt giải thuật Ví dụ: - Input: N nguyên dương, dãy a - Output: Tìm Max của dãy đã cho. Ý tưởng: Giả thiết Max = a1. Với mỗi i, nếu ai > Max thì thay giá
trị Max= ai.
Cách liệt kê Bước 1. Nhập N và dãy a1, ..., an Bước 2. Đặt Max = a1, i = 2; Bước 3. Nếu i > N thì đến Bước 5; Bước 4. 4.1. Nếu ai > Max thì Max = ai. 4.2. Đặt i=i+1 rồi quay bước 3; Bước 5. Đưa ra Max rồi kết thúc.
19
20
5
8/15/2017
1.2.2 Ngôn ngữ diễn đạt giải thuật
1.2.2 Ngôn ngữ diễn đạt giải thuật
Sơ đồ khối:
if (result // n thể hiện độ dài mảng x
int result;
result=x[0];
for (int i=1;i Dùng ngôn ngữ lập trình ( C):
int max(int *x,int n) //hàm tìm max
{
} 21 22 Thiết kế giải thuật Module hóa và việc giải quyết bài toán Chiến thuật “chia để trị” (divide and conquer)
Cách thiết kế “từ đỉnh xuống”(top-down) Phương pháp tinh chỉnh từng bước (stepwise
refinement): là phương pháp thiết kế giải thuật
gắn liền với lập trình
Phản ánh: quá trình modun hóa bài toán và thiết kế kiểu top-down (từ bài toán đến chương trình) 23 24 Quản lý học bổng của sinh viên, lập báo cáo tổng kết theo kỳ Thiết kế: B1: xác định input/ouput B2: Xác định các công việc chủ yếu Input: file chứa thông tin HB của SV: mã SV, tt SV, ĐTB, Mức HB. Output: Tìm kiếm, cập nhập, hiển thị thông tin của SV, In bảng tổng kết B3: Giải quyết từng công việc một cách chi tiết bằng cách lặp Đọc file vào bộ nhớ trong lấy thông tin của SV Xử lý thông tin đọc được Ghi file Lưu thông tin cập nhật vào file 25 26 Đọc file: Ghi file Input: file thông tin trên đĩa
Output: đọc file và lưu vào mảng (mỗi ptử lưu thông tin một sinh viên) Xử lý thông tin Input: Mảng lưu thông tin các sinh viên
Output: Lưu trở lại file • Tìm một sinh viên cho trước
• Hiển thị thông tin của sinh viên
• Cập nhật thông tin của sinh viên
• In bản tổng kết 27 28 Input: Mảng lưu thông tin của các sinh viên
Output: Các chiến lược thiết kế giải thuật: Phân tích & đánh giá giải thuật
Tại sao cần phân tích giải thuật?
Chương trình chạy đúng chưa đủ, cần xét tính hiệu
quả (bộ nhớ sử dụng, thời gian tính) với các tập dữ
liệu khác nhau (đặc biệt dữ liệu lớn vấn đề thời
gian) Lưu ý: chỉ phân tích các giải thuật đúng – là thuật
toán mà với một bộ dữ liệu vào bất kỳ thì thuật toán
dừng và cho kết quả đúng 29 30 Các lưu ý khi phân tích giải thuật Đánh giá thời gian thực hiện giải thuật Thử nghiệm: không chính xác (vì phụ thuộc vào nhiều yếu tố) Lý thuyết: Coi thời gian thực hiện giải thuật là một
hàm của cỡ dữ liệu vào. T(n) gọi là “độ phức tạp
của giải thuật” Tính đúng đắn của giải thuật
Tính đơn giản của giải thuật
Tốc độ thực hiện (hoặc thời gian thực hiện) và dung
lượng bộ nhớ cần chiếm dụng của giải thuật (còn gọi
là tính hiệu quả của giải thuật )
chỉ đánh giá thời gian thực hiện giải thuật Cách xác định: tính số các phép toán sơ cấp mà giải
thuật cần dùng (lưu ý thao tác đặc trưng của giải
thuật) 31 32 1.2.3 Thiết kế và phân tích giải thuật Quy tắc xác định độ phức tạp của giải thuật Quy tắc hằng số: Nếu P có T(n)= O(c1f(n)) P có độ phức tạp O(f(n)). Quy tắc lấy max: Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O( max ( f(n), g(n))). Khái niệm hàm O lớn: Hàm T(n) được gọi là
Omega lớn của g(n), ký hiệu T(n) =O (g(n))
nếu c>0 và n0 sao cho với mọi n n0 :
T(n) c g(n)
Trong đó: g(n) là giới hạn trên của T(n). 33 34 1.2.3 Thiết kế và phân tích giải thuật 1.2.3 Thiết kế và phân tích giải thuật Ví dụ: chƣơng trình lấy max ở trên QT tổng int result;
result=x[0];
for (int i=1;i int max(int *x,int n) //hàm tìm max
{
} Câu lệnh rẽ nhánh dạng If ...else.
QT Max
Các câu lệnh lặp: while, do …while, for
QT Nhân 35 36 Điều kiện: Có điểm dừng (trường hợp suy biến không cần đệ quy/ Khái niệm: Ta nói một đối tượng là đệ quy nếu nó được
định nghĩa qua chính nó hoặc một đối tượng khác cùng
dạng với nó bằng quy nạp. phần neo) Ví dụ: Tính giai thừa/ tính tổ hợp Làm cho kích thước bài toán nhỏ hơn (để về gần TH suy biến/ phần đệ quy) Chú ý: Giải thuật đệ quy: Nếu lời giải một bài toán P được thực
hiện bằng lời giải của bài toán P‟ có dạng giống như P
thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời
giải như vậy gọi là giải thuật đệ quy P‟ giống P
Nhưng P‟ “nhỏ hơn” P theo nghĩa nào đó 37 38 Thiết kế giải thuật đệ quy: 3 bước Ví dụ: Thông số hóa bài toán
Phân rã bài toán
Tìm điều kiện dừng 39 40 Ưu điểm: Mạnh, rõ ràng, chặt chẽ
Thiết kế TT đơn giản, ngắn gọn
Trong một số giải thuật đệ quy cũng có hiệu quả cao (quick sort) Nhược điểm: Lời gọi hàm tốn rất nhiều thời gian, không gian nhớ.
Tốc độ chậm
Thận trọng đừng để chạy vô hạn Lưu ý: mọi giải thuật đệ quy đều có thể thay bằng một giải
thuật không đệ quy khử đệ quy (tự nghiên cứu tại nhà) 41 42 End chapter 1 void main()
{ for (int i=1;i if (result #include 43 int n,*a;
printf("nhap so phan tu:"); scanf("%d",
&n);
a=(int*)malloc(n*sizeof(int));
if (a==NULL)
{
}
printf("\n nhap cac phan tu cua day:\n");
for (int i=0;i Cấu trúc lưu trữ mảng: là hình thức lƣu trữ kế Khái niệm: mảng là một tập có thứ tự gồm một số Địa chỉ các phần tử liên tiếp nhau là một cấu trúc dữ liệu Các phần tử được sắp xếp theo hàng Bộ nhớ cố định Đặc điểm: Kiểu dữ liệu mảng: 1chiều, nhiều chiều Cấu trúc đơn giản, truy cập nhanh Ví dụ: vectơ, ma trận Thiếu mềm dẻo trong các phép toán như xóa, chèn Nhập/xuất mảng Truy cập phần tử mảng Duyệt mảng (tìm kiếm một phần tử của Thêm một phần tử vào mảng (có hay ko?) Bớt một phần tử trong mảng (có hay ko?) clrscr();
int a[N];// khai bao mang kich thuoc N
for(int i=0; i for(int j=0; j • Khái niệm : danh sách là tập có thứ tự các phần tử Danh sách con: gồm các phần tử liên tiếp từ ai đến aj của 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 Ví dụ: DS = (a,b,c,d,e,f). Khi đó: (c,d,e) là một danh sách con của Danh sách con nhiều trường (field) (c,d,e,f) là một phần cuối của Danh sách con • Ví dụ: danh sách sinh viên, danh mục điện thoại (a,c,f) là một dãy con của Dãy con 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 Các trường chứa thông tin Data Next • Định nghĩa: Head: con trỏ trỏ tới nút đầu tiên Tail: Con trỏ trỏ tới nút cuối cùng (có thể không có) Trƣờng Next của nút cuối cùng chứa giá trị NULL- là địa chỉ typedef struct node{
typeData data;
struct node *next;
}node; Head … an-1 a0 a1 Chú ý: Tìm kiếm nút có giá trị là v trong danh sách Head là con trỏ trỏ tới nút đầu tiên, khi con trỏ rỗng thì Head=NULL 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 . 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 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. con trỏ mới) • Thêm một phần tử có giá trị dữ liệu là v có bốn tình huống: Thêm vào đầu danh sách
Giải thuật: Head • 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 Head v bộ nhớ 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 v (head) – 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 NULL
• Gán con trỏ Head trỏ tới nút mới • Gán con trỏ Head trỏ tới nút mới NewNode Xóa nút có giá trị v trong danh sách
Giải thuật: CurrNode 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 v 2 tình huống: NewNode Nút cần xóa ở đầu / giữa hoặc cuối danh sách Xóa nút có giá trị v … Head a0 a1 Head … a0 a1 a1 a1 Hoạt động theo nguyên tắc “Vào trƣớc ra sau” Pop Push 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 Hình ảnh minh họa: chồng sách, chồng máy Đỉnh Đáy Trình thông dịch
Một số bài toán tìm đƣờng đi trong lý thuyết 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 Khử đệ quy: bài toán đổi cơ số, bài toán in xâu Bài toán ký pháp trung/hậu tố (ký pháp Hoạt động theo nguyên tắc “vào trƣớc – ra Ví dụ minh họa: Hàng đợi thanh toán, soát vé Các thao tác cơ bản 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 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 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 3.1 Định nghĩa và khái niệm cơ bản
3.2 Cài đặt cây nhị phân
3.3 Một số phép toán trên cây nhị phân
3.5 Cây tìm kiếm 76 đó: 3.1.1 Định nghĩa
3.1.2 Các khái niệm cơ bản về cây
3.1.3 Cài đặt cấu trúc cây V: Tập hữu hạn các phần tử (nút)
E: Tập hữu hạn(cung) thể hiện mối
quan hệ phân cấp là quan hệ “
cha – con”.
Kí hiệu: T= không có nút nào 77 78 Các ví dụ về cấu trúc cây
Mục lục của một cuốn sách
Cấu trúc thư mục trên đĩa máy tính.
Sơ đồ nhân sự của tổ chức
Cây phả hệ
Dùng cây để biểu diễn biểu thức số học, chẳng hạn: ( a+b) x (c-d/e) 79 80 Số các con của một nút gọi là cấp/bậc (degree) của nút Cây có thứ tự: là cây mà có xét đến thứ tự giữa các con của một nút
Con trưởng/con cực trái của một nút: là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha Em liền kề của một nút: là nút đứng ngay sau trong quan hệ thứ đó
Nút có bậc bằng 0 gọi là nút lá (leaf)
Các nút không phải nút lá gọi là nút nhánh ( branch)
Bậc cao nhất có trong các nút của một cây gọi là bậc của cây tự giữa các nút cùng cha đó. Mức-Level: Gốc của cây có mức 1, nếu một nút có mức i Cây có nhãn: mỗi nút của cây được gán một nhãn. Nhãn
có thể là kiểu số nguyên, kiểu ký tự hay một kiểu dữ liệu
khác khác tạp hơn thì các nút con của nút đó có mức i+1.
Chiều cao (height) của cây là số mức lớn nhất của các nút có trên cây đó Rừng:Tập hợp hữu hạn các cây phân biệt gọi là một rừng 81 82 3.1.3.1 Cài đặt cây bởi mảng
3.1.3.2 Cài đặt cây bởi danh sách các con
3.1.3.3 Cài đặt cây bằng con trỏ
3.1.3.4 Ứng dụng 83 84 Nhận xét Quy ƣớc: Cho cây T có n nút Gán tên cho các nút lần lượt là 0, 1, 2, .., n-1. Khắc phục bằng qui ƣớc: Hàm PARENT(n,T) tốn chỉ một hằng thời gian Các hàm đòi hỏi thông tin về các con không làm việc tốt (vì phải tốn vòng lặp để dò tìm), vd: tìm nút con trái nhất của nút i là không thể xác định được. Dùng một mảng một chiều a để lưu trữ cây bằng cách cho
a[i].parent = j với j là nút cha của nút i. Nếu i là nút gốc ta cho
a[i].parent = -1 vì nút gốc không có cha Cách lưu trữ này chỉ phù hợp với cây mà các nút của cây khác nhau từng đôi một Nếu cây T là cây có nhãn, ta có thể dùng thêm một mảng một
chiều L chứa các nhãn của cây bằng cách cho L[i] = x với x là
nhãn của nút i, hoặc khai báo mảng a là một struct có ba trường:
trường Parent là 1 mảng giữ chỉ số các nút cha; trường Data là 1
mảng giữ nhãn của nút và một trường MaxNode giữ số nút hiện tại
đang có trên cây 85 86 Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc. Nút cha được đánh số trước các nút con. Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải 0 A Ví dụ 1 B 2 C 3 I 4 E 5 6 J D F G H 7 8 9 int MaxNode; /* Số nút thực sự trong cây */ #define MAXSIZE ... /* chỉ số tối đa của mảng */
typedef ... DataType;
typedef int Node;
typedef struct
{
DataType Data[MAXSIZE];/* Nhãn của nút trong cây */
Node Parent[MAXSIZE]; /* Cha của các nút trong cây */
} Tree; 87 88 3.1.3.2 Cài đặt cây bởi danh sách các con Quy ƣớc: Mỗi nút có một danh sách lưu nhãn các nút con.
Vì số nút con của một nút là không biết trước nên dùng danh sách liên kết. typelabel lable; // nhãn của một nút trên cây
childlist *next; 89 90 Khai báo cấu trúc dữ liệu
typedef struct childlist
{
}childlist;
typedef struct node
{
typedata data;
childlist* children;
} node;
node tree[maxsize]; Ví dụ: 3.1.3.2 Cài đặt cây bởi danh sách các con Nhận xét
Các hàm đòi hỏi thông tin về các con làm việc rất
thuận lợi, nhưng hàm PARENT lại không làm
việc tốt. Ví dụ: tìm nút cha của nút 8 đòi hỏi ta phải duyệt tất cả các danh sách chứa các nút con. 91 92 3.2.1 Cài đặt cây nhị phân bằng mảng
3.2.2 Cài đặt cây nhị phân bằng danh sách liên kết Cây nhị phân là cây mà mỗi đỉnh có tối đa 2 cây con
Cây nhị phân suy biến: cây lệch trái, cây lệch phải, cây dích dắc 93 94 Cây nhị phân hoàn chỉnh(Perfect/Full binary Cây nhị phân đầy đủ ( Complete Binary tree): là cây nhị
phân mà nếu liệt kê các nút theo trình tự từ mức thấp đến
mức cao, ở mỗi mức thì theo trình tự từ trái sang phải ta
sẽ được một dãy liên tục không khuyết nút nào. (cây đầy
đủ trái) tree): Là cây nhị phân mà mọi nút đều có đủ hai
con, trừ những nút ở mức cao nhất đều là nút lá
(không có con) 95 96 Ứng dụng của cây nhị phân Biểu diễn bằng mảng Đánh số thứ tự các nút trên cây theo thứ tự “ trên – dưới” và “trái – phải”. Biều diễn biểu thức: Tính giá trị biểu thức, tính đạo hàm
Cây quyết định
… Với nút thứ i bất kỳ: • Nút con trái của nó là 2i và
• Nút con phải là 2i+1.
• Nút cha là [i/2]. 97 98 Ví dụ Ƣu điểm: Cấu trúc mảng tạo thuận lợi khi triển khai các phép toán. Truy cập nhanh chóng vào bất cứ nút nào, chi phí truy
cập là đồng đều cho mọi nút. (từ concha và ngược
lại đều dễ dàng) Nhƣợc điểm: 99 100 Quy ước: Mỗi nút là một bản ghi bao gồm:
Trường Data lưu giữ liệu liên quan
Trường Left chứa liên kết trỏ tới nút con trái hoặc Null.
Trường Right chứa liên kết trỏ tới nút con phải hoặc Null. Nút gốc sẽ là nút đầu tiên của danh sách móc nối, các
nút lá có trường Left và Right đều chứa giá trị Null. 101 102 Khai báo cấu trúc dữ liệu 103 104 Duyệt cây nhị phân: là thực hiện một thao tác xử lý Duyệt theo thứ tự trước phần dữ liệu trong mọi nút đúng một lần. Quy tắc duyệt: nút nào cũng được „thăm‟ và mỗi nút được „thăm‟ đúng một lần. Thăm nút xử lý dữ liệu
Duyệt cây con trái theo thứ tự trước
Duyệt cây con phải theo thứ tự trước Cách duyệt: dựa theo thứ tự duyệt của nút gốc, cây con Thứ tự duyệt: abdce trái và cây con phải. Phép duyệt được thực hiện một cách
đệ quy.
Duyệt theo thứ tự trước (preorder traversal)
Duyệt theo thứ tự giữa (inorder traversal)
Duyệt theo thứ tự sau (postorder traversal) 105 106 Duyệt theo thứ tự sau: Duyệt theo thứ tự giữa Duyệt cây con trái theo thứ tự sau
Duyệt cây con phải theo thứ tự sau
Thăm nút Duyệt cây con trái theo thứ tự giữa
Thăm nút
Duyệt cây con phải theo thứ tự giữa Thứ tự duyệt: dbeca Thứ tự duyệt: bdaec 107 108 Ví dụ: Cài đặt chƣơng trình printf(“gia tri %d”,t->data);
firstorder(t->left);
firstorder(t->right); if (t==NULL) exit(0);
else
{
} void firstorder(btree t){// duyệt thứ tự trước
} 109 110 if (t==NULL) exit(0); if (t==NULL) exit(0); endorder(t->left);
endorder(t->right);
printf(“gia tri %d”,t->data); inorder(t->left);
printf(“gia tri %d”,t->data);
inorder(t->right); void inorder (btree t){// duyệt thứ tự giữa
else
{
}
} void endorder(btree t){// duyệt thứ tự sau
else
{
}
} 111 112 Ứng dụng của phép duyệt cây Tìm kiếm trên cây nhị phân Áp dụng phép duyệt trên cây để tìm các nút thỏa mã một điều kiện cho trước nào đó. Phép tìm kiếm có thể dừng ngay khi một nút thỏa mãn Tính chiều cao của cây
Tính số nút/số nút lá của cây
Tính kích thước của cây
… được tìm thấy tùy thuộc vào điều kiện tìm kiếm.
Phép tìm kiếm trên cây nhị phân thông thường có độ phức tạp tương đương với phép duyệt cây. 113 114 Một số phép toán khác trên cây nhị phân 3.4.1 Khái niệm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm Thêm một nút vào cây nhị phân.
Bớt một nút trên cây nhị phân.
Sao chép cây.
Ghép một cây thành nhánh một cây khác. 115 116 Cây nhị phân tìm kiếm là một cây nhị phân mà mỗi nút Ví dụ của nó đều được gán một giá trị khóa và mọi nút trên cây
phải thỏa mãn: Giá trị của các nút của cây con trái nhỏ hơn giá trị của nút gốc; Giá trị của các nút cây con phải lớn hơn giá trị của nút gốc; Cây con trái và cây con phải cũng là cây tìm kiếm nhị phân. Các giá trị khóa là khác nhau. 117 118 Biểu diễn giống như biểu diễn cây nhị phân nói chung Phép tìm kiếm:Có nút nào chứa giá trị bằng khóa?
Giải thuật: Các phép toán: Bắt đầu từ gốc, so sánh giá trị nút với khóa:
Bằng nhau thì Kết thúc
Nhỏ hơn thực hiện trên cây con trái
Lớn hơn thực hiện trên cây con phải Tìm kiếm
Phép chèn
Phép xóa
Tạo một cây nhị phân tìm kiếm 119 120 Phép chèn thêm một phần tử có giá trị x
Giải thuật: 4 4 Xin cấp bộ nhớ cho một nút mới,
Gán giá trị mới vào trường Data của nút mới.
Gán giá trị Null cho các trường Left và Right của nút mới.
Từ gốc, đối sánh với giá trị mới cần thêm vào:
Nếu bằng nhau kết thúc
Ngược lại duyệt theo cây con trái (nếu <) hoặc cây con phải (nếu >) 2 6 2 6 1 7 1 7 3 5 3 121 122 9 9 Nếu x có một trong hai cây con là cây rỗng thì điều chỉnh lại
con trỏ của nút cha của x bằng cách trường liên kết tương ứng thay
vì trỏ đến x thì bây giờ trỏ tới nút gốc của cây con duy nhất của x
và giải phóng bộ nhớ đã cấp cho x. 4 4 con x1. 2 2 5 Trường liên kết của nút con x1 thay vì là null nay trỏ vào nút x2 7 1 3 1 7 3 6 9 6 9 123 124 Trƣờng hợp tổng quát: 1. Thay giá trị của x bằng giá trị nút bên phải cùng
của cây con trái (hoặc bằng giá trị nút bên trái cùng
của cây con phải) 4 4 2. Cắt bỏ nút có giá trị vừa gán cho nút x. 2 2 6 5 8 1 8 1 3 3 5 9 125 126 7 7 9 Phép xóa Phép xóa 4 3 5 4 2 5 2 5 2 5 2 7 1 7 1 7 3 1 7 1 6 9 3 3 127 128 6 6 9 9 6 9 Tất cả các thao tác Search, Insert, Del đều có độ phức tạp trung bình O(h), với h là chiều cao của cây Trong trường hợp tốt nhất, cây nhị phân tìm kiếm là cây
đầy đủ có n đỉnh thì sẽ có độ cao h = log(n). Chi phí tìm
kiếm sẽ tương đương tìm kiếm nhị phân trên mảng có
thứ tự. Trong trường hợp xấu nhất, cây có thể bị suy biến thành
1 danh sách liên kết (khi mà mỗi đỉnh đều chỉ có 1 con
trừ đỉnh lá). Các thao tác có độ phức tạp O(n). 130 129 Cấu trúc dữ
liệu và giải
thuật {1,9,7,2,5} {1,2,5,7,9}
{ “Dƣơng”, “Hƣơng” ,“An”, “Bình” }
{“An”, “Bình”, “Dƣơng”, “Hƣơng”} 131 132 Cấu trúc dữ
liệu và giải
thuật Việc sắp xếp là một bài toán phổ biến trong tin học. Khóa sắp xếp Do các yêu cầu tìm kiếm thuận lợi, sắp xếp kết xuất cho Một bộ phận của bản ghi biểu diễn đối tƣợng đƣợc sắp xếp.
Khóa sẽ đƣợc sử dụng để xác định thứ tự sắp xếp bản ghi trong một Dữ liệu thƣờng đƣợc tổ chức thành các bản ghi. Bảng khóa Mỗi bản ghi thƣờng có một số các trƣờng dữ liệu khác Sử dụng trong sắp xếp khi muốn hạn chế việc di chuyển các dữ liệu.
Một tập hợp các bản ghi chỉ chứa 2 trƣờng: Trƣờng tham gia quá trình tìm kiếm gọi là khóa. Khóa: Chứa khóa sắp xếp.
Link: Con trỏ ghi địa chỉ của bản ghi đối tƣợng dữ liệu tƣơng ứng.
Thứ tự các bản ghi trong bảng khóa cho phép xác định thứ tự các 133 134 • Các phần tử có cùng khóa sẽ giữ nguyên thứ tự tương đối của chúng như trước khi sắp xếp Tính tại chỗ: 135 136 Cấu trúc dữ
liệu và giải
thuật Cấu trúc dữ
liệu và giải
thuật Ý tưởng: Bài toán sắp xếp đƣợc đơn giản hóa dƣới dạng nhƣ Tại mỗi lượt, chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp. Đưa phần tử được chọn vào vị trí đúng bằng phép đổi chỗ. các khóa được sắp xếp theo thứ tự tăng dần. Sau lượt thứ i (i = 1..n-1), dãy cần sắp coi như được chia thành 2 phần: • Phần đã sắp: từ vị trí 1 i • Phần chưa sắp: từ vị trí i +1 n 137 138 Cấu trúc dữ
liệu và giải
thuật Cấu trúc dữ
liệu và giải
thuật Ví dụ: sắp xếp dãy sau theo thứ tự tăng dần: A = { 12, 5, 3, 10, 18, 4, 9, 16} Lượt 1 Lượt 2 Lượt 3 Lượt 4 Lượt 5 Lượt 6 Lượt 7 12 3 3 3 3 3 3 3 5 5 4 4 4 4 4 4 3 12 12 5 5 5 5 5 10 10 10 10 9 9 9 9 18 18 18 18 18 10 10 10 4 4 5 12 12 12 12 12 9 9 9 9 10 18 18 16 139 140 16 16 16 16 16 16 16 18 Ví dụ: sắp xếp dãy sau theo thứ tự tăng dần: Ý tưởng: Dãy cần sắp được chia thành 2 phần: một là phần đã sắp, còn lại là phần chưa sắp Tại mỗi lượt, phần tử đầu tiên trong phần chưa sắp sẽ
được “thêm” vào đúng vị trí của nó trong phần đã sắp. 141 142 A = { 12, 5, 3, 10, 18, 4, 9, 16} Lượt 1 Lượt 2 Lượt 3 Lượt 4 Lượt 5 Lượt 6 Lượt 7 12 5 3 3 3 3 3 3 5 12 5 5 5 4 4 4 3 3 12 10 10 5 5 5 10 10 10 12 12 10 9 9 18 18 18 18 18 12 10 10 4 4 4 4 4 18 12 12 9 9 9 9 9 9 18 16 16 16 16 16 16 16 16 18 Cấu trúc dữ
liệu và giải
thuật Ý tưởng: Dãy cần sắp được chia thành 2 phần: một là phần đã sắp, còn lại là phần chưa sắp Thông qua phép đổi chỗ, tại mỗi lượt phần tử nhỏ nhất
trong phần chưa được sắp sẽ được “đẩy dần” lên trước và
cuối cùng nhập vào phần được sắp void INSERTION-SORT(int A[], int n){ A[j] := A[j-1]; j := j -1; 144 143 //Chọn phần tử đầu tiên của phần chƣa đƣợc sắp xếp
int val = A[i];
int j = i;
/* Tìm vị trí thích hợp đề chèn phần tử A[i] trong phần đã
sắp- chứa các phần tử từ vị trí 1 đến i-1 */
while ( j > 0 & A[j-1] > val)
{
}
// Chèn phần tử A[i] vào vị trí thích hợp
A[j] := val; for( int i = 1; i< n; i++) {
} } Cấu trúc dữ
liệu và giải
thuật Ví dụ: sắp xếp dãy sau theo thứ tự tăng dần: A = { 12, 5, 3, 10, 18, 4, 9, 16} Lượt 1 Lượt 2 Lượt 3 Lượt 4 Lượt 5 Lượt 6 Lượt 7 12 3 3 3 3 3 3 3 5 12 4 4 4 4 4 4 3 5 12 5 5 5 5 5 10 4 5 12 9 9 9 9 18 10 9 9 12 10 10 10 4 18 10 10 10 12 12 12 9 9 18 16 16 16 16 16 16 16 16 18 18 18 18 18 145 146 Sắp xếp lựa chọn (Selection Sort) Sắp xếp chèn (Insertion Sort) Thời gian thực hiện thuật toán: Sắp xếp chèn là tại chỗ và ổn định • Trường hợp tốt nhất: Thời gian thực hiện thuật toán: • Trường hợp tốt nhất: • Trường hợp xấu nhất: • Trường hợp xấu nhất: Độ phức tạp thời gian trung bình: O(n2) Độ phức tạp thời gian trung bình: O(n2) 147 148 – Dãy ban đầu đã được sắp xếp. – 0 phép đổi chỗ, chỉ thực hiện n(n-1)/2 phép so sánh. – Dãy ban đầu đã được sắp xếp. – 0 phép đổi chỗ, chỉ thực hiện n(n-1)/2 phép so sánh. – n-1 phép đổi chỗ, n(n-1)/2 phép so sánh. – n(n-1)/2 phép so sánh và đổi chỗ. Sắp xếp nổi bọt (Bubble Sort) Thời gian thực hiện thuật toán: • Trường hợp tốt nhất: Độ phức tạp thời gian trung bình: O(n2) 150 149 – Dãy ban đầu đã được sắp xếp. – 0 phép đổi chỗ, chỉ thực hiện n(n-1)/2 phép so sánh. • Trường hợp xấu nhất: – n(n-1)/2 phép so sánh và đổi chỗ. Cấu trúc dữ
liệu và giải
thuật Tìm kiếm là thuật toán tìm 1 phần tử có giá trị cho Tìm kiếm tuần tự Mô tả Các phần tử trong tập đầu vào không được sắp xếp theo khóa tìm kiếm Duyệt dãy (danh sách, hàng đợi , v…v ) chứa các phần tử trong tập So sánh với khóa cần tìm tới khi tìm thấy khóa hoặc duyệt qua hết mảng mà chưa tìm thấy Trả lại chỉ số phần tử trong dãy (nếu thấy) 151 152 Cấu trúc dữ
liệu và giải
thuật Cấu trúc dữ
liệu và giải
thuật Độ phức tạp Trường hợp tốt nhất: O(1) Trường hợp tồi nhất: O(n) Trường hợp trung bình: O(n) 154 153 Cấu trúc dữ
liệu và giải
thuật Tìm kiếm nhị phân Sử dụng cho việc tìm kiếm trên mảng đã được sắp xếp Mô tả • Chọn phần tử “ở giữa” dãy – A[k] để thực hiện so sánh với giá trị cần tìm • Nếu key = A[k] thì tìm thấy, kết thúc • Nếu key < A[k] thì tìm trên nửa đầu của mảng đã cho • Nếu key > A[k] thì tìm trên nửa sau của mảng đã cho 155 156 Cấu trúc dữ
liệu và giải
thuật 157 158 Tìm kiếm nhị phân tìm kiếm nhanh hơn tìm kiếm tuần 159 Cấu trúc dữ
liệu và giải
thuật1.2.3 Thiết kế và phân tích giải thuật
1.2.3 Thiết kế và phân tích giải thuật
Quyết định chất lượng chương trình
Ý nghĩa: Sự đa dạng và phức tạp của các bài toán
cần sử dụng nguồn nhân lực lớn hơn
thời gian để thử nghiệm, bảo trì và mở rộng hệ thống
chiếm phần đáng kể so với thời gian xây dựng CT.
6
8/15/2017
Ví dụ
Ví dụ
lại B1 và B2
Ví dụ
Ví dụ
7
8/15/2017
1.2.3 Thiết kế và phân tích giải thuật
1.2.3 Thiết kế và phân tích giải thuật
Module hóaChia để trị (divide and conquer/top-down)
Phương pháp tham lam (greedy)
Phương pháp quy hoạch động (dynamic programming)
Phương pháp nhánh cận (branch and bound)
Phương pháp quay lui (backtracking)
1.2.3 Thiết kế và phân tích giải thuật
1.2.3 Thiết kế và phân tích giải thuật
8
8/15/2017
1.2.3 Thiết kế và phân tích giải thuật
Quy tắc cộng: Nếu P1 có T1(n) = O(f(n)) và P2 có
T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)).
Quy tắc nhân: Nếu P có T(n)= O(f(n)). Khi đó nếu
thực hiện k(n) lần P với k(n)=O(g(n)) thì độ phức tạp là
O(f(n) g(n)).
Áp dụng đánh giá chương trình
Câu lệnh đơn thực hiện một thao tác
QT hằng số: T(n)= O(c).
Câu lệnh hợp thành là một dãy các câu lệnh
- T(n)= O(n)
9
8/15/2017
1.2.4 Giải thuật đệ quy
1.2.4 Giải thuật đệ quy
1.2.4 Giải thuật đệ quy
1.2.4 Giải thuật đệ quy
Tìm từ trong từ điển
Tìm tệp trong tệp trên máy tính
10
8/15/2017
1.2.4 Giải thuật đệ quy
1.2.2 Ngôn ngữ diễn đạt giải thuật
CHƢƠNG 2:
Một số cấu trúc dữ liệu cơ bản
11
8/15/2017
2.1 Mảng (Array)
Nội dung
2.1.1 Khái niệm
2.1 Mảng
2.1.2 Một số phép toán trên mảng
2.2 Danh sách
2.1.3 Cài đặt mảng 1 và 2 chiều
2.3 Ngăn xếp
2.4 Hàng đợi
2.1.1 Khái niệm
2.1.1 Khái niệm
tiếp
cố định các phần tử cùng kiểu 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
12
8/15/2017
2.1.2 Một số phép toán trên mảng
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
mảng)
}
( Sinh viên tự cài đặt)
2.2 Danh sách (List)
2.1.3 Cài đặt mảng 1 chiều và 2 chiều
#define N 10
#define M 5
void main() { //cài đặt một mảng 2 chiều, kích thước
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
cho trước
int a[N][M];// khai bao mang kich thuoc NxM
for(int i=0; i
}
13
8/15/2017
2.2.1 Khái niệm
2.2.1 Khái niệm
danh sách
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
số phần tử.
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
2.2.3 Cài đặt danh sách liên kết
2.2.2 Phân loại danh sách
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.
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
A
14
8/15/2017
2.2.3 Cài đặt danh sách liên kết
2.2.3 Cài đặt danh sách liên kết
đặc biệt
free(p);
• Tạo nút mới:
node* p=malloc(sizeof(node));
• Giải phóng nút:
• Khai báo một con trỏ:
node *head;
2.2.3 Cài đặt danh sách liên kết
2.2.4 Một số phép toán trên danh sách
15
8/15/2017
2.2.4 Một số phép toán trên danh sách
2.2.4 Một số phép toán trên danh sách
Thêm vào danh sách rỗng/ đầu/giữa và
cuối danh sách
2.2.4 Một số phép toán trên danh sách
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
Giải thuật:
-Tìm nút thứ index – currNode
-Tạo nút mới
-Móc nối nút mới vào danh sách
16
8/15/2017
2.2.4 Một số phép toán trên danh sách
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
2.3.1 Khái niệm
2.3.1Khá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
(LIFO)
tính, hộp chứa đạn súng trƣờng
17
8/15/2017
2.3.3 Ứng dụng
2.3.2 Cài đặt ngăn xếp
đồ thị
đảo ngƣợc
Balan)
2.4.1 Khái niệm
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
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.
trƣớc” (FIFO)
18
8/15/2017
2.4.1 Khái niệm
2.4.2 Cài đặt hàng đợi
CHƢƠNG 3: Cây và Cây tìm kiếm
2.4.3 Ứng dụng
Chương 3. Cây
19
8/15/2017
3.1.1 Định nghĩa
3.1 Định nghĩa và khái niệm cơ bản
Cây: (Tree)
Cây T là một bộ
Chương 3. Cây
Chương 3. Cây
3.1.1 Định nghĩa
3.1.1 Định nghĩa
x
-
+
/
c
a
b
d
e
Chương 3. Cây
Chương 3. Cây
20
8/15/2017
3.1.2 Các khái niệm cơ bản về cây
3.1.2 Các khái niệm cơ bản về cây
(forest).
Chương 3. Cây
Chương 3. Cây
3.1.2 Các khái niệm cơ bản về cây
3.1.3 Cài đặt cấu trúc cây
1
A
2
D
B
C
3
E
F
G
H
I
4
J
K
Chương 3. Cây
Chương 3. Cây
21
8/15/2017
3.1.3.1 Cài đặt cây bởi mảng
3.1.3.1 Cài đặt cây bởi mảng
Chương 3. Cây
Chương 3. Cây
3.3.1 Cài đặt cây bởi mảng
3.1.3.1 Cài đặt cây bởi mảng
Khai báo cấu trúc dữ liệu
Chương 3. Cây
Chương 3. Cây
22
8/15/2017
3.1.3.1 Cài đặt cây bởi mảng
Cài đặt các phép toán
(yêu cầu sv viết chương trình)
Chương 3. Cây
Chương 3. Cây
3.1.3.2 Cài đặt cây bởi danh sách các con
Chương 3. Cây
Chương 3. Cây
23
8/15/2017
Khái niệm
3.2 Cài đặt cây nhị phân
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
Chương 3. Cây
Chương 3. Cây
Khái niệm
Khái niệm
Chương 3. Cây
Chương 3. Cây
24
8/15/2017
Khái niệm
3.2.1 Biểu diễn cây nhị phân bằng mảng
Chương 3. Cây
Chương 3. Cây
3.2.1 Biểu diễn cây nhị phân bằng mảng
3.2.1 Biểu diễn cây nhị phân bằng mảng
1
1
2
3
4
5
6
7
A
A B E C D F G
2
3
B
E
C
D
F
G
Lãng phí bộ nhớ nếu cây gầy, khuyết nhiều nút
4
5
6
7
Chương 3. Cây
Chương 3. Cây
25
8/15/2017
3.2.2 Cài đặt cây nhị phân bằng danh sách liên kết
3.2.2 Cài đặt cây nhị phân bằng danh sách liên kết
Chương 3. Cây
Chương 3. Cây
3.3 Một số phép toán trên cây
3.2.2 Cài đặt cây nhị phân bằng danh sách liên kết
3.3.1 Duyệt cây
3.3.2 Tìm kiếm trên cây
3.3.3 Một số phép toán khác
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
typedef node *btree;
Chương 3. Cây
Chương 3. Cây
26
8/15/2017
3.3.1 Duyệt cây
3.3.1 Duyệt cây
Chương 3. Cây
Chương 3. Cây
3.3.1 Duyệt cây
3.3.1 Duyệt cây
Chương 3. Cây
Chương 3. Cây
27
8/15/2017
3.3.1 Duyệt cây
3.3.1 Duyệt cây
Chương 3. Cây
Chương 3. Cây
3.3.1 Duyệt cây
3.3.1 Duyệt cây
Chương 3. Cây
Chương 3. Cây
28
8/15/2017
3.3.1 Duyệt cây
3.3.2 Tìm kiếm trên cây
Chương 3. Cây
Chương 3. Cây
3.3.2 Một số phép toán khác
3.4 Cây tìm kiếm
Chương 3. Cây
Chương 3. Cây
29
8/15/2017
3.4.1 Khái niệm
3.4.1 Khái niệm
Chương 3. Cây
Chương 3. Cây
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Chương 3. Cây
Chương 3. Cây
30
8/15/2017
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Phép xóa
Nếu nút x là nút lá ta chỉ cần “cắt bỏ” x
Chương 3. Cây
Chương 3. Cây
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Phép xóa
Nếu nút x có hai cây con (có gốc tương ứng là x1 và x2)
và một trong hai cây con (chẳng hạn x1) không có con
thì ta thay nút x1 làm nút cha của cây con có gốc là x2.
Ta thay đổi trường liên kết như sau:
Trường liên kết nút cha của x thay vì trỏ tới x thì nay trỏ tới nút
Chương 3. Cây
Chương 3. Cây
31
8/15/2017
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Vì nút được lựa chọn để thay thế là bên phải/ trái cùng
nên không thể có hai con, việc cắt bỏ nó sẽ thực hiện
theo các cách đã nêu trên
Chương 3. Cây
Chương 3. Cây
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Chương 3. Cây
Chương 3. Cây
32
8/15/2017
3.4.2 Cài đặt và phép toán trên cây tìm kiếm
Chƣơng 4
4.1 Bài toán sắp xếp và một số phƣơng pháp sắp xếp đơn giản
4.1.1 Khái quát về sắp xếp
4.1.2 Sắp xếp lựa chọn
4.1.3 Sắp xếp chèn
4.1.4 Sắp xếp nổi bọt
4.1.5 Độ phức tạp của các phép sắp xếp cơ bản
4.2 Bài toán tìm kiếm
4.2.1 Tìm kiếm tuần tự (Sequential Searching)
4.2.2 Tìm kiếm nhị phân (Binary Searching)
4.2.3 Độ phức tạp
Chương 3. Cây
4.1 Bài toán sắp xếp và một số phương
pháp sắp xếp đơn giản
4.1.1. Khái quát về sắp xếp
Sắp xếp là quá trình bố trí lại các phần tử của một tập
đối tƣợng nào đó theo thứ tự nhất định (tăng hoặc giảm
dần).
Ví dụ:
4.1.1 Khái quát về sắp xếp
4.1.2 Sắp xếp lựa chọn (Selection Sort)
4.1.3 Sắp xếp chèn (Insertion Sort)
4.1.4 Sắp xếp nổi bọt (Bubble Sort)
4.1.5 Độ phức tạp của các phép sắp xếp đơn giản
Cấu trúc dữ liệu và giải thuật
33
8/15/2017
4.1.1. Khái quát về sắp xếp
4.1.1. Khái quát về sắp xếp
các bảng biểu,…
tập các bản ghi
nhau.
bản ghi dữ liệu.
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
4.1.1. Khái quát về sắp xếp
4.1.1. Khái quát về sắp xếp
Một số phƣơng pháp sắp xếp
Các đặc trƣng của thuật toán sắp xếp:
Tính ổn định của thuật toán sắp xếp
Thuật toán đòi hỏi không gian nhớ phụ là hằng số
(không phụ thuộc vào số lƣợng phần tử trong dãy cần
sắp)
34
8/15/2017
4.1.1. Khái quát về sắp xếp
4.1.2 Sắp xếp lựa chọn (Selection Sort)
sau:
Đầu vào: Một dãy các số nguyên (các khóa)
Đầu ra: Một hoán vị của dãy số đã cho trong đó giá trị
4.1.2 Sắp xếp lựa chọn (Selection Sort)
4.1.2 Sắp xếp lựa chọn (Selection Sort)
if ( A[j] < A[min]) min = j ;
int i;
for (i = 0 ; i
void SELECTION-SORT(int A[], int n)
{
}
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
35
8/15/2017
4.1.3 Sắp xếp chèn (Insertion Sort)
4.1.3 Sắp xếp chèn (Insertion Sort)
Cấu trúc dữ liệu và giải thuật
4.1.4 Sắp xếp nổi bọt (Bubble Sort)
4.1.3 Sắp xếp chèn (Insertion
Sort)
Cấu trúc dữ liệu và giải thuật
36
8/15/2017
4.1.4 Sắp xếp nổi bọt (Bubble Sort)
4.1.4 Sắp xếp nổi bọt (Bubble Sort)
void BUBBLE-SORT(int A[], int n) {
for ( int i = 1; i< n-1; i++ ) {
// Duyệt từ cuối dãy
for ( int j = n-1 ; j>i; j--)
/* Kiểm tra 2 phần tử kề cận nhau, nếu ngƣợc thứ tự
thì đổi chỗ */
if (A[j] < A[j-1]){
int X:= A[j]; A[j] := A[j-1]; A[j-1] := X;
}
}
}
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
4.1.5 Độ phức tạp
4.1.5 Độ phức tạp
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
37
8/15/2017
4.1.5 Độ phức tạp
4.2 Bài toán tìm kiếm
4.2.1 Khái quát về tìm kiếm
4.2.2 Tìm kiếm tuần tự (Sequential Searching)
4.2.3 Tìm kiếm nhị phân (Binary Searching)
4.2.4 Độ phức tạp
Cấu trúc dữ liệu và giải thuật
4.2.2 Tìm kiếm tuần tự (Sequential Searching)
4.2.1 Khái quát về tìm kiếm
trƣớc trong một tập các phần tử
Khóa tìm kiếm: Một bộ phận của các phần tử
trong tập mà giá trị của nó đƣợc sử dụng để so
sánh và tìm kiếm
38
8/15/2017
4.3.2 Tìm kiếm tuần tự
4.2.2 Tìm kiếm tuần tự
Function SEQUENTIAL(A, n, key)
{tìm phần tử có khóa key trong mảng A gồmn phần tử.
Giải thuật tìm kiếm tuần tự không phụ thuộc vào thứ tự
của các phần tử trong mảng, do vậy đây là phƣơng pháp
tổng quát nhất để tìm kiếm trên một dãy bất kỳ
Kết quả trả ra: -1 nếu không tìm thấy phần tử có khóa
key, chỉ số của phần tử nếu tìm thấy}
1. i:= 1;
Một thuật toán có thể đƣợc cài đặt theo nhiều cách khác
nhau, kỹ thuật cài đặt ảnh hƣởng nhiều đến tốc độ thực
hiện.
2. while (i <= n ) and (A[i] <> key) do i:= i + 1;
3. if (i> n) then return -1 { không thấy};
4. else
return i{tìm thấytạivị trí i}
Cấu trúc dữ liệu và giải thuật
4.2.3 Tìm kiếm nhị phân
4.2.3 Tìm kiếm nhị phân (Binary Searching)
Function BINARY-SEARCH(A,l, r, key)
1. if (l> r) return -1;
2. m = (l+r) /2 ;
3. if (A[m] = key ) then
return m ;
4. else if (A[m] > key) then
return BINARY-SEARCH(A,l,m-1,key);
5. else
return BINARY-SEARCH(A, m+1, r, key);
Cấu trúc dữ liệu và giải thuật
39
8/15/2017
4.2.3 Tìm kiếm nhị phân
4.2.3 Tìm kiếm nhị phân
void BINARY-SEARCH(int A[], int l, int r, int key) {
if (l> r) return -1;
m = floor ((l+r) /2) ;
if (A[m] == key ) return m ;
r= m-1;
else if (A[m] > key)
l= m+1
return BINARY-SEARCH(A,l,m-1,key);
//Tìm chỉ số của phần tử ở giữa
int m= floor((l+r) / 2);
if ( key < A[m])
else
if ( key > A[m])
else return m;
else
return BINARY-SEARCH(A, m+1, r, key);
}
void BINARY-SEARCH(int A[], int n, int key) {
int l=0, r = n-1 ;
while ( l <= r ) {
}
return -1; // Không tìm thấy
}
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
4.2.4 Độ phức tạp
Tìm kiếm dựa vào quan hệ giá trị của các phần tử
trong mảng để định hƣớng trong quá trình tìm kiếm,
do vậy chỉ áp dụng đƣợc với dãy đã có thứ tự.
tự.
Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải
quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi
mảng đƣợc sắp thứ tự rồi thì mới tìm kiếm nhị phân.
40
