Bài giảng Kỹ thuật lập trình - Chương 7: Cấu trúc dữ liệu

uả
 IntStack *stack = CreateStack(MAX);
 do{
 //Tính chữ số bên phải nhất,đẩy vào stack
 PushStack(stack, n% b);
 n/= b; //Thay n = n/b để tính tiếp
 } while(n!= 0); //Lặp đến khi n = 0
 while( !IsEmptyStack(stack) ){
 // Rút lần lượt từng phần tửcủa stack
 PopStack(stack, &n);
 // chuyển sang dạng ký tự và in kết quả
 printf(“%c”, digitChar[n]); 
 }
}
 Ứng dụng
 Tính biểu thức dùng ký pháp hậu tố
▪ Biểu thức số học được biểu diễn bằng ký pháp trung tố. 
 ▫ Với phép toán 2 ngôi: Mỗi toán tử được đặt giữa hai toán hạng. 
 Với phép toán một ngôi: Toán tử được đặt trước toán hạng
 -2 + 3 * 5 (-2) + (3 * 5)
▪ Thứ tự ưu tiên của các toán tử
 () > ^ > * = % = / > + = –
 Ứng dụng
 Tính biểu thức dùng ký pháp hậu tố
 Ký pháp hậu tố
▪ Toán hạng đặt trước toán tử
▪ Không cần dùng các dấu ().
 Ví dụ
 a*b*c*d*e*f => ab*c*d*e*f*
 1 + (-5) / (6 * (7+8)) => 1 5 -6 7 8 + * / + 
 (x/y–a*b) * ((b+x) –y ) => x y / a b * –b x + y y ^ –*
 (x*y*z –x^2 / (y*2 –z^3) + 1/z) * (x –y) =>
 xy*z*x2^y2*z3^ –/ –1z/+xy –*
Ví dụ (7 –11) * 2 + 3
 Biểu thức hậu tố: 
 7 11 – 2 * 3 + 
 -5
 3 +
 -8 -8
 2 *
 - 4 - 4
 11 -
 7 7
 Ứng dụng
 Tính biểu thức dùng ký pháp hậu tố
▪ Tính giá trị của một một biểu thức hậu tố được lưu trong
một xâu ký tự và trả về giá trị kết quả
▪ Quy ước
 - Toán hạng: Là các số nguyên không âm một chữ số (cho đơn
 giản)
 - Toán tử: + , - , * , / , % , ^
bool isOperator(char op) {
 return op == '+‘ || op == '-' || 
 op == '*‘ || op == '%‘ || 
 op == '/‘ || op == '^‘ ;
}
int compute(int left, int right, char op) {
 int value;
 switch(op){
 case '+' : value = left + right; break;
 case '-' : value = left - right; break;
 case '*' : value = left * right; break;
 case '%‘ : value = left % right; break;
 case '/' : value = left / right; break;
 case '^' : value = pow(left, right); 
 }
 return value;
}
int TinhBtHauTo(string Bt) {
 int left, right, kq;
 char ch;
 IntStack *stack = CreateStack(MAX);
 for(int i=0; i < Bt.length(); i++)
 {
 ch = Bt[i];
 if ( isdigit(ch) )
 PushStack(stack, ch-'0'); 
 // đẩy toán hạng vào stack
 else if (isOperator(ch)) { 
 // rút stack 2 lần để lấy 2 toán hạng 
left và right
 PopStack(stack, &right);
 PopStack(stack, &left);
 kq =compute(left, right, ch); 
 // Tính "leftop right" 
 PushStack(stack, kq); 
 // Đẩy kq vào stack
 } else //không phải toán hạng hoặc toán tử
 printf(“Bieu thuc loi”);
 }
 // Kết thúc tính toán, giá trị biểu thức 
 // nằm trên đỉnh stack, đưa vào kq
 PopStack(stack, kq);
 Return kq;
}
4.
Hàng đợi
Queue
 Hàng đợi
 Queue
danh sách mà việc thêm 
phải được thực hiện tại 
một đầu còn xóa phải thực 
hiện tại đầu kia.
Thao tác trên
hàng đợi
Enqueue Front
. Thêm một phần tử . Phần tử đầu
. P: Tràn (overflow) . P: Queue rỗng
Dequeue Rear
. Xóa một phần tử . Phần tử cuối
. P: Underflow . P: Queue rỗng
 Hàng đợi
 Queue
▪ Phần tử đầu hàng sẽ được phục trước, phần tử này được gọi
là front, hay head của hàng. Tương tự, phần tử cuối hàng , 
cũng là phần tử vừa được thêm vào hàng, được gọi là rear 
hay tail của hàng.
▪ Biểu diễn hàng đợi
 ▫ Mô hình vật lý
 ▫ Hiện thực tuyến tính
 ▫ Hiện thực dãy vòng
 Mô hình 
 vật lý
▪ Dùng mảng. Phải nắm giữ cả front và rear.
▪ Giữ front luôn là vị trí đầu của dãy. 
 ▫ Thêm phần tử vào hàng ⇒ thêm vào cuối dãy. 
 ▫ Lấy ra 1 phần tử ra ⇒ dịch chuyển tất cả các phần tử của dãy
 lên 1 vị trí. 
▪ Tương tự hình ảnh hàng đợi trong thực tế
 ▫ Không phù hợp với lưu trữ trong máy tính
 Mô hình
 hiện thực tuyến tính
▪ Dùng 2 chỉ số front và rear để lưu trữ đầu và cuối hàng mà
không di chuyển các phần tử.
 ▫ Thêm phần tử vào hàng ⇒ Tăng rear lên 1 và thêm phần tử vào
 vị trí đó
 ▫ Lấy ra 1 phần tử ra ⇒ Lấy phần tử tại front và tăng front lên 1
▪ Nhược điểm: front và rear chỉ tăng mà không giảm ⇒ lãng
phí bộ nhớ
 ▫ Khắc phục: Khi hàng đợi rỗng thì ta gán lại front=rear=đầu dãy
 Mô hình
 hiện thực dãy vòng
▪ Dùng 1 dãy tuyến tính để mô phỏng 1 dãy vòng. 
 ▫ Các vị trí trong vòng tròn được đánh số từ 0 đến max-1, trong
 đó max là tổng số phần tử
 ▫ Để thực hiện dãy vòng, chúng ta cũng sử dụng các phân tử được
 đánh số tương tư dãy tuyến tính. 
 ▫ Sự thay đổi các chỉ số chỉ đơn giản là phép lấy phần dư số học: 
 khi một chỉ số vợt quá max-1, nó đc bắt đầu trở lại vợi trị 0. 
 ▸ Tương tự với việc cộng thêm giờ trên đồng hồ mặt tròn
 i = ((i+1) == max) ? 0: (i+1);
 hoặc if ((i+1) == max) i = 0; else i = i+1;
 hoặc i = (i+1) % max;
Mô hình
hiện thực dãy vòng
 Cấu trúc dữ liệu
 dùng mảng động
typedef struct intqueue{
 int *queueArr;
 int maxSize;
 int count;
 int front;
 int rear;
} IntQueue;
 Tạo
 hàng đợi
IntQueue *CreateQueue(int max){
 IntQueue *queue;
 queue = (IntQueue *)malloc(sizeof(IntQueue));
 /*Cấp phát cho mảng */
 queue->queueAry= malloc(max *sizeof(int));
 /* Khởi tạo queue rỗng */
 queue->front = -1;
 queue->rear = -1;
 queue->count = 0;
 queue->maxSize= maxSize;
 return queue;
} /* createQueue*/
 Thêm vào cuối 
 hàng đợi
int enqueue(struct intqueue *queue, int datain) 
{
 if (queue->count >= queue->maxSize) 
 return 0;
 (queue->count)++;
 queue->rear = (queue->rear + 1) % queue-
>maxSize;
 queue->queueAry[queue->rear] = datain;
 return 1;
}
 Xóa ở đầu
 hàng đợi
int dequeue(struct intqueue *queue, int *dOutPtr) 
 {if(!queue->count)
 return 0;
 *dOutPtr= queue->queueAry[queue->front];
 (queue->count)--;
 queue->front = (queue->front + 1) % queue-
>maxSize;
 return 1;
}
 Lấy phần tử 
 đầu
int Front(struct intqueue *queue,int *dOutPtr) { 
 if(!queue->count) 
 return 0;
 else{ 
 *dOutPtr= queue->queueAry[queue->front];
 return 1;
 }
}
 Lấy phần tử 
 cuối
int Rear(struct intqueue *queue,int*dOutPtr) {
 if(!queue->count) 
 return 0;
 else{ 
 *daOutPtr= queue->queueAry[queue->rear];
 return 1;
 }
}
 Kiểm tra 
 rỗng và đầy
