[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: 751

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    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

    Bình Luận Bằng Facebook

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 Offline |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 |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap