Ôn tập cuối học phần

Yêu cầu

Giả sử phải xây dựng một chương trình soạn thảo văn bản, hãy chọn cấu trúc dữ liệu thích hợp để lưu trữ văn bản trong quá trình soạn thảo. Biết rằng :

Số dòng văn bản không hạn chế.

Mỗi dòng văn bản có chiều dài tối đa 80 ký tự.

Các thao tác yêu cầu gồm :

Di chuyển trong văn bản (lên, xuống, qua trái, qua phải)

Thêm, xoá sửa ký tự trong một dòng

Thêm, xoá một dòng trong văn bản

Đánh dấu, sao chép khối

Tổ chức dữ liệu

Văn bản gồm các dòng, mỗi dòng đứng sau một dòng và đứng trước một dòng khác. Như vậy có thể dùng một danh sách tuyến tính các dòng đểå biễu diễn văn bản.

Mỗi dòng văn bản là một danh sách tối đa 80 ký tự, vậy có thể dùng mảng để biễu diễn.

Số dòng văn bản không hạn chế nên phải dùng một danh sách liên kết. Vì có nhu cầu lưu thông 2 chiều (di chuyển lên xuống) nên phải dùng danh sách liên kết kép.

Định nghĩa các CTDL sau :

typedef DONG char[80];

typedef struct tagdongVB // một dòng trong văn bản

{

DONG noidung;struct tagdongVB * pPrev;struct tagdongVB * pNext;

}DONGVB;

Nên sử dụng các biến sau để quản lý văn bản :

DONGVB * vanban; // con trỏ đến dòng đầu tiên trong văn bản

DONGVB * curdong; // con trỏ đến dòng hiện hành

int curcot; // chỉ số cột của ký tự hiện hành

// ký tự hiện hành được xác định bởi curdong,curcot;

int x,y; // vị trí hiện hành trên màn hình

Tổ chức xử lý

Giải thuật cho dòng xử lý chính :

main() // con trỏ đến dòng đầu tiên trong văn bản

{

char ch;x = y =0;curdong = vanban;curcot = 0;do{

ch = getch()switch (ch){

case(ch == ­ ): curdong = curdong->pprev; break;

case(ch == ¯ ): curdong = curdong->pNext; break;

case(ch ==® ): curcot +=1; break;

case(ch == ¬ ): curcot-=1; break;

case(ch == ENTER): InserNode(vanban);

case(ch == CTRL_Y): DelNode(curdong);

else

if (ch>=’A’) && (ch<=’a’)

curdong->notdung[curcot] = ch;

}

}while(1);

}

Lưu ý :

Giải thuật này chỉ phác thảo các công việc chính, cơ bản của chương trình soạn thảo, không xét đến các trường hợp đặc biệt (xâu rỗng..) cũng như các chức năng phức tạp (xem như bài tập)

Các thao tác cập nhật curdong, curcot chỉ kiểm soát được ký tự hiện hành trong danh sách lưu trữ, để liểm soát sự di chuyển tương ứng trên màn hình cần phải cập nhật x,y.

Yêu cầu

Cài đặt chương trình phát sinh hệ thống thực đơn cho một ứng dụng bất kỳ tùy theo mô tả của ứng dụng.

Ví dụ : Cho tập tin MENU.TXT chứa văn bảng có dạng sau :

Menu

popup

item "Hello World" popup

item "Good morning"

item "Good afternoon"

item "Good everning"

item "Good night"

end

item "Conversation" popup // menu cấp 1

item "Good Luck" popup // menu cấp 2

item "Good luck for this examination"

end

item "Hi"

item "Happy New Year"

end

end

Chương trình sẽ đọc nội dung tập tin MENU.TXT và phát sinh giao diện :

Tổ chức dữ liệu

Mỗi thực đơn là danh sách gồm các phần tử , mỗi phần tử là 1 item. Đến lượt mỗi item lại là một danh sách => cả hệ thống menu có thể biểu diễn qua một danh sách tổng quát

Để thuận tiện cho việc chọn lựa một mục trong menu, nên dùng danh sách kép

Để tiện quản lý các phần tử trong một mục, nên có thêm một con trỏ liên kết với menu cấp cha.

Định nghĩa các CTDL sau :

typedef struct tagitem

char tieude[20];

struct tagitem * pPrev;

struct tagitem * pNext;

struct tagitem * pParent;

}ITEM;

Tổ chức xử lý

Cần xây dựng module xử lý file văn bản để lấy được từng từ, kiểm tra ý nghĩa từ khoá để xem có bắt đầu một menu con hay không ?

Lưu ý :

Giải thuật này chỉ phác thảo các công việc chính, cơ bản của chương trình soạn thảo, không xét đến các trường hợp đặc biệt (xâu rỗng..) cũng như các chức năng phức tạp (xem như bài tập)

Các thao tác cập nhật curdong, curcot chỉ kiểm soát được ký tự hiện hành trong danh sách lưu trữ, để liểm soát sự di chuyển tương ứng trên màn hình cần phải cập nhật x,y.

Từ điển Anh_Việt

Yêu cầu

Cài đặt chương trình từ điển điện tử AnhViệt.

Tổ chức dữ liệu

- Thao tác chính trên từ điển Anh Việt là tra cứu, nên CTDL thích hợp để tìm kiếm là cây AVL

- Định nghĩa các CTDL sau :

typedef struct tagavNode

char Eword[10];

char Vmeaning[20];

struct tagavNode* pleft;

struct tagavNode* pright;

}AVNODE;

typedef AVNODE *AVTREE;

Tổ chức xử lý

Cài đặt các thao tác thông thường trên cây AVL.