▪ Empty
int isEmpty(struct intqueue *queue) 
{
 return(queue->count == 0);
}
▪ Full
int isFull(struct intqueue *queue) 
{
 return( queue->count == queue->maxSize);
}
 Xóa 
 hàng đợi
struct intqueue *destroyQueue(struct intqueue
*queue) 
{
 if(queue)
 {
 free(queue->queueAry); 
 free(queue);
 } 
 return NULL;
}
5.
Cây
Tree
 Cây
 Tree
▪ Nhược điểm của danh sách: Tính tuần tự, chỉ thể hiện được
các mối quan hệ tuyến tính.
▪ Cây được sử dụng để lưu trữ các thông tin phi tuyến như
 ▫ Các thư mục file
 ▫ Các bước di chuyển của các quân cờ
 ▫ Sơ đồ nhân sự của tổ chức
 ▫ Cây phả hệ
 Cây
 Tree
Một cây (tree) gồm một 
tập hữu hạn các nút (node) 
và 1 tập hữu hạn các cành
(branch) nối giữa các nút. 
 Định nghĩa 
 đệ quy
Một cây là tập các nút
o là tập rỗng, hoặc
o có 1 nút gọi là nút gốc 
 có 0 hoặc nhiều cây con, 
 các cây con cũng là cây
Biểu diễn
cây
 Các khái niệm
 cơ bản
▪ Cạnh đi vào nút gọi là cành vào (indegree), cành đi ra khỏi
nút gọi là cành ra (outdegree). 
▪ Số cạnh ra tại một nút gọi là bậc (degree) của nút đó. Nếu
cây không rỗng thì phải có 1 nút gọi là nút gốc (root), nút này
không có cạnh vào
▪ Các nút còn lại, mỗi nút phải có chính xác 1 cành vào. Tất cả
các nút đều có thể có 0,1 hoặc nhiều cành ra
Các khái niệm
cơ bản
Cây
con
Đường
đi
Độ sâu và
chiều cao
Cấp
 Cây
 nhị phân
▪ Mỗi nút có nhiều nhất 2 nút con: Nút trái và nút phải
▪ Một tập các nút T được gọi là cây nhị phân, nếu :
 a) Nó là cây rỗng, hoặc
 b) Gồm 3 tập con không trùng nhau:
 1) Một nút gốc
 2) Cây nhị phân con trái
 3) Cây nhị phân con phải
Cây nhị phân đầy đủ và
cây nhị phân hoàn chỉnh
▪Cây nhị phân đầy ▪Cây nhị phân hoàn
đủ chỉnh
▫Cây nút trừ nút lá có ▫Tất cả các nút lá có cùng độ
cấp bằng 2 sâu và tất cả các nút giữa có
 cấp bằng 2
 Cây
 cân bằng
▪ Khoảng cách từ 1 nút đến nút gốc xác định chi phí cần để
định vị nó: 
 ▫ 1 nút có độ sâu là 5 ⇒ phải đi từ nút gốc và qua 5 cành
▪ Nếu cây càng thấp thì việc tìm đến các nút sẽ càng nhanh. 
▪ Hệ số cân bằng của cây (balance factor) là số chênh lệch
giữa chiều cao của 2 cây con trái và phải của nó:
 B = HL-HR
▪ Một cây cân bằng khi B = 0 và các cây con của nó cũng cân
bằng
 Lưu trữ
 cây nhị phân
▪ Lưu trữ kế tiếp: Sử dụng mảng
▪ Lưu trữ móc nối: Sử dụng con trỏ
 Cấu trúc dữ liệu
 dùng mảng
typedef struct tree_node
{
 int data ;
 struct tree_node *left ;
 struct tree_node *right ;
}TREE_NODE;
 Tạo
 cây nhị phân
TREE_NODE *root, *leftChild, *rightChild;
// Tạo nút con trái
leftChild= (TREE_NODE *)malloc(sizeof(TREE_NODE));
leftChild->data = 20;
leftChild->left = leftChild->right = NULL;
// Tạo nút con phải
rightChild = (TREE_NODE *)malloc(sizeof(TREE_NODE)); 
rightChild->data = 30;
rightChild->left = rightChild->right = NULL;
// Tạo nút gốc
root = (TREE_NODE *)malloc(sizeof(TREE_NODE)); 
root->data = 10;
root->left = leftChild;
root->right = rightChild;
root->data= 50;// gán 50 cho root
 Duyệt
 cây nhị phân
