Cấu trúc dữ liệu và giải thuật
I.

Sắp sếp và tìm kiếm

1: Sắp xếp
• sắp xếp chọn(selection sort)
A: Thuật toán selection sort
void selection_sort(){
int i, j, k, temp;
for (i = 0; i< N; i++){
k = i;
for (j = i+1; j < N; j++){
if (a[j] < a[k]) k = j;
}
temp = a[i]; a[i] =a [k]; a[k] = temp;
}
}

B. Độ phức tạp
Cmin=Cmax=Ctb=n(n-1)/2
Tốt nhất: nlogn

C: Ví dụ, các bước thực hiện sắp xếp chọn dãy số bên dưới như sau:
Cho dãy số K={5, 6, 9, 1, 3, 4, 2, 7, 8}
bước 1: 1

6

9


bước 3: 1

2

3

5

9

4

6

7

8

bước 4: 1

2

3

4

9

5


4

5

6

9

7

8

bước 7: 1

2

3

4

5

6

7

9

8



18
10

12
12
11

15
15
15
12

10
18
18
18
12

19
19
19
19
19
13

11
11
12
15

18
18
18

16
16
16
16
16
16
16
17
19
19

• Sắp xếp chèn (Insert sort)
A: Thuật toán
void insertion_sort(){
int i, j, k, temp;
for (i = 1; i< N; i++){
temp = a[i];
j=i-1;
while ((a[j] > temp)&&(j>=0)) {
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}



7

6

5

1

3

8

9

2

bước 2:

4

6

7

5

1

3

bước 4:

1

4

5

6

7

3

8

9

2

bước 5:

1

3

4

5


bước 7:

1

3

4

5

6

7

8

9

2

bước 8:

1

2

3

4


18

b2

12

15

18

b3

10

12

15

18

b4

10

12

15

18


19

b7

10

11

12

13

15

17

18

19

b8
b9

10
10

11
11

12

}
}while (i
11
11
11

6
3
3
3
3

15
15
12
12
12

5
4
4
4
4

10
10
15
12
12

1
5

7
7
9

11
11
12
15
15

17
17
17
17
16

13
13
13
16
17

12
18
18
18
18

Sắp xếp nổi bọt ( Bubble sort)


19


i++;
} until (no_exchange || (i == n-1));
}

B: Độ phức tạp

O(n2) với n=|k|
C: Ví dụ: kiểm nghiệm thuật toán trên bộ khoá
k={9
7
18
8
6
bước 1:
bước 2:
bước 3:
bước 4:
bước 5:

6
6
6
6
6

9
7


ví dụ 2: K={9
bước 1:
bước 2:
bước 3:
bước 4:
bước 5:

b1
b2
b3
b4
b5
b6
b7
b8
b9

18 12
10 18
11

1

7

8

3


7
7
7

4
8
8
8
8

15
12
18
12

10
15
12
18
12

19
11
15
12
18
13

11
19

13
17
13
19
16
16
16
18
17

12
13
17
16
19
17
17
17
18
18

16
16
16
17
17
19
19
19
19

a[0]=a[m];
m--;
downheap(0);
return temp;
}
void heap_sort(){
int i;
m=0;
6


for (i=0; i=0; i--) a[i]=remove_node();
}

B: Độ phức tạp
O(N2).

C: Ví dụ
• sắp xếp trộn (Merge sort)
A: Thuật toán
void merge_sort(int *a, int left, int right){
int middle;
if (right
4
5
1
6 3

8

7

2}

7
7

9

2

9

2

1

4

5

6


2

3

4

5

6

7

8

18
12
10
10

12
18
12
11

15
10
15
12

B1


12
12
12
12

16
16
16
16


B4

10

11

12

13

13

15

16

17


if (x=a[k]) return k;
else return -1;
}
-----------------------------------------------------------------

Cài đặt:
int bsearch (float a[], int n, float x)
{ int i,j,k;
If (!storted(a,n))
Return -2;
i=0, j=n-1
int storted (float a[], int n)
8


{for (int i=0; i a[i+1])
Return 0;
Return 1;}
i=0; j=n-1;
while(ix) j=k-1;
Else j=k+1;}
Return -1;}

B: Độ phức tạp
O(log2n)


9


}

o Kiểm tra ngăn xếp đầy
int

