C programming. 2003 - 2005
1
C programming. 2003 - 2005
2 THUẬT TOÁN

THUẬT TOÁN TRÊN CẤU TRÚC CÂY
C programming. 2003 - 2005
3
Giới thiệu

Thuật toán - Thuật giải (Algorithm) là phương pháp để giải một bài
toán.
Cấu trúc dữ liệu (Data structure): cách lưu trữ thông tin.

Các thuật toán hiệu quả dùng những cấu trúc dữ liệu được tổ chức
tốt.

Trong chương trình, chúng ta sẽ nghiên cứu các thuật toán sau:
- sắp xếp (sorting)
- tìm kiếm (searching)
-

Sử dụng máy tính trong công việc, con người luôn mong muốn
- máy tính chạy càng ngày càng nhanh hơn
- xử lý được nhiều dữ li


Đối với một thuật toán, chúng ta thường quan tâm đến các yếu tố
sau.
Kích thước, dung lượng của dữ liệu đầu vào: N
Th
ời gian thực hiện. Thường tỉ lệ với:
1
log N
N
N log N
N
2

2
NĐôi khi chúng ta cũng gặp các tỉ lệ khác như:
log log N (log(log(N))
log* N số các log cho đến khi đạt đến 1

Thường thì người ta sẽ viết ra các công thức ước lượng thời gian
chạy trong các trường hợp:
C programming. 2003 - 2005
5
- xấu nhất (đây là trường hợp đảm bảo thuật toán không vượt
qua ngưỡng này)
- trung bình (mang tính ước lượng)

Việc phân tích phụ thuộc vào các thông tin chi tiết trên

3 * N
2
+ 5 ≤ 4 * N
2

nghĩa là T(N) là O(N
2
).
C programming. 2003 - 2005
6
Biểu Diễn Xếp Chồng (Stack) Bằng Cấu Trúc DSLK

Các thao tác trên Stack đã được giới thiệu trong phần trước.

Chúng ta sẽ cài đặt Stack bằng DSLK typedef struct intListNode * IntListPtr;

typedef struct intListNode
{ int data;

if (new == NULL)
{
return 0; /* FAILURE */
}
new->data = num;
new->next = ps->top;
ps->top = new;
ps->size++;
return 1; /* success */
}

/* Cach 1 */
int PopStack (IntStack * ps)
{
IntListPtr temp;

if (ps->top == NULL)
{
return 0; /* FAILURE */
}
temp = ps->top;
ps->top = ps->top->next;
free (temp);
ps->size ;
return 1; /* success */
}

int TopStack (IntStack * ps)
{ /* assume that stack is not empty */
return ps->top->data;

IntStack s;

MakeStack(s);

PushStack(&s, 1);
PushStack(&s, 1);
PushStack(&s, 1);

while(!IsEmptyStack(&s))
{
printf(“%d\n”, TopStack(&s));
PopStack(&s); // su dung PopStack cach 1
}

FreeStack(&s);

return EXIT_SUCCESS;
}

Trong trường hợp sử dụng PopStack cách 2, đoạn mã trên cần
sửa lại như sau:

PushStack(&s, 1);

while(PopStack(&s,&I))
{
printf(“%d\n”, I);
}

C programming. 2003 - 2005

front rear size
3
data+next
1
data+next
2
data+next
3
null
front rear size
3
Prev+Data+Next
null 1
Prev+Data+Next
2
Prev+Data+Next
3 null
C programming. 2003 - 2005

printf ("%d\n", glptr->data);
}
else
{ /* sub-list */
DisplayIntGenList (glptr->subList);
}
glptr = glptr->next;
}
}
Hea
dSize
1 null 2 null ? 5 null null
3 null
4 null null
C programming. 2003 - 2005
11
Sắp xếp (Sorting)

Các thuật toán sắp xếp cơ bản

Insertion Sort - Sắp xếp bằng cách chèn
Selection Sort - Sắp xếp bằng cách chọn
nghĩa hàm con (subroutine).
- Macro: đơn giản, chi phí thấp
- Hàm con: tổng quát hơn, nhưng tốn kém hơn C programming. 2003 - 2005
13

Selection sort - Sắp xếp bằng cách chọn

A S O R T I N G E X A M P L E
A S O R T I N G R X A M P L E
A A O R T I N G E X S M P L E
A A E R T I N G O X S M P L E
A A E E T I N G O X S M P L R
A A E E G I N T O X S M P L R
A A E E G I N T O X S M P L R
A A E E G I L T O X S M P N R
A A E E G I L M O X S T P N R
A A E E G I L M N X S T P O R
A A E E G I L M N O S T P X R
A A E E G I L M N O P T S X R
A A E E G I L M N O P R S X T
A A E E G I L M N O P R S X T
A A E E G I L M N O P R S TX
A A E E G I L M N O P R S T X


