Tài liệu Xây dựng từ điển anh việt và ngược lại

Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT LỜI MỞ ĐẦU Tin học là một ngành khoa học mũi nhọn phát triển hết sức nhanh chóng trong vài chục năm trở lại đây và ngày càng mở rộng lĩnh vực nghiên cứu, ứng dụng trong mọi mặt của đời sống xã hội. Mà hơn tất cả đó là các phần mềm hữu dụng phục vụ các công việc thường ngày của con người. Ngày nay, các sản phẩm phần mềm ra đời nhằm cung cấp các chương trình ứng dụng thực hiện trên các thiết bị điện tử như máy tính, các bộ điều khiển,… Điều này thực hiện được để đơn giản hoá các công đoạn trong hệ thống công việc. Do đó bọn em đã chọn đề tài:” Xây dựng từ điển Anh-Việt và ngược lại “ vì đó là một đề tài thiết thực trong công việc học tập, giúp e có thể tự mình tạo ra một từ điển nhỏ phục vụ cho việc học tập. Nhóm 5 Page 2 Trường đại học Bách Khoa Hà Nội I. Bài tập lớn môn học KTLT HƯỚNG LÀM BÀI TẬP 1. Ý tưởng: - Do đề bài yêu cầu 1 bộ từ điển có từ, nghĩa của từ, câu mẫu nên Chúng ta sẽ xây dựng 1 cơ sở dữ liệu, trong đó sử dụng danh sách liên kết, mỗi 1 node sẽ bao gồm từ và nghĩa của từ. - Đồng thời, do chúng ta cần lưu lại sử dụng lại cơ sở dữ liệu nên ta cần phải lưu các từ ra 1 file txt để sử dụng - Do từ điển cần phải thêm- update các từ, cũng như có thể có nhu cầu xóa, nên ta sẽ xây dựng 1 menu gồm: + Thêm từ + Tra từ + Xóa từ + Xem cà danh sách 2. Các thuật toán cần phải tìm hiểu. Để thực hiện các ý tưởng đặt ra, chúng ta cần phải tìm hiểu về các thuật toán sau: + Các thuật toán liên quan đến danh sách liên kết: + Các thuật toán liên quan đến xuất/nhập, in MENU ra màn hình chính + Các thuật toán liên quan đến xử lý file II. CÁC BƯỚC THỰC HIỆN 1. Cấu trúc chương trình: Chương trình bao gồm 1 file Header và 1 file cpp để thực hiện,  File header sẽ bao gồm: + Các thuật toán liên quan đến danh sách liên kết Page 3 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT + Các thuật toán liên quan đến xuất/ nhập, in ra Menu + Các thuật toán liên quan đến xử lý tệp  File cpp sẽ bao gồm các hàm thực hiện 2. File header Hash_table.h  Khai báo các thư viện cần dùng #include #include #include #include #include #include using namespace std; #define M 26 2.1.1. Các thuật toán liên quan đến danh sách liên kết  Lập danh sách liên kết: typedef struct tagnode { char word[20]; char mean[100]; struct tagnode*pNext; }NODE; typedef struct tagList { NODE* pHead; Page 4 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT NODE* pTail; }LIST;  Khởi tạo với danh sách rỗng: void initList(LIST &l) { l.pHead= l.pTail = NULL; }  Tạo ra một phần tử chứa thông tin dữ liệu NODE* GetNode(char word[],char mean[]) { NODE *p; p = new NODE; if(p==NULL) { cout<<"Khong du bo nho"; return NULL; } strcpy(p->word,word); strcpy(p->mean,mean); p->pNext = NULL; return p; } Page 5 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT 2.1.2. Các thuật toán chèn phần tử, thêm bớt phần tử, dùng để khai thác cơ sở dữ liệu của mình:  Chèn vào đầu: void AddFirst(LIST &l,NODE* new_ele) { if(l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { new_ele->pNext = l.pHead; l.pHead = new_ele; } } NODE* InsertHead(LIST &l,char word[],char mean[]) { NODE* new_ele = GetNode(word,mean); if(new_ele == NULL) return NULL; if(l.pHead == NULL) { l.pHead = new_ele; l.pTail = l.pHead; Page 6 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT } else { new_ele->pNext = l.pHead; l.pHead = new_ele; } return new_ele; }  Chèn vào cuối: void AddTail(LIST &l,NODE *new_ele) { if(l.pHead == NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->pNext = new_ele; l.pTail = new_ele; } } NODE* InsertTail(LIST &l,char word[],char mean[]) { Page 7 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT NODE* new_ele = GetNode(word,mean); if(new_ele == NULL) return NULL; if(l.pHead == NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->pNext = new_ele; l.pTail = new_ele; } return new_ele; }  Chèn vào sau một phần tử nào đó trong danh sách: NODE* InsertAfter(LIST &l,NODE *q,char word[],char mean[]) { NODE* new_ele = GetNode(word,mean); if(new_ele ==NULL) return NULL; if(q!=NULL) { Page 8 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT new_ele->pNext = q->pNext; q->pNext = new_ele; if(q==l.pTail) l.pTail = new_ele; } else AddFirst(l,new_ele); }  Tìm kiếm một phần tử trong danh sách : NODE *Search(LIST l,char word[]) { NODE *p; p = l.pHead; while((p!=NULL) && (strcmp(p->word,word)!=0)) p =p->pNext; return p; }  Xóa phân tử: int RemoveNode(LIST &l,char word[]) { NODE *p = l.pHead; NODE *q = NULL; while(p!=NULL) Page 9 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT { if(strcmp(p->word,word)==0) break; q = p; p = p->pNext; } if(p==NULL) return 0; if(q!=NULL) { if(p == l.pTail) l.pTail = q; q->pNext = p->pNext; delete p; } else { l.pHead = p->pNext; if(l.pTail==NULL) l.pTail = NULL; } return 1; } II.2.2. Các thuật toán liên quan đến xuất/ nhập, in ra Menu Page 10 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT  Duyệt danh sách: void ProcessList(LIST l) { ofstream fg; fg.open("output.txt",ios::app); NODE *p; int i = -1; p = l.pHead; while(p!= NULL) { cout <<"\""<word<<"\"";fg <<"\""<< p->word <<"\""; cout << " nghia cua tu : ";fg << " nghia cua tu :"; cout << p->mean;fg << p->mean; cout << endl;fg << endl; p = p->pNext; } fg.close(); }  Như vậy, ta đã xây dựng danh sách liên kết chính của mình , với các cú pháp thêm, chèn dữ liệu, và cả duyệt danh sách. Sau khi đã xây dựng xong, ta phải tiến hành khai thác danh sách liên kết để thực hiện chương trình. Page 11 Trường đại học Bách Khoa Hà Nội  Bài tập lớn môn học KTLT Hàm băm: int hashfunc(char word[]) { char ch = toupper(word[0]); return ((ch - 65)%M); }  Khởi tạo void initbucket() { for(int i=0;iword); AddTail(bucket[i],p); }  Tìm kiếm 1 phần tử và trả về địa chỉ của nó : NODE* Find(char word[]){ int i=hashfunc(word); return (Search(bucket[i],word)); } Page 12 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT Bây giờ, ta sẽ bắt đầu xây dựng các hàm menu thực hiện Hàm thêm từ:  void MakeDictionary() { NODE*p; char word[20]; char mean[100]; char c; do { fflush(stdin); cout << "Nhap tu can tao:";gets(word);cout<mean<=65 && temp<=90)||(temp >=97 && temp<=122)) return true; return false; } void MakeFromFile() { NODE*p; char c; int dem =0; int i=0;int j=0; char word[20]; char mean[100]; FILE*f; f = fopen("data.txt","rt"); if(f==NULL) Page 15 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT { printf("Khong mo duoc file"); exit(0); } while(!(feof(f))) { c = getc(f); if(dem == 0) { if(!(ischar(c)) && c!='\n') { word[i]='\0'; dem=1; } else word[i++] = c; } else { if(c!='\n') { mean[j++]=c; } else Page 16 Trường đại học Bách Khoa Hà Nội Bài tập lớn môn học KTLT { mean[j] = '\0'; if(strlen(word)!=0 || strlen(mean)!=0) { p = GetNode(word,mean); Insert(p); } dem = 0;i = 0;j=0; //} } } } } 3. Chương trình chính gồm: //Chuong trinh tu dien don gian theo phuong phap ket noi truc tiep #include"Hash_table.h" void main() { MakeFromFile(); char chon; do { cout<<"\t\t------------------------------------------------------"< - Xem thêm -