Cấu trúc dữ liệu Tree trong C++

Một bộ thư viện cài đặt cấu trúc dữ liệu Tree trong C++ theo STL Style khá hay và dễ sử dụng:

http://tree.phi-sci.com/

Hỗ trợ các thao tác cơ bản với Tree như chèn, xóa node trong Tree, duyệt cây theo thứ tự pre, in-order, post-order,…

Rất đáng để tìm hiểu.

Advertisements

Duyệt các file trong một thư mục với C++ sử dụng thư viện boost

Khi lập trình C++ thao tác với file/thư mục; một yêu cầu thường gặp là duyệt tất cả các file trong một thư mục. Các hàm xử lý thư mục không phải là hàm chuẩn trong C++, và thư viện STL cũng không có các hàm này. Trên các platform khác nhau lại có các hàm xử lý khác nhau. Điều này gây khó khăn khi chuyển từ platform này sang platform kia, ta lại phải làm lại.

Bài viết ghi chép lại cách sử dụng bộ thư viện boost cho C++ để thực hiện việc duyệt các file trong một thư viện (tổng hợp từ nhiều nguồn trên NET).

boost C++ là bộ thư viện mã nguồn mở, extend các chức năng của bộ thư viện sẵn có của C++, cho phép khả năng khả chuyển trên nhiều platform. Để sử dụng boost, trước tiên cần cài bộ thư viện này. Download tại: http://www.boost.org/

Tham khảo các tài liệu về bộ thư viện này tại: http://en.highscore.de/cpp/boost/http://shoddykid.blogspot.com/2008/07/getting-started-with-boost.html

Để duyệt các file trong một thư mục, tôi sử dụng lớp Boost Filesystem và các hàm trong lớp đó.

Đoạn chương trình sau đây minh họa cách sử dụng lớp Filesystem để duyệt các file trong một thư mục.


#include <iostream>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/fstream.hpp>

using namespace std;

/**
* List all files in the directory
* @param dirname
*/
void directoryListing(const string& dirname) {
  // Tạo full path cho thư mục dirname
  boost::filesystem::path dirpath(dirname, boost::filesystem::native);

  // Kiểm tra xem thư mục có tồn tại
  if (!boost::filesystem::exists(dirpath)) {
    cerr << "Directory: " << dirname << " does not exist!" << endl;
    return;
  }
  if (!boost::filesystem::is_directory(dirpath)) {
    cerr << dirpath.string() << " is not a directory!" << endl;
    return;
  }

  // Khai báo iterator để duyệt thư mục
  boost::filesystem::directory_iterator end_itr;

  for (boost::filesystem::directory_iterator itr(dirpath); itr != end_itr; itr++) {
    string filename = itr->leaf(); // Tên file hiện tại
    cout << filename; //
    if (boost::filesystem::is_directory(*itr)) {
      cout << " (dir)"; // Nếu là thư mục in ra (dir)
    }
    cout << "\n";
  }
}

Khi duyệt file, ngoài việc in ra tên file/thư mục, có thể chèn các dòng code xử lý file tùy ý. Chú ý khi dịch bạn cần chỉ rõ đường dẫn tới các header files và thư viện boost (dùng tùy chọn -I và -L khi biên dịch).

Hàm trim cho một xâu ký tự (C++)

(1) Phiên bản với kiểu string (loại bỏ ký tự trắng ở đầu và cuối xâu)

// remove leading spaces and trailing spaces of a string
void trimSpaces( string & str) {   
    size_t startpos = str.find_first_not_of(" \t");
    size_t endpos = str.find_last_not_of(" \t");
    if ((string::npos == startpos) || (string::npos == endpos)) {
      str = "";
    }
    else {
      str = str.substr(startpos, endpos - startpos + 1);
    }

Đọc, ghi text file với C++

(1) Đọc từng dòng của một file text vào một mảng các string, bỏ qua dòng trống


// read_line.cpp
// read all lines of a text file into an array of strings

using namespace std;

// remove space after the string s
void rtrim(char *s)
{
 unsigned int len = strlen(s);

 while (len > 0 && s[len-1] == ' ') len--;
 s[len] = 0;
}

void readToArr(char* fileName, vector<string> & arr)
{
ifstream fin(fileName, ifstream::in);
char line[10000];

while (fin.getline(line, 1000)) {
rtrim(line);
if (strlen(line) == 0) continue;
arr.push_back(line);
}
fin.close();
}

int main(int argc, char* argv[])
{
vector<string> arr;

readToArr(argv[1], arr);

// print all line in arr
vector::iterator it;

for( it = arr.begin(); it < arr.end(); it++ )
{
cout << *it << endl;
}
return 0;
}

(2) Ghi vào file với C++

#include <iostream>
#include <fstream>

using namespace std;

int main(int argc, char* argv[]) {
  ofstream fo("filename", ios::out);
  fo << "Line 1: Demo viết 1 dòng vào file" << endl;
fo << "Line 2: Ví dụ rất đơn giản" << endl;
  fo.close();

  return 0;
}

Lấy ra raw string từ các câu đã được pos tagged

Đầu vào: Câu đã được POS Tagging. Ví dụ

Upon_IN such_JJ reading_NN of_IN any_DT such_JJ certificate_NN or_CC paper_NN ,_, the_DT President_NNP of_IN the_DT Senate_NNP shall_MD call_VB for_IN objections_NNS ,_, if_IN any_DT ._.

Đầu ra: Câu chưa được POS Tagging

Upon such reading of any such certificate or paper , the President of the Senate shall call for objections , if any

Hàm ruby (Sử dụng hàm gsub)

def get_raw_text(str)
return str.gsub(/_(.+?)\s|_(.+?)/, ' ').strip
end

Hàm tokenizer bằng C++

Hàm sau đây nhận đầu vào là một xâu gồm các từ cách nhau bởi dấu cách và trả về một vector của các từ trong tiếng Anh.

Ví dụ: I am a student
=> Trả về vector gồm các từ: ‘I’, ‘am’, ‘a’, ‘student’.


vector<string> tokenizer(const string & str, const string & delimiters)
{

  vector<string>  tokens;

  // Skip delimiters at beginning.

  string::size_type lastPos = str.find_first_not_of(delimiters, 0);

  // Find first "non-delimiter".

  string::size_type pos = str.find_first_of(delimiters, lastPos);

  while (string::npos != pos || string::npos != lastPos)
  {
    // Found a token, add it to the vector.
    tokens.push_back(str.substr(lastPos, pos - lastPos));
    // Skip delimiters. Note the "not_of"
    lastPos = str.find_first_not_of(delimiters, pos);
   // Find next "non-delimiter"
   pos = str.find_first_of(delimiters, lastPos);
  }
  return tokens;
}