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

Đề tài: Bàn luận về việc cấp phát bộ nhớ động trong danh sách liên kết

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

    Wink Bàn luận về việc cấp phát bộ nhớ động trong danh sách liên kết

    Ai biết giải thích giúp mình với. Mình viết chương trình bằng C++, trên Dev-C++:
    Mình tạo một danh sách liên kết các số nguyên, trong đó có phương thức sắp xếp các nút theo thứ tự tăng dần hoặc giảm dần. Mình làm theo hai cách:

    Cách 1: sắp xếp trực tiếp trên danh sách đã có.

    Cách 2: khai báo một danh sách mới, lấy các phần tử của danh sách cũ để sắp xếp trên danh sách mới rồi delete danh sách cũ đi, chuyển con trỏ head và tail của danh sách cũ trỏ đến head và tail của danh sách mới.

    Cách 1 thì mình đã làm được rồi nhưng ở cách 2 thì lại có vấn đề xảy ra:
    1. Ví dụ là mỗi nút có kiểu là IntNode có hai thành phần là số nguyên int và một con trỏ IntNode* next để trỏ đến nút kế tiếp, danh sách có kiểu là IntList chứa hai con trỏ IntNode *head, và IntNode *tail. Nếu mình khai báo danh sách mới là IntList A chẳng hạn(mới khai báo thì head= tail= NULL), sau đó xin cấp phát bộ nhớ bằng new để lưu các phần tử của danh sách cũ đã được sắp xếp, tiếp tục là xóa danh sách cũ, chuyển head và tail của danh sách cũ chỉ sang head và tail của danh sách mới: head= A.head, tail= A. tail, lúc thoát khỏi chương trình thì danh sách lại chẳng có gì nữa(khi gọi hàm này rồi gọi hàm in danh sách ra file thì chương trình dừng không chạy tiếp). Các nút đều được dùng toán tử new mà ra khỏi hàm thì lại không thấy đâu nữa. Mình đã debug rồi, thao tác của mình trong hàm không hề sai, chỉ khi ra khỏi dấu ngoặc đóng hàm thì giá trị các nút mới biến mất.

    2. Mình khai báo danh sách mới là con trỏ IntList *p= new IntList; để thay cho A. Làm các thao tác để sắp xếp, lưu danh sách vào p như đã nói ở trên. Tiếp tục là xóa danh sách cũ và lấy địa chỉ mới cho head và tail của danh sách cũ: head= p->head, tail= p->tail. Nhưng nếu như trước khi ra khỏi hàm mà mình delete p để xóa cái new IntList thì ra khỏi hàm danh sách mới tạo cũng mất tăm, phải để cái new IntList mà p trỏ tới đấy thì danh ra khỏi hàm danh sách mới còn. Các bạn chú ý rằng mình delete p không phải là xóa danh sách mà chỉ là xóa cái new IntList do p trỏ tới, cái này có hai thành phần là IntNode *head và IntNode *tail, còn danh sách thì mỗi nút lại được tạo bằng một cái new IntNode riêng. Nếu không delete p; thì ra khỏi hàm chỗ bộ nhớ được cấp phát khi IntList *p= new IntList; do từ khóa new sẽ không được quản lí.

    Mời các bạn cùng thảo luận. ( mình viết bằng C++, trên Dev-C++)

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

    Mình thấy cách 2 rắc rối cái cấp phát bộ nhớ như vậy, nên đã làm theo cách 1. Code dưới đây là của thằng bạn nó làm theo cách 2, cũng tượng tự như cách 2 mình nói ở trên. Do không attach được file nên mình đành post code lên đây vậy. Các bạn chú ý:
    1. Hàm sắp xếp như mình đã nói ở trên là hàm void IntList::sort(); trong hàm này có gọi đến hàm void IntList::addNode(int a); . Hàm addNode(int a) có tác dụng chèn một nút mới vào danh sách đã được sắp xếp tăng dần sao cho không làm mất thứ tự tăng dần của danh sách.
    2. Lớp IntList có hai hàm khởi tạo. Câu lệnh IntList *A= new IntList; trong hàm void IntList::sort() gọi đến hàm khởi tạo không có tham số, tạo một danh sách rỗng( head= tail= NULL).
    3. Chương trình lấy dữ liệu từ một file DANHSACH.TXT để tạo danh sách, sau đó sắp xếp danh sách, cuối cùng là in danh sách đã sắp xếp ra file SAPXEP.TXT. File DANHSACH.TXT chứa một dãy số được lưu mỗi số một dòng có dạng như sau:
    3
    2
    7
    4
    12
    0
    9
    123
    4
    8
    7
    45
    56
    45

    4. Cài đăt có một số chỗ chưa được tối ưu, hơi dài dòng nhưng vẫn chạy tốt.

    5.Điều quan trọng nhất mong các bạn chú ý và chỉ giúp là trong hàm void IntList::sort() khai báo một con trỏ mới IntList *A= new IntList; để lưu danh sách được sắp xếp như mình đã nói ở bài mở đầu topic này. Nếu trước khi ra khỏi hàm mà delete A thì chương trình bị lỗi( dừng không chạy tiếp). Các bạn chú ý là delete p thì chỉ xóa bộ nhớ cấp phát cho new IntList, còn các nút có kiểu là IntNode được cấp phát do new IntNode.
    6. Nếu khai báo một danh sách mới theo kiểu IntList A; để thay cho IntList *A= new IntList; thì hiện tượng cũng tương tự( các nút được cấp phát do new IntList).
    7. Hàm main ở dưới cùng.

    C++ Code:
    1. #include <iostream>
    2. #include <fstream>
    3. #include <conio.h>
    4. #include <cstdlib>
    5.  
    6.  
    7. using namespace std;
    8.  
    9. class IntNode{
    10.       public:
    11.              int info;
    12.              IntNode* next;
    13.              IntNode(int el,IntNode* ptr = NULL){
    14.                          info =el;
    15.                          next = ptr;
    16.              }
    17. };
    18.  
    19. class IntList{
    20.       public:
    21.              IntList(){
    22.                        head =tail= NULL;
    23.              }
    24.             IntList(char *);
    25.             ~IntList();
    26.             int isEmpty(){
    27.                 return head == NULL;
    28.             }
    29.             void addToHead(int);
    30.             void addToTail(int);
    31.             void writeToFile(char*);
    32.             void addNode(int);
    33.             void sort();
    34.            
    35.          
    36.       private:
    37.               IntNode* head,* tail;
    38.        
    39.      
    40. };
    41.  
    42.  
    43. IntList::~IntList(){
    44.       for(IntNode* p; !isEmpty();)
    45.       {
    46.                    p= head-> next;
    47.                    delete head;
    48.                    head= p;
    49.       }
    50. }
    51.  
    52. IntList::IntList(char *s){
    53.       head= tail= NULL;
    54.       ifstream input(s, ios::in);
    55.       if (!input)
    56.       {
    57.          cout <<" Not OK.\n";
    58.          getch();
    59.          exit(1);
    60.       }
    61.       int a;
    62.       while (input >> a)
    63.       {
    64.             addToTail(a);
    65.       }
    66.       input.close();
    67. }
    68.        
    69. void IntList::addNode(int a)
    70. {
    71.      if(isEmpty()) addToHead(a);// danh sach rong
    72.      
    73.      else
    74.           {
    75.           if(a<= head->info) addToHead(a); // chen vao dau danh sach
    76.           else if(a>= tail->info) addToTail(a);//
    77.                else
    78.                {
    79.                    IntNode* tg,* tmp;
    80.                    for(tg= head, tmp= head->next;
    81.                        tmp!= NULL&& tmp->info<=a;
    82.                        tg=tg->next,tmp= tmp->next
    83.                        );
    84.                    tg->next= new IntNode(a, tmp);
    85.                }
    86.           }            
    87. }
    88.  
    89.  
    90. void IntList::sort()
    91. {
    92.      IntList *A= new IntList;
    93.      for (IntNode *tg= head; tg !=NULL; tg= tg->next)
    94.          A->addNode(tg->info);
    95.      for(IntNode* p; !isEmpty();)
    96.       {
    97.                    p= head-> next;
    98.                    delete head;
    99.                    head= p;
    100.       }
    101.       head= A->head;
    102.       tail= A->tail;
    103. }
    104.  
    105. void IntList:: addToTail (int el){
    106.      if (NULL!=tail){
    107.                      tail->next= new IntNode(el);
    108.                      tail= tail->next;
    109.      }
    110.      else head=tail=new IntNode(el);
    111. }
    112.  
    113. void IntList:: addToHead (int el){
    114.      head= new IntNode(el, head);
    115.      if(NULL==tail)
    116.                    tail=head;
    117. }
    118.  
    119. void IntList::writeToFile(char out[]){
    120.       ofstream output(out, ios::out);
    121.       for(IntNode* tg2=head; tg2!=NULL; tg2= tg2->next)
    122.                    output<< tg2->info<<endl;
    123.       output.close();
    124.       cout<<"\nDa sap xep va ghi ra file: SAPXEP.TXT";
    125. }
    126.  
    127. int main()
    128. {
    129.     IntList ds("DANHSACH.TXT");
    130.     ds.sort();
    131.     ds.writeToFile("SAPXEP.TXT");
    132.    
    133.     getch();
    134.     return 0;
    135. }
    Đã được chỉnh sửa lần cuối bởi valiant-man : 01-01-2008 lúc 09:13 AM.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Code này bạn nên tạo thêm copy constructor và quá tải toán tử '='. Còn về phần sort, nếu sort trực tiếp trên Node thì thao tác quá cồng kềnh, nhưng nếu muốn rèn luyện thì cũng không sao. Mình thì gán vào mãng, sort trên mãng rồi đưa ngược trở lại, vậy thì đơn giản hơn rất nhiều !

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

  1. Lập trình C Các bác giải dùm em bài trộn 2 danh sách có thứ tự thành 1 danh sách có thứ tự trong DS liên kết đơn
    Gửi bởi letranhoangtai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 05-09-2012, 02:03 AM
  2. Bài tập C++ Tách chẵn lẽ thành 2 danh sách trong danh sách liên kết đơn?
    Gửi bởi leo009394 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 01-01-2012, 04:52 PM
  3. Bài tập C++ Tìm năm có nhiều khóa luận nhất trong danh sách liên kết
    Gửi bởi truonglong99 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 13-11-2011, 10:47 AM
  4. đảo ngược vùng liên kết trong danh sách liên kết đơn
    Gửi bởi khongcochi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 07-07-2011, 10:18 PM
  5. Thảo luận về Danh sách liên kết
    Gửi bởi while trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 22-09-2010, 01:22 AM

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