Mảng là một dữ liệu có kích thước cố định, đồng nhất, và cơ cấu sử dụng rộng rãi.

Đồng nhất, chúng có nghĩa là nó bao gồm các thành phần đó là tất cả cùng loại, loại yếu tố gọi là hay kiểu cơ sở.

Cố định kích thước, chúng có nghĩa là số lượng các thành phần là không đổi, và vì vậy không thay đổi trong suốt thời gian tồn tại của cấu trúc dữ liệu đó.

LB=Lower Bound                              U=Upper Bound

Địa chỉ của các phần tử của hàng thứ i và cột thứ j:

addr(a[i, j]) = ((i−LB1)*(UB2−LB2+1)*size)+((j−LB2)*size)

Hàm đệ quy là một hàm gọi chính nó. Nó có 2 pha cơ bản là Winding và Unwinding

-Winding: hàm đệ quy gọi lại sự tồn tại của hàm đệ quy bằng cách tạo 1 vài điều kiện để gọi lại hàm đệ quy. Winding chấm dứt khi 1 trong những lần gọi hàm dẫn đến điều kiện chấm dứt. Điều kiện xác định chấm dứt pha mà tại đó một hàm đệ quy phải trả lại thay vì làm một cuộc gọi đệ quy. Mỗi chức năng đệ quy phải có ít nhất một điều kiện chấm dứt, nếu không, pha Winding không bao giờ chấm dứt.

-Unwinding: bắt đầu khi pha Winding kết thúc. Điều kiện trước được thực hiện theo chiều ngược lại. Pha sẽ tiếp tục cho đến khi chương trình gốc gọi trở về.

Example 1:  Factorial n!.  

    F(n) = n* F(n-1)

If( n > 1)  F(n) = 1

If( n = 1 or n = 0) Compute F(4) = ?

Winding Phase

F(4) = 4 * F(3)

F(3) = 3 * F(2)

F(2) = 2 * F(1)

F(1) = 1

UnWinding Phase

F(4) = 4 * 6 = 24

F(3) = 3 * 2 = 6

F(2) = 2 * 1 = 2

F(1) = 1

Hàm đệ quy được cho là đệ quy đuôi nếu tất cả các cuộc gọi đệ quy trong nó là đệ quy đuôi.

Một cuộc gọi đệ quy là đệ quy đuôi khi nó là lệnh cuối cùng sẽ được thực hiện trong cơ thể của một hàm và giá trị trả về của nó không phải là một phần của biểu thức.

Hàm đệ quy đuôi có đặc tính là không có gì làm trong pha Unwinding.(đặc tính quan trọng)

Example 2:  Compute n!

       F(n, a) = F(n-1, n*a)

If (n>1) F(n,a) = a

if (n = 1 or n = 0) Compute F(4,1) = ?

Winding Phase

F(4,1) = F(3,4)

F(3,4) = F(2,12)

F(2,12) = F(1,24)

F(1,24) = 24

UnWinding Phase

(Nothing to do)

Quay lui là một cách có hệ thống để đi qua tất cả các cấu hình có thể của một không gian tìm kiếm.

Đệ quy có thể được sử dụng để thực hiện quay lui dễ dàng.

Quay lui có thể dễ dàng được sử dụng để chuyển đổi qua tất cả các tập con hoặc hoán vị của một tập hợp.

Quay lui đảm bảo tính chính xác của liệt kê tất cả các khả năng.

Để quay lui có hiệu quả, chúng ta phải tỉa không gian tìm kiếm.

Sắp xếp cơ bản:

void InsertionSort()//Chèn phần tử thứ i trong mảng vào vị trí thích hợp

        {

            for (i = 1; i < n; i++)

            {

                for (j = i - 1, temp = a[i]; temp < a[j]; j--) a[j + 1] = a[j];

                a[j + 1] = temp;

            }

        }

void SelectionSort()//Chọn phần tử bé (lớn) nhất trong mảng còn lại để đưa vào vị trí đang xét

        {

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

            {

                for (j = i + 1, temp = a[i], pos = 0; j < n; j++)

                {

                    if (temp >= a[j])

                    {

                        temp = a[j];

                        pos = j;

                    }

                }

                if (pos > 0)

                {

                    tg = a[pos];

                    a[pos] = a[i];

                    a[i] = tg;

                }

            }

        }

void BubbleSort()//Xét mảng và đối chỗ lần lượt từ trái qua phải (từ phải qua trái) n lần

        {

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

            {

                for (j = 1; j < n ; j++)

                {

                    if (a[j - 1] > a[j])

                    {

                        tg = a[j - 1];

                        a[j - 1] = a[j];

                        a[j] = tg;

                    }

                }

            }

        }

Sắp xếp nhanh:

Tìm kiếm:

