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).

[Tutorial] Xử lý file XML với libxml2 trong C

Bài viết này hướng dẫn cách xử lý file XML trong C/C++ với libxml2.

Bài viết dựa trên LibXML tutorial download tại: http://xmlsoft.org/tutorial/xmltutorial.pdf

Mục tiêu:

+ Hướng dẫn các thao tác cơ bản trong xử lý XML: như kiểm tra hợp lệ của file XML, lấy các thông attibute của các node, lấy text content của các node, duyệt các node trong XML Tree với XPath

+ Cung cấp các tài liệu tham khảo cần thiết khi xử lý file XML với C/C++

+ Cung cấp các hàm tiện ích cho xử lý file XML

(1) Định dạng XML: Dùng để lưu trữ và biểu diễn dữ liệu, đặc biệt quan trọng với các dữ liệu trên Web.

Nếu chưa quen thuộc với XML, có thể tham khảo thêm tại: http://www.w3schools.com/xml/default.asp

Ví dụ file XML:

<?xml version="1.0"?>
<note>
 <to>Tove</to>
 <from>Jani</from>
 <heading>Reminder</heading>
 <body>Don't forget me this weekend!</body>
</note>

(2) Xử lý file XML với libxml

3 kiểu dữ liệu cơ bản:

+ xmlChar: Kiểu dữ liệu cơ bản, lưu trữ 1 bye trong UTF-8 Encoding
+ xmlDoc: Cấu trúc dữ liệu chứa tree của xml doc được parsed. xmlDocPtr để lưu trữ con trỏ tới xmlDoc
+ xmlNode và xmlNodePtr: Lưu trữ 1 sing node trong cây

Function 1: Parse một xml file, trả về con trỏ xmlDocPtr, nếu văn bản không được parse thành công trả về NULL.

Thêm các dòng #include sau vào đầu các file

#include <string>
#include <libxml/parser.h>
#include <libxml/xpath.h>
#include <libxml/xmlmemory.h>

// Return a pointer of type xmlDocPtr point to xmlDoc
// @docname: xml document name
xmlDocPtr getDoc( const char* docname ) {
  xmlDocPtr doc;
  doc = xmlParseFile( docname );
  if ( doc == NULL ) {
    cerr << "Document not parsed successfully" << endl;
    return NULL;
  }
  return doc;
}

Function 2: Tìm một node với tên cho trước, trả về con trỏ xmlNodePtr

