Cấu trúc dữ liệu và giải thuật - Smart dictonary

ĐẠI HỌC BÁCH KHOA HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP LỚN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ĐỀ TÀI: smart dictonary Giáo viên hướng dẫn: do bich diep Nhóm sinh viên thực hiện: Tháng 11 năm 2007 1. Định nghĩa: Cây nhị phân là cây mà mỗi nút chỉ có tối đa 2 con. Đối tượng cất giữ: Cây nhị phân có thể cất giữ các đối tượng kiểu cơ bản như:integer,char,float…và các đối tượng kiểu trừu tượng như mảng, xâu, cấu trúc… 2. Cài đặt: Cấu trúc dữ liệu biểu diễn và các phép toán cơ bản Ta có thể định nghĩa 1 cây nhị phân như sau: class Node { //định nghĩa 1 nút nhị phân public: Element data; int posmean; Node *left,*right; Node(){ //tạo một nút rỗng left=0; right=0; }; Node(Element el,int x){ //tạo nút có dữ liệu el và x strcpy(data,el); posmean=x; left=0; right=0; }; } Các phép toán cơ bản được khai báo trong một lớp của cây nhị phân BinTree: class BinTree{ //cây nhị phân và các phép toán private: Node *root; Node *current; int error; public: BinTree(){ root=0; current=0; error=0; }; void insert(Element,int); void remove(KeyType); void find(KeyType); void traverse(int order); int retrieve(void); void destroy(void); int countNode(Node*); int depth(Node*); int hasError(void); private: void preorder(Node *); void inorder(Node *); Node* findNode(KeyType key); Node* findRighty(Node *); Node* findParent(KeyType); void destroyNode(Node *); }; /* ************************************************************** */ void BinTree::insert(Element el,int x) { if (root= =0) //co the chen vao goc root= new Node(el,x); else if (strcmpi(root->data,el)= =0) error=1; // nut goc la nut can tim ko chen duoc else { Node *parent=findParent(el); //tim vi tri cha cua nut can chenn76 if(strcmpi(parent->data,el)<0) { if (parent->right= =0){ //co tu can chen hay chua parent->right= new Node(el,x); current=parent->right; } else error=1; } else { if (parent->left= =0){ //co tu can chen hay chua parent->left= new Node(el,x); current=parent->left; } else error=1; } error=0; } void BinTree::destroyNode(Node *p){ //xóa 1 nút và toàn bộ các con if (p!=0) { destroyNode(p->left); destroyNode(p->right); delete(p); } } void BinTree::destroy(){ //xóa cả cây destroyNode(root); } /* ************************************************************** */ void BinTree::preorder(Node *p){ //duyệt theo thứ tự trước if (p!=0) { cout data << endl; preorder(p->left); preorder(p->right); } } /* ************************************************************** */ void BinTree::inorder(Node *p) { //duyệt theo thứ tự giữa if (p!=0) { inorder(p->left); cout data << endl; inorder(p->right); } } /* ************************************************************** */ void BinTree::postorder(Node *p) { //duyệt theo thứ tự sau if (p!=0) { postorder(p->left); postorder(p->right); cout data << endl; } } /* ************************************************************** */ int BinTree::countNodes(Node *root){ //Đếm số nút của cây if(root= =NULL) return 0; else{ int ld=countNode(root->left); int rd=countNodes(root->right); return 1+rd+ld; } } /* ************************************************************** */ int BinTree::depth(Node *root) //đếm số nút trên đường đi dài nhất { if(root= =NULL) return 0; else{ int ld=depth(root->left); int rd=depth(root->right); return 1+(ld>rd?ld:rd); } } /* ************************************************************** */ void BinTree::mirror(Node* root) //soi gương một cây { if (root= =NULL) { return; } else { Node* temp; // làm với cây con mirror(root->left); mirror(root->right); // đổi chỗ con trái – con phải temp = root->left; root->left = root->right; root->right = temp; } } /* ************************************************************** */ void doubleTree(Node* tree) //nhân đôi 1 cây { Node* oldLeft; if (tree= =NULL) return; doubleTree(tree->left); doubleTree(tree->right); oldLeft = tree->left; tree->left = newnode(tree->word); tree->left->left = oldLeft; } /* ************************************************************** */ int sameTree(Node* a, Node* b) //kiem tra 2 cay co giong nhau ko { // 1. ca 2 cay rong thi dungtra ve true if (a= =N`ULL && b= =NULL) return(true); // 2. ca 2 cay ko rong thi so sanh else if (a!=NULL && b!=NULL) { return( a->word = = b->word && sameTree(a->left, b->left) && sameTree(a->right, b->right) ); } // 3. mot cay rong 1 cay khac rong tra ve false else return ; } 3. Ứng dụng: Bài toán: sử dụng cây nhị phân, các hàm của cây nhị phân tìm kiếm để cài đặt chương trình tra từ điển kết hợp 1 số chức năng về quản lý từ điển. Bộ dữ liệu gồm 2 từ điển: từ điển thuật ngữ tin học: 1400 từ từ điển chuyên ngành dầu khí: 10000 từ - chương trình chạy tốt trên DevC++ - chương trình sử dụng giao diện text, từ cần tra được nhập từ bàn phím Mô tả thuật toán: Lưu trữ dữ liệu từ điển được chia thành 2 file File name.idx chứa từ và vị trí nghĩa (để cho đảm cho cây từ điển được cân bằng thì file dữ liệu vào không được sắp xếp theo ABC, mà được lưu theo thứ tự duyệt trước). File name.dict chứa nghĩa lưu trữ nghĩa của mỗi từ trên 1 dòng Đánh giá độ phức tạp thuật toán: Các hàm xử lý câyDo khi nạp dữ liệu, từ điển được xây dựng là 1 cây nhị phân đầy đủ, nên ta đánh giá các hàm xử lý cây với cây nhị phân đầy đủ Hàm tìm kiếm nút findNode() Gọi số lượng nút là n. Thân vòng lặp while(p!=0 && stricmp(p->data,key)!=0) { if (stricmp(p->data,key)right; else p=p->left; } Có thời gian chạy là O(1). Ta chỉ cần tính số lần lặp. Gọi t là số lần lặp tối đa, ta có sau mỗi lần lặp số nút cần xét giảm đi 1 nửa=> t<= log2 n Thời gian chạy O(log2n) Hàm findParent(), find() Làm tương tự như trên ta có thời gian chạy là O(log2n) Hàm duyệt cây preOder(), inOder(), postOder() void BinTree::preorder(Node *p){ if (p!=0) { cout data << endl; preorder(p->left); preorder(p->right); } } Giả sử cây có n nút, tại nút gốc có n/2 con trái và n/2 con phải. Thời gian chạy của hàm: T(n)= O(1)+ 2T(n/2) Thay O(1) bởi hằng số C ta có T(n)= 2T(n/2) + C. Áp dụng định lý thợ với a=b=2, k=0 thời gian thực hiện là O(n) Tương tự ta có thời gian chạy của hàm inOder(), postOder() là O(n) Hàm xoá cây destroy(), destroyNode() Duyệt qua tất cả n nút của cây, tại mỗi nút thực hiện if (p!=0) { destroyNode(p->left); destroyNode(p->right); delete(p); } CM tương tự như hàm preOder() ta có thời gian chạy là O(n) Hàm retrieve(): thời gian chạy là hằng số O(1) Hàm chèn nút vào cây insert() void BinTree::insert(Element el,int x){ các câu lệnh có độ phức tạp O(1) else { Node *parent=findParent(el); //Các câu lệnh có độ phức tạp O(1) } else error=1; } else { // các câu lệnh có độ phức tạp O(1) } Nếu cây rỗng(n=0), thời gian chạy là O(1). Thời gian thực hiện hàm findParent() là O(log2n) (CM trên) =>Thời gian tính của hàm insert() là O(log2n) Hàm xoá nút remove() Coi nút bị xoá là nút gốc của 1 cây nhị phân Độ phức tạp của hàm nằm ở câu lệnh gọi 2 hàm Node *parent=findParent(key): cha của nút cần thao tác. Ta có thời gian tính là O(f(n))=O(log2n) (theo CM trên) Node *righty=findRighty(p->left): Tìm con phải cùng của cây con trái nút cần xóa. Node* BinTree::findRighty(Node *p) { Node *Righty=p; while (Righty->right!=0) Righty=Righty->right; return Righty; } Ta có thời gian thực hiện vòng lặp while là O(1), số vòng lặp không quá n/2( do chỉ tìm con phải) => O(g(n))= O(n/2)= O(n) => thời gian tính của hàm T(n)= max{O(f(n)); O(g(n)) }= O(n) Các hàm ứng dụng và quản lý từ điển Hàm selectDict(), showMenu() có thời gian thực hiện là O(1) Hàm đọc từ điển loadDict() if ((f=fopen(index,"rt"))==0) { …khối câu lệnh có độ phức tạp O(1) } while (!feof(f)) { f_gets(el,50,f); if (strlen(el)) { T.insert(el,x); …Các câu lệnh có độ phức tạp O(1) } }Gọi thời gian thực hiện của hàm là T(n)- Thời gian thực hiện của hàm f_gets(el,50,f) đọc xâu từ file .idx là O(f(n))- Thời gian thực hiện của hàm T.insert(el,x) chèn từ vừa đọc vào cây từ điển là O(g(n)). Phần trên ta đã chứng minh hàm insert có O(g(n))=O(log2n) vòng lặp while thực hiện đọc toàn bộ n từ vào cây từ điển=> lặp n vòng=> thời gian thực hiện hàm là T(n)= n* max{O(f(n)), O(g(n)) } - Tính O(f(n)): đọc tất cả các kí tự trên 1 dòng cho tới khi gặp dâu tab \t while (!feof(f) && i<n){ khối câu lệnh có độ phức tạp O(1) } Vòng lặp thực hiện không quá m lần với m là số kí tự lớn nhất của 1 từ trong từ điển. Ta có O(f(n))=O(m). Do m T(n)= n*O(g(n))= n* log2n Hàm xóa từ điển đã load resertDict(). gọi hàm destroy() để xoá cây từ điển đã tạo => thời gian tính là O(n) (chứng minh phần trên) Hàm tra từ findWord() void DictionaryApp::findWord(){ … các câu lệnh có thời gian thực hiện O(1) T.find(el); if (T.hasError()) cout <<"Khong tim thay\n"; else { khối câu lệnh có thời gian tính O(1) } if (f_seek_line(f,T.retrieve()-1)!=0){ khối câu lênh có thời gian tính O(1) } Ta có T(n)= max{O(f(n)); O(g(n)) } với T(n): thời gian thực hiện của hàm findWord() O(f(n)) thời gian tính hàm T.find(el). Từ phần đánh giá cho các hàm xử lý cây ta có O(f(n))=log2n O(g(n)): thời gian thực hiện của hàm tìm kiếm nghĩa của từ f_seek_line(f,T.retrieve()-1)!=0)Dễ thấy f_seek_line() chạy qua các dòng của file nghĩa cho tới khi gặp dòng cần đọc=> thời gian chạy chỉ phụ thuộc vào vị trí dòng nghĩa k O(g(n))=O(n) T(n)= max{O(n); O(n) }= O(n) Hàm xoá từ khỏi cây từ điển delWord(): hàm thực hiện 2 công việc kế tiếp: Gọi hàm xoá 1 nút vào cây remove()=> thời gian tính O(n) Gọi hàm T.traverse(f,PRE_ORDER): ghi lại file từ điển theo thứ tự duyệt trước. Do hàm này chỉ thực hiện lời giọi preOder() hoặc inOder() tuỳ theo tham số truyền vào=> thờ gian tính O(n) => Thời gian tính T(n)= max{O(n); O(n) }= O(n) Hàm thêm từ vào từ điển addWord(): tương tự như trên, hàm thực hiện việc chèn 1 từ vào cây từ điển insert() sau đó ghi lại file chứa từ name.idx theo thứ tự duyệt giữa inOder(), chèn thêm 1 dòng vào cuối file chứa nghĩa name.dic => thời gian tính T(n)= O(n) Hàm ghi lại các file lưu từ điển T.traverse(): ghi lại file lưu trữ từ điển khi có xoá hay thêm từ void BinTree::traverse(FILE *f,int order) { if (order == PRE_ORDER) preorder(f,root); else if (order == IN_ORDER) inorder(f,root); else cout << "no such order " << endl; } thực hiện gọi hàm inOder() ghi lại file nghĩa .dic và gọi hàm preOder()để ghi lại file từ .idx => thời gian thực hiện T(n)= max{O(f(n)); O(g(n)) } với O(f(n)) và O(g(n)) lần lượt là thời gian tính của hàm preOder(),inOder(). Theo phần đầu ta có O(f(n))=O(n); O(g(n))= O(n) =>T(n)= O(n) c. Mô tả cài đặt chương trình: Chương trình được tổ chức thành 2 file BinTree.cpp: chứa khai báo lớp và cài đặt các hàm cho cây nhị phân DictionaryApp.cpp: chứa cài đặt cho các ứng dụng từ điển d.Ví dụ minh họa và hướng dẫn sử dụng: 1. Chạy chương trình chọn từ điển cần tra cứu: phím 1 là chọn từ điển Thuật Ngữ Tin Học phím 2 là chọn từ điển Dầu Khí 2. chọn các chức năng xuất hiện trên mà hình băng phím tương đương Ví dụ1: chọn từ điển Tin Học chọn chức năng tra từ (phím 1) đánh từ cần tra : “map” xuất hiện nghĩa: “-ánh xạ -bản đồ”. chọn các chức năng khác hoặc ấn phím “x” để thoát ra ngoài. Ví dụ2:chọn từ điển Tin Học chọn chức năng tra từ (phím 1) đánh từ cần tra : “oxide” xuất hiện nghĩa: “o xit”. chọn các chức năng khác hoặc ấn phím “x” để thoát ra ngoài.