▪ Duyệt theo thứ tự trước
▪ Duyệt theo thứ tự giữa
▪ Duyệt theo thứ tự sau
 Duyệt theo thứ tự
 trước
1. Thăm nút.
2. Duyệt cây con trái theo thứ tự trước.
3. Duyệt cây con phải theo thứ tự trước.
 Duyệt theo thứ tự
 giữa
1. Duyệt cây con trái theo thứ tự giữa
2. Thăm nút.
3. Duyệt cây con phải theo thứ tự giữa.
 Duyệt theo thứ tự
 sau
1. Duyệt cây con trái theo thứ tự sau.
2. Duyệt cây con phải theo thứ tự sau
3. Thăm nút
 Duyệt theo
 thứ tự trước
void Preorder(TREE_NODE *root)
{
 if (root != NULL)
 {
 // tham node
 printf("%d", root->data);
 // duyet cay con trai
 Preorder(root->left);
 // duyet cay con phai
 Preorder(root->right);
 }
}
 Ứng dụng của
 duyệt cây
1. Tính độ cao của cây
2. Đếm số nút lá trong cây
3. Tính kích thước của cây (số nút)
4. Sao chép cây
5. Xóa cây
 Tính độ cao
 của cây
int Height(TREE_NODE *tree)
{
 Int heightLeft, heightRight, heightval; 
 if( tree== NULL )
 heightval= -1; 
 else
 { // Sửdụng phương pháp duyệt theo thứ tự sau
 heightLeft= Height (tree->left); 
 heightRight= Height (tree->right); 
 heightval= 1 + max(heightLeft,heightRight);
 }
 return heightval; 
}
 Đếm số
 nút lá
int CountLeaf(TREE_NODE *tree)
{
 if (tree == NULL)
 return 0;
 int count = 0;
 //Đếm theo thứ tự sau
 count += CountLeaf(tree->left);// Đếm trái
 count += CountLeaf(tree->right);//Đếm phải
 //nếu nút tree là nút lá, tăng count
 if(tree->left == NULL && tree->right == NULL) 
 count++;
 return count;
}
 Tính
 kích thước
int TreeSize(TREE_NODE *tree)
{
 if(tree== NULL) 
 return 0; 
 else
 return( TreeSize(tree->left) + 
 TreeSize(tree->right) + 1 );
}
Sao chép
cây
 Sao chép
 cây
TREE_NODE *CopyTree(TREE_NODE *tree)
{
 // Dừng đệ quy khi cây rỗng
 if (tree== NULL) return NULL; 
 TREE_NODE *leftsub, *rightsub, *newnode;
 leftsub=CopyTree(tree->left); 
 rightsub= CopyTree(tree->right); 
 // tạo cây mới
 newnode= malloc(sizeof(TREE_NODE));
 newnode->data = tree->data;
 newnode->left = leftsub;
 newnode->right = rightsub;
 return newnode; 
}
 Xóa
 cây
void DeleteTree(TREE_NODE *tree)
{
//xóa theo thứ tự sau
 if(tree != NULL)
 {
 DeleteTree(tree->left); 
 DeleteTree(tree->right); 
 free(tree);
 }
}
 Ứng dụng của
 cây nhị phân
▪ Cây biểu diễn biểu thức
 ▫ Tính giá trị biểu thức
 ▫ Tính đạo hàm
▪ Cây quyết định
 Cây biểu diễn
 biểu thức
▪ là một loại cây nhị phân đặc biệt, trong đó:
 1. Mỗi nút lá chứa một toán hạng
 2. Mỗi nút giữa chứa một toán tử
 3. Cây con trái và phải của một nút toán tử thể hiện các biểu
 thức con cần được đánh giá trước khi thực hiện toán tử tại
 nút gốc
 Cây biểu diễn
 biểu thức
▪ Các mức chỉ ra thứ tự ưu tiên
 ▫ Các mức (độ sâu) của các nút chỉ ra thứ tự ưu tiên tương đối 
 của chúng trong biểu thức (không cần dùng ngoặc để thể hiện 
 thứ tự ưu tiên).
 ▫ Các phép toán tại mức cao hơn sẽ được tính sau các các phép 
 toán có mức thấp.
 ▫ Phép toán tại gốc luôn được thực hiện cuối cùng.
 Cây biểu diễn
 biểu thức
▪ Dễ dàng để tạo ra các biểu thức tiền tố, trung tố, hậu tố
▪ Trung tố: ( ( 8 -5 ) * ( ( 4 + 2 ) / 3 ) )
▪ Tiền tố: * -8 5 / + 4 2 3
▪ Hậu tố: 8 5 -4 2 + 3 / *
 (thực chất là các phép duyệt theo thứ tự giữa, trước và sau)
 Cài đặt
 cây biểu thức
▪ Mỗi nút có 2 con trỏ
struct TreeNode {
 InfoNode info ;// Dữ liệu
 TreeNode *left ;// Trỏ tới nút con trái
 TreeNode *right ; // Trỏ tới nút con phải
};
 Cài đặt
 cây biểu thức
▪ InfoNode có 2 dạng
enum OpType { OPERATOR, OPERAND } ;
struct InfoNode {
 OpType whichType;
 union // ANONYMOUS union
 {
 char operator;
 int operand ;
 }
};
 Cài đặt
 cây biểu thức
int Eval(TreeNode* ptr){ 
 switch(ptr->info.whichType) { 
 case OPERAND : 
 return ptr->info.operand;
 case OPERATOR :
 switch ( tree->info.operation ){
 case ‘+’: 
 return ( Eval(ptr->left) + Eval(ptr->right) ) ; 
 case ‘-’: 
 return ( Eval(ptr->left) – Eval(ptr->right) ) ;
 case ‘*’: 
 return ( Eval(ptr->left) * Eval(ptr->right) ) ;
 case ‘/’: 
 return ( Eval(ptr->left) / Eval(ptr->right) ) ;
 }
 }
}
 Cây
 tổng quát
▪ Biểu diễn giống như cây nhị phân?
 ▫ Mỗi nút sẽ chứa giá trị và các con trỏ trỏ đến các nút con của
 nó?
 ▫ Bao nhiêu con trỏ cho một nút? 
 Không hợp lý
▪ Mỗi nút sẽ chứa giá trị và một con trỏ trỏ đến một “tập” các
nút con
 ▫ Xây dựng “tập”? 
 Cây
 tổng quát
▪ Mỗi nút sẽ có 2 con trỏ: 
 ▫ một con trỏ trỏ đến nút con đầu tiên của nó, 
 ▫ con trỏ trỏ đến nút anh em kề với nó
Ví dụ
Cây tổng quát
 Duyệt
 cây tổng quát
▪ Thứ tự trước:
 1. Thăm gốc
 2. Duyệt cây con thứ nhất theo thứ tự trước
 3. Duyệt các cây con còn lại theo thứ tự trước
▪ Thứ tự giữa
 1. Duyệt cây con thứ nhất theo thứ tự giữa
 2. Thăm gốc
 3. Duyệt các cây con còn lại theo thứ tự giữa
▪ Thứ tự sau:
 1. Duyệt cây con thứ nhất theo thứ tự sau
 2. Duyệt các cây con còn lại theo thứ tự sau
 3. Thăm gốc
 Ứng dụng
 Cây quyết định
▪ Dùng để biểu diễn lời giải của bài toán cần quyết định lựa 
chọn
▪ Bài toán 8 đồng tiền vàng:
 ▫ Có 8 đồng tiền vàng a, b, c, d, e, f, g, h
 ▫ Có một đồng có trọng lượng không chuẩn
 ▫ Sử dụng một cân Roberval (2 đĩa)
 ▫ Output: 
 ▸ Đồng tiền k chuẩn là nặng hơn hay nhẹ hơn
 ▸ Số phép cân là ít nhất
Cây
quyết định
void EightCoins(a, b, c, d, e, f, g, h) {
 if (a+b+c == d+e+f) {
 if (g > h) Compare(g, h, a);
 else Compare(h, g, a);
 }
 else if (a+b+c > d+e+f){
 if (a+d == b+e) Compare(c, f, a);
 else if (a+d > b+e) Compare(a, e, b);
 else Compare(b, d, a);
 }
 else{
 if (a+d == b+e) Compare(f,c,a);
 else if (a+d > b+e) Compare(d, b, a);
 else Compare(e, a, b);
 }
}
// so sánh x với đồng tiền chuẩn z
void Compare(x,y,z){ 
 if(x>y) printf(“x nặng”);
 else printf(“y nhẹ”);
}
Thanks!
 Any questions?
 Email me at trungtt@soict.hust.edu.vn
 Presentation template by SlidesCarnival