A E G I N O R S T X A M P L E
A E G I N O R S T X A M P L E
A A E G I N O R S T X M P L E
A A E G I M N O R S T X P L E
A A E G I M N O P R S T X L E
A A E G I L M N O P R S T X E
A A E E G I L M N O P R S T X
A A E E G I L M N O P R S T X
void insertion (itemType a[], int l, int r)
{
int i, j;

for (i = l+1; i <= r; i++)
{
itemType v = a[i];
j = i;
while (j>l && less(v, a[j-1]))
{ a[j] = a[j-1]; j ; }
a[j] = v;
}
} C programming. 2003 - 2005
15
Bubble sort - Sắp xếp theo nguyên lý nổi bọt


- nổi bọt hai chiều. C programming. 2003 - 2005
16
Tính chất của các giải thuật sắp xếp cơ bản

Thời gian chạy là bậc 2.

Selection sort:
số lần so sánh: N-1 + N-2 + . . . + 2 + 1 = N^2/2
số lần hoán vị: N

Insertion sort:
số lần so sánh: (N-1 + N-2 + . . . + 2 + 1) / 2 = N^2/4
số lần hoán vị: N^2/4

Bubble sort:
số lần so sánh: N-1 + N-2 + . . . + 2 + 1 = N^2/2
số lần hoán vị: khoảng N^2/2

Với bộ dữ liệu trong đó các bản ghi có kích thước lớn, khóa nhỏ
selection sort tăng tuyến tính theo số các bản ghi
N bản ghi M từ (khóa là mộ
t từ)
số lần so sánh: N^2/2
số lần hoán vị: NM
if N tỉ lệ với M
chi phí và số bản ghi tỉ lệ với:


typedef int itemType

#define less(A, B) (data[A].key < data[B].key)
#define exch(A, B) {itemType t = A; A = B; B = t;}

Trong trường hợp dùng con trỏ đến các bản ghi

typedef dataType* itemType
#define less(A, B) (*A.key < *B.key)
#define exch(A, B) {itemType t = A; A = B; B = t;} C programming. 2003 - 2005
18
Sắp xếp với các bản ghi có hai khóa

Sắp xếp theo khóa thứ nhất, sau đó sắp tiếp theo khóa thứ 2

Aaron 4 Fox 1
Andrews 3 Quilici 1
Battle 4 Chen 2
Chen 2 Furia 3
Fox 1 Kanaga 3
Furia 3 Andrews 3
Gazsi 4 Rohde 3
Kanaga 3 Battle 4
Quilici 1 Aaron 4
Rohde 3 Gazsi 4

Sắp xếp theo khóa thứ 2, nếu bằng nhau thì dừng lại, thực hiện

A I O R E L N G P S A M T X E

A I N R E L O G P S A M T X E
A I A R E L N G P S O M T X E
A I A R E L E G P S N M T X O

A I A G E L E R P S N M T X O
A I A G E L E M P S N R T X O

A I A G E L E M P S N R T X O

C programming. 2003 - 2005
20
Sắp xếp đan xen bộ 4

Sử dụng thuật toán sắp xếp chèn với bước tăng là 4

A S O R T I N G E X A M P L E
A I O R T S N G E X A M P L E
A I N R T S O G E X A M P L E
A I N G T S O R E X A M P L E

Shellsort
Sử dụng các bước tăng giảm dần

A S O R T I N G E X A M P L E
A S O R T I N G E X A M P L E
A E O R T I N G E X A M P L S

A E O R T I N G E X A M P L S
A E O R T I N G E X A M P L S
A E N R T I O G E X A M P L S
A E N G T I O R E X A M P L S
A E N G E I O R T X A M P L S
A E N G E I O R T X A M P L S
A E A G E I N R T X O M P L S
A E A G E I N M T X O R P L S
A E A G E I N M P X O R T L S
A E A G E I N M P L O R T X S
A E A G E I N M P L O R T X S

A E A G E I N M P L O R T X S
A A E
G E I N M P L O R T X S
A A E G E I N M P L O R T X S
A A E E G I N M P L O R T X S
A A E E G I N M P L O R T X S
A A E E G I N M P L O R T X S
A A E E G I M N P L O R T X S
A A E E G I M N P L O R T X S
A A E E G I L M N P O R T X S
A A E E G I L M N O P R T X S

