dungnvBài làm tham khảo đề ctdlgt đề 09-I-1 01
Thursday, December 18, 2014
Bài làm tham khảo đề ctdlgt
Câu 1 a
v a1: Hàm đếm số lượng các phần tử trong
danh sách. Count(l);
int
Count(node *l)
// dem so phan tu. cau 1 a1
{
int
dem=0;
node *p=l;
while
(p!=NULL)
{
dem++;
p=p->link;
}
return
dem;
}
Gọi hàm: Hàm trả về 1 số nguyên kiểu dữ liệu int. Do điểm mạnh của
danh sách liên kết là lưu trữ không giớ hạn phần tử nên việc điếm là hơi chung
chung. Nếu các bạn muốn đếm nhiều phần tử hơn thì đổi kiểu int thành kiểu khác
có giới hạn lớn hơn.
printf("\nDem so phan tu trong
dslk: %d",Count(l));
v a2: Hàm đảo ngược danh sách liên kết Reverse(l);
node *Reverse(node *l)
// dao dslk. cau 1 a2
{
node *p=l,*tg1,*tg2=NULL;
while
(p!=NULL)
{
tg1=p;
p=p->link;
tg1->link=tg2;
tg2=tg1;
}
return
tg1;
}
Gọi hàm: Hàm sẽ đảo danh sách liên kết. và trả về địa chỉ.
l=Reverse(l);
code đầy đủ bài. Các bạn
có thể tải về test thử.
·
Phần mô tả.
typedef struct node
{
int
info;
node *link;
};
·
Hàm
xem danh sách liên kết
void
xem(node *l)
//xem dslk
{
node *p=l;
while
(p!=NULL)
{
printf("%5d",p->info);
p=p->link;
}
}
·
Hàm
nhập danh sách lifo
node *nhap(node *l,int n)
//nhap dslk lifo
{
node *p;
for(int i=0;i<n;i++)
{
p=new(node);
printf("\nNhap phan tu thu
%d :",i);
scanf("%d",&p->info);
p->link=l;
l=p;
}
return
l;
}
Code c/c++
#include <stdio.h>
#include <conio.h>
typedef struct
node
{
int info;
node
*link;
};
void xem(node *l)
//xem dslk
{
node
*p=l;
while (p!=NULL)
{
printf("%5d",p->info);
p=p->link;
}
}
node *nhap(node *l,int n)
//nhap dslk lifo
{
node
*p;
for(int
i=0;i<n;i++)
{
p=new(node);
printf("\nNhap phan tu thu
%d :",i);
scanf("%d",&p->info);
p->link=l;
l=p;
}
return l;
}
int Count(node *l)
// dem so phan tu. cau 1 a1
{
int dem=0;
node
*p=l;
while (p!=NULL)
{
dem++;
p=p->link;
}
return dem;
}
node *Reverse(node *l)
// dao dslk. cau 1 a2
{
node
*p=l,*tg1,*tg2=NULL;
while (p!=NULL)
{
tg1=p;
p=p->link;
tg1->link=tg2;
tg2=tg1;
}
return tg1;
}
int main()
{
node
*l=NULL;
int n;
printf("\nNhap so phan tu : ");
scanf("%d",&n);
l=nhap(l,n);
printf("\nMang vua nhap ");
xem(l);
printf("\nDem so phan tu trong dslk: %d",Count(l));
printf("\nDanh sach lien ket sau khi dao nguoc");
l=Reverse(l);
xem(l);
getch();
}
test
Câu 2a. Viết biểu thức hậu tố
Biểu thức : A/(B+C)-D+E
Ký tự
|
Thao tác
|
stack
|
kết quả
|
A
|
Ghi A ra kết quả
|
A
|
|
/
|
Cho / vào stack
|
/
|
A
|
(
|
Cho ( vào stack
|
/(
|
A
|
B
|
Ghi B ra kết quả
|
/(
|
AB
|
+
|
Cho + vào stack
|
/(+
|
AB
|
C
|
Ghi C ra kết quả
|
/(+
|
ABC
|
)
|
Gặp ) đẩy + ra khỏi
stack
|
/
|
ABC+
|
-
|
Gặp - đẩy / ra khỏi
stack ghi vào kết quả, ghi - vào stack
|
-
|
ABC+/
|
D
|
Ghi D ra kết quả
|
-
|
ABC+/D
|
+
|
Gặp + đẩy - ra khỏi
stack ghi vào kết quả, ghi + vào stack
|
+
|
ABC+/D-
|
E
|
Ghi A ra kết quả
|
+
|
ABC+/D-E
|
Lấy các toán tử ra
khỏi stack ghi vào kết quả
|
ABC+/D-E+
|
Câu 2b. Vẽ Cây nhị phân
Phép duyệt trước NLR : +-/A+BCDE
Phép duyệt sau LRN : ABC+/D-E+
Câu 2c.
Minh họa quá trình định giá biểu thức hậu tố
|
|||
Biểu thức : 8 3 1 + /
2 - 4 +
|
|||
Ký tự
|
Thao tác
|
trạng thái stack
|
|
8
|
Đẩy 8 vào stack
|
8
|
|
3
|
Đẩy 3 vào stack
|
8,3
|
|
1
|
Đẩy 1 vào stack
|
8,3,1
|
|
+
|
Tính 1+3 đẩy 4 vào
stack
|
8,4
|
|
/
|
Tính 8/4 đẩy 2 vào
stack
|
2
|
|
2
|
Đẩy 2 vào stack
|
2,2
|
|
-
|
Tính 2-2 đẩy 0 vào
stack
|
0
|
|
4
|
Đẩy 4 vào stack
|
0,4
|
|
+
|
Tính 0+4 đẩy 4 vào
stack
|
4
|
|
câu 3a:
All comments [ 0 ]
Your comments