CTDL>

Trường THCN công kỹ nghệ
việt tiến

Đà Nẵng, tháng 7 năm 2004
bài mở đầu
I. Cấu trúc dữ liệu link
(Structure data )

- Một CTDL bao gồm một tập hợp các dữ liệu. Các dữ liệu này được liên kết với nhau bởi một phương pháp nào đó.
- Các dữ liệu có thể là dữ liệu đơn hoặc là một cấu trúc dữ liệu đã được xây dựng link
Giải thuật là dãy các câu lệnh xác định trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn các bước ta đạt được kết quả mong muốn link
II. Giải thuật (Algorithm)
- Input (Dữ liệu vào): Tập các giá trị cho trước
- Output (Dữ liệu ra): Kết quả của sự thực hiện giải thuật.

Như vậy, giải thuật và cấu trúc dữ
liệu liên hệ chặt chẽ với nhau, được
thể hiện qua công thức

CTDL + GT =Chương trình.
các kiểu dữ liệu đơn giản
bài 1

I. Mảng

- Khai báo:
[SoPTT ]
[= {Giá trị khởi gán}];
. Ví dụ: int a[100];i
- Truy cập: [ChiSo] ;lui
- Dùng vòng lặp:
Giả sử mảng a có n phần tử. Để duyệt qua tất cả các phần tử của mảng a ta dùng lệnh:
for (i =0; i Thực hiện các thao tác sau trên mảng số nguyên:
Nhập/xuất mảng.
Tính tổng các phần tử trong mảng.
Tính trung bình cộng các phần tử.
Đếm xem có bao nhiêu p.tử là số chẵn

bài 1

II. Bản ghi (RECORD)
Là các phần tử có kiểu kết hợp của các kiểu dữ liệu cơ sở hoặc kiểu dữ liệu đã định nghĩa trước.
Mỗi bộ giá trị là 1 bản ghi, mỗi thành phần con là một trường (Field) link
Khai báo cấu trúc:
typedef struct
{
;
;
.. .
;
};


- Khai báo biến:
;
- Truy cập:
. link
Ví dụ:
Sinh Viên(id, họ lót, tên, lớp, giới tính, quê quán,.)
Nhân viên(mã nv, họ lót, tên, phòng ban, giới tính,..)
Ví dụ:
Sinh Viên(id, họ lót, tên, lớp, giới tính, quê quán,.)
typedef struct sinhvien
{ long id;
char holot[30];
char ten[10];
char lop[6];
int gioitinh;//0: nam; -1 nữ
//char gioitinh[5];
};
//có thể thêm các trường: quê quán, địa chỉ trọ, sđt
Ví dụ 1:
Viết chương trình nhập thông tin một sinh viên, sau đó xuất thông tin sinh viên vừa nhập ra màn.
Ví dụ 2:
Viết chương trình nhâp từ bàn phím vào một danh sách sinh viên, xuất danh sách sinh viên vừa nhập ra màn hình.
Xuất danh sách sinh viên nữ ra màn hình
Xuất danh sách sinh viên lớp k5t1a
Vd: Định nghĩa kiểu dữ liệu phân số
typedef struct PhanSo
{ int tu;
int mau;
};

Viết chương trình nhập vào 2 phân số sau đó thực hiện các yêu cầu sau:
a. Tổng của 2 phân số
b. Hiệu của 2 phân số
c. Tích của 2 phân số
d. Thương của 2 phân số
bài 1
I. Mảng

II. Bản ghi
III. Con trỏ
Con trỏ là loại biến đặc biệt, không dùng để chứa dữ liệu mà chứa địa chỉ của một biến khác link
*;
- Ví dụ:
int *p;
=> Khai báo biến con trỏ p có kiểu dữ liệu nguyên (int) link
* Cấp phát:
=new
- Ví dụ: int *p;
//Cấp phát bộ nhớ cho con trỏ p kiểu nguyên. p = new int;
* Huỷ bỏ:
- Dùng hàm free (trong thư viện alloc.h)
hoặc hàm delete
* Phép toán & và phép *
Phộp toỏn & cho d?a ch? c?a d?i tu?ng:
Vớ d?:
int x =5, *p;
Thỡ khi gỏn p =&x;
S? gỏn d?a ch? c?a x cho p, p bõy gi? g?i l� "tr? t?i" x.
* Phộp toỏn *: d? l?y ra n?i dung c?a bi?n mà con trỏ trỏ (chỉ) tới.
Vớ d?: Ti?p vớ d? trờn
int y;
Gỏn:
y = *p;
S? gỏn cho y n?i dung c?a bi?n m� p tr? t?i, nghia l� y=5;
Bài tập:
(1) int i = 10, j = 20, *p =&i, *q = &j;
(2) cout<(3) cout<(4) cout<(5) *p = *q;
(6) i = 100;
(7) p = q;
bài 2
I. Sắp xếp

1. Phương pháp đổi chỗ trực tiếp link
2. Phương pháp chọn trực tiếp link
Bước 1: Thực hiện so sánh từng cặp phần tử của dãy a[0], a[1], .. ., a[n-1] để tìm phần tử nhỏ nhất để vào đầu dãy.
Bước 2: Thực hiện so sánh từ cặp phần tử của dãy a[1], a[2], .. ., a[n-1], sắp phần tử nhỏ nhất vào vị trí thứ 2 của dãy.
.. ..
Bước n-1: Thực hiện so sánh từng cặp phần tử của dãy a[n-2], a[n-1], sắp phần tử nhỏ nhất vào vị trí thứ n -1 của dãy nguồn.
* thuật toán
B1: i = 0; // bắt đầu từ đầu dãy
B2: j = i + 1; // tìm p.tử a[j] < a[i], j > i
B3: - Trong khi j < n thì thực hiện:
Nếu a[i] > a[j] thì hoán vị a[i] với a[j].
- j = j + 1
B4: i = i + 1;
Nếu i < n -1: lặp lại B2.
Ngược lại: thuật toán kết thúc.
* Cài đặt thuật toán
void sapxep(int a[100 ], int n)
{ int i, j;
for (i = 0 ; i < n - 1 ; i++)
for (j = i + 1; j < n ; j++)
if(a[j ] < a[i]) hoanvi( a[i], a[j]);
}// Hàm hoanvi(a, b) đã được định nghĩa trước.
Bài tập
1/ Viết chương trình hoàn thành thuật toán trên.
2/ Viết chương trình tìm số nhỏ nhất trong mảng, vị trí số nhỏ nhất.
Ví dụ: n=5;a[ ] = {10 15 5 20 40}
Kết quả: gtnn = 5
vtgvnn = 3
* ý tưởng
- Chọn phần tử nhỏ nhất trong dãy nguồn, sắp xếp nó vào vị trí đầu tiên trong dãy đích
- Chọn phần tử nhỏ nhất trong dãy nguồn còn lại (đây là phần tử nhỏ thứ hai), xếp nó vào vị trí thứ hai trong dãy đích
- Lặp lại việc này cho đến khi hết dãy nguồn
* thuật toán
B1: i = 0; // bắt đầu từ đầu dãy
B2: Tìm phần tử a[csnn] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].
B3: Hoán vị a[csnn] với a[i]
B4: Nếu i < n -1 thì i = i+ 1; lặp lại B2.
Ngược lại: thuật toán kết thúc.
* Cài đặt thuật toán
void sapxepchon(int a[100], int n )
{ int csnn;
for (int i=0; i < n -1 ; i++)
{ csnn = i;
for(int j = i+1; j < n ; j++)
if (a[j ] < a[csnn]) csnn = j;
hoanvi(a[csnn], a[i]);
}
}H?i: m?c dớnh l�m gỡ? Dóy a[i],,a[n-1]
Bài tập
Nhập/ xuất mảng số nguyên
Kiểm tra mảng vừa nhập đã có thứ tự tăng dần hay chưa?
+ Nếu chưa thì săp xếp mảng theo thứ tự tăng dần.
+ Ngược lại: thông báo mảng đã tăng dần.
Sử dụng IE, tìm demo của bài toán tháp hà nội
bài 2