while(j >= h && less(v, a[j-h]))
{ a[j] = a[j-h]; j -= h; }
a[j] = v;
}
}
}

Thuật toán Shellsort có tốc độ sắp xếp nhanh, cài đặt đơn giản; rất
thích hợp với các tập tin nhỏ và vừa, với các tập tin lớn, thuật toán
Shellsort vẫn có hiệu suất thực hiện rất cao.

Tỉ lệ tăng nào là thích hợp?
• có nhiều tỉ lệ đã được chứng minh hiệu quả.
• dễ chọn nhất là dùng: 1, 4, 13, 40, 121, 363, 1090, C programming. 2003 - 2005
23
Thuật toán CombSoft

Giả sử chúng ta sắp xếp tăng dần một danh sách bằng thuật toán
nổi bọt.
Thuật toán sắp xếp nổi bọt có một nhược điểm là nếu phần tử
tương đối nhỏ nằm ở gần cuối danh sách thì sẽ di chuyển rất chậm

Cài đặt thuật toán

#define SHRINKFACTOR 1.3
comb_sort(itemType a[], int size)
{
int switches, i, j, top, gap;

gap = size;
do {
gap = (int) ((float)gap/SHRINKFACTOR);
switch (gap)
{
case 0: /* the smallest gap is 1 bubble sort */
gap = 1;
break;
case 9:
case 10:
gap = 11;
break;
default:
break;
}
switches = 0; /* dirty pass flag */
top = size - gap;
for(i=0; i<top; ++i)
{
j = i + gap;
if(a[i] > a[j])
{ /* swap */
exch(a[i], a[j]);

A

L I N G O P M R X T S
L I G M O P N
G I L
I L
I
N P O
O P
P
S T X
TX
T
A A E E G I L M N O P R S T X

C programming. 2003 - 2005
26
Phân vùng (partitioning)
Để phân vùng một mảng trước khi thực hiện sắp xếp, đầu tiên,
chúng ta chọn ra một phần tử làm mốc a[i
0
]
• quét mảng từ bên phải sang để tìm phần tử nhỏ hơn a[i
0

j: vị trí dò từ phải sang trái.

int partition(Item a[], int l, int r)
{
int i, j;
Item v;
v = a[r]; i = l-1; j = r;
for( ; ; )
C programming. 2003 - 2005
27
{
while(less(a[++i], v));
while(less(v, a[ j]));
if(j == l) break;
if(i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}

Cài Đặt Quicksort

quicksort (Item a[], int l, int r)
{
int i;
if(r > l)
{
i = partition(a, l, r);
quicksort(a, l, i-1);

r = pop(); l = pop();
if(r <= l) continue;
i = partition(a, l, r);
if(i-l > r-i)
{ push2(l, i-1); push2(i+1, r); }
else
{ push2(i+1; r); push2(l, i-1); }
}
}

Với cài đặt trên, trong trường hợp xấu nhất, chúng ta có thể đạt
được mức chi phí bộ nhớ nhỏ hơn (lg N) nhưng thời gian chạy thì
vẫn ở tỉ lệ bình phương.

Phân tích thuật toán

Tổng thời gian chạy là tổng của
chi_phí * tần_suất
của tất cả các phép toán cơ bản.

chi_phí (cost) phụ thuộc vào kiểu máy tính
tần_suất (frequency) phụ thuộc vào thuật toán và loại dữ
liệu đầu
vào.

C programming. 2003 - 2005
29
Đối với thuật toán Quicksort, gọi
A là số lần thực hiện phân vùng.
B là số lần hoán vị

Tìm Kiếm Trên Mảng Đã Có Thứ Tự
Bài toán: tìm x trong một mảng.
Điều kiện: mảng đã được sắp thứ tự tăng (giảm) dần
Các hàm tìm kiếm sẽ trả về -1 nếu x không xuất hiện trong dãy,
ngược lại, các hàm tìm kiếm sẽ trả về chỉ số của x trong dãy.

Tìm kiếm theo phương pháp lặp

Do dãy số đã có thứ tự tăng dần, nên nếu tìm được phầ
n tử đầu
tiên có giá trị lớn hơn x thì có thể kết luận dãy số không chứa phần
tử x. Vì vậy, chúng ta có thể rút ngắn thời gian tìm kiếm.

Cài đặt thuật toán

int search(int a[], int n, int x)
{
int i = 0;
while(i < n && a[i] < x)
i++;
return (i<n && a[i]==x ? i : -1);
}

void main(void)
{
int x, pos, size;
int a[];

// nhap day so va sap xep day so (tang/giam) dan
size = enter_array(a);

// gia su ban dau chua tim duoc
unsigned char found=FALSE;

// Pham vi tìm kiem ban dau tu k=0 den m = n-1
int k=0;
int m=n-1;
int j;

while (k<=m && !found)
{
j=(k+m) /2; // chi so phan tu giua
if (a[j]==x)
found=TRUE;
else
if (x>a[j])
k=j+1; //Pham vi tim moi la (j+1, m)
else
m=j-1; // Pham vi tim moi la (k, j-1)
}
return (found ? j : -1) ;
}C programming. 2003 - 2005
32
Tìm Kiếm Nhị Phân bằng Đệ Qui

1. Phạm vi tìm kiếm ban đầu là toàn bộ danh sách k=0 đến
m=n-1.
2. Lấy phần tử chính giữa của phạm vi tìm kiếm (a[j]) rồi so sánh


C programming. 2003 - 2005
33
Các Thuật Toán Trên Cấu Trúc Cây

Cây là một cấu trúc dữ liệu rất thông dụng và quan trọng trong
nhiều phạm vi khác nhau của kỹ thuật máy tính.
Ví dụ: Tổ chức các quan hệ họ hàng trong một gia phả, mục lục
của một cuốn sách, xây dựng cấu trúc cú pháp trong các trình biên
dịch.

Khái niệm
Cây là tập hợp các phần tử gọi là nút, (một nút có thể có kiểu bất
kỳ) và tập các cạnh có định hướng kết n
ối các cặp nút trong cây.

Nút gốc (Root): là nút ở “trên cùng” trong một cây. Trên nút gốc
không có nút nào nữa.
Nút con (child): nút kế tiếp (phía dưới) của một nút trong cây. Một
nút có thể có nhiều nút con, các nút con này được nhìn theo
thứ tự từ trái sang phải. Nút con tận cùng bên trái là nút đầu
tiên và nút con tận cùng bên phải là nút con cuối cùng.
Nút cha (parent): nút liền kề (phía trên) của một nút trong cây. Một
nút chỉ có duy nhất một nút cha.
Các nút anh em (siblings): các nút con của cùng một nút.
Các cạnh/nhánh (edge/branch): đường nối từ nút cha đến các nút
con của nó.
Nút tổ tiên (Ancestors)
: Các nút tổ tiên của một nút bao gồm nút
cha của nút, nút cha của nút cha, v.v đến trên cùng là nút

Định nghĩa cây theo đệ quy:
- Một nút đơn cũng chính là một cây.
- Các nút được gọi là ở cùng một cây khi có đường đi giữa các
nút này.
- Một cây sẽ bao gồm một nút gốc (Root) và m cây con, trong
mỗi cây con lại có một nút gốc và m1 cây con nhỏ hơn.
- Một cây không có một nút nào cả gọi là cây rỗng.

I
H K
R
L
M N
E
D B
C
C programming. 2003 - 2005
35
Cây Nhị Phân

Trong cây nhị phân, mỗi nút có tối đa hai nút con: nút con nhánh
trái và nút con nhánh phải.
Khi một nút chỉ có một nút con, cần phải phân biệt là nút con bên
nhánh trái, hay nút con bên nhánh phải, chứ không chỉ đơn thuần

Một cây nhị phân được gọi là đầy với chiều cao d thì
- nó phải là cây nhị phân đúng
- tất cả các nút lá đều có mức d
Ghi chú: cây nhị phân đầy là cây nhị phân có số nút tối đa ở mỗi
mức.
C programming. 2003 - 2005
37
Cây nhị phân tìm kiếm (Binary search tree)
Một cây nhị phân được gọi là cây nhị phân tìm kiếm nếu và chỉ nếu
đối với mọi nút của cây thì khóa của một nút bất kỳ phải lớn hơn
khóa của tất cả các nút trong cây con bên trái của nó và phải nhỏ
hơn khóa của tất cả các nút trong cây con bên phải của nó.
Cây nhị phân cân bằng (AVL tree):
Một cây nhị phân được gọi là cây nhị phân cân bằng nếu và chỉ
nếu đối với mọi nút của cây thì chiều cao của cây con bên trái và
chiều cao của cây con bên phải hơn kém nhau nhiều nhất là 1.
(Theo Adelson Velski và Landis).

C programming. 2003 - 2005
38
Cây nhị phân cân bằng hoàn toàn


Preorder (NLR)
Duyệt qua nút gốc trước, sau đó qua cây con bên trái, dùng
preorder cho cây con bên trái. Cuối cùng qua cây con bên phải và
dùng preorder cho cây con bên phải.

If the node is NULL
Return
Else
Visit the item in the node to do something
Traverse (Preorder) the node’s left subtree
Traverse (Preorder) the node’s right subtree

Ví dụ trong hình: 1Æ2Æ3Æ4Æ6Æ7Æ5Æ8Æ9 C programming. 2003 - 2005
40
Inorder (LNR)
Qua cây con bên trái duyệt trước (theo thứ tự LNR). Sau đó duyệt
qua nút gốc. Cuối cùng duyệt qua cây con bên phải (theo thứ tự
LNR).

If the node is NULL

C programming. 2003 - 2005
41
Biểu diễn cây
Sử dụng khái niệm liên kết để biểu diễn cây.
Cây tổng quát:
Mỗi nút có:
- dữ liệu của nút
- các con trỏ chỉ tới các nút con của nó.
Các nút có thể có số nút con khác nhau. Vì số lượng các nút con của một nút không xác định trước nên sẽ
rất khó khăn nếu đưa các liên kết trực tiếp từ nút đến các nút con
của nó.
Thay vào đó, chúng ta có thể qu
ản lý các nút con của một nút bằng
một danh sách liên kết.


Mỗi nút có đúng hai con trỏ chỉ tới nút con bên trái và nút con bên
phải của nó.

struct nodetype
{
int key;
int info;
struct nodetype* left;
struct nodetype* right;
};
typedef struc nodetype* NODEPTR;
NODEPTR tree;

a
b c
g
a
b c
g
C programming. 2003 - 2005
43
Các phép toán trên cây nhị phân
Tạo cây
Khởi tạo (inititalize)


C programming. 2003 - 2005
44
Tạo cây BST (Create_Tree)

void Insert(NODEPTR root, int x, int a)
{
NODEPTR p;
if(x == root->key) // key duplicated, STOP
{
printf("bi trung khoa, khong them nut nay duoc");
return;
}

// Stop condition
if(x < root->info && root->left == NULL)
{
p = New_Node();
p->key =x;
p->info = a;
p->left = NULL;
p->right = NULL;
root->left=p;
return;
}

// stop condition
if(x > root->info && root->right == NULL)
{
p = New_Node();

if (root==NULL)
{ p = New_Node();
p->key = khoa;
p->info = noidung;
p->left = NULL;
p->right = NULL;
root =p;
}
else Insert(root,khoa,noidung);
}
} while (khoa!=0); // Stop entering when key=0
}Để tạo cây nhị phân do biến tree quản lý, ta gọi:
Create_Tree (&tree); Cập nhật cây
Giải phóng vùng nhớ (Free_Node)

void Free_Node(NODEPTR p)
{
free(p);
}

Gọi hàm:
Free_Node (p);

C programming. 2003 - 2005
Trường hợp 3
: Nút p có hai cây con. Do tính chất nút cực trái của
cây con bên nhánh phải của p có khóa lớn hơn khóa của p, nên để
loại p thì chọn nút cực trái làm nút thay thế (rp) cho vị trí của p. Sau
đó, hủy p.

Hàm Remove xóa nút p, trả về con trỏ chỉ tới nút thay thế (rp).

NODEPTR Remove(NODEPTR p)
{
NODEPTR rp, f;

if(p == NULL)
printf(“p is not real. Cannot delete!\n”);
else
C programming. 2003 - 2005
48
{
if(p->right == NULL) // no right subtree
rp = p->left;
else
{
if(p->left == NULL) // no left subtree
rp = p->right;
else // node has left and right subtrees

đó ta gọi.
tree = Remove(tree); C programming. 2003 - 2005
49
Tìm kiếm (Search)
Tìm nút có khóa x trên BST có nút gốc là root. Nếu tìm thấy thì trả
về địa chỉ của nút có khóa x, ngược lại, trả về trị NULL.
Tìm kiếm bằng phương pháp nhị phân

NODEPTR Search(NODEPTR root, int x)
{
NODEPTR p;
p = root;
while(p != NULL && x != p->key)
if(x < p->key)
p = p->left;
else
p = p->right;
return (p);
}

Gọi hàm:
p = Search(tree, x);
{
if(root != NULL)
{
Inorder(root->left);
printf("%d ", root->info);
Inorder(root->right);
}
}
Duyệt theo thứ tự LRN (Postorder)

void Posorder(NODEPTR root)
{
if(root != NULL)
{
Posorder(root->left);
Posorder(root->right);
printf("%d ", root->info);
}
}