Mô phỏng cây thư mục bằng ngôn ngữ C++ ?

[ysea]

Chào các bác.
Em có bài tập lớn viết bằng ngôn ngữ C++ với đề tài là :"Mô phỏng cây thư mục và một số thao tác trên cây thư mục".
Yêu cầu : cài đặt một cấu trúc dữ liệu mô phỏng dạng cây thư mục trên ổ đĩa, và cài đặt các thao tác( tương ứng với các lệnh của MS-DOS như MD- tạo một nút mới, RD- Xóa nút...).
Em không rõ làm thế nào để quản lý hiệu quả nhất các node trên cây vì em thấy thường cây nhị phân được sử dụng nhiều nhất nhưng nếu áp dụng vào cây thư mục thì sẽ phức tạp vì ở cây thư mục một nút có thể có nhiều nút con nên việc insert hay delete khó. Và để tạo chương trình biên dịch những câu lệnh như của DOS em cũng chưa rõ cách viết như thế nào.
Em đã tạo được 2 lớp là CNode để biểu diễn 1 nút trên cây và CTree để quản lý các nút trên cây .
class CNode
{ public:
void nhap();
void hien();
....
private:
char *Infor; // tên thư mục
CNode *Child; // chứa địa chỉ nút con
CNode *Sibling; // chứa địa chỉ nút em
CNode *Parent; // chứa địa chỉ nút cha
int IsFile; // xác định file hay thư mục
}

class CTree
{ public:
void insert(CTree *,CNode *Cur,CNode *New);
void delete(CNode *Node);
....
private:
CNode *ptree; // chứa địa chỉ nút gốc của cây thư mục
}
Ở đây em sử dụng cây nhị phân tương đương nhưng em đang vướng mắc phần insert. Mong các bác gợi ý cho em cách làm hoặc chỉ cho em tài liệu nghiên cứu, em đã lên mạng search phần Directory Tree nhưng không tìm được phần hướng dẫn

[mtt333]

Hehe, nếu em sử dụng C++ thì có thể sử dụng Vector trong C++ có đầy đủ cả insert, delete, ... cả
Tiếp nữa là các hàm delete, insert, nên đưa vào lớp CNode chứ không nên đưa vào lớp CTree

Ngoài ra em nên tạo hai loại node là nodeFolder và nodeFile, chỉ node Folder mới chứa node con và node file thì chứ nội dung.

#include <stdlib.h>
#include <vector.h>

class CNode
{
public:
    char *strName;

    CNode(char* pstrName)
    {
        strName = pstrName;
    }
}

class CNodeFolder : public CNode
{
public:
    vector<CNode*> m_vtChild;
    CNodeFolder(char* strName) : CNode(strName)
    {
    }

    void Insert(CNode *nodeCur)
    {
        m_vtChild.push(nodeCur);
    }

    void Delete(int i)
    {
        mi_vtChild.erase(mi_vtChild.begin() + i);
    }

    int GetElementCount()
    {
       return m_vtChild.size();
    }

    CNode* GetAt(int i)
    {
       return m_vtChild[i];
    }
}

class CNodeFile : public CNode
{
public:
    vector<CNode*> m_vtChild;
    void* m_pContent;
    int   m_iSize;

    CNodeFile(char* strName) : CNode(strName)
    {
    }

    void SetContent(void* pContent, iSize)
    {
        m_pContent = pContent;
        m_iSize = iSize;
    }
}

Như vậy để tạo cây em chỉ cần một node đầu tiên là gốc, mỗi một node thuộc cây có thể add, delete, ... bao nhiêu node tùy ý.

CNodeRoot   nodeRoot("");
CNodeFolder nodeCDrv("C:");
CNodeFolder nodeDDrv("D:");
CNodeFolder nodeGames("Games");
CNodeFolder nodeWindows("Windows");
CNodeFolder nodeProgramFiles("Program files");
CNodeFolder nodeSystem32("System32");
CNodeFile   nodeKernelDll("Kernel32.dll");

// My computer
nodeRoot.Insert(&nodeCDrv); // C driver
nodeRoot.Insert(&nodeDDrv); // D driver

// C driver
nodeCDrv.Insert(&nodeGames);        // c:\games
nodeCDrv.Insert(&nodeWindows);      // c:\Windows
nodeCDrv.Insert(&nodeProgramFiles); // c:\Program Files

// Windows folder
nodeWindows.Insert(&nodeSystem32);  // c:\Windows\System32

// System32 folder
nodeKernelDll.SetContent("Test node file", 15);  
nodeSystem32.Insert(&nodeKernelDll); // c:\Windows\System32\Kernel32.dll

Tổ chức trên là khá đủ đơn giản để làm việc,
Có rất nhiều cách cải tiến khác để có thể làm việc tốt hơn về hiệu năng hoặc chức năng.
Chẳng hạn em có thể bổ sung:
- Thêm lệnh Dir vào CNodeFolder
- Em có tạo ra những loại thư mục đặc biệt như:
+ CNodeDriver thừ kế từ CNodeFolder chuyên cho các loại ổ đĩa như C:, D: với các lệnh như tính dung lượng ổ đĩa, dung lượng còn lại.
+ CNodeRecycleBin thừa kế từ CNodeFolder và có các lệnh Restore, Empty
+ CNodeDesktop cũng thừa kế từ CNodeFolder với một lệnh Dir trình bày kết quả khác hẳn so với CNodeFolder thông thường...
- Cải tiến cách lưu nội dung của file thay vì chỉ lưu bằng một con trỏ void.