// Return a pointer to xmlNodePtr
// Find the child node with name node_name
xmlNodePtr getChildNode( xmlNodePtr parent, string node_name ) {
  xmlNodePtr cur = parent->xmlChildrenNode;
  while ( cur != NULL ) {
    if ( !xmlStrcmp( cur->name, ( xmlChar* ) node_name.c_str() ) ) {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

Function 3: Tìm node anh em của một node, với tên node được cho trước (Sử dụng hàm next())

// Get sibling node with @node_name
xmlNodePtr getSiblingNode( xmlNodePtr a_node, string node_name ) {
  xmlNodePtr cur = a_node->next;
  while ( cur != NULL ) {
    if ( !xmlStrcmp( cur->name, ( xmlChar* ) node_name.c_str() ) ) {
      return cur;
    }
    cur = cur->next;
  }
    return NULL;
}

Function 4: Trả về giá trị của một attribute của một node, tên cho trước

// Get attribute value of @att_name
string getAttrStr( xmlNodePtr cur, string att_name ) {
 xmlChar* uri = xmlGetProp( cur, (xmlChar*) att_name.c_str() );
 if ( uri == NULL ) {
 cerr << "Attribute " << att_name << " does not exist" << endl;
 return "";
 }
 string att_val = (char*) uri;
 xmlFree(uri);
 return att_val;
}

Function 5: Lấy text content của một node

string getElementContent( xmlDocPtr doc, xmlNodePtr cur ) {
 xmlChar * txt_content = xmlNodeListGetString( doc, cur->xmlChildrenNode, 1);
 if ( txt_content == NULL ) {
 cerr << "Text content does not exist!!!" << endl;
 return "";
 }
 string strContent = (char*) txt_content;
 trimSpaces( strContent );
 xmlFree( txt_content );
 return strContent;
}

Function 6: Trả về một tập các node theo xPath

// Return a pointer to xmlPathObject
// @doc: context of the type xmlDocPtr
// @xpath: criteria for the xpath to retrieve set of nodes
xmlXPathObjectPtr getNodeSet(xmlDocPtr doc, xmlChar* xpath) {
 xmlXPathContextPtr context;
 xmlXPathObjectPtr result;
 context = xmlXPathNewContext( doc );
 if ( context == NULL ) {
 cerr << "Error in xmlXPathNewContext" << endl;
 return NULL;
 }

 result = xmlXPathEvalExpression( xpath, context );
 xmlXPathFreeContext( context );

 if ( result == NULL ) {
 cerr << "Error in xmlXPathEvalExpression" << endl;
 return NULL;
 }

 if ( xmlXPathNodeSetIsEmpty ( result->nodesetval ) ) {
 xmlXPathFreeObject( result );
 // cerr << "No result" << endl;
 return NULL;
 }
 return result;
}

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;
}

Hướng dẫn cài đặt và sử dụng thư viện Xerces-C

Xerces-C là thư viện được phát triển bởi Apache nhằm cung cấp cho các developer các API hữu ích cho việc tạo, xử lý tài liệu XML. Bài viết nhằm memo nhứng step chính để cài đặt và bắt đầu sử dụng thư viện Xercess-C trên môi trường Linux. Hướng dẫn được tổ chức thành từng step cho tiện theo dõi và thực hiện.

Step 1: Download mã nguồn Xerces-C tại địa chỉ: http://xerces.apache.org/xerces-c/download.cgi. Phiên bản hiện tại là 3.0.1. Download file xerces-c-3.0.1.tar.gz vào thư mục trên máy. Chẳng hạn thư mục /home/user-name/src

Step 2: Mở một terminal, chuyển đến thư mục /home/user-name/src bằng lệnh cd

Step 3: Giải nén file bằng lệnh tar
tar xfz xerces-c-3.0.1.tar.gz

Step 4: Chuyển vào thư mục vừa được tạo ra ở bước 3 (thư mục xerces-c-3.0.1

Step 5: Cấu hình việc make file dùng script sẵn có configure. Có thể thay đổi các tùy chọn của lệnh ./configure (muốn xem các tùy chọn này, gõ ./configure –help). Trong TH của tôi, tôi sử dụng
./configure CC=gcc-4.3 CXX=g++-4.3 –prefix=/home/user-name/opt
Trong đó gcc-4.3 là tên trình biên dịch C, g++-4.3 là tên trình biên dịch C++ (muốn xem version dùng lệnh gcc –version). Tùy chọn –prefix chỉ ra thư mục mà bạn muốn cài đặt thư viện và các include file (mặc định là /user/local)

Step 6: Gõ
make

Step 6: Cài đặt sử dụng
make install

Step 7: Export đường dẫn cho thư viện

Thêm dòng sau đây vào file cấu hình

export LD_LIBRARY_PATH=/home/user-name/opt/lib

Nếu không có gì đặc biệt, bạn sẽ cài đặt xong thư viện Xerces với 7 bước như trên. Nếu muốn bạn có thể kiểm tra xem thư viện đã được cài đặt thành công hay không, sử dụng:
make check

Phần 2: Biên dịch chương trình với thư viện Xerces-C

File sử dụng là DOMCount.cpp và DOMCount.hpp (trong thư mục samples/src)

Soạn file Makefile như sau:

cc = g++

INCLUDE = /home/user-name/opt/include

LIBS = /home/user-name/opt/lib

objs = DOMCount.o

DOMCount: $(objs) DOMCount.hpp
$(cc) -I$(INCLUDE) -L$(LIBS) -lxerces-c $(objs) -o DOMCount

DOMCount.o: DOMCount.cpp DOMCount.hpp
$(cc) -c DOMCount.cpp -I$(INCLUDE)

clean:
rm DOMCount $(objs)

Tại Terminal gõ make

Sau đó thực thi chương trình theo hướng dẫn

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;
}