Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Tạo danh sách liên kết kép theo hướng lập trình hướng đối tượng

  1. #1
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Mặc định Tạo danh sách liên kết kép theo hướng lập trình hướng đối tượng

    Hôm trước có mấy bạn hỏi mình về vấn đề này. Thấy hướng dẫn OOP cho dslk cài đặt bằng C++ không thấy nên nay có time mình ngồi code demo

    tạm thời là full code

    C++ Code:
    1.  
    2. #include <iostream>
    3. #include <fstream>
    4.  
    5. using namespace std;
    6.  
    7. typedef class node* Node;
    8. class node
    9. {
    10.     private:
    11.         int data;
    12.         Node next;
    13.         Node prev;
    14.     public:
    15.         node (int data, Node next, Node prev)
    16.         {
    17.             this->data = data;
    18.             this->next = next;
    19.             this->prev = prev;
    20.         }
    21.  
    22.         void setData (int data)
    23.         {
    24.             this->data = data;
    25.         }
    26.  
    27.         int getData ()
    28.         {
    29.             return data;
    30.         }
    31.  
    32.         void setNext (Node next)
    33.         {
    34.             this->next = next;
    35.         }
    36.  
    37.         Node getNext ()
    38.         {
    39.             return next;
    40.         }
    41.  
    42.         void setPrev (Node prev)
    43.         {
    44.             this->prev = prev;
    45.         }
    46.  
    47.         Node getPrev ()
    48.         {
    49.             return prev;
    50.         }
    51.  
    52.         void print ()
    53.         {
    54.             cout << getData() << endl;
    55.         }
    56.  
    57.         friend class linkedlist;
    58. };
    59.  
    60.  
    61. typedef class linkedlist* Linkedlist;
    62.  
    63. class linkedlist
    64. {
    65.     private:
    66.         Node head;
    67.         Node tail;
    68.         int size;
    69.     public:
    70.  
    71.         linkedlist ()
    72.         {
    73.             head = NULL;
    74.             tail = NULL;
    75.             size = 0;
    76.         }
    77.         void setTail (Node tail)
    78.         {
    79.             this->tail = tail;
    80.         }
    81.  
    82.         Node get (int index)
    83.         {
    84.             if (index<0 || index > size)
    85.                 return NULL;
    86.             Node tmp = head;
    87.             for (int i = 0; i < index; i ++)
    88.                 tmp = tmp->getNext();
    89.             return tmp;
    90.         }
    91.  
    92.         int getSize ()
    93.         {
    94.             return size;
    95.         }
    96.         void creatList (const char* filename)
    97.         {
    98.             fstream _read;
    99.             _read.open (filename, ios::in);
    100.             cout << _read.good () << endl << endl;
    101.  
    102.             int data;
    103.             Node tmp;
    104.             while (!_read.eof ())
    105.             {
    106.                 _read >> data;
    107.                 tmp = new node (data, NULL, NULL);
    108.                 size ++;
    109.  
    110.                 if (head == NULL)
    111.                     head = tail = tmp;
    112.                 else
    113.                 {
    114.                     tail->setNext(tmp);
    115.                     tmp->setPrev(tail);
    116.                     setTail(tmp);
    117.                 }
    118.             }
    119.         }
    120.  
    121.         void printNext ()
    122.         // in ra theo chieu next
    123.         {
    124.             Node tmp = head;
    125.             while (tmp!= NULL)
    126.             {
    127.                 tmp->print ();
    128.                 tmp = tmp->getNext();
    129.             }
    130.  
    131.         }
    132.  
    133.         void printPrev ()
    134.         // in ra theo chieu prev
    135.         {
    136.             Node tmp = tail;
    137.             while (tmp!= NULL)
    138.             {
    139.                 tmp->print ();
    140.                 tmp = tmp->getPrev();
    141.             }
    142.         }
    143.  
    144.         void sortBN ()
    145.         // sap xep noi bot theo chieu next
    146.         {
    147.             Node bsh;
    148.             int data;
    149.             bool _bit = false;
    150.             while (!_bit)
    151.             {
    152.                 _bit = true;
    153.                 for (bsh = head; bsh->getNext() != NULL; bsh = bsh->getNext())
    154.                     if (bsh->getData () < bsh->getNext()->getData())
    155.                     {
    156.                         data = bsh->getData ();
    157.                         bsh->setData(bsh->getNext()->getData());
    158.                         bsh->getNext()->setData (data);
    159.                         _bit = false;
    160.                     }
    161.             }
    162.         }
    163.  
    164.         void addTail1 (int data)
    165.         {
    166.             Node tmp = new node (data, NULL, NULL);
    167.             if (head == NULL)
    168.             {
    169.                 head = tail = tmp;
    170.                 return;
    171.             }
    172.             tmp->setPrev(tail);
    173.             tail->setNext(tmp);
    174.             setTail(tmp);
    175.             size ++;
    176.         }
    177.  
    178.         void addTail2 (int data)
    179.         {
    180.             Node n = new node(data, NULL, NULL);
    181.             Node tmp = get (size - 1);
    182.             n->setPrev(tmp);
    183.             tmp->setNext(n);
    184.             setTail(n);
    185.             size ++;
    186.         }
    187.  
    188. };
    189.  
    190. int main ()
    191. {
    192.     Linkedlist l = new linkedlist ();
    193.     l->creatList("hung.txt");
    194.  
    195.     l->addTail2(100);
    196.     l->printNext();
    197.     cout << endl;
    198.     l->printPrev ();
    199.     return 0;
    200. }


    Khi chuyển từ C sang C++ ta vẫn thường có thói quen làm theo lập trình cấu trúc. Có nghĩa cũng là lập trình OOP nhưng thiên về cấu trúc của C

    - Khi cài đặt class bình thường nên có các phương thức get..., set... cho các thành phần private:
    trong bài của mình VD: data ---> getData (): Nhiệm vụ của hàm get là trả về dữ liệu hiện thời. Dữ liệu hiện có của đối tượng này là gì thì ta cho hiện ra
    Còn phương thức set....: Nhiệm vụ là: cập nhật dữ liệu cho đối tượng
    trong bài VD: setNext (Node next): nhiệm vụ của phương thức này cho biết đối tượng tiếp theo của đối tượng hiện thời là gì

    Trong bài này có lẽ nhiều bạn cho rằng mình giở hơi khi cho thêm phương thức

    C++ Code:
    1. Node get (int index)
    2.         {
    3.             if (index<0 || index > size)
    4.                 return NULL;
    5.             Node tmp = head;
    6.             for (int i = 0; i < index; i ++)
    7.                 tmp = tmp->getNext();
    8.             return tmp;
    9.         }

    Nhưng mà cũng không giở hơi lắm nhỉ khi mà dslk là dslk đơn. Khi dùng dslk đơn thì phương thức get cực kì hiệu quả vì được sử dụng rất nhiều. Mình có một ví dụ lẩm cẩm ngay trong bài

    C++ Code:
    1. void addTail2 (int data)
    2.         {
    3.             Node n = new node(data, NULL, NULL);
    4.             Node tmp = get (size - 1);
    5.             n->setPrev(tmp);
    6.             tmp->setNext(n);
    7.             setTail(n);
    8.             size ++;
    9.             // hơi vòng quanh một tí nhưng nếu đọc kỹ bạn sẽ thấy hàm get có ứng dụng rất lớn cho dslk đơn
    10.         }

    Sorry vì mình không có nhiều time nên mình cho luôn phương thức get và addTail2 vào bài này để giới thiệu khi bạn làm dslk đơn. Khi ta xóa hay thêm một phần tử thì ta sử dụng phương thức get tìm một vị trí thích hợp để xóa, chèn như vậy sẽ tiết kiệm được khá nhiều giấy
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    1

    Bạn ơi bạn có thể code bài này theo danh sách liên kết kép đc k ???

    Nhờ bạn đấy. Nhớ giải thích rỏ ràng cho mình nha, thank much !


    Mô tả bài toán: cho 2 danh sách A và B lần lượt có m và n phần tử đã sắp xếp theo thứ
    tự. Bài toán đặt ra trộn 2 danh sách A và B với nhau thành danh sách C cũng là một
    danh sách có thứ tự.
    Thuật toán:
    Bước 1: khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba
    mảng A, B và C.
    Bước 2: tại mỗi bước nếu cả hai chỉ số (i<m và j<n) ta chọn min(A[i],B[j]) và lưu nó
    vào trong C[k]. Chuyển sang Bước 4.
    Bước 3: tăng giá trị k lên 1 và quay về Bước 2.
    Bước 4: sao chép tất cả các giá trị còn lại từ các danh sách mà chỉ số còn vi phạm (tức
    i<m hoặc j<m) vào trong mảng C.

    Cài đặt:

    #include <iostream.h>
    #include <conio.h>
    #define max 100
    void NhapMang(int A[],int n) {
    for(int i=0; i<n; i++) {
    cout<<"Phan tu "<<i<<" = ";
    cin>>A[i];
    }
    }
    void XuatMang(int A[],int n) {
    cout<<endl;
    for(int i=0; i<n; i++)
    cout<<A[i]<<"\t";
    }
    void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
    int i = 0, j = 0;
    k = 0;
    while (i < m && j < n) {
    if (A[i] <= B[j]) {
    C[k] = A[i];
    i++;
    } else {
    C[k] = B[j];
    j++;
    }
    k++;
    }
    if (i < m) {
    for (int p = i; p < m; p++) {
    C[k] = A[p];
    k++;
    }
    } else {
    for (int p = j; p < n; p++) {
    C[k] = B[p];
    k++;
    }
    }
    }
    void main() {
    int A[max],B[max],C[max],n,m,k;
    clrscr();
    cout<<"n = ";
    cin>>n;
    cout<<"m = ";
    cin>>m;
    cout<<"Nhap danh sach co thu tu A:\n";
    NhapMang(A,m);
    cout<<"Nhap danh sach co thu tu B:\n";
    NhapMang(B,n);
    cout<<"\nSap xep tron 2 mang A, B\n";
    MergeSort(m,n,k,A,B,C);
    XuatMang(C,k);
    getch();
    }

Các đề tài tương tự

  1. Thêm 1 nút , Xóa 1 nút , Sửa 1 nút, duyệt danh sách theo liên kết phải, theo liên kết trái.
    Gửi bởi dodinhlong trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 23-05-2013, 11:51 AM
  2. Đảo ngược danh sách liên kết đơn theo cách nào?
    Gửi bởi cautrucdulieu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 15-05-2013, 05:44 PM
  3. Lập trình C++ Lỗi xuất danh sách liên kết đơn theo con trỏ cuối danh sách
    Gửi bởi thienthanoze trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 26-01-2013, 11:25 PM
  4. sắp xếp danh sách liên kết đơn theo số lượng bằng thuật toán buble sort
    Gửi bởi HoaNhien trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 07-09-2012, 11:04 AM
  5. Kỹ thuật C++ Danh sách liên kết theo hướng đối tượng lỗi với template :(
    Gửi bởi kem92 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 10-11-2011, 09:00 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn