Copyright ® Lớp CT1001

mylopct1001.tk

DANH SÁCH

Danh sách gồm 2 loại : Danh sách kề (mảng, con trỏ) và danh sách liên kết.

I. Danh sách kề (Mảng) :

1. Cấu trúc:

struct List

{

int data[MAX];

int n;

};

2. Cài đặt

a. Khởi tạo (Init)

void Init (List &l)

{

l.n = 0;

}

b. Hủy (Destroy)

void Destroy(List &l)

{}

c. Tìm kiếm (Search)

e.Chèn (Insert)

void Insert(List &l, int k, int v)

{

int i;

if (l.n==MAX) return;

for (i=0; i<l.n; i++)

if (l.data[i] == v)

break;

if (i==l.n) return;

for (int j=l.n; j>i; j--)

l.data[j] = l.data[j-1];

int Search(List &l, int k)

{

for (int i=0; i<l.n; i++)

if (l.data[i] == k)

return 1;

return 0;

}

d.Thêm (Add)

void Add(List &l, int k)

{

if (l.n == MAX)

return;

l.data[l.n+1] = k;

l.data[i] = k;

l.n++;

}

f. Xóa (Remove)

void Remove (List &l, int k)

{

int i;

for (i=0; i<l.n; i++)

if (l.data[i] == k) break;

if (i==l.n) return;

l.n--;

}

for ( ; i<l.n;i++)

l.data[i] = l.data[i+1];

}

3.Tính chất

- Các phần tử nằm liên tiếp nhau.

- Có khả năng truy xuất ngẫu nhiên.

- Khi danh sách đầy không thêm được nữa.

II. Danh Sách Kề (Con Trỏ)

1.Cấu trúc

struct List

{

int *data;

int n, max;

};

2. Cài đặt

a. Khởi tạo (Init)

void Init (List &l)

{

l.max = 0;

l.n = 0;

l.data = new int (l.max);

}

b.Hủy (Destroy)

void Destroy (List &l)

{

delete l.data;

}

c. Tìm kiếm (Search)

int Search(List &l, int k)

{

for (int i=0; i<l.n; i++)

if (l.data[i] == k)

return 1;

return 0;

}

d. Thêm (Add)

void Add (List &l, int k)

{

if (l.n == l.max)

{

int *tmp = new int[l.max+10];

if (!tmp) return;

l.max+=10;

memcpy(tmp,l.data,sizeof(int),l.n);

delete l.data;

l.data = tmp;

e.Chèn (Insert)

void Insert (List &l, int k, int v)

{

int n = l.n;

for (int i=0; i<l.n; i++)

if (l.data[i] == v) break;

if (i==l.n) return;

Add ( l, l.data[l.n-1]);

if (n==l.n) return;

for (int j=l.n-2; j>i; j--)

l.data[j] = l.data[j-1];

l.data[i] = k;

}

f. Xóa (Remove)

void Remove (List &l, int k)

{

int i;

for (i=0; i<l.n; i++)

if (l.data[i] == k) break;

if (i==l.n) return;

l.n--;

}

} else

l.data[l.n++] = k;

for ( ; i<l.n;i++)

l.data[i] = l.data[i+1];

}

3. Tính chất

- Các phần tử nằm liên tiếp nhau.

- Có khả năng truy xuất ngẫu nhiên.

- Khi danh sách đầy có thể thêm được nữa.

III. Danh Sách Liên Kết

1. Cấu trúc

struct Node

{

int data;

Node * next;

};

struct List

{

Node *head, *tail;

};

2. Cài đặt

a. Khởi tạo (Init)

void Init (List &l)

{

l.head = l.tail = NULL;

}

c.Tìm kiếm (Search)

int Search (List &l, int k)

{

Node *p = l.head;

while (p && p->data != k)

p = p -> next;

return p ? 1 : 0;

b.Hủy (Destroy)

void Destroy(List &l)

{

Node *p = l.head;

while (p)

{

l.head = p->next;

delete p;

p = l.head;

}

}

d. Thêm (Add)

void Add (List &l, int k)

{

Node *p = new Node;

if (!p) return;

p->data = k;

p->next; = NULL;

}

if (l.tail)

l.tail->next = p;

else

{

l.head = p;

l.tail = p;

}

}

e.Chèn (Insert)

void Insert (List &l, int k, int v)

{

Node *q = NULL;

Node *p = l.head;

while (p && p -> data != v)

{

q = p;

p = p->next;

}

if (!p) return;

Node *t = new Node;

if (!t) return;

t->data = k;

t->next = p;

if (q)

q->next = t;

else

l.head = t;

}

3. Tính chất

- Các phần tử không nằm liên tiếp nhau.

- Không có khả năng truy xuất ngẫu nhiên.

- Danh sách đầy khi bộ nhớ hết.

f.Xóa (Remove)

void Remove (List &l, int k)

{

Node *q = NULL;

Node *p = l.head;

while (p && p->data != k)

{

q = p;

p = p->next;

}

if (!p) return;

if (q)

q->next = p->next;

else

l.head = p->next;

if (l.tail = p)

l.tail = q;

delete p;

}

STACK

I. Định nghĩa Stack

- Stack là một danh sách.

- Có hai thao tác đưa 1 phần tử vào stack (Push) và lấy 1 phần tử ra khỏi stack (Pop)

II. Tính chất của Stack.

-

-

-

Thêm một phần tử mới ở đầu Stack.

Lấy một phần tử ra ở đầu Stack.

Vì vậy các phần tử đưa vào sau cùng sẽ được lấy ra đầu tiên.

III. Cài đặt Stack bằng danh sách liên kết

1. Cấu trúc

struct Node

{

int key;

Node *next;

};

struct Stack

{

Node *head;

};

2. Cài đặt

a. Đẩy vào Stack (Push)

void Push(Stack &t, int k)

{

Node *tmp = new Node;

if (!tmp) return;

tmp->key = k;

tmp->next = t.head;

t.head = tmp;

}

b. Lấy ra khỏi Stack (Pop)

int Pop(Stack &t)

{

int tmp = t.head->key;

t.head = t.head->next;

return tmp;

}

QUEUE

I. Định nghĩa Queue

- Queue là một danh sách.

- Có hai thao tác đưa 1 phần tử vào queue (Push) và lấy 1 phần tử ra khỏi queue (Pop)

II. Tính chất của Queue

- Thêm một phần tử ở đầu Queue.

- Lấy một phẩn tử ra ở cuối Queue.

- Vì vậy thứ tự lấy ra sẽ giống với thứ tự đưa vào.

III. Cài đặt Queue bằng danh sách liên kết

1.Cấu trúc

struct Node

{

int key;

Node *next;

};

struct Queue

{

Node *head,*tail;

};

2.Cài đặt

a. Đẩy một phần tử vào Queue (Push).

void Push(Queue &q, int k)

{

Node *tmp = new Node;

if (!tmp) return;

tmp->key = k;

tmp->next = NULL;

}

if (!q.tail)

{

tmp->next = q.tail;

q.tail = tmp;

q.head = tmp;

}

else

{

q.tail->next = tmp;

q.tail = tmp;

}

b. Lấy một phần tử ra khỏi Queue

(Pop)

int Pop(Queue &q)

{

Node *tmp = q.head;

q.head = q.head->next;

int x = tmp->key;

delete tmp;

return x;

}

ỨNG DỤNG CỦA STACK

I. Biểu thức hậu tố.

Biểu thức hậu tố hay còn gọi là kí pháp nghịch đảo Ba Lan. Tức là các toán tử + - * /

đều được đặt ở phía sau toán hạng.

Ví dụ : Biểu thức trung tố : 5 + ((1 + 2) * 4) + 3

Biểu thức hậu tố :

II. Phương pháp đổi hậu tố

512+4*+3+

·

·

·

·

·

Nếu gặp một toán hạng (con số ) thì ghi vào chuỗi kết quả.

Nếu gặp kí tự mở ngoặc thì đưa vào ngăn xếp.

Nếu gặp toán tử (gọi là o1) ta thực hiện hai bước tiếp theo sau :

o Chừng nào còn có toán tử o2 ở đỉnh stack và độ ưu tiên của toán tử o1 nhỏ

hơn hay bằng độ ưu tiên của toán tử o2 thì lấy o2 ra khỏi đỉnh stack và ghi

vào chuỗi kết quả.

o Đẩy o1 vào ngăn xếp.

Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử ở trong stack ra và ghi vào kết quả

