[Cấu trúc dữ liệu] Thuật toán cài đặt danh sách Liên kết đơn (Node) trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 1,147

  1. Trong bài này mình sẽ giới thiệu đến các bạn một trong các cách cài đặt danh sách tuyến tính trong C++, đó là sử dụng danh sách móc nối đơn (Node).

    Khi nào thì sử dụng danh sách liên kết đơn trong C++?
    • Khi ta không biết kích thước của dữ liệu hãy dùng con trỏ và bộ nhớ động;
    • Khi không biết kiểu dữ liệu hãy dùng con trỏ void;
    • Khi không biết số lượng dữ liệu hãy dùng danh sách móc nối.

    Với kiểu danh sách móc nối trong C++ ta có các khái niệm sau:
    • first: trỏ vào ô đầu tiên của danh sách, ô first không lưu trữ phần tử nào cả. Trong trường hợp danh sách rỗng thì con trỏ của first = NULL.
    • q: phần tử bất kì mà con trỏ trỏ tới.
    • q->next: con trỏ trỏ vào ô ngay sau phần tử q.
    Đầu tiên ta sẽ xây dựng hàm struct để làm việc với kiểu danh sách liên kết đơn: ở đây mình lấy ví dụ cụ thể với kiểu số nguyên.

    Mã:
    truct Node{
        int data;            //Giá trị của ô được trỏ vào
        Node* next;         //Con trỏ chỉ đến vị trí tiếp theo
    };
    Node* first;
    Để xây dựng các hàm, giả sử ban đầu ta có 1 file dữ liệu "input.txt" mình lưu ở ổ D như sau:

    Mã:
    7 8 4 5 9 10 13 7 9 -1 //kết thúc bằng phần tử -1
    Ban đầu ta sẽ xây dựng 1 hàm để đọc dữ liệu từ file.

    Mã:
    void readData(char* fn){
        FILE* f = fopen(fn,"r");
      
        while (1){
          
            fscanf(f,"%d",&x);
            if (x == -1) break;
            first = insertLast(x,first);
        }
        fclose(f);
    }
    Bắt đầu với hàm đầu tiên là hàm chèn phần tử vào sau 1 phần tử bất kì vào trước 1 phần tử trong danh sách:
    Để dễ hiểu hàm insert được mô tả như sau:

    [​IMG]
    Mã:
    Node* insert (int x, int y, Node* first){
        Node* q = new Node;
        q->data = y;
        if (first == NULL)
            return q;
        Node* p=first;
        while(p!= NULL && (p->next)->data!=x){
            p=p->next;
            }
        Node*qr=p->next;
        p->next=q;
        q->next=qr;
    }
    
    Hàm tính tổng giá trị các nút:
    Mã:
    int Sum (Node* first){
        int T = 0;
        while (first != NULL){
            T += first->data;
            first = first->next;
        }
        return T;
    }

    Hàm loại bỏ 1 phần tử trong danh sách:


    http://www.mediafire.com/?nh5g8be463brqnb



    [​IMG]
    Mã:
    void remove (int x, Node* p){
        while (p != NULL && (p->next)->data != x){
            p = p->next;
        }
        if (p->next == NULL) return;
        Node* q = new Node;
        q = p->next;
        p->next = q->next;
        delete q;  
    }


    Với mỗi lần thực hiện hàm ta đều phải có lệnh để in ra danh sách vừa được thay đổi
    Hàm in ra các giá trị như sau:
    Mã:
    void printList(Node* first){
        Node* p = first;
        while (p != NULL){
            printf("%d   ", p -> data);
            p = p -> next;
        }
    }
    
    Tổng hợp lại các hàm, ta có chương trình cho danh sách nối đơn như sau:

    Mã:
    #include <stdio.h>
    
    struct Node{
        int data;
        Node* next;
    };
    
    Node* first = NULL;
    
    Node* insertLast(int x, Node* first){
        Node* q = new Node;
        q -> data = x;
        q -> next = NULL;
    if (first == NULL){
        first = q;
        return first;
    }
        Node* p = new Node;
        p = first;
        while (p-> next != NULL){
            p = p->next;
        }
        p->next = q;
        return first;
    }
    void readData(char* fn){
        FILE* f = fopen(fn,"r");
        while (1){
            int x;
            fscanf(f,"%d",&x);
            if (x == -1) break;
            first = insertLast(x,first);
        }
        fclose(f);
    }
    Node* insert (int x, int y, Node* first){
        Node* q = new Node;
        q->data = y;
        if (first == NULL)
            return q;
        Node* p=first;
        while(p!= NULL && p->data!=x){
            p=p->next;
            }
        Node*qr=p->next;
        p->next=q;
        q->next=qr;
    }
    
    
    
    void remove (int x, Node* p){
        while (p != NULL && (p->next)->data != x){
            p = p->next;
        }
        if (p->next == NULL) return;
        Node* q = new Node;
        q = p->next;
        p->next = q->next;
        delete q;  
    }
    
    
    
    
    int Sum (Node* first){
        int T = 0;
        while (first != NULL){
            T += first->data;
            first = first->next;
        }
        return T;
    }
    
    
    void printList(Node* first){
        Node* p = first;
        while (p != NULL){
            printf("%d   ", p -> data);
            p = p -> next;
        }
    }
    int main (){
        char input[50]="D:/input.txt";
        readData(input);
      
        printf ("Read data OK!");
        printf ("n");
        printf ("Danh sach ban dau: ");
        printList(first);
        printf ("n");
        printf ("Tong bang %d",Sum(first));
        printf ("n");
        remove (4, first);
        printf ("Danh sach sau khi xoa phan tu 4: ");
        printList(first);
        printf ("n");
        insert (10,1000, first);
        printf ("Danh sach sau khi chen 1000 vao sau 10: ");
        printList(first);
      
    }
    Ngoài các hàm được giới thiệu ở trên, các bạn cũng có thể xây dựng thêm nhiều hàm khác tùy thuộc vào yêu cầu.

    Các bạn có thể đọc thêm cách sử dụng Cygwin để dịch chương trình C++ tại đây:

    http://minhduongit.com/huong-dan-su-dung-cygwin-dich-chuong-trinh-cc-bang-cygwin/

    Chúc mọi người thành công!!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex PC |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack | Hack Like Facebook | Bot cảm xúc |Sitemap