void LinearSearch()

        {

            i = 0;

            while ((i < n) && (tg != a[i]))

            {

                i++;

            }

            if (i < n) pos = i;//found vị trí i

            else pos = 0;//not found

        }

void BinarySearch()

        {

            i = 1; j = n;

            while (i < j)

            {

                temp = (i + j) / 2;

                if (tg > a[temp]) i = temp + 1;

                else j = temp;

            }

            if (tg == a[i]) pos = i;//Found vị trí i

            else pos = 0;//Not found

        }

void InterpolationSearch()//tìm kiếm nội suy

        {

            i = 1; j = n;

            while (j > i)

            {

                temp = i + ((tg - a[i]) / (a[j] - a[i])) * (j - i);

                if (temp < i || temp > j)//Not Found

                {

                    pos = 0;

                    break;

                }

                else if (a[temp] == tg)//Found vị trí i

                {

                    pos = temp;

                    break;

                }

                else if (a[temp] < tg) i = temp + 1;

                else if (a[temp] > tg) j = temp - 1;

            }

        }

Stack:

-First In Last Out: vào trước ra sau, vào sau ra trước. Plate vào sau đè lên Plate vào trước.

-Nội dung ngăn xếp được ẩn, chỉ có Plate trên đầu được nhìn thấy. Nếu muốn thấy Plate thứ  3 thì phải bỏ Plate 1 và 2 ra.

Push: thêm vào nội dung lên trên đầu Stack

Pop: lấy ra nội dung trên đầu Stack

Peek: Xem nội dung trên cùng của Stack

Infix & Prefix & RPN:

Convert (A+B)/(C-D)+E to RPN

Step

Sym

Stack

RPN

Step

Sym

Stack

RPN

1

8

C

AB+C

2

A

A

9

-

/(-

AB+C

3

+

(+

A

10

D

/(-

AB+CD

4

B

(+

AB

11

AB+CD-

5

AB+

12

+

+

AB+CD-/

6

AB+

13

E

+

AB+CD-/E

7

AB+

14

AB+CD-/E+

RPN = 4 5 + 2 3 + * 6 + 8 7 + /

Step

Sym

Stack

Step

Sym

Stack

1

4

4

8

6

45 6

2

5

5

9

+

51

3

+

9

10

8

51 8

4

2

9 2

11

7

51 8 7

5

3

9 2 3

12

+

51 15

6

+

9 5

13

3.4

7

*

45

Convert (A+B)/(C-D)+E to Prefix

Step

Sym

Stack

Prefix

Step

Sym

Stack

Prefix

1

E

E

9

+/)

-CDE

2

+

+

E

10

B

+/)

B-CDE

3

+)

E

11

+

+/)+

B-CDE

4

D

+)

DE

12

A

+/)+

AB-CDE

5

-

+)-

DE

13

+/

+AB-CDE

6

C

+)-

CDE

14

+

/+AB-CDE

7

+

-CDE

15

+/+AB-CDE

8

+/

-CDE

Prefix = / + * + 4 5 + 2 3 6 + 8 7

Step

Sym

Stack

Step

Sym

Stack

1

7

7

8

5

15 6 5 5

2

8

7 8

9

4

15 6 5 5 4

3

+

15

10

+

15 6 5 9

4

6

15 6

11

*

15 6 45

5

3

15 6 3

12

+

15 51

6

2

15 6 3 2

13

3.4

7

+

15 6 5

Convert RPN = AB+CD-/E+ to Prefix = +/+AB-CDE

Step

Sym

Stack

1

A

A

2

B

A B

3

+

+AB

4

C

+AB C

5

D

+AB C D

6

-

+AB -CD

7

/+AB-CD

8

E

/+AB-CD E

9

+

+/+AB-CDE

Convert Prefix = +/+AB-CDE to RPN = AB+CD-/E+

Step

Sym

Stack

1

E

E

2

D

E D

3

C

E D C

4

-

E CD-

5

B

E CD- B

6

A

E CD- B A

7

+

E CD- AB+

8

E AB+CD-/

9

+

AB+CD-/E+

Convert RPN = AB+CD-/E+ to Infix = (A+B)/(C-D)+E

Step

Sym

Stack

1

A

A

2

B

A B

3

+

A+B

4

C

A+B C

5

D

A+B C D

6

-

A+B C-D

7

(A+B)/(C-D)

8

E

(A+B)/(C-D) E

9

+

(A+B)/(C-D)+E

Convert Prefix = +/+AB-CDE to Infix = (A+B)/(C-D)+E

Step

Sym

Stack

1

E

E

2

D

E D

3

C

E D C

4

-

E C-D

5

B

E C-D B

6

A

E C-D B A

7

+

E C-D A+B

8

E (A+B)/(C-D)

9

+

(A+B)/(C-D)+E

Queue là một nhóm lệnh cho các mục đồng nhất của các nguyên tố.

Hàng đợi có hai đầu:

Các yếu tố được thêm vào ở một đầu.

Các yếu tố được loại bỏ từ đầu kia.

Các yếu tố được thêm vào đầu tiên cũng được gỡ bỏ trước (FIFO: First In, First Out).

Đặc điểm kỹ thuật xếp hàng

MaxSize: số hạng mục có thể được vào hàng đợi

ItemType: Kiểu dữ liệu của các mục vào hàng đợi.

Tree:

Three common tree traversals:

Preorder traversal: NLR

Inorder traversal: LNR

Postorder traversal: LRN

4 type tree:

Binary Trees: có thể là cây rỗng hoặc cây có 1 gốc hoặc cây có gốc, cành, lá......

Full Binary Trees: là cây nhị phân mà mỗi gốc tương đối bậc i sẽ có đủ 2 cành hay mỗi cành tương đối bậc i sẽ có 2 lá.(xếp theo chiều ngang, mỗi hàng thỏa mãn 2n phần tử).

Complete Binary Trees: là cây nhị phân mà mỗi gốc tương đối sẽ có đủ 2 cành hay mỗi cành tương đối sẽ có 2 lá.(xếp theo chiều ngang, mỗi hàng thỏa mãn 2n phần tử).

Balanced Binary Trees: Trên cùng 1 bậc gốc hay cành thì chỉ có 1 phần tử khác duy nhất.

Level order: Visited: D B F A C E G

In Order: Visted: A B C D E F G

Post Order: Visited: A C B E G F D

Pre Order: Visited: D B A C F E G

Tìm kiếm dựa vào giá trị khóa

//Hoàn toàn dựa trên sách giáo khoa

1. Đây là phương pháp tìm kiếm dựa vào giá trị khóa

- Bằng một quy tắc biến đổi nào đó, từ giá trị khóa ta tính ra một địa chỉ (địa chỉ tương đối)

- Địa chỉ này sẽ dùng để lưu trữ bản ghi (hay khóa tương ứng), đồng thời cũng để tìm kiếm bản ghi ấy.

- Phương pháp này còn có tên gọi khác là kỹ thuật lưu trữ rải. Tương ứng với nó có các khái niệm Hàm rải, địa chỉ rải, bảng rải

2.Hàm rải

- PP chia

                Lấy số dư của trị khóa chia cho kích thước m của bảng rải để làm địa chỉ rải

- PP nhân

                Giá trị khóa được nhân với chính nó, sau đó lấy con số bao gồm một số chữ số ở giữa để làm địa chỉ rải

- PP phân đoạn

                Khi khóa có kích thước lớn, ta dùng phương pháp phân đoạn. Trước hết ta chia giá trị khóa thành nhiều đoạn = nhau (có thể trừ đoạn đầu hoặc cuối), thường mỗi đoạn có độ dài bằng độ dài địa chỉ. Để làm như vậy, người ta dùng các kĩ thuật

-          Phương pháp phân đoạn được dùng để tạo địa chỉ rải giống như cách làm món thịt băm

-          Do vậy nó còn có tên là phương pháp băm. Đi với nó có các khái niệm hàm băm, bảng băm, địa chỉ băm

VD: k = 121  

PP chia:

                Cho m = 13

k mod  m  =  121 mod 13 =  !!!! (đang lười nhẩm)

Lấy !!!! gì gì đó làm địa chỉ rải

PP nhân

                k^2 = ###### (làm vội! Thông cảm  :D  )

Lấy từ ###### chọn ra ba số ở giữa là  $$$ nào đó làm địa chỉ rải cho khóa   k

Ngoài ra có thể phối hợp các phương pháp với nhau

                Cho thêm a = 11

                a*k*k  mod  m = ???????

Chọn từ  ??????? ba số ở giữa là %%% hoặc  làm địa chỉ rải cho khóa k

Vd:Hàm băm Bậc hai: Cho a = 53, m = 331

       Tính giá trị băm cho các khóa sau:

       8947 8723 6374 6174 5451

     i   Key      a*key    a*key*key    HashValue

     1  8947     474191 4242586877          4

     2  8723     462319 4032808637        296

     3  6374     337822 2153277428        289

     4  6174     327222 2020268628        198

     5  5451     288903 1574810253        299

Vd: Hàm băm Tuyến tính: Cho a = 29, b = 49, m = 311

       Tính giá trị băm cho các khóa sau:

       5197 1213 1366 4244 9787

i   Key      a*key    a*key+b    HashValue

     1  5197     150713     150762        238

     2  1213      35177      35226         83

     3  1366      39614      39663        166

     4  4244     123076     123125        280

     5  9787     283823     283872        240