StackFull(stack s){
return (s.top = = MAX-1);

}

o Bổ sung một phần tử vào ngăn xếp
void

Push(stack *s, int x){
if (StackFull(*s)){
printf(“Ngan xep day !”);
return;
}else{
s-> top ++;
s-> nut[s-> top] = x;
return;
}

o Lấy ra một phần tử khỏi ngăn xếp
int

Pop(stack *s){

}return(0);
}
void push(stack *ps,int p){
if (ps->top=MAX-1)
{ printf("\n stack đầy");
return;
}
else{ ps->top=(ps->top)+1;
ps->node[ps->top]=p;
}
}
int pop(stack *ps){
if(empty(ps))
{printf("\n stack rỗng");
return(0);
};
return(ps->node[ps->top--];
}
void main(void){
int coso,sodu;
float n;
stack s;
s.top=-1;
printf("\n nhập số n=");
scanf("%f",&n);
printf("\n cơ số cần chuyển:");
scanf("%d",&coso);
while(n!=0)
{
sodu=n%coso;

tử mới nhất được đưa vào mà là phần tử đã được lưu trong hàng đợi lâu nhất.

b)

Biểu diễn

• Khai báo
#define MAX 100
typedef struct {
int head, tail, count;
int node[MAX];

} queue;

• Thao tác khởi tạo hàng đợi
void QueueInitialize(queue *q){
q-> head = 0;
q-> tail = MAX-1;
q-> count = 0;

12


return;
}

• Thao tác kiểm tra hàng đợi rỗng
int QueueEmpty(queue q){
return (q.count
}
3) Danh sách liên kết :

13


a) Định nghĩa danh sách liên kết đơn : Là danh sách có cấu trúc dữ liệu có kiểu
truy cập tuần tự. Mỗi phần tử trong danh sách liên kết có chứa thông tin về phần tử tiếp
theo, qua đó ta có thế truy cập tới phần tử này.

b) Biểu diễn
• Khai báo
struct node {
int item;
struct node *next;
};
typedef struct node *listnode;

• Tạo, cấp phát và giải phóng bộ nhớ cho một nút
listnode p; // Khai báo biến p
p = (listnode)malloc(sizeof(struct node));//cấp phát bộ
nhớ cho p
free(p); //giải phóng bộ nhớ đã cấp phát cho nút p;

• khởi tạo danh sách
void init(DanhSach &d)
{d.pfirst=NULL;d.plast=NULL;
}

• Kiểm tra rỗng


• Thêm phần tử vào giữa danh sách
void Insert_Middle(listnode *p, int position, int x){
int count=1, found=0;
listnode q, r;
r = *p;
while ((r != NULL)&&(found==0)){
if (count == position){
q = (listnode)malloc(sizeof(struct node));
q-> item = x;
q-> next = r-> next;
r-> next = q;
found = 1;
}
count ++;
r = r-> next;
}
if (found==0)
printf(“Khong tim thay vi tri can chen !”);
}

• Xoá phần tử ở đầu danh sách
void Remove_Begin(listnode *p){
listnode q;
if (*p == NULL) return;
q = *p;
*p = (*p)-> next;
q-> next = NULL;
free(q);
}

q-> next = NULL;
free (q);
found = 1;
}
count ++;
r = r-> next;
}
if (found==0)
printf(“Khong tim thay vi tri can xoa !”);

}

c) Ứng dụng
#include <stdio.h>
#include <conio.h>
16


#include <iostream.h>
#include <stdlib.h>
struct node
{
int info;
node *link;
};
typedef node *list;
void create (list &first)
{
first = NULL;
}