II. Tìm kiếm
1. Tìm kiếm tuần tự link
2. Tìm kiếm nhị phân link
* ý tưởng:
- Xuất phát từ đầu dãy, so sánh lần lượt từng phần tử với giá trị tìm kiếm x, lặp cho đến khi:
+ Tìm thấy -> kết thúc hàm tìm kiếm (tìm kiếm thành công)
+ Hoặc hết dãy mà không tìm thấy-> kết thúc hàm tìm kiếm (tìm kiếm thất bại)
* thuật toán
- Bước 1: i = 0; //bắt đầu từ phần tử đầu tiên của dãy.
- Bước 2: So sánh a[i] với x, có 2 khả năng:
+ a[i] = x; Tìm thấy, dừng thuật tóan.
+ a[i] != x; Chuyển sang Bước 3.
- Bước 3:
i = i + 1; //xét tiếp ptử kế trong mảng.
Nếu i < n thì lặp lại Bước 2.
Ngược lại, không tìm thấy (thuật toán kết thúc).
int tktt(int a[50], int n, int x)
{
for(int i = 0; i < n; i++)
if(a[i]==x) return i;
return -1; //không tìm thấy
}
Ví dụ: Cài đặt thuật toán trên
Gửi mail nộp bài toán tháp Hà Nội.
* Thuật toán tìm kiếm nhị phân chỉ áp dụng cho các dãy đã được sắp xếp (tăng hoặc giảm)
Đặc tả:
Vào: - Chiều dài mảng (n)
- Tên mảng (a)
- Giá trị cần tìm (x).
Ra:
- Tìm thấy (chỉ số tương ứng)
- Không tìm thấy (chỉ số là -1)
Thuật toán:

Bước 1:
Khởi gán L = 0, R = n-1
Bước 2:
Nếu L <= R thì chuyển sang Bước 3
Ngược lại: kết thúc thuật toán (tìm kiếm thất bại).
Bước 3:
M = (L + R)/2;
So sánh a[M] với x:
. Nếu a[M] > x thì tìm tiếp trong nửa đầu dãy: L = 0; R = M -1 quay lại Bước 2.
. Nếu a[M] = x thì kết thúc tìm kiếm (tìm kiếm thành công).
. Nếu a[M] < x thì tìm tiếp trong nửa cuối dãy: L =M + 1; R = n-1 quay lại Bước 2.
Cài đặt thuật toán
int tknp(int a[100], int n, int x)
{ int l, r, m;
l =0; r = n-1;
while (l < = r)
{ m = (l + r)/2 ;
if( x== a[m]) return m;
else if (x > a[m]) l = m + 1;
else r = m - 1;
}
return -1;
}
* Cài đặt thuật toán
int tknhiphan(int a[50], int n, int x)
{ int left = 0, right = n -1, mid;
while (left < = right)
{ mid = (left + right)/2 ;
if( x== a[mid]) return mid;
else
if (x > a[mid]) left = mid + 1;
else right = mid - 1;
}
return -1;
}
bài 2

