Danh sách liên kết đơn bản 2

View as PDF
Submit solution
All submissions
Best submissions
Time limit: 1.0s , Memory limit: 256M , Points: 1 (partial)

Cho một danh sách liên kết đơn lưu trữ các số nguyên và các hàm cần được cài đặt định nghĩa như sau:

typedef struct Node{
    int data;
    struct Node *next;
}SList;
//Hàm chèn một phần tử x và cuối danh sách.
void InsertLast(SList *& F, int x);
//Hàm chèn một phần tử x vào vị trí trước vị trí p trong danh sách.
void InsertBeforeP(SList *& F, int x, int p);
//Hàm xóa một phần tử ở vị trí p.
void Delete(SList *&F, int p);
//Hàm tính giá trị trung bình của các phần tử trong danh sách.
float Average(SList *F);

Hãy cài đặt các hàm và thực hiện các yêu cầu mô tả trong input, output.

Input

Dòng đầu chứa số nguyên dương n là số phần tử hiện có của danh sách.

Dòng tiếp theo chứa n sô` nguyên lần lượt được chèn vào danh sách bằng phép chèn cuối.

Dòng thứ ba trở đi, mỗi dòng là một bộ có cấu trúc như sau:

  • i x p nghĩa là chèn x vào danh sách ở vị trí trước p, và p được đánh chỉ số bắt đầu từ 1.

  • d p nghĩa là xóa phần tử thứ p. Nếu p không thuộc phạm vi danh sách thì không xóa.

  • a nghĩa là in ra giá trị trung bình cộng của danh sách.

  • 0 0 dùng để kết thức dữ liệu vào.

Output

Chỉ in ra dữ liệu khi gặp lệnh có cấu trúc , mỗi kết quả in trên một dòng và lấy 4 chữ số sau dấu chấm thập phân.

Samples

Sample Input 1
6
1 1 1 1 1 1
i 4 1
a
i 6 7
i 12 1
i 1 14
a
d 1
a
0 0
Sample Output 1
1.4286
2.9000
1.8889

Comments


  • 0
    hoho  commented on June 1, 2025, 8:30 p.m.

    // Chèn đầu void InsertFirst (Node & first, long long data){ Node newNode = new Node; newNode -> data = data;

    newNode -> next = first;
first = newNode;

    }

    // Chèn cuối void InsertLast (Node & first, long long data){ Node newNode = new Node; newNode -> data = data; newNode -> next = NULL;

    if(first == NULL){
    first = newNode;
} else {
    Node * tmp = first;
    while(tmp -> next != NULL){
        tmp = tmp->next;
    }
    tmp -> next = newNode;
}

    }

    // Chèn vị trí bất kỳ void InsertPos (Node & first, int value, int pos){ Node newNode= new Node; newNode -> data = value; newNode -> next = NULL; if(first == NULL || pos <= 1){ newNode -> next = first; first = newNode; return; }

    Node * tmp = first;
int dem = 1;
while(tmp -> next != NULL && dem < pos - 1){
    tmp = tmp -> next; 
    dem++; 
}

newNode -> next = tmp->next;
tmp -> next = newNode;

    }

    // Tìm kiếm theo một điều kiện void Find(Node first, string sdt) { Node tmp = first; while (tmp != NULL) { if (tmp->sdt == sdt) { cout<<tmp->ten<<" "<<tmp->sdt<<endl; return; } tmp = tmp->next; } cout<<"Not found\n"; }

    // Xóa với một điều kiện void DeleteX (Node *& first, string sdt) { if (first == NULL) return;

    if (first->sdt == sdt) {
    Node *tmp = first;
    first = first->next;
    delete tmp;
    return;
}

Node *tmp = first;
while (tmp->next != NULL && tmp->next->sdt != sdt) {
    tmp = tmp->next;
}

if (tmp->next != NULL) {
    Node *nodeXoa = tmp->next;
    tmp->next = nodeXoa->next;
    delete nodeXoa;
}

    }

    // Xóa vị trí bất kỳ void DeletePos(Node *&first, int pos){ if(first == NULL && pos < 1) { return; }

    if(pos == 1) {
    Node * tmp = first;
    first = first -> next;
    delete tmp;
    return;
}

Node * tmp = first; 
int dem = 1;
while(tmp -> next != NULL && dem < pos - 1){ 
    tmp = tmp -> next; 
    dem++; 
}

if(tmp -> next != NULL){
    Node * nodeXoa = tmp -> next;
    tmp -> next = nodeXoa -> next;
    delete nodeXoa;     
}

    }

    // Kiểm tra trùng mã bool kiemTraTrungMa(Node first, string mahang) { for (Node i = first; i != NULL; i = i->next) { if (i->mahang == mahang) { return true; // Trùng mã } } return false; // Không trùng }

    // Sắp xếp danh sách liên kết void sortLinkedList(Node& first) { vector<Node> nodes; Node* current = first;

    while (current != nullptr) {
    nodes.push_back(current);
    current = current->next;
}

sort(nodes.begin(), nodes.end(), [](Node* a, Node* b) {
    return a->score < b->score;
});

if (nodes.empty()) {
    first = nullptr;
    return;
}

first = nodes[0];
current = first;

for (size_t i = 1; i < nodes.size(); ++i) {
    current->next = nodes[i];
    current = current->next;
}
current->next = nullptr;

    }

    Link

      • 0
        hoho  commented on June 1, 2025, 8:31 p.m.

        note cho các bạn học

        Link

      • 2
        23t1020360  commented on May 8, 2024, 2:38 a.m.

        xem giúp bài mình và chỉ lỗi sai giúp mình với ạ

        Link

        • 0
          23t1020122  commented on April 27, 2024, 3:29 p.m. ← edited

          Cho mình hỏi, ở hàm insertBeforePos, nếu pos > n thì mình chèn cuối ạ? Nếu chèn cuối thì có ảnh hưởng đến hàm delete không?

          Link

            • 0
              Aryaa  commented on April 28, 2024, 1:52 a.m.

              có chứ do số phần tử tăng thì vị trí xóa của delete sẽ rộng hơn

              Link

            • 0
              23T1020343  commented on April 25, 2024, 2:22 p.m.

              xem dùng bài của mình, và chỉ dùm lỗi sai với ạ...

              Link

                • 0
                  Aryaa  commented on April 27, 2024, 11:35 a.m.

                  ông xem lại hàm tbc và đổi kiểu dữ liệu thành float và xóa cái *1.0 là oke nha với cnt có hàm size rồi thì tui nghĩ ông nên dùng lại hàm size và xóa cnt++ cho gọn code hơn :3

                  Link

                • -3
                  God_of_War  commented on April 22, 2024, 9:39 a.m.

                  Gà

                  Link

                  • 0
                    23t1020600  commented on April 21, 2024, 11:08 a.m.

                    bài này code sao ạ

                    Link

                      • 0
                        Aryaa  commented on April 22, 2024, 5:17 a.m.

                        ông tạo các hàm theo yêu cầu r tạo dslk như input r dùng char để check kí tự gì r xử lý bằng các hàm là oke

                        Link

                      • 0
                        23t1020026  commented on April 11, 2024, 3:34 p.m.

                        tại sao output thứ 3 lại in ra 1.8889 v ạ? không phải là 3.1111 hay sao ạ? ai giải thích giúp em với.

                        Link

                          • 1
                            Aryaa  commented on April 13, 2024, 2:57 a.m.

                            delete 1 là xóa node có giá trị 12 á

                            Link