Tuy nhiên thực tế các hệ điều hành quản lý thư mục , file theo cách khác, nói thì dài dòng nhưng nó không sử dụng vector theo kiểu mảng như trên mà nó dùng một dạng gần giống như danh sách liên kết, tất nhiên tổ chức phức tạp hơn nhiều.
Tuy nhiên anh nghĩ đây có vẻ chỉ như một bài tập, không bắt tìm hiểu cấu trúc quản lý file của các hệ điều hành mà chỉ rèn luyện lập trình C++, hướng đối tượng, và cấu trúc dữ liệu cây nên chỉ cần cấu trúc tổ chức cây như trên là tốt rồi.
Nếu có điều kiện, thời gian và đam mê em tìm hiểu về FAT, NTFS, còn Linux nó sử dụng cái gì ai biết nhắc giùm cái. Nếu không hiểu có thể lên đây tiếp tục hỏi.

[ysea]

Cám ơn anh.
Nhưng có 2 vấn đề: chương trình TC của em không có thư viện <vector.h> và quan trọng hơn là đây là bài tập lớn, vì vậy em phải tuân theo yêu cầu của bài là tạo 2 lớp CNode và CTree. Về thuật toán thì em đã rõ nhưng về cách sử dụng con trỏ thì em hơi bí. Em đã xem hết các bài viết về con trỏ của C++ trong diễn đàn này nhưng không có bài viết giải đáp vấn đề của em.
Em ví dụ em đang ở thư mục hiện hành, em muốn chuyển đến thư mục con trong thư mục hiện hành
windows\>cd system
sẽ trở thành: windows\system\>
trong hàm main của em có câu lệnh
pTree->Next(pTree->getroot(),pTenthumuc); // pTree->getroot()->getInfor() : "windows" , pTenthumuc :"system"
Và trong phương thức Next
void CTree::Next(CNode *CurNode,char *s)
{
.............
CurNode->getInfor(); // windows
CurNode=CurNode->getChild(); // trỏ đến node con của CurNode
CurNode->getInfor(); // system
}
Nhưng khi quay lại hàm main em kiểm tra lại biến pTree->getroot()->getInfor() thì nó vẫn giữ giá trị "windows" ? Em không hiểu tại sao lại vậy. Em muốn khi thoát khỏi phương thức Next mà pTree->getroot->getInfor() chứa giá trị mới là "system" thì phải làm như thế nào ?
Mong anh giúp đỡ.

[mtt333]

Nếu không có vector.h, em có thể chủ động tạo cho mình một lớp tương tự, bản chất của lớp vector này chỉ là chứa một mảng động thôi.

Phương án anh đưa ra vẫn đảm bảo có lớp CNode và CTree, CTree chứa node gốc, node gốc chứa các node con đồng thời cho phép mở rộng đề bài hơn nếu em có đủ thời gian.

Quan trọng hơn anh nghĩ đây là bài tập lớn chứ không phải là bài tập nhỏ: tức là em được quyền đưa ra giải pháp và phương hướng giải quyết của em chứ không phải thụ động theo giải pháp mà đề bài hoặc giáo viên đưa ra như bài tập nhỏ. Thiết nghĩ đây mới là cách học tốt chứ không phải cách học thụ động máy móc để được điểm cao.

Còn về vấn đề em hỏi, nguyên nhân là do con trỏ CurNode trong
Next(CNode *CurNode,char *s)
được truyền dạng tham biến nên trong trong hàm này em gán kiểu gì cũng không thể thay đổi được CurNode.

Tiếp nữa là bản thân hàm getRoot của em trả về 1 con trỏ chứa địa chỉ mà nó trỏ vào, nhưng không phải là con trỏ thực sự mà nó nắm giữ.
ví dụ nhé
lớp pTree của em lưu con trỏ char* c;

char* getRoot()
{
    return c;
}

hàm này trả về 1 con trỏ khác c cùng trỏ tới vùng bộ nhớ mà c đang trỏ vào chứ không phải là trả về c, vì vậy em không thể thay đổi được c bằng cách gán

char* rootReturn = getRoot();
rootReturn = NULL;

Cách giải quyết thì có, trong sáng nhất thì không đi theo đúng thiết kế của em, mà theo thiết kế của em thì giải pháp trở nên không trong sáng.

Theo thiết kế của em thì phải sửa như sau

// Tham số truyền là con trỏ của con trỏ thì mới gán được
void CTree::Next(CNode **pCurNode,char *s)
{
 ...
 (*pCurNode) = CurNode->getChild();
 ...
}

Còn hàm getRoot em phải chữa lại thành

Còn về hàm getRoot em phải sửa như sau:

typedef MY_TYPE CNode*
MY_TYPE& getRoot()
{
----
}