cho đến khi lấy được dấu mở ngoặc ra khỏi stack.

Khi đã duyệt hết biểu thức trung tố lần lượt lấy tất cả các toán tử (nếu có) từ stack

và ghi vào chuỗi kết quả.

Để cho các bạn có thể hiểu rõ hơn. Chúng ta sẽ cùng xét một ví dụ cụ thể như sau :

Biểu thức cần chuyển đổi: 3+4*2/(1-5)

Ký

tự

Thao tác

Stack

Chuỗi hậu tố

3

Ghi 3 vào k.quả

3

+

Push +

+

4

Ghi 4 vào k.quả

34

*

Push *

+*

2

Ghi 2 vào kquả

342

/

Lấy * ra khỏi stack, ghi

vào k.quả, Push /

+ /

342*

(

Push (

+/(

342*

1

Ghi 1 vào k.quả

+/(

342*1

-

Push -

+/(–

342*1

5

Ghi 5 vào k.quả

+/(–

342*15

)

Pop cho đến khi lấy

được (, ghi các toán

tử pop được ra k.quả

+/

342*15-

2

Ghi 2 ra k.quả

+/

342*15–2

Pop tất cả các toán tử

ra khỏi ngăn xếp và

ghi vào kết quả

342*15–2 /+

III. Tính giá trị biểu thức từ biểu thức hậu tố.

Ý tưởng : Ta sẽ đọc biểu thức từ trái sang phải. Nếu kí tự là một toán hạng thì đẩy vào

stack. Nếu gặp toán tử o (+ - * /) thì lấy liên tiếp ở đỉnh Stack ra 2 số thực hiện phép

toán với toán tử o. Kết quả của phép toán ta dưa vào stack. Cứ tiếp tục công việc đó cho

đến khi duyệt xong biểu thức. Con số duy nhất trong stack đó chính là kết quả của biểu

thức.

Ta xét ví dụ sau : Tính giá trị của biểu thức hậu tố : 5 1 2 + 4 * + 3 +

Quá trình tính toán với Stack sẽ diễn ra theo bảng dưới đây :

Ký tự

Thao tác

Trạng thái stack

5

Push 5

5

1

Push 1

5, 1

2

Push 2

5, 1, 2

+

Tính 1 + 2

Push 3

5, 3

4

Push 4

5, 3, 4

*

Tính 3 * 4

Push 12

5, 12

+

Tính 12 + 5

Push 17

17

3

Push 3

17, 3

+

Tính 17 + 3

Push 20

20

CÂY NHỊ PHÂN TÌM KIẾM – BST

I. Định nghĩa

Cây là một cấu trúc dữ liệu trừu tượng và gồm một tập hợp hữu hạn các nút, giữa các

nút có một quan hệ phân cấp gọi là quan hệ “Cha - Con”. Có một nút đặc biệt gọi là nút

gốc (Root).

II. Cây nhị phân tìm kiếm – BST

1. Tính chất

- Là một cây nhị phân ( Một gốc chỉ có nhiều nhất 2 nhánh left và right)

- Tất cả các khóa của cây con bên trái nhỏ hơn gốc.

- Tất cả các khóa của cây con bên phải lớn hơn gốc.

- Trong cây nhị phân tìm kiếm không thể có hai khóa trùng nhau.

- Trong cây nhị phân tìm kiếm chỉ có một vị trí thêm duy nhất.

2. Phép duyệt cây (Traverse)

Có tất cả 6 phép duyệt cây được tính theo hoán vị của 3 chữ cái:

N-L-R (Node – Left – Right).

Nhưng ta chỉ quan tâm đến 4 phép duyệt chính là NLR, LNR, RNL, LNR.

III. Cài đặt cây BST

1. Cấu trúc

struct Node

{

int key;

Node *left, *right;

};

struct BStree

{

Node *root;

};

2. Cài đặt

a. Khởi tạo (Init)

void Init (BStree &t)

{

t.root = NULL;

}

b. Hủy (Destroy)

void Destroy(BStree &t)

{

Destroy2(t.root);

}

void Destroy2(Node *&root)

{

Destroy2(root->left);

Destroy2(root->right);

delete root;

}

c. Tìm kiếm (Search)

Node** Search(BStree &t, int k)

{

return Search2(t.root, k);

}

Node** Search2(Node *&root, int k)

{

if (root)

{

if (root->key == k) return &root;

if (root->key < k)

return Search2(root->right, k);

return Search2(root->left,k);

}

else return 0;

}

d. Phép chèn ( Insert)

void Insert(BStree &t, int k)

{

Node *newnode = new Node;

newnode->key = k;

newnode->left = NULL;

newnode->right = NULL;

Insert2(t.root, newnode);

}

void Insert2(Node *&root, Node *newnode)

{

if (!root)

root = newnode;

else if (newnode->key > root->key)

Insert2(root->right, newnode);

else if (newnode->key < root->key)

Insert2(root->left,newnode);

}

e. Xóa một Node

void DeleteNode(BStree &t, int k)

{

Node **tmp = Search(t,k);

if (tmp)

DeleteNode2(*tmp);

}

void DeleteNode2(Node *&root)

{

if (root->left == NULL)

{

Node *tmp = root;

root = root->right;

delete tmp;

}

else if (root->right == NULL)

{

Node *tmp = root;

root = root->left;

delete tmp;

}

else

{

Node** tmp = &(root->left);

while ((*tmp)->right != NULL)

tmp = &((*tmp)->right);

root->key = (*tmp)->key;

DeleteNode2(*tmp);

}

}

f. Phép duyệt cây (Traverse)

void DuyetCay(BStree &t)

{

DuyetCay2(t.root);

}

void DuyetCay2(Node *&root)

{

if (root)

{

DuyetCay2(root->left);

cout<<root->key<<" ";

DuyetCay2(root->right);

}

}

CÂY AVL

I. Định nghĩa.

- Cây AVL là cây BST và có khả năng tự cân bằng.

- Chỉ số cân bằng : Là hiệu của chiều cao cây con phải trừ chiều cao cây con trái.

- Cây được gọi là cân bằng khi chỉ số cân bằng của các node không lớn hơn 1 và không

nhỏ hơn -1.

- Các phép toán trên cây AVL cũng tương tự như các phép toán trên cây AVL.

II. Cài đặt cây AVL

1. Cấu trúc

struct Node

{

int key;

Node *next;

int bal;

};

struct AVLTree

{

Node *root;

};

2. Cài đặt.

Trong cây AVL các phép toán khởi tạo, tìm kiếm, duyệt cây đều giống như cây BST. Vì

vậy trong chương này chúng ta chỉ xét 2 phép toán là Thêm và Xóa một node trên cây

AVL.

Khi thêm hoặc xóa một khóa có thể dẫn đến cấu trúc cân bằng của cây bị phá vỡ. Vì vậy

sau mỗi lần thêm ta đều phải tính lại chỉ số cân bằng của các node cha. Nếu mất cân

bằng chúng ta phải tái cân bằng lại cây AVL.

ò Có 4 trường hợp mất cân bằng :

Trường hợp 1: +2 +1 (Right – Right)

Quay trái

Trường hợp 2: -2 -1 (Left – Left)

Quay phải

Trường hợp 3: +2 -1 (Right - Left)

1. Quay phải B

2. Quay trái A

Trường hợp 4: -2+1 (Left - Right)

1. Quay trái B

2. Quay phải A

ò Cài đặt phép toán.

1. Phép quay phải

void RorateRight(Node *&root)

{

Node *p = root->left;

root->left = p->right;

p->right = root;

root = p;

}

2. Phép quay trái

void RorateLeft(Node *&root)

{

Node *p = root->right;

root->right = p->left;

p->left = root;

root = p;

}

3. Phép cân bằng trái (Balance Left)

void BalanceLeft(Node *&root)

{

Node *b = root->right;

if (b->bal >=0)

{

root->bal = 0;

b->bal = 0;

RorateLeft(root);

}

else

{

Node *c = b->left;

root->bal = c->bal < 0 ? 0 : -1;

b->bal = c->bal > 0 ? 0 : 1;

c->bal = 0;

RorateRight(root->right);

RorateLeft(root);

}

}

4. Phép cân bằng phải (Balance Right).

void BalanceRight(Node *&root)

{

Node *b = root->left;

if (b->bal <=0)

{

root->bal = 0;

b->bal = 0;

RorateRight(root);

}

else

{

Node *c = b->right;

root->bal = c->bal < 0 ? 1 : 0;

b->bal = c->bal > 0 ? -1 : 0;

c->bal = 0;

RorateLeft(root->left);

RorateRight(root);

}

}

5. Phép chèn

int Insert2(Node *&root, int k)

{

if (!root){

Node *tmp = new Node;

tmp->key = k;

tmp->left = NULL;

tmp->right = NULL;

tmp->bal = 0;

root = tmp;

return 1;

}

if (root->key == k) return 0;

if (root->key > k) {

if (!Insert2(root->left,k)) return 0;

root->bal--;

}

else{

if (!Insert2(root->right,k)) return 0;

root->bal ++;

}

if (root->bal ==0) return 0;

if (root->bal ==-1 || root->bal == +1) return 1;

if (root->bal == -2) BalanceRight(root);

else BalanceLeft(root);

return 0;

}

void Insert(AVL &t, int k)

{

Insert2(t.root,k);

}

6. Tính chiều cao của cây AVL và BST.

int GetHeight2(node *&root)

{

if (root)

{

if (root->left == NULL && root->right == NULL) return 1;

int height_left = GetHeight2(root->left);

int height_right = GetHeight2(root->right);

return height_left > height_right ? height_left +1 : height_right + 1;

}

return 0;

}

int GetHeight(BSTree &t) // nếu là cây AVL thì đổi BSTree thành AVLTree

{

return GetHeight2(t.root);

}

Tính biểu thức trong cấu trúc dữ liệu và giải thuật.

Đầu tiên là   các ký pháp trong cùng một biểu thứ:

Cho một biểu thức như sau:

7*(3+7)-4*(6-3).

Nếu duyệt theo dạng tiền tố(prefix)(Kiểu ký pháp Ba Lan) :

Ta sẽ được: – *  + 3 7  7 * – 6 3 4.

Qui tắc được ưu tiên :*,/,+,-,(

Chú ý:Dạng tiền tố thì toán tử được viết trước 2 toán hạng.

Để đơn giản thì ta cho :

_x=7*(3+7).

_y=4*(6-3).

Lưu ý:Dấu giữa 2 vế ta sẽ cho nằm ngoài cùng.

x=7*(3+7).

x= * + 7 3 7.

+ 7 3= 10.

* 10 7=70.

y=4*(6-3).

y= * – 6 3 4.

- 6 3=3.

* 3 4=12.

- x y= – 70 12.

Đáp án là 58.

Tiếp theo là dạng trung tố (infix)

Qui tắc được ưu tiên :*,/,+,-,(.

_Cái tên nói lên tất cả,toán tử sẽ nằm giữa 2 toán hạng

Cho biểu thức  (3-1+6)*(2+8)

Ta sẽ viết như sau: 3 – 1 * 2 + 8

Nhưng đôi lúc sẽ gây ra hiểu lầm ở phép nhân nên ta sẽ viết như sau:

((3-1)+6)*(2+8)

Phần này khá đơn giản nên mình kết thúc ở đây.

Và cuối cùng là dạng Hậu tố:(postfix)(ký pháp nghịch đảo Ba lan)

Qui tắc được ưu tiên :*,/,+,-,(

Chú ý:Dạng tiền tố thì toán tử được viết sau 2 toán hạng.

Mình sẽ cho vd ở câu 1 để thấy rõ sự khác biệt:

vd :7*(3+7)-4*(6-3).

Ta cũng sẽ lần lượt cho x và y là:

_x=7*(3+7).

_y=4*(6-3).

_x=7*(3+7).

x= 7 3 + 7 *.

7 3 +=10.

10 7 *=70.

_y=4*(6-3).

6 3 – 4 *

6-3=3.

3 4 *=12.

x y -=70 – 12 =58.

Cách chuyển từ dạng Trung tố sang Hậu tố

Cho biểu thức : (4+3)*(7-2*5)

Sau đó ta xét stack 1 lần nữ và kiểm tra kết quả:

Xét stack: (4+3)*(7-2*5)/4 3 + 7 2 5 * – *

4                      4

3                      4    3

+                      7

7                      7     7

2                     7      7     2

5                     7      7      2        5

*                     7       7     10

-                    7       -3

*                   -21.