1. Khái niệm link
2. Cấu trúc của giải thuật đệ qui link
III. Đệ qui
3. ưu, nhược điểm link
Giải bài bài toán bằng cách rút gọn liên tiếp bài toán ban đầu về bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn gọi là đệ qui. lui
Một hàm đệ quy về cơ bản có 2 phần:
+ Phần cố định: chứa tác động của hàm với một giá trị cụ thể của tham số.
+ Phần hạ bậc: Lời gọi hàm đệ quy nhưng với dữ liệu đầu vào nhỏ hơn.
Ví dụ: Hàm đệ quy tính n!
long giaithua(int n)
{ if (n==1)
return 1;
else
return (n*giaithua(n-1));
} lui
* Ưu điểm: Đơn giản, dễ hiểu, dễ triển khai thành chương trình.
* Nhược điểm:
- Chiếm dụng nhiều bộ nhớ, dễ tràn ngăn xếp
- Khi chạy chương trình thường chậm.
BTVN:
Tính F(n) = 2 + 4 + .+ 2n; n >0
2. Tính F(n) = 1 + 3 +. + (2n -1); n>0
3. Tính tổng các chữ số của n
Ví dụ: n = 1234 -> Tổng = 10
4. Đếm n có bao nhiêu chữ số
Ví dụ: n = 1234 -> Đếm = 4
danh sách liên kết
bài 1
Khái niệm link
Danh sách liên kết là một dãy các nút được liên kết với nhau, mỗi nút gồm có 2 thành phần:

+ Thành phần thứ nhất chứa thông tin dữ liệu của nút gọi là data (value, infor)
+ Thành phần thứ hai chứa con trỏ chỉ đến nút tiếp (địa chỉ của nút tiếp theo) trong danh sách gọi là next (link) lui
bài 1

II. Cài đặt
1. Khai báo link
2. Khởi tạo link
3. Truy cập link
Cú pháp:
typedef struct node * list;
struct node
{ data;
list next;
};

Ví dụ: Khai báo một danh sách liên kết có tên là list, mỗi nút có chứa dữ liệu là số nguyên.
typedef struct node * list;
struct node { int data;
list next;
}; lui

Input(Vào): Biến con trỏ đầu (first-head) và cuối (last-tail)
Output(Ra): Trả về con trỏ rỗng (NULL) cho đầu và cuối của danh sách liên kết.
Cài đặt:
void khoitao(list * first, list * last)
{
*first = * last = NULL;
}

G/s một nút p của danh sách liên kết gồm có hai trường là data và next.
- Truy cập đến nút dữ liệu của nút p là: p -> data
- Truy cập đến con trỏ chỉ đến nút tiếp mà p chứa là: p -> next
bài 2
I. Thêm phần tử

1. Thêm vào đầu danh sách link
2. Thêm vào cuối danh sách link
3. Thêm vào vị trí bất kỳ link
first
last
p
Đặc tả:
Vào: . first, last: con trỏ chỉ đến nút đầu và cuối của dslk
. Giá trị x cần chèn vào đầu dslk.
Ra: Dslk mới đã chèn nút có giá trị là x thành công vào đầu danh sách.
Hướng dẫn:
Cấp phát vùng nhớ cho nút p (new), sau đó gán dữ liệu cần chèn x vào trường data và NULL vào trường next của nút p.
Nếu dslk rỗng thì: gán con trỏ first và last bằng con trỏ p.
list p = new node;
p - > data = x;
p -> next = NULL;
if(*first == NULL)
*last = *first = p;
1
2
1
1
2
Ngược lại:
. Gán trường next của con trỏ p bằng con trỏ first;
. Cập nhập con trỏ first bằng con trỏ p;
3
else
{ p -> next = *first;
*first = p;
}
3
Cài đặt:
void chendau(list *first, list *last, int x)
{ list p = new (node);
p -> data = x;
p -> next = NULL;
if(*first = = NULL)
*first = *last = p;
else { p -> next = *first;
*first = p;
}
}
1
2
3
Bài tập:
Viết chương trình thực hiện các thao tác sau trên danh sách liên kết theo cơ chế LIFO (Last In First Out = vào sau ra trước):
Nhập từ bàn phím vào 1 dãy số nguyên (nhập số không để thoát)
Xuất dãy số vừa nhập ra màn hình.
p
first
last
Hướng dẫn:
Cấp phát vùng nhớ cho nút p, gán dữ liệu cần chèn x vào trường data và giá trị NULL vào trường next của nút p.
Nếu dslk rỗng thì
. Gán con trỏ first và last bằng con trỏ p.
1
2
H­íng dÉn:
list p = new (node);
p - > data = x;
p -> next = NULL;
if(*first == NULL)
*last = *first = p;
1
2
Ngược lại
. Gán trường next của con trỏ last bằng con trỏ p;
. Cập nhật con trỏ last bằng con trỏ p;
3
3
Hướng dẫn:
else
{ (*last)-> next = p;
*last = p;
}

