[Toán Cấu trúc rời rạc] Cấu trúc dữ liệu và giải thuật(CODE)

Bài giải siêu chi tiết giải thuật Nổi bọt (Bubble sort); Chọn (selection sort); Đổi chổ (Interexchange sort) và Phân hoạch (Quick sort); Danh sách liên kết đơn

Câu 1:
Giá trị trong mảng chứa n phần tử, được so sánh tuần tự với dữ liệu X. Nếu dữ liệu X “trùng khớp” với giá trị nào đó trong mảng, “thoát” là được thực hiện. Ngoài ra, dữ liệu X được lưu giữ vào vị trí có chỉ số n+1.

Chỉ số	1	2	3	…	i	…	n	n+1
Giá trị	A[1]	A[2]	A[3]	…	A[i]	…	A[n]	X

Thuật toán duyệt tuyến tính tìm X theo mô tả ở trên được đề xuất như sau:.

Dựa vào tư tưởng tìm X ở trên, viết hàm SearchX(int A[], int n, int X) trả về vị trí xuất hiện X trong dãy A hoặc trả về -1 nếu không tìm thấy.
Viết chương trình thực hiện tuần tự 3 công việc sau:
– Tạo dãy A có n (1≤n≤100) phần tử
– Xuất dãy các phần tử của dãy A (cách nhau 1 ký tự trắng)
– Nhập giá trị X cần tìm, thông báo lên màn hình vị trí xuất hiện X trong dãy hoặc thông báo “Khong tim thay” trong trường hợp ngược lại.

CODE:

#include <stdio.h>

void input(int a[], int n)   /*Hàm nhập mảng*/
{
    for(int i=0; i<n; i++) {
        printf("a[%d]", i);
        scanf("%d", &a[i]);
    }
}

void output(int a[], int n)   /*Hàm xuất mảng*/
{
    for(int i=0; i<n; i++) {
            printf("%d\t", a[i]);
    }
}

void timkiem(int a[],int n,int x)   /*Hàm tìm kiếm*/
{
    int dem=0, vitri =0;
    printf("Nhap x ban muon tim: "); scanf("%d", &x);
    for(int i=0;i<n;i++)
        if(a[i]==x) {
            dem++;
            vitri = i+1;
        }
        if(dem!=0)
            printf("Phan tu %d co trong mang va o vi tri %d\n", x, vitri);
        else
            printf("Phan tu %d khong co trong mang\n",x);
}

int main()
{
    int a[50], n, x;
    printf("Nhap n phan tu:");
    scanf("%d", &n);
    input(a,n);
    output(a,n);
    printf("\n");
    timkiem(a,n,x);
    return 0;
}

Câu 2:
Cài đặt các giải thuật Nổi bọt (Bubble sort); Chọn (selection sort); Đổi chổ (Interexchange sort) và Phân hoạch (Quick sort)

Yêu cầu:

Cài đặt hàm void input(int a[], int *n) để tạo dãy các số nguyên A có n phần tử bằng cách nhận từng phần tử từ bàn phím.
Cài đặt hàm void output(int a[], int n) để xuất ra màn hình các phần tử của dãy A, viết cách nhau 1 ký tự trắng.
Cài đặt các thuật toán sắp xếp bằng kỹ thuật Nổi bọt (bubble sort); Chọn (selection sort); Đổi chổ (Interexchange sort) và Phân hoạch (Quick sort). Mỗi thuật toán được cài đặt bằng 1 hàm với tham số vào là dãy A có cỡ dữ liệu n.
Dãy A gồm n phần tử đã được sắp xếp tăng, cài đặt hàm void insert(int A, int n, int X) để chèn X vào A sao cho dãy thu được vẫn đảm bảo thứ tự tăng.
Viết chương trình hiển thị menu như bên dưới, cho phép người dùng kiểm tra các chức năng tương ứng. Muốn kết thúc, nhập 8 để thoát khỏi chương trình.

Chuong trinh sap xep day:

Nhap day // Nhập dãy A
Xuat day // Xuất dãy A
Noi bot // Nổi bọt
Chon // Chọn
Doi cho // Đổi chỗ
Phan hoach // Phân hoạch – Sắp xếp nhanh
Chen phan tu // Chèn X vào dãy A
Thoat // Kết thúc chương trình

Nhap vao 1 so tu 1..7 de thuc hien chuc nang tuong ung. Nhap 8 de ket thuc chuong trinh.

CODE:

#include <stdio.h>      
void nhapmang(int a[], int n)
{
    for(int i=0; i<n; i++) {
        printf("a[%d]: ", i);
        scanf("%d", &a[i]);
    }
}
void xuatmang(int a[], int n)
{
    for(int i=0; i< n; i++)
        printf("%d\t", a[i]);
}
void noibot(int a[], int n)
{
    int temp = 0;
    for(int i=0; i<n; i++)
        for(int j= n-i; j>i; j--)
            if(a[i]<a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
}
void doicho(int a[], int n)
{
    int temp1 = 0;
    for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++)
    if(a[j]<a[i]) {
        temp1=a[i];
        a[i] = a[j];
        a[j] = temp1;
    }
}
void phanhoach(int a[], int left, int right) //Quicksort
{
    int i, j ,x, temp3;
    if(left >= right) return;
    x = a[(left + right)/2];
    i = left;
    j = right;
    do{
        while(a[i] < x) i++;
        while(a[j] > x) j--;
        if(i <= j) {
            temp3 = a[i];
            a[i] = a[j];
            a[j] = temp3;
            i++;
            j--;
        }
    } while(i < j);
    if(left < j) phanhoach(a, left, j);
    if(i<right) phanhoach(a, i, right);
}
void chon(int a[], int n)
{
    int min = 0, temp2;
    for(int i=0; i<n-1; i++) {
        min = i;
        for(int j = i+1; j<n; j++)
            if(a[j] < a[min]) 
                min=j; 
            if(min != i) {
                temp2 = a[min];
                a[min] = a[i];
                a[i] = temp2;
            }
    }
}
void them(int a[], int &n, int k, int x)
{
    int i;
    printf("Nhap vi tri can chen: ");
    scanf("%d", &k);
    printf("Nhap gia tri muon chen: ");
    scanf("%d", &x);
    for(i=n;i>=k;i--) { a[i]=a[i-1]; }
    a[k-1]=x;
    n++;
}
int main()
{
    int a[50], n, choice = 0, left, right,x,k;
    printf("Nhap n phan tu:");
    scanf("%d", &n);
    printf("*****Chuong trinh sap xep day*****\n");
    do
    {
        printf("1. Nhap mang.");
        printf("2. Xuat mang.");
        printf("3. Sap xep noi bot.");
        printf("4. Sap xep chon.");
        printf("5. Sap xep doi cho.");
        printf("6. Sap xep phan hoach.");
        printf("7. Chen x.");
        printf("8. Thoat.");
        printf("\nNhap lua chon cua ban:"); scanf("%d", &choice);
        switch(choice)
        {
        case 1:
            nhapmang(a,n);
            break;
        case 2:
            printf("Mang vua nhap la:\n");
            xuatmang(a,n);
            break;
        case 3:
            noibot(a,n);
            xuatmang(a,n);
            break;
        case 4:
            chon(a,n);
            xuatmang(a,n);
            break;
        case 5:
            doicho(a,n);
            xuatmang(a,n);
            break;
        case 6:
            phanhoach(a, left, right);
            xuatmang(a,n);
            break;
        case 7:
            them(a,n,k,x);
            xuatmang(a,n);
            break;
        case 8:
           printf("\t****~~^o^End^o^~~****\n");
           printf("\n");
           break;
        }
    } while(choice < 8);
}

Câu 3

Viết chương trình thực hiện 3 công việc sau:

Nhập dãy A gồm n số thực dương (các phần tử của dãy phải >0). Xuất dãy vừa nhập với các phần tử cách nhau 1 khoảng trắng.
Sắp xếp để được dãy giảm dần. Hiển thị dãy sau khi sắp xếp.
Cho dãy B gồm 3 phần tử có giá trị lần lượt là 2, 22, 222 (int B[] = {2, 22, 222}). Chèn các phần tử của B vào A sao cho dãy A thu được vẫn có thứ tự giảm dần. Hiển thị dãy A sau khi thực hiện chèn B vào A.

Gợi ý: Xây dựng các chương trình con thực hiện nhập mảng, xuất mảng, sắp xếp mảng và chèn mảng. Sau đó viết hàm main() gọi các hàm đã viết để hoàn thiện các yêu cầu trên.

CODE:

#include <conio.h>
#include <stdio.h>
void nhapmang(int a[], int &n)
{
    for(int i=0;i<n;i++) {
        printf("Phan tu %d= ",i+1);
        scanf("%d",&a[i]);
    }
}
void xuatmang(int a[], int n)
{
    for(int i=0;i<n;i++) {
        printf("%d\t",a[i]);
    }
}
void ghep(int a[], int n, int b[], int m, int c[], int &k)
{
    k = m + n;
    for(int i = 0; i<k; i++)
    if(i<n)
        c[i] = a[i];
    else
        c[i] = b[i-n];
}
void noibot(int a[], int n)/*giam dan*/
{
    int temp = 0;
    for(int i=0; i<n; i++)
        for(int j= n-i; j>i; j--)
            if(a[i]<a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
}
int main()
{
    int a[50],n;
    int b[50],m;
    int c[100], k;
    printf("Nhap mang A voi n ptu: ");
    printf("\nNhap so phan tu: ");
    scanf("%d",&n);
    nhapmang(a,n);
    printf("Nhap mang B voi m ptu: ");
    printf("\nNhap so phan tu: ");
    scanf("%d",&m);
    nhapmang(b,m);
    ghep(a,n,b,m,c,k);
    xuatmang(c,k);
    printf("\n");
    noibot(c,k);
    xuatmang(c,k);
    return 0;
}

Câu 4. (3đ)

Định nghĩa NODE là cấu trúc gồm 2 thành phần: DATA lưu một số nguyên và NEXT là con trỏ lưu địa chỉ của một NODE khác.
Định nghĩa LIST là một cấu trúc gồm 2 thành phần: FIRST là con trỏ lưu địa chỉ của NODE đầu danh sách và LAST là con trỏ lưu địa chỉ của NODE cuối danh.
Viết chương trình dùng cấu trúc NODE và LIST để tổ chức và quản lý dữ liệu bằng DANH SÁCH LIÊN KẾT ĐƠN lưu trữ dãy n số nguyên nhập từ bàn phím. Hiển thị dãy số của danh sách với 5 phần tử trên 1 dòng, các phần tử cách nhau một khoảng trắng.

Gợi ý: Sinh viên có thể phân rã bài toàn thành nhiều modun và cài đặt các chương trình con thực hiện các modun tương ứng. Sau đó dùng main() để gọi các chương trình con thực hiện yêu cầu đã nêu trên.

CODE:

#include <stdio.h>
#include <conio.h>

/////////////1. Khai bao 1 NODE/////////////
struct Node
{
    int Data;
    struct Node *pNext;//(link)
};
typedef Node NODE;
struct List
{
    NODE *pHead;
    NODE *pTail;
};
typedef List LIST;

/////////////2. Khoi tao danh sach lien ket don/////////////
void Init(LIST &l)
{
    l.pHead = l.pTail = NULL;
}
/////////////3. Tao Node trong danh sach/////////////
NODE* GetNode(int x) //X la du lieu dua vao Data
{
    //Cap phat 1 Node
    NODE *p= new NODE; //C++ style
    if(p == NULL)
    {
        printf("\nMemory is full!");
        exit(1);
    }
    p ->Data = x; //Luu X vao Data
    p ->pNext = NULL;//Khoi tao moi lien ket
    return p;
}

/////////////4.Them Node(dau hoac cuoi)/////////////
//Them cuoi:[1] 2 3 4 5
//Them dau: 5 4 3 2 [1]
void AddHead(LIST &l, NODE *p)
{
    if(l.pHead == NULL)//Danh sach rong
    {
        l.pHead = l.pTail = p;
    }
    else
    {
        p ->pNext = l.pHead;//p noi vao Head tro thanh ptu dau
        l.pHead = p;
    }
}

/////////////5.Nhao du lieu vao danh sach/////////////
void Input(LIST &l)
{
    int n;
    printf("\nNhap so phan tu n: "); scanf("%d", &n);
    Init(l);//Cuc ki quan trong ko dc quen. //Khoi tao danh sach tuong tu nhu gan dem = 0.
    for(int i = 1; i <= n; i++) //Moi lan lap lai ta nhap 1 node
    {
        int x;
        printf("\nNhap vao gia tri: ");
        scanf("%d", &x);
        NODE *p = GetNode(x);//Tao Node dua Data x vao thanh Node p
        //AddTail(l, p);
        AddHead(l,p);
    }
}
void Output(LIST l)
{
    //Ben mang ta co: for(int i = 0; i < n; i++)
    //Voi i = 0 la l.pHead
    //Voi i = n-1 la l.pTail
    int dem=0;
    printf("\nCac gia tri vua nhap vao:\n");
    for(NODE *p = l.pHead; p != NULL; p = p ->pNext)//Tro den khi nao bang NULL thi dung
    {
    //printf("%4d", p ->Data);//4 la khoang cach giua cac ptu
    dem++;
    printf("%d\t",p->Data);
    if((dem)%5==0)
    {
        printf("\n");
    }
}

/*
Neu muon in cac phan tu theo k dong thi su dung doan code sau vao cho if((dem)%5==0)
printf("%d\t",a[i]);
        if((i+1)%k==0)//in ra cac phan tu tren 1 dong
        printf("\n");
*/

/////////////MAIN/////////////
int main()
{
    LIST l;
    Input(l);
    Output(l);
    printf("\n\n");
    return 0;
}

[Toán Cấu trúc rời rạc] Cấu trúc dữ liệu và giải thuật(CODE)

Tùng Nguyễn

Để lại một bình luận Hủy

[Python – 30d Challenge] Day 16 | Data Cleaning & Preparation: Handling Missing and Transform

[Python – 30d Challenge] Day 15 | Data Cleaning & Preparation: Handling Missing and Transform

[Python – 30d Challenge] Day 14 | Data Loading, Storage, File Formats

Share Article:

[Toán Cấu trúc rời rạc] Đại số Bool – Phương pháp biểu đồ Karnaugh

Để lại một bình luận Hủy