Ép kiểu
Thường sử dụng khi gán biểu thức gồm các
toán hạng khác kiểu.
Vd:
Muốn có giá trị chính xác trong phép chia hai
số nguyên cần dùng phép ép kiểu :
((float)a)/b
Để đổi giá trị thực r sang nguyên, ta dùng :
(int)(r+0.5)
149 trang |
Chia sẻ: lylyngoc | Lượt xem: 1467 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Ôn tập tốt nghiệp TC38, NC3 (2012), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Các môn:
1) Phƣơng pháp lập trình (1t)
2) Cấu trúc dữ liệu và giải thuật (2t)
3) Hệ cơ sở dữ liệu (2t)
ÔN TẬP TỐT NGHIỆP TC38, NC3 (2012)
GV: Bùi Thị Hạnh Tổ Công nghệ Thông tin Khoa Công nghệ
Ngày 24/6/2012
1
I. Kiểu dữ liệu cơ bản trong C++
II. Cấu trúc điều khiển
III. Các kiểu dữ liệu có cấu trúc
PHƢƠNG PHÁP LẬP TRÌNH
2
I. Kiểu dữ liệu cơ bản
Tên kiểu Kthước Miền giá trị Ghi chú
Char 01 byte -128 đến 127 Có thể dùng như số nguyên 1
byte có dấu hoặc kiểu ký tự
unsign char 01 byte 0 đến 255 Số nguyên 1 byte không dấu
Int 02 byte -32738 đến 32767
unsign int 02 byte 0 đến 65335 Có thể gọi tắt là unsign
Long 04 byte -232 đến 231 -1
unsign long 04 byte 0 đến 232-1
Float 04 byte 3.4E-38 3.4E38 Giới hạn chỉ trị tuyệt đối.Các
giá trị <3.4E-38 được coi = 0.
Tuy nhiên kiểu float chỉ có 7
chữ số có nghĩa.
Double 08 byte 1.7E-308
1.7E308
long double 10 byte 3.4E-4932
1.1E4932
Ép kiểu
Thường sử dụng khi gán biểu thức gồm các
toán hạng khác kiểu.
Vd:
Muốn có giá trị chính xác trong phép chia hai
số nguyên cần dùng phép ép kiểu :
((float)a)/b
Để đổi giá trị thực r sang nguyên, ta dùng :
(int)(r+0.5)
4
Các toán tử đặc biệt
Toán tử tăng giảm
k=5;++k + 10 ;// được 16
k++ +10; //được 15
--k+10; //được 14
k--+10; //được 15
Toán tử điều kiện
toán hạng 1 ? toán hạng 2 : toán hạng 3
Vd: int m = 1, n = 2;
int min = (m < n ? m : n); // min nhận giá trị 1
Toán tử sizeof(x):
Trả lại số bye mà x chiếm trong bộ nhớ
5
II. Cấu trúc điều khiển
Tuần tự
Phân nhánh
Không điều kiện : goto , break , continue ,
return
Có điều kiện : if ; switch
Lặp :
for
while
do … while
6
Goto
Lệnh nhảy goto là một lệnh nhảy đơn giản,
cho phép chương trình nhảy vô điều kiện tới
một vị trí trong chương trình thông qua tên
nhãn
Cách sử dụng lệnh goto:
Tạo một nhãn
goto đến nhãn
7
main()
{
int i = 0;
lap: // nhãn
cout<<i<<“:”;
i++;
if ( i < 10 )
goto lap; // nhãy về nhãn
lap
return 0;
}
i:0
i:1
i:2
i:3
i:4
i:5
i:6
i:7
i:8
i:9
8
Câu lệnh if
if (biểu thức điều kiện)
{
....
}
[else
{
...
}]
9
int s;
s = 3;
s += 1;
if (s > 5)
{
cout<<s;
}
else
{
cout<<s * 10;
}
10
Câu lệnh switch
switch (biểu thức điều kiện)
{
case :
[default:
]
}
11
int diem=7;
switch (diem)
{
case 3:
{
cout<<"Yeu";
break;
}
case 5:
{
cout<<"Trung binh";
break;
}
default:
{
cout<<"Khong biet";
break;
}
}
12
Câu lệnh for
for ([ phần khởi tạo] ; [biểu thức điều kiện]; [bước lặp])
{
;
;
;
}
13
for (int i = 2; i < 10; i++)
{
for (int j = 1; j <= 10; j++)
{
cout<<i<<"x“<<j<<"=“<<i*j<<" \n ");
}
}
14
Câu lệnh while
while (Biểu thức)
{
;
;
;
}
true
false
Các câu lệnh thực hiện Điều kiện
15
char pass = "ABCD";
char chuoi[5];
int solan;
solan = 0;
while (solan < 3)
{
cout<<"Nhap pass : ";
gets(chuoi);
if strcmp(chuoi, pass)
{
cout<<"Dung roi";
solan = 4;
}
else
{
cout<<"Sai roi";
solan += 1;
}
}
16
Câu lệnh do/while
do
{
;
;
;
}
while ( điều kiện )
true
false
Các câu lệnh thực hiện
Điều kiện
17
main()
{
int i = 11;
do
{
cout<<i;
i++;
} while ( i < 10 );
}
18
III. Kiểu dữ liệu có cấu trúc
1. Kiểu chuỗi ký tự:
Chuỗi ký tự trong C được cấu trúc như một chuỗi liên
tiếp các ký tự kết thúc bằng ký tự có mã ASCII bằng 0
(NULL character). Như vậy, giới hạn chiều dài của một
chuỗi ký tự trong C là 1 Segment (tối đa chứa 65335 ký
tự), ký tự đầu tiên được đánh số là ký tự thứ 0.
char S[10]; //Khai báo một chuỗi ký tự S có chiều dài
// tối đa 10 (kể cả kí tự kết thúc)
char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều
// dài bằng chiều dài của chuỗi "ABC"
// và giá trị khởi đầu của S là "ABC"
19
2. Kiểu mảng:
Kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử
của nó là một tập hợp có thứ tự các giá trị có cùng cấu
trúc được lưu trữ liên tiếp nhau trong bộ nhớ.
Mảng 1 chiều: [<Số phần
tử>];
Ví dụ int a[100];
int a[5] = (1, 7, -3, 8, 19);
int a[] = (1, 7, -3, 8, 19);
Mảng 2 chiều hay nhiều chiều:
[][]...;
int a[100][150];
int a[][]={{1, 7, -3, 8, 19}, {4, 5, 2, 8, 9}, {21, -7, 45, -3, 4}};
20
3. Kiểu cấu trúc
là kiểu dữ liệu mà trong đó mỗi phần tử của nó là tập
hợp các giá trị có thể khác cấu trúc.
typedef struct
{
;
;
…
}[];
Vd:
struct nguoi
{char HoTen[35];
int NamSinh;
char NoiSinh[40];
char GioiTinh;
char DiaChi[50];
char Ttgd;
}NGUOI; 21
4. Kiểu con trỏ
*
Vd: int a, b, *pa, *pb;
=&
định vị con trỏ đến địa chỉ của một biến đang
làm việc.
*
nội dung ô nhớ.
22
int main()
{
int a=2,b=3,c=4;
int *x=&a; //x=2
int *y;
*x=11; //a=11
y=&c; //y=4
c++; //c=5, y=5
x=&b; //x=3
b--;//b=2, x=2
cout<<a<<” “<<b<<endl;
cout<<*x<<” “<<*y<<endl;
return 0;
}
11 2
2 5 23
Con trỏ và mảng
* Con trỏ và mảng 1 chiều:
//nhập phần tử mảng
for(i=0;i<n;i++)
{
cout<<"Phan tu thu “<<i<<“:”;cin<<a+i;
}
//in ra mảng
for(i=0;i<n;i++) cout<<*(a+i)<<“ “;
* Con trỏ và mảng 2 chiều
float *pa= (float*) calloc(m*n,sizeof(float));
Để truy nhập đến phần tử pa[i][j] trong thân hàm,
dùng công thức:
*(pa+ i*n + j) //n là số cột
24
Con trỏ và tham chiếu của hàm
Khi nào sử dụng đối con trỏ (tham chiếu)
Khi muốn bảo lƣu lại kết quả tính toán
đƣợc của các đối số trong hàm để sử
dụng cho chƣơng trình gọi hàm có đối
số thì chúng ta phải khai báo đối số của
hàm là tham chiếu (con trỏ hay dạng địa
chỉ).
25
#include
#include
void HoanVi(int *a, int *b)
{
int c=*a;
*a=*b;
*b=c;
}
int main()
{
int m=20,n=30;
clrscr();
cout<<"Truoc khi goi ham m=“<<m<<“ n=“<<n;
HoanVi(&m,&n);
cout<<"Sau khi goi ham m=“<<m<<“ n=“<<n;
getch();
return 0;
}
26
Con trỏ và cấu trúc
->
(*).
Ví dụ:
struct Diem diemA={0,0};
struct Diem *pDiem;
pDiem = &diemA;
pDiem -> x = 5;
(*pDiem). y = 10;
27
I. Các giải thuật tìm kiếm
II. Các giải thuật sắp xếp
III. Đệ quy
IV. Danh sách đặc
V. Danh sách liên kết đơn
VI. Ngăn xếp (Stack) – Hàng đợi (Queue)
VII. Danh sách liên kết đôi
VIII. Cây nhị phân
IX. Cây nhị phân tìm kiếm
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
28
I. Các giải thuật tìm kiếm
Tìm tuần tự (Tìm tuyến tính) (Linear Search)
int LinearSearch (int a[], int n, int x)
{ int k = 0;
a[n]=x;
while (a[k] != x)
k++;
if (k <n)
return (k);// trả về vị trí tìm thấy
else return (-1);
}
29
Tìm nhị phân (Binary Search)
int BinarySearch( int a[], int n, int x)
{
int left=0, right=n-1, mid;
do
{
mid=(left+right)/2;
if(x==a[mid]) return(mid);
if(x<a[mid]) right=mid-1;
else left=mid+1;
} while(left<=right);
return (-1);
}
30
II. Các giải thuật sắp xếp
1. Đổi chỗ (Interchange Sort)
2. Nổi bọt (Bubble Sort)
3. Chèn (Insertion Sort)
4. Chọn (Selection Sort)
5. Nhanh (Quick Sort)
31
1. Interchange Sort
Đi từ đầu tiên, nếu có phần tử nào sau nó nhỏ hơn
thì thực hiện đổi chỗ.
void InterchangeSort(int a[], int N )
{
int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ
Doicho(a[i],a[j]);
}
32
33
Interchange Sort – Ví dụ
2 8 5 1 6 4 15 12
2 3 4 5 6 7 8 1
i
j
1
34
Interchange Sort – Ví dụ
12 8 5 2 6 4 15 1
2 3 4 5 6 7 8 1
i
j
2
35
Interchange Sort – Ví dụ
2 12 8 5 6 4 15 1
2 3 4 5 6 7 8 1
i
j
4
36
Interchange Sort – Ví dụ
2 4 12 8 6 5 15 1
2 3 4 5 6 7 8 1
i
j
5
37
Interchange Sort – Ví dụ
2 4 5 6 8 12 15 1
2 3 4 5 6 7 8 1
2. Buble Sort
Xuất phát từ cuối dãy đổi chỗ các cặp phần tử
kế cận để đưa phần tử nhỏ hơn trong cặp
phần tử đó về vị trí đúng đầu dãy hiện hành
void BubleSort(int a[], int n)
{ int i, j;
for (i = 0 ; i<n-1 ; i++)
for (j =n-1; j >i ; j --)
if(a[j]< a[j-1])// nếu sai vị trí thì đổi chỗ
Doicho(a[j],a[j-1]);
}
38
39
Bubble Sort – Ví dụ
2 8 5 1 6 4 15 12
2 3 4 5 6 7 8 1
i
j
1
40
Bubble Sort – Ví dụ
12 2 8 5 4 6 15 1
2 3 4 5 6 7 8 1
i
j
2
41
Bubble Sort – Ví dụ
2 12 4 8 5 6 15 1
2 3 4 5 6 7 8 1
i
j
4
42
Bubble Sort – Ví dụ
2 4 12 8 5 6 15 1
2 3 4 5 6 7 8 1
i
j
5
43
Bubble Sort – Ví dụ
2 4 5 12 8 6 15 1
2 3 4 5 6 7 8 1
i
j
6
44
Bubble Sort – Ví dụ
2 4 5 6 12 8 15 1
2 3 4 5 6 7 8 1
i
j
8
45
Bubble Sort – Ví dụ
2 4 5 6 8 12 15 1
2 3 4 5 6 7 8 1
i
j
3. Insertion Sort
Giả sử có một dãy a1 , a2 ,... ,an trong đó i phần tử
đầu tiên a1 , a2 ,... ,ai-1 đã có thứ tự.
Tìm cách chèn phần tử ai vào vị trí thích hợp của
đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở
nên có thứ tự.
46
47
Insertion Sort – Ví dụ
2 8 5 1 6 4 15 12
2 3 4 5 6 7 8 1
48
2 8 5 1 6 4 15 12
i
x
2 3 4 5 6 7 8 1
pos
2
Insertion Sort – Ví dụ
Insert a2 into (1, 2)
49
12 8 5 1 6 4 15 2
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a3 into (1, 3)
8
50
8 12 5 1 6 4 15 2
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a4 into (1, 4)
5
51
5 8 12 1 6 4 15 2
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a5 into (1, 5)
1
52
2 5 8 12 6 4 15 1
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a6 into (1, 6)
6
53
2 5 6 8 12 4 15 1
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a7 into (1, 7)
4
54
2 4 5 6 8 12 15 1
i
x
2 3 4 5 6 7 8 1
pos
Insertion Sort – Ví dụ
Insert a8 into (1, 8)
55
2 4 5 6 8 12 15 1
pos
2 3 4 5 6 7 8 1
Insertion Sort – Ví dụ
4. Selection Sort
Chọn phần tử nhỏ nhất trong N phần tử ban
đầu
Đưa phần tử này về vị trí đúng là đầu dãy
hiện hành
Xem dãy hiện hành chỉ còn N-1 phần tử của
dãy ban đầu
Bắt đầu từ vị trí thứ 2;
Lặp lại quá trình trên cho dãy hiện hành... đến khi
dãy hiện hành chỉ còn 1 phần tử
56
57
Selection sort – Ví dụ
2 8 5 1 6 4 15 12
i
min
2 3 4 5 6 7 8 1
Find MinPos(1, 8) Swap(ai, amin)
58
Selection sort – Ví dụ
2 8 5 12 6 4 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(2, 8) Swap(ai, amin)
59
Selection sort – Ví dụ
2 8 5 12 6 4 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(3, 8) Swap(ai, amin)
60
Selection sort – Ví dụ
2 4 5 12 6 8 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(4, 8) Swap(ai, amin)
61
Selection sort – Ví dụ
2 4 5 12 6 8 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(5, 8) Swap(ai, amin)
62
Selection sort – Ví dụ
2 4 5 6 12 8 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(6, 8) Swap(ai, amin)
63
Selection sort – Ví dụ
2 4 5 6 8 12 15 1
i
min
2 3 4 5 6 7 8 1
Find MinPos(7, 8) Swap(ai, amin)
5. QuickSort
Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc
phaân thaønh 3 ñoaïn:
a
k
< x , vôùi k = 0 .. (j-1)
a
k
= x , vôùi k = (j+1) .. (i-1)
a
k
> x , vôùi k = i..n
Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh
vieäc phaân hoaïch töøng daõy con theo cuøng phöông
phaùp phaân hoaïch daõy ban ñaàu vöøa trình baøy
64
65
Quick sort – Ví duï
2 8 5 1 6 4 15 12
2 3 4 5 6 7 8 1
left right
5 X
STOP
Not less than X
i j
STOP
Not greater than X
Phân hoạch dãy
66
Quick sort – Ví duï
2 8 5 1 6 12 15 4
2 3 4 5 6 7 8 1
left right
5 X
STOP
Not less than X
i j
STOP
Not greater than X
Phân hoạch dãy
67
Quick sort – Ví duï
2 1 5 8 6 12 15 4
2 3 4 5 6 7 8 1
left right
i j
68
6 X
Quick sort – Ví duï
2 4 5 8 6 12 15 1
2 3 4 5 6 7 8 1
left right
i j
STOP
Not less than X
STOP
Not greater than X
Sắp xếp đoạn 3
Phân hoạch dãy
69
Quick sort – Ví duï
2 4 5 6 8 12 15 1
2 3 4 5 6 7 8 1
left right
i j
Sắp xếp đoạn 3
III. Đệ quy
Chương trình đệ qui gồm hai phần chính:
Phần neo: Điều kiện thoát khỏi đệ qui
Phần đệ quy: Trong phần thân chương trình
có lời gọi đến chính bản thân chương trình
với giá trị mới của tham số nhỏ hơn giá trị
ban đầu
70
Cho hàm sau:
int Func( int n )
{
if (n == 5)
return 5;
else
return 2 * Func(n + 1); }
Cho biết kết quả khi gọi hàm Func(2) ?
71
IV. Danh sách đặc
Danh sách đặc là danh sách mà không gian bộ nhớ
lưu trữ các phần tử nằm kề cận nhau trong bộ nhớ.
Sử dụng kiểu mảng để định nghĩa danh sách đặc.
Khai báo:
VD: # define MaxLen 1000 //chiều dài tối đa
int n; //chiều dài thực
int a[MaxLen]; //khai báo danh sách a là 1 mảng
với MaxLen phần tử tối đa
2 1 4 7 4 8 3 6 4 7
0 1 2 3 4 5 6 7 8 9
72
Các thao tác trong danh sách đặc
Thêm 1 phần tử vào danh sách tại vị trí pos
Hủy 1 phần tử khỏi danh sách
Tìm kiếm
Sắp xếp
Tách
73
Thêm 1 phần tử x vào ds tại vị trí pos
Kiểm tra chiều dài thực có = chiều dài tối đa?
Thực hiện đi từ cuối danh sách đến vị trí pos, gán
giá trị thứ a[i]=a[i-1];
Đến vị trí pos, gán: a[pos]=x; chiều dài thực tăng
lên 1.
int Themphantu(int M[], int &n, int x, int pos)
{
if (Len == MaxLen) return (-1);
for (int i= n; i >pos; i--)
a[i] = a[i-1];
a[pos] = x;
n++; return (n);
}
74
Hủy 1 phần tử trong ds có vị trí del
Kiểm tra ds có rỗng và del>chiều dài thực?
Thực hiện đi từ vị trí del đến cuối dãy, gán giá trị a[i]
cho giá trị đứng sau nó a[i+1];
Chiều dài thực giảm 1.
int Xoaphantu(int a[], int &n, int del)
{
int (n ==0 || del >=Len) return (-1);
for (int i =del; i<n-1; i++)
a[i] = a[i+1];
n --;
return (n);
}
75
V. DSLK đơn( Singly Linked List)
DSLK đơn là chuỗi các node, được tổ chức
theo thứ tự tuyến tính
Mỗi node gồm 2 phần:
Phần Data, information :lưu trữ các thông
tin về bản thân phần tử.
Phần link hay con trỏ : lưu trữ địa chỉ của
phần tử kế tiếp; nếu là cuối ds thì =NULL.
Data Link
Node
76
Khai báo
typedef struct Node
{
int data;
NODE * link;
}NODE;
typedef struct List
{
NODE* first;
NODE* last;
}LIST;
77
Các thao tác
Tạo 1 nút
Thêm 1 nút vào danh sách
Xóa 1 nút khỏi danh sách
Duyệt danh sách
78
Tạo 1 nút DSLK đơn
NODE *GetNode(int x)
{
NODE *p;
// Cấp phát vùng nhớ cho phần tử
p = (NODE*)malloc(sizeof(NODE))//p= new NODE;
if (p==NULL)
{ cout<<“Khong du bo nho!”; exit(1);
}
p->data = x; // Gán thông tin cho phần tử p
p->link = NULL;
return p;
}
79
Thêm 1 nút vào đầu DSLK đơn
new_ele->link = l.first;
l.first = new_ele;
A B C D E
first
last
X new_ele
80
Thêm 1 nút vào cuối DSLK đơn
l.last->link = new_ele;
l.last = new_ele ;
A B C D E
first
last
X new_ele
81
Chèn 1 nút sau nút q
new_ele->link = q->link;
q->link = new_ele;
A B C D E
first
last
X new_ele
q q->link
82
Xóa 1 nút đầu DSLK đơn
if (l.first !=NULL)
{
NODE* p=l.first;
l.first=p->link;
if(l.first == NULL) l.last=NULL;//Nếu ds rỗng
free(p); //delete p;
}
A B C D E
first
last p
83
Xóa 1 nút sau nút q trong DSLK đơn
if(q !=NULL && q->link !=NULL)
{
NODE* p = q->link;
q->link = p->link;
if(p==l.last) l.last=q;
free(p);
}
A B C D E
first
last q p
84
Duyệt DSLK đơn
NODE* p=l.first;
while(p!=NULL)
{
coutdata<<“\t”;
p=p ->link; //trỏ đến phần tử kế tiếp
}
85
VI. Ngăn xếp (Stack) – Hàng đợi (Queue)
Stack là cấu trúc dữ liệu làm việc theo cơ chế
LIFO (Last In First Out)
Việc thêm (push) hoặc lấy (pop) thực hiện
theo cơ chế Vào sau Ra trước và thực hiện tại
1đầu của Stack.
Hiện thực Stack có thể có
thể dùng kiểu mảng hoặc
DSLK
Stack
86
Hàng đợi (Queue)
87
Queue là cấu trúc dữ liệu làm việc theo cơ chế
LIFO (Fisrt In First Out)
Việc thêm (Enqueue) hoặc lấy (Dequeue) thực
hiện theo cơ chế Vào trước Ra trước.
Việc thêm vào luôn diễn ra ở cuối queue và
việc lấy ra luôn diễn ra ở đầu queue.
Hiện thực Queue có thể có thể dùng kiểu
mảng hoặc DSLK
88
VII. DSLK đôi (Doubly Linked List)
Là danh sách mà mỗi node trong ds kết nối
với node đứng trước và node đứng sau trong
ds.
A B C D
89
VII. DSLK đôi (Doubly Linked List)
Là danh sách mà mỗi node trong ds kết nối
với node đứng trước và node đứng sau trong
ds.
A B C D
90
Khai báo DSLK đôi
typedef struct DNODE
{
Data Info;
DNode* pPre; // lưu trữ địa chỉ của node trước
DNode* pNext;// ưu trữ địa chỉ của node sau
};
typedef struct DLIST
{
DNODE* first; // con trỏ trỏ đến đầu ds
DNODE* last; // con trỏ trỏ cuối ds
};
91
Tạo 1 node
DNODE* GetNode(Data x)
{ DNODE *p;
p = new DNODE;
if ( p==NULL) return NULL;
p->Info = x;
p->pPrev = p->pNext = NULL;
return p;
}
92
Chèn vào đầu và cuối DSLK đôi
new_ele->pNext = l.first; // (1)
l.first->pPrev = new_ele; // (2
l.first = new_ele; // (3)
X
first
last
A B C D
(1)
(2) (3)
X
first
last
A B C D
(1)
(2)
(3)
l.last->Next = new_ele; // (1)
new_ele->pPrev = l.last; //(2)
l.last = new_ele; // (3)
93
Chèn vào sau node q
DNODE *p=q->pNext;
new_ele->pNext = p;//(1)
new_ele->pPrev = q//(2)
if(p != NULL) p->pPrev = new_ele; //(3)
q->pNext = new_ele; //(4)
X
first
last
A B C D
(1) (2)
(4) (3)
q
94
Chèn vào trƣớc node q
DNODE *p=q->pPrev;
new_ele->pNext = q;//(1)
new_ele->pPrev = p;//(2)
q->pPrev = new_ele;//(3)
if(p != NULL) p->pNext = new_ele;//(4)
X
first
last
A B C D
(1) (2)
(3) (4)
q
95
Hủy phần tử đầu và cuối DSLK đôi
Gán node tạm chứa địa chỉ node đầu hoặc cuối.
Cắt bỏ các mối liên kết
Xóa node tạm
Code xóa node đầu DSLK đôi:
p = l.first;
l.first = l.first->pNext;
l.first->pPrev = NULL;
delete p;
Code xóa node cuối DSLK đôi:
p = l.last;
l.last = l.last->pPrev;
l.last->pNext = NULL;
delete p;
96
Hủy node trƣớc hoặc sau node q
Cắt bỏ các mối liên kết với node trước hoặc sau q
Xóa node trước hoặc sau q
Code xóa node trước q
p = q ->pPrev;
q->pPrev = p->pPrev;
p->pPrev->pNext = q;
delete p;
Code xóa node sau q:
p = q ->pNext ;
q->pNext = p->pNext;
p->pNext->pPrev = q;
delete p;
97
VIII. Cây, cây nhị phân
Gốc(root)
Nút trong
lá
cha
và
con
98
Các khái niệm
Bậc của một nút : là số cây con của nút đó
Bậc của một cây : là bậc lớn nhất của các nút trong
cây. Cây có bậc n thì gọi là cây n-phân.
Nút gốc : là nút không có nút cha.
Nút lá : là nút có bậc bằng 0 .
Nút trong : là nút có bậc khác 0 và không phải là
gốc .
Mức của một nút:
Mức (gốc (T) ) = 0.
Gọi T1, T2, T3, ... , Tn là các cây con của T0 Mức
(T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) + 1.
Chiều cao (chiều sâu – depth) của cây là mức cao
nhất của cây + 1.
99
24/06/2012 100
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
A Tree Has Levels
LEVEL 0
24/06/2012 101
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Level One
LEVEL 1
24/06/2012 102
Owner
Jake
Manager Chef
Brad Carol
Waitress Waiter Cook Helper
Joyce Chris Max Len
Level Two
LEVEL 2
24/06/2012 103
Cây nhị phân
Cây nhị phân là cây mỗi