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);
intCount(node *l)
// dem so phan tu. cau 1 a1
{
intdem=0;
node *p=l;
while(p!=NULL)
{
dem++;
p=p->link;
}
returndem;
}
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;
}
returntg1;
}
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
{
intinfo;
node *link;
};
· Hàm xem danh sách liên kết
voidxem(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;
}
returnl;
}
Code c/c++
#include <stdio.h>
#include <conio.h>
typedef structnode
{
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(inti=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:
No comments:
Post a Comment