else
{
qp = first;
node *q = qp->link;
while (q != NULL) // chay den cuoi danh sach
{
qp = q;
q = q->link;
}
qp->link = p; // chen p vào link cua nút cuoi
}
}
void add(list &q,int x) //
{
}
void remove(list &first, list &q)
{
node *p = first, *pp = NULL;
while (p != NULL && p != q)
{
pp = p;
p = p->link;
}
if (p == q)
{
pp->link = p->link;
delete q;
18



2. Cài đặt cây nhị phân bằng danh sách liên kết
• Khai báo
struct node {
int

item;

struct node *left;
struct node *right;

19


}
typedef struct node *treenode;

treenode root;

• Khởi tạo cây rỗng

void init(node *&proot)
{
proot=NULL;

};

• Tạo 1 nút mới

node* makenode(int x)
{node* p = new node;

pleft = q;}

• Thêm nút là vào bên phải của p

Void insertright (node*p, float x)
{
if (pright!=NULL)
{ printf(“\ ben phai p co node con”);
Return;}
Node*q = make’(x);
pright = q;}

• Duyệt thứ tự trước: (NLR – Node – Left - Right) Đầu tiên là thăm nút gốc.
Sau đó duyệt cây con bên trái, cuối cùng duyệt cây con bên phải

void

PreOrder (treenode root ) {
if (root !=NULL) {

20


printf(“%d”, root.item);
PreOrder(root.left);
PreOrder(root.right);
}
}

• Duyệt thứ tự giữa: (LNR): Duyệt cây con bên trái sau đó thăm nút gốc. Cuối

tính. Đây cũng là một phương pháp đơn giản và được lựa chọn để áp dụng
trong rất nhiều tình huống thực tế.
Ý tưởng cơ bản của phương pháp này là xây dựng một cây nhị phân tìm kiếm. Đó
là một cây nhị phân có tính chất sau: Với mỗi nút của cây, khoá của các nút của cây con bên
trái bao giờ cũng nhỏ hơn và khoá của các nút của cây con bên phải bao giờ cũng lớn hơn
hoặc bằng khoá của nút đó.

2. Cài đặt cây tìm kiếm nhi phân
struct node {
int

item;

struct node *left;
struct node *right;

21


}
typedef struct node *treenode;
treenode tree_search(int x, treenode root){
int found=0;
treenode temp=root;
while (temp!=NULL){
if (x < temp.item) temp=temp.left;
elseif (x > temp.item)temp=temp.right;
else break;
}
return temp;


- Nếu xgốc và chưa có lá con bên phải thì thực hiện thêm node vào nhánh
bên phải.
if(x=proot->infor){
printf("\n nội dung bị trung");
delay(2000);return;
}
else if(x->proot-> infor&&proot->left==NULL){
select(proot,x);return;
}
else if(x->proot-> infor&&proot->right==NULL){
select(proot,x);return;
}
else if(xproot->infor)
insert(proot->left,x);
else insert(proot->right,x);
}
c. Thao tác xóa một node trên cây nhị phân tìm kiếm
/*Khi xoa mot nut P trong cay nhi phan tim kiem ta tim mot nut de thay the
nut do. Neu P la nut la thi nut thay the la nut NULL. Neu P chi co mot
cay con thi nut thay the la nut con cua no. Neu P co 2 cay con thi nut
thay the la nut trai nhat cua cay con ben phai hoac nut phai nhat cua
cay con ben trai.Ta quy uoc chon nut phai nhat cua cay con ben trai*/
void remove(node *&proot, int x)
{node *fp,*p,*f,*rp,*q; /*rp la nut thay the cho nut p co noi dung x,
f la nut cha cua nut thay the rp*/
p=search2(proot,fp,x); //fp la nut cha cua nut p
if(p==NULL) {cout

V.Đồ thị
+ Đồ thị G = <V,E> là đồ thị đơn  với mọi u,v thuộc V sao cho tồn tại
nhiều nhất một cạnh
+ Đồ thị G = <V,E> là đa đồ thị  tồn tại u, v thuộc V sao cho có nhiều
hơn một cạnh

Ví dụ:

Hình 1

1. Biểu diễn đồ thị:

a) Ma trận kề:: Biểu diến đồ thị bằng ma trận vuông cấp n có các phần tử
G = <V,E> như hình vẽ :

24


+ Đồ thị vô hướng

-

MTK của đồ thị vô hướng là đối xứng (Aij = Aji)

-

Tổng các phần tử của ma trận bằng 2 lần số cạnh của đồ thị

-

0
0
1
0
0
0
3
1
1
0
1
1
1
1
0
0
0
4
1
0
1
0
1
0
0
0
0
0
A=
5

0
0
8
0
0
0
0
0
1
1
0
0
1
9
0
0
0
0
1
1
0
0
0
1
10
0
0
0
0
0

0
0
0

0
0
0
0
1
0

0
0
1
0
0
1

25

0
1
0
1
0
0

0
0
0