Pcuoi = NULL;
}else if(Q == Pdau){ //Pdau trỏ vào Q
Pdau = Pdau -> P_R; //chuyển Pdau thành phần tử tiếp theo
Pdau -> P_L = NULL; //Vì bên trái của phần tử tiếp theo đó là Q nên phải đặt lại là NULL
}else if(Q == Pcuoi){ //Pcuoi trỏ vào Q, làm ngược lại bên trên
Pcuoi = Pcuoi -> P_L;
Pcuoi -> P_R = NULL;
}else{ //Q ở giữa list
Truoc = Q -> P_L; //lấy 2 phần tử trước và sau của nút Q
Sau = Q -> P_R;
//gán lại trước sau cho chúng nó
Truoc -> P_R = Sau;
Sau -> P_L = Truoc;
}
free(Q); //giải phóng bộ nhớ Q
}
3. Trình bày (bằng ngôn ngữ tựa C) giải thuật cộng 2 đa thức: C = A + B. Các phần tử trong mỗi đa thức có cấu trúc như sau:
HSO Ghi hệ số, MU Ghi số mũ, NEXT Ghi địa chỉ đến phần tử tiếp theoThemNut(HSO, MU, TONG, DUOI){
NUT = malloc();
NUT->HSO = HSO;
NUT->MU = MU;
NUT->NEXT = NULL;
if(TONG == NULL){
TONG = NUT;
}else if(TONG!=NULL){
DUOI->NEXT = NUT;
}
DUOI = NUT;
return DUOI;
}
CongDaThuc(D1, D2, TONG){
TONG = NULL;
DUOI = NULL;
while(D1 != NULL && D2 != NULL){
if(D1->MU > D2->MU){
//store D1 tong
DUOI = ThemNut(D1->HSO, D1->MU, TONG, DUOI);
//tinh tien 1 buoc
D1 = D1->NEXT;
}else if(D1->MU < D2->MU){
DUOI = ThemNut(D2->HSO, D2->MU, TONG, DUOI);
D2 = D2->NEXT;
}else{ //mu 1 == mu 2
DUOI = ThemNut(D1->HSO + D2->HSO, D1->MU, TONG, DUOI);
D1 = D1->NEXT;
D2 = D2->NEXT;
}
}
if(D1 != NULL){
while(D1 != NULL){
DUOI = ThemNut(D1->HSO, D1->MU, TONG, DUOI);
D1 = D1->NEXT;
}
}else if(D2 != NULL){
while(D2 != NULL){
DUOI = ThemNut(D2->HSO, D2->MU, TONG, DUOI);
D2 = D2->NEXT; } } return TONG; }
4. Trình bày (bằng ngôn ngữ tựa C) giải thuật định giá biểu thức hậu tố bằng cách dùng STACK. Minh hoạ diễn biến của quá trình đọc biểu thức và sự thay đổitrong STACK với biểu thức: 8 4 - 6 3 / + theo dạng: Diễn biến đọc biểu thức Diễn biến STACK Thực hiện phép toán
***Ý tưởng
Ta xem biểu thức hậu tố như một dãy các thành phần, mà mỗi thành phần là toán hạng hoặc toán tử
B1: Khởi tạo 1 stack rỗng
B2: Đọc lần lượt các phần tử của biểu thức từ trái qua phải
Nếu là toán hạng, đẩy vào stack
Nếu là toán tử X, lấy từ stack ra 2 giá trị (Y và Z) sau đó áp dụng toán tử đó vào 2 giá trị vừa lấy ra, đẩy kết quả tìm được (Z X Y) vào stack
B3: sau khi kết thúc B2, thì tất cả biểu thức hậu tố đã đọc xong, trong stack còn duy nhất 1 phần tử là giá trị của biểu thức***
DINH_GIA_BT(){
//sử dụng stack S, trỏ bởi T (top), ban đầu T = -1;
do(
X = ký tự tiếp theo;
if(X là toán hạng){
PUSH(STACK, T, X);
}else if(X là toán tử){
S1 = POP(STACK, T);
S2 = POP(STACK, T);
KQ = S2 X S1 //thực hiện phép toán
//(Phải là S2 X S1 vì S2 ở trước S1 (nên S2 ra sau))
PUSH(STACK, T, KQ);
}
)while(không gặp dấu kết thúc);
KQ = POP(STACK, T);
printf(KQ);
}
5. Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự trước
bằng giải thuật không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như
sau:
Ý tưởng:
Chia sẻ với bạn bè của bạn: |