Nhận xét: mã nguồn của em đang dần trở nên không trong sáng, bắt đầu có sự lằng nhằng. Nếu căn cứ theo hàm và cách sử dụng hàm thì anh không hiểu CTree để làm cái quái gì, chẳng hiểu chức năng của nó là gì nữa.

[ysea]

Đây là 2 lớp CNode và CTree của em
class CNode
{ public:
CNode();
CNode(char s[]);
char *getInfor();
CNode *getChild() const;
CNode *getSibling() const;
CNode *getParent() const;
void setInfor(char *s);
void setParent(CNode *Node);
void setChild(CNode *Node);
void setSibling(CNode *Node);
int getIsFile();
void setIsFile();
int getIsRoot();
void setIsRoot();
void nhap();
void hien();
private:
char *Infor;
CNode *Child;
CNode *Sibling;
CNode *Parent;
int IsFile;
};

class CTree
{ public:
//CTree():root(){};
CTree(CNode *root);
void Insert(CNode *CurNode,char *s); // Lenh MD,COPY CON
void Delete(CNode *CurNode,char *Tenthumuc,char *s); // Lenh RD,DEL
void Next(CNode *CurNode,char *s);// Lenh CD
CNode *getroot();
void setroot(CNode *Node);
void PrintTree(CNode *Node);
private:
CNode *root;

};
Khi tạo 2 lớp này thì suy nghĩ của em là lớp CNode để biểu diễn 1 nút trên cây còn lớp CTree để quản lý các nút trên cây, các phương thức của lớp CTree tương ứng với các thao tác trên cây. Thuộc tính của lớp CTree dùng để chứa node gốc của cây.
Với suy nghĩ như vậy nên em làm theo cách như em đã nói với anh.
Em nghĩ không cần tạo lớp CNodeFolder và CNodeFile vì trong lớp CNode của em đã có thuộc tính IsFile rồi nên nó sẽ nhận biết được đâu là thư mục và đâu là file.
Em nghĩ cách giải quyết này là trong sáng rồi nhưng do trình độ của em còn thấp nên code của em không trong sáng và lằng nhằng.
Mà bây giờ cho em hỏi về vấn đề con trỏ. Không hiểu hồi trước anh học bao lâu thì sử dụng được con trỏ(bắt lỗi và sửa được lỗi do nó gây ra), chứ em tìm hiểu nó 1 tháng rồi mà nhiều lỗi của nó em không biết khắc phục như thế nào.
Ví dụ liên quan đến câu lệnh cout. Khi in nội dung con trỏ, trước câu lệnh in con trỏ nếu có câu lệnh cout<<.. thì nội dung con trỏ sẽ in đúng còn không thì sẽ in ra các kí tự lạ ( hoặc ngược lại nếu có cout thì nó in không đúng, tất nhiên là tùy từng chỗ nó bị vậy). Hoặc ( giả sử trường Infor của Node chứa giá trị windows):
Node->hien();
cout<<"\\>";
-> đáng lẽ nó phải in ra : windows\> thì nó lại chỉ hiện \>
và em phải sửa lại thành: cout<<'\\'; thì lúc đấy nó mới hiện ra
Nói chung là về con trỏ em rất mơ hồ nên mong anh giải đáp những thắc mắc của em và nếu có thể thì anh chỉ cho em tài liệu hướng dẫn chi tiết về con trỏ(tiếng Việt hay tiếng Anh đều được)
Không biết em có đòi hỏi nhiều quá không nhưng thực sự là bây giờ em rất cần sự giúp đỡ của anh.
Em cám ơn

[ysea]

Phù.., may quá, cuối cùng cũng xong được các chức năng. Hóa ra những lỗi em hỏi anh là do chưa khởi tạo con trỏ, thảo nào lỗi linh tinh hết cả lên. Giờ chỉ cần làm giao diện nữa là xong.
Cám ơn anh mtt333, không có hướng dẫn của anh chắc em phải loay hoay còn lâu mới xong.

[mtt333]

Em nghĩ không cần tạo lớp CNodeFolder và CNodeFile vì trong lớp CNode của em đã có thuộc tính IsFile rồi nên nó sẽ nhận biết được đâu là thư mục và đâu là file.

Chào mừng em đến với thế giới của hướng đối tượng nơi người ta tranh cãi nhau có nên để CFile hay IsFile

[ysea]

Em lập trình còn kém nên không rõ vấn đề CFile hay IsFile tranh cãi nhau như thế nào, mong anh và mọi người tiếp tục giúp đỡ.

[tanphat310]

help_________________uh........anh ơi anh có tài liệu nào về cây đa phân ko....nếu có thì cho em với........em đang cần để viết bài tương tự như là cây thư mục của windown mà mình thường dùng vậy đó....nếu có thì giúp em với.......em đang cần tại liệu về cây đa phân.......em định dùng nó để viết gia phả á mà...........

[=========> Bổ sung bài viết <=========]

em dùng cây nhị phân viết rồi nhưng rối quá nên em phải dùng cây đa phân.....anh nào giúp em thì pm cho em với.........
______________chân thành cảm ơn rất nhiều_________________