Bài tập:
Nhập từ bàn phím vào một danh sách liên kết theo cơ chế FIFO, kết thúc việc nhập bằng số không, xuất danh sách vừa nhập ra màn hình.
Bài tập:
Nhập/ xuất danh sách liên kết số nguyên (LIFO hoặc FIFO)
Đếm xem trong danh sách có bao nhiêu nút.
Tính tổng các giá trị của các nút.
Tính trung bình cộng các nút.
q
first
tmp
p
last
Đặc tả:
Vào: . Con trỏ first, last chỉ đến nút đầu và cuối của dslk.
. k: vị trí cần thêm.
. x: giá trị cần thêm
Ra: . Danh sách mới sau khi thêm nút có giá trị x vào vị trí k của danh sách.
Hướng dẫn:
Cấp phát vùng nhớ cho nút tmp, sau đó gán dữ liệu cần chèn x vào trường data và giá trị NULL vào trường next của nút tmp.
Nếu k = 1 thì:
. Thêm vào đầu danh sách.
Ngược lại:
. Xác định vị trí của p và q trong danh sách;
. Nếu k bằng tổng số nút và p khác NULL thì thêm nút (tmp) có dữ liệu cần thêm vào giữa con trỏ p và con trỏ q.
. Ngược lại, thông báo chèn không được
2
1
3
3.1
3.2
3.3
Ví dụ: 1-> 2-> 3-> NULL
k = 2, x = 10 => 1-> 10-> 2-> 3->NULL
k = 1, x = 20 =>20-> 1-> 2->3-> NULL
k = 5, x= 15 => Không chèn được
Bài tập: Viết chương trình thực hiện trên danh sách đơn:
- Nhập / xuất danh sách ra màn hình (kết thúc bằng số không).
- Thêm giá trị x vào vị trí k của danh sách.
- Xuất danh sách sau khi thêm x vào vị trí k của danh sách.
bài 2

1. Xóa vào đầu danh sách link
2. Xóavào cuối danh sách link
3. Xóa vào vị trí bất kỳ link
II. Xóa phần tử
first
last
Đặc tả:
Vào: . Con trỏ first, last chỉ đến nút đầu, cuối của dslk.
Ra: . Danh sách mới sau khi đã xóa thành công nút đầu của danh sách.
Hướng dẫn:
Nếu ds rỗng thì thông báo:
" Danh sach rong, khong the xoa duoc".
Ngược lại:
+ Gán con trỏ p bằng first;
+ Nếu danh sách chỉ có một nút thì:
*first = NULL;
1
2
+ Ngược lại:
.Tách p (nút đầu tiên) ra khỏi danh sách liên kết.
+ Huỷ con trỏ do p trỏ tới.
2.1
2.2
2.3
Bài tập: Viết chương trình thực hiện trên d.sách:
+ Nhập/xuất một ds số thực, kết thúc việc nhập bằng số không.
+ Xóa phần tử đầu tiên của danh sách.
+ Xuất danh sách sau khi xóa phần tử đầu tiên của danh sách. link
first
Đặc tả:
Vào: . Con trỏ first, last chỉ đến nút đầu tiên của dslk.
Ra: . Danh sách mới sau khi đã xóa thành công phần tử cuối của danh sách.
Hướng dẫn:
Nếu ds rỗng thì thông báo:
" Danh sach rong, khong the xoa duoc".
Ngược lại:
+ Gán con trỏ p bằng f;
+ Nếu danh sách chỉ có một nút thì:
.Gán f bằng giá trị NULL.
+ Ngược lại:
. Xác định nút gần cuối cp của danh sách.
. Tách nút cuối p ra khỏi danh sách.
+ Hủy con trỏ mà p trỏ tới.
Bài tập: Viết chương trình thực hiện trên d.sách liên kết:
+ Nhập /xuất danh sách.
+ Xóa phần tử cuối cùng của danh sách.
+ Xuất danh sách sau khi xóa phần tử cuối cùng của danh sách. link
p
q
first
Vào: . Con trỏ first, last chỉ đến nút đầu tiên và nút cuối của dslk.
. Vị trí của nút cần xóa (k).
Ra: . Danh sách mới sau khi đã xóa thành công phần tử ở vị trí k của danh sách.
Hướng dẫn:
Nếu ds rỗng thì thông báo:
"Danh sach rong, xoa khong duoc!";
Ngược lại:
{ Nếu k bằng một thì:
Xoá nút đầu của DS;
Ngược lại:
{ . X¸c ®Þnh vÞ trÝ cña nót p vµ q trong danh s¸ch (p ë vÞ trÝ k – 1, q ë vÞ trÝ k);
. NÕu k b»ng tæng sè nót vµ q kh¸c NULL th× t¸ch nót q ra khái danh s¸ch
. Ng­îc l¹i, th«ng b¸o xãa kh«ng ®­îc
}
Hñy con trá p.
}
Bài tập: Viết chương trình thực hiện trên d.sách:
+ Nhập /Xuất danh sách liên kết
+ Xóa phần tử ở vị trí k của danh sách.
+ Xuất danh sách sau khi xóa thành công phần tử ở vị trí k của danh sách.
Ngăn xếp hàng đợi
bài 1
I. Khái niệm lui

II. Các thao tác trên ngăn xếp
1. Cài đặt link
2. Đẩy phần tử vào ngăn xếp link
3. Lấy phần tử ra khỏi ngăn xếp link
Ngăn xếp (stack) là một kiểu Ds tuyến tính đặc biệt mà phép bổ sung hay loại bỏ luôn thực hiện ở một đầu gọi là đỉnh.
Do vậy cơ chế thêm vào và lấy ra của ngăn xếp là Vào sau- Ra trước (LIFO) lui
lui
bài 1
I. Khái niệm lui

II. Các thao tác trên ngăn xếp
1. Cài đặt link
2. Đẩy phần tử vào ngăn xếp link
3. Lấy phần tử ra khỏi ngăn xếp link
- Khai báo: Dùng cấu trúc struct
typedef struct node *stack;
struct {
int value;
stack next;
};
- Khởi tạo ngăn xếp rỗng
void init(stack * s)
{
*s=NULL;
}
- Kiểm tra ngăn xếp rỗng:
Ngăn xếp rỗng thì trả về giá trị 1, ngược lại trả về giá trị 0
int emty(stack s)
{
if (s= =NULL)
return 1;
else return 0;
} lui
void push (stack *s, int x)
{
stack tmp;
tmp=new stack;
tmp->value=x;
tmp->next=*s;
*s=tmp;
}
Ví Dụ









Thêm phần tử 2 vào ngăn xếp:

lui
ý tưởng:
+ Kiểm tra ngăn xếp: Nếu ngăn xếp rỗng. Ta không xóa được và thông báo ngăn xếp rỗng
if (empty(s)==1)
cout<< " Ngan xep rong";

+ Ngược lại (Ngăn xếp không rỗng):
Dùng 1 con trỏ kiểu stack trỏ đến đỉnh ngăn xếp
Cho con trỏ s trỏ đến phần tử tiếp theo trong ngăn xếp
Lấy phần tử ở đỉnh ngăn xếp
stack tmp;
tmp=*s;
*s=(*s)->next;
x=tmp->value;// lay gia tri o nut xoa
delete (tmp);
Mô phỏng
void pop(stack * s, int &x)
{
if(!empty(*s))
cout<< “ Ngan xep rong”;
else
{ stack tmp;
tmp= *s;
*s=(*s)->next;
x=tmp->value;
delete (tmp);
}
}
bài 2
I. Khái niệm lui

II. Các thao tác trên hàng đợi
1. Cài đặt link
2. Đẩy phần tử vào hàng đợi link
3. Lấy phần tử ra khỏi hàng đợi link
Hàng đợi (Queue) là 1 kiểu danh sách tuyến tính mà phép bổ sung được thực hiện ở một đầu (gọi là lối sau - rear ), phép loại bỏ thực hiện ở một đầu khác (gọi là lối trước - front)
Mô phỏng
lui
bài 2
I. Khái niệm lui

II. Các thao tác trên hàng đợi
1. Cài đặt link
2. Đẩy phần tử vào hàng đợi link
3. Lấy phần tử ra khỏi hàng đợi link
Khai báo
typedef struct Node * pointer;
struct Node
{
int value;
pointer next;
};
struct Queue
{
pointer front;
pointer rear;
};
Khởi tạo
- Khởi tạo hàng đợi rỗng
void Init (Queue *&q)
{
q->front=NULL;
}
Kiểm tra hàng đợi rỗng:
- Hàng đợi rỗng khi front trỏ vào NULL
- Hàm kiểm tra hàng đợi rỗng trả về giá trị 1 nếu hàng đợi rỗng, ngược lại trả về giá trị 0
int Empty(Queue * q)
{
if(q->front==NULL ) return 1;
return 0;
}lui
- Thêm phần tử x vào hàng đợi q được thực hiện tại đầu rear.
- Dùng thêm biến ok để dùng trong chương trình chính sau này:
+ Biến ok sẽ có tác dụng kiểm tra việc có thêm phần tử vào hàng đợi nữa hay không.
+Biến ok cũng dùng để kiểm tra hàng đợi còn phần tử để lấy ra không?
void Add_Q (int x, Queue *& q, int & ok)
{ pointer tmp;
tmp=new Node;
tmp->value=x;
tmp->next=NULL;

if (Empty(q))
{ q->front=q->rear=tmp;
}
else
{
(q->rear)->next=tmp;
(q->rear) =tmp;
}
ok=1;
} lui
void Pop_Queue(Queue *&q, int &x,int &ok)
{ pointer tmp;
if(Empty(q)) ok=0;
else
{
ok=1;
tmp=q->front;
x=(q->front)->value;
q->front=(q->front)->next;
delete(tmp);
}
}

CHương 4: cây
I. Định nghĩa

II. Các khái niệm:
1. Cấp link
2. Mứclink
3. Độ caolink
I. Định nghĩa:
Cây là 1 tập hợp T các phần tử (gọi là nút) trong đó có 1 nút đặc biệt đước gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2, .., Tn theo quan hệ phân cấp trong đó Ti cũng là cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp (i + 1). Quan hệ này người ta còn gọi là quan hệ cha- con.
1. Cấp
- Bậc của một nút: là số cây con của nút đó.
- Cấp của một cây: là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). Cây có bặc n thì gọi là cây n - phân.
II. Các khái niệm:
2. Mức:
Mức (gốc(T)) = 0
Gọi T1, T2, .., Tn là các cây con của T0
Mức (T1) = Mức (T2) = .. .= Mức (Tn) = Mức (T0) + 1
3. Độ cao:
Bài 2: Cây nhị phân
I. Khái niệm:
II. Tạo cây:
III. Duyệt cây:

I. Khái niệm:
1. Khái niệm:
Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con.


Ví dụ:


Cây nhị phân có thể ứng dụng
trong nhiều bài toán thông dụng.
Ví dụ dưới đây cho ta hình ảnh
của một biểu thức toán học

2. Cài đặt:
typedef struct TNODE TREE;
struct TNODE
{ Data Key;
//Data l� kdl ?ng v?i t.tin luu t?i nỳt
TNODE *pLeft, *pRight;
};
II. Tạo cây:
III. Duyệt cây: