Bài tập

CTDL và giải thuật - Áp dụng kiến thức vào bài tập thực tế

avatar
Huy Erick
00:00 12/04/2024

Bài tập thực hành với danh sách liên kết đơn Phần này sẽ giúp bạn áp dụng kiến thức về CTDL và giải thuật vào bài tập thực tế một cách hiệu quả. Chúng ta...

Bài tập thực hành với danh sách liên kết đơn

Phần này sẽ giúp bạn áp dụng kiến thức về CTDL và giải thuật vào bài tập thực tế một cách hiệu quả.

Chúng ta sẽ thực hiện giải hai bài tập sau đây:

  1. Bài tập về danh sách liên kết đơn kiểu cơ sở
  2. Bài tập về danh sách liên kết đơn kiểu cấu trúc

Qua hai bài tập này, bạn sẽ có khả năng quản lý danh sách liên kết và thực hiện các thao tác trên nó một cách thành thạo.

Xem thêm:

1. Bài tập về danh sách liên kết đơn kiểu cơ sở

Trong bài tập này, chúng ta sẽ giải một bài toán như sau:

s(x, n) = x1 + x2 + x3 + ... + xn

Bạn cần xây dựng danh sách liên kết đơn có phần tử pHead, pTail. Sau đó, nhập x và n để tạo danh sách liên kết (mỗi nút có hai giá trị x và i, trong đó i chạy từ 1 đến n). Sử dụng con trỏ để khai báo cho danh sách liên kết. Viết hàm để xuất ra tổng các phần tử trong danh sách liên kết.

Gợi ý: Để giải bài toán này, ta cần cấu trúc dữ liệu của danh sách liên kết đơn. Mỗi nút có giá trị data là x và i, và có mối liên kết là pNext. Khởi tạo pHead và pTail bằng NULL.

Sau đó, viết hàm tạo Node dựa vào cấu trúc dữ liệu đã nêu. Đồng thời, cần có hàm InsertLast để thêm Node vào cuối danh sách liên kết.

Tạo thêm hàm PrintList để in danh sách liên kết và hàm SumOfList để tính tổng các phần tử.

Cuối cùng, sử dụng hàm main để hiển thị và kiểm tra kết quả.

Code đầy đủ:

#include 
#include 
using namespace std;

struct Node {
    int x;
    int i;
    Node *pNext;
};

struct SingleList {
    Node *pHead;
    Node *pTail;
};

void Initialize(SingleList *&list) {
    list = new SingleList;
    list->pHead = list->pTail = NULL;
}

Node *CreateNode(int x, int i) {
    Node *pNode = new Node;
    if(pNode == NULL) {
        cout  "Loi cap phat bo nho";
        exit(0);
    }
    pNode->i = i;
    pNode->x = x;
    pNode->pNext = NULL;
    return pNode;
}

void InsertLast(SingleList *&list, int x, int i) {
    Node *pNode = CreateNode(x, i);
    if(list->pTail == NULL) {
        list->pHead = list->pTail = pNode;
    } else {
        list->pTail->pNext = pNode;
        list->pTail = pNode;
    }
}

void PrintList(SingleList *list) {
    Node *pTmp = list->pHead;
    while(pTmp != NULL) {
        if (pTmp->pNext != NULL) {
            cout  pTmp->x  "^"  pTmp->i  " + ";
        } else {
            cout  pTmp->x  "^"  pTmp->i;
        }
        pTmp = pTmp->pNext;
    }
}

double SumOfList(SingleList *list) {
    double sum = 0;
    for(Node *pTmp = list->pHead; pTmp != NULL; pTmp = pTmp->pNext) {
        double value = pow(pTmp->x, pTmp->i);
        sum += value;
    }
    return sum;
}

int main(int argc, char** argv) {
    SingleList *list;
    Initialize(list);
    int n, x;
    cout  "Nhập n: ";
    cin >> n;
    cout  "Nhập x: ";
    cin >> x;
    for(int i = 1; i = n; i++) {
        InsertLast(list, x, i);
    }
    cout  "Danh sách liên kết đơn: ";
    PrintList(list);
    double sum = SumOfList(list);
    cout  endl  "Tổng các phần tử trong danh sách: "  sum  endl;
    cout  "- Chương trình này được đăng tại hiepsiit.com -";
}

Kết quả:

Hình ảnh minh họa

Nguồn: hiepsiit.com

Với những kiến thức này, bạn có thể áp dụng vào thực tế để giải quyết các bài toán liên quan đến danh sách liên kết đơn. Chúc bạn thành công trong học tập và ứng dụng kiến thức!

BÀI LIÊN QUAN
1