Cấu trúc đề:

1. Mảng 1 chiều, mỗi phần tử có kiểu struct. Tìm kiếm tuần tự, nhị phân. Sắp xếp chọn, chèn, nổi bọt, đổi chổ trực tiếp.

2. Danh sách liên kết: Khai báo danh sách liên kết, tìm kiếm, thêm , xoá, đếm, xuất,…

3. Cây nhị phân & cây nhị phân tìm kiếm (ko cần viết code): Xây dựng cây. Duyệt theo kiểu NLR, LNR, LRN. Các thao tác trên cây như tìm, thêm, xoá.

Tài liệu các bạn tìm ở đây nhe.

VD mẫu của cô cho:

1. Một chương trình quản lý kho hàng dùng mảng 1 chiều để lưu trữ, thông tin bao gồm Mã, tên, số lượng.
a/ KHai báo cấu trúc để lưu
b/ Viết hàm thêm vị trí của mặt hàng có mã là x bằng phương pháp tìm tuần tự, tìm nhị phân.
c/ Sắp xếp tăng dần theo đơn giá sử dụng các thuật toán: Sắp xếp chọn, chèn, nổi bọt, đổi chỗ trực tiếp.
[i]Bài giải bài này tương đương nó nè[/i] <=

2. Danh sách liên kết (thích chọn đơn hay kép thì chọn).
KHai báo, viết hàm tìm 1 phần tử x và thêm vào sau nó.
Tìm x, xoá phần tử đứng trước/sau nó.
Xuất các phần tử.
Đếm.
Tìm x, thêm ptử vào trước/sau nó.
Sắp xếp giảm dần.

3. Cây.
Cho dãy số 9,15,7,6,4,10,11,2,1,5,13,12,3,14,8.
Xây dựng cây nhị phân tìm kiếm.
Duyệt NLR, RLN, LNR.
Mô tả thuật toán xoá 1 nút trên cây. VD xoá nút 10.
Mô tả thuật toán thêm 1 nút.

Bài giải thử :-s

Câu 1:

[codes=c]#include

include

include

define MAX 100

typedef struct khohang
{
char mahang[10];
char tenhang[25];
int soluong;
int dongia;
}kho;

kho khohang[MAX];

void Nhap1ma(kho &x)
{
printf("Nhap ma hang:");
fflush(stdin);
gets(x.mahang);
printf("Nhap ten hang:");
fflush(stdin);
gets(x.tenhang);
printf("Nhap so luong:");
scanf("%d",&x.soluong);
printf("Nhap don gia:");
scanf("%d",&x.dongia);
}

void xuat1ma(kho x)
{
printf("\n—————————");
printf("\n|Ma hang : %s            ",x.mahang);
printf("\n|Ten hang: %s              ",x.tenhang);
printf("\n|So luong: %4d             ",x.soluong);
printf("\n|Don gia : %4d             ",x.dongia);
printf("\n—————————");
}

void nhapmang(kho a[],int &n)
{
printf("So mat hang can nhap:");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("\nNhap thong tin thu %d\n",i);
Nhap1ma(a[i]);
printf("\n————————————\n");
}
}

void xuatmang(kho a[],int n)
{
for(int i=0;i<n;i++)
{
xuat1ma(a[i]);

}
}

int timtuyentinh(kho a[],int n,char* x)
{
for(int i=0; i<n; i++)
{
if(strcmp(a[i].mahang,x)==0)
return i;
}
return -1;
}

int timnhiphan(kho a[], int n, char *x)
{
int left=0, right=n-1, mid;
while(left<=right)
{
mid=(left+right)/2;
if(strcmp(a[mid].mahang,x)==0)
return mid;
if(strcmp(a[mid].mahang,x)<0)
left=mid+1;
else
right=mid-1;
}
return -1;
}

void swap(kho &a, kho &b)
{
kho temp;
temp =a;
a=b;
b=temp;
}

void selection(kho a[],int n)
{
int min;
for(int i=0; i<n-1; i++)
{
min=i;
for(int j=i; j<n; j++)
if(strcmp(a[j].mahang,a[min].mahang)<0)
min=j;
swap(a[i], a[min]);
}
}

void InsertionSort(kho a[], int n)
{
int pos;
char w;
for(int i=1; i < n; i++)
{
w = a[i].mahang;
pos = i-1;
while ((pos >= 0) && (strcmp(a[pos].mahang,w)>0))
{
a[pos+1] = a[pos];
pos–;
}
a[pos+1].mahang = *w;
}
}

void bubble(kho a[], int n)
{
for(int i=0; i<n-1; i++)
for(int j=n-1; j<i; j++)
if(strcmp(a[j].mahang,a[j-1].mahang)<0)
swap(a[j], a[j-1]);
}

void interchange(kho a[], int n)
{
for(int i=0; i<n-1; i++)
for(int j=i+1; j<n; j++)
if(strcmp(a[i].mahang,a[j].mahang)>0)
swap(a[i], a[j]);
}

int main()
{

kho a[MAX];
int n;
char *x;
nhapmang(a,n);

printf("THONG KE KHO HANG :\n");
xuatmang(a,n);

printf("\n—————————");
printf("\nTim kiem tuan tu:");
printf("\nNhap ma hang can tim :");
fflush(stdin);
gets(x);
int kq=timtuyentinh(a,n,x);
if(kq==-1)
printf("\nKhong tim thay thong tin .");
else
xuat1ma(a[kq]);

printf("\n—————————");
printf("\nTim kiem nhi phan:");
printf("\nNhap ma hang can tim :");
selection(a,n);
fflush(stdin);
gets(x);
int kq2=timnhiphan(a,n,x);
if(kq2==-1)
printf("\nKhong tim thay thong tin .");
else
xuat1ma(a[kq2]);

printf("\n—————————");
printf("\nSap xep chon:");getch();
selection(a,n);
xuatmang(a,n);
printf("\n—————————");
printf("\nSap xep chen:");getch();
InsertionSort(a, n);
xuatmang(a,n);
printf("\n—————————");
printf("\nSap xep noi bot:");getch();
bubble(a,n);
xuatmang(a,n);
printf("\n—————————");
printf("\nSap xep truc tiep:");getch();
interchange(a,n);
xuatmang(a,n);
getch();
}
[/codes]

Câu 2:

Khai báo cấu trúc node quản lý dãy số nguyên:

[codes=c]typedef struct chuoi{
int  data;
struct chuoi *next;
};

chuoi *head;

void create(chuoi *&head)
{
head=NULL;
}

chuoi createchuoi(int x)
{
chuoi p=new chuoi;
p->data=x;
p->next=NULL;
return p;
}[/codes]

Nhập, xuất:

[codes=c]void nhap(chuoi*&head, int n)
{
int x;
for(int i=1; i<=n; i++)
{
printf("Nhap thong tin cua nut:"); scanf("%d", &x);
chendau(head,x);
}
}

void xuat(chuoi head)
{
for(chuoi p=head; p!=NULL; p=p->next)
printf("%4d", p->data);
}[/codes]

Tính tổng:

[codes=c]long tong(chuoi head)
{
long s=0;
for(chuoi p=head; p!=NULL; p=p->next)
{

s+=p->data;

}
return s;
}[/codes]

Tìm min, max:

[codes=c]int min(chuoi head)
{
int min = head->data;
for(chuoi p=head; p!=NULL; p=p->next)
{
if((p->data)<min)
min=p->data;
}
return min;
}

int max(chuoi head)
{
int max=head->data;
for(chuoi p=head; p!=NULL; p=p->next)
{
if(p->data>max)
max=p->data;
}
return max;
}[/codes]

Thêm đầu và thêm cuối:

[codes=c]void themdau(chuoi &head, int x)
{
chuoi p= createchuoi(x);
if(head==NULL)
head=p;
else
{
p->next=head;
head=p;
}

}

void themcuoi(chuoi &head, int x)
{
chuoi p=createchuoi(x);
if(head==NULL) head=p;
else
{
chuoi *t=head;
while(t->next!=NULL)
t=t->next;
t->next=p;
}
}[/codes]

Cấu trúc hàm main:

[codes=c]int main()
{
int x, n;
long s;
create(head);
//…
getch();
}[/codes]

Last modified on March 31st, 2021 at 1:06 am

10cth1 C