데이터구조 - HW4 - The Librarian and Lexical trees - 연세대학교 최정윤 교수님

소개

데이터구조 연세대 최정윤교수님 HW4입니다

The Librarian and Lexical trees

보고서 첨부되어있습니다.

컴파일 실행환경

Microsoft Visual C++ 6

본문내용

EEE2020-01 Data Structures 2011 Fall term Jeung-Yoon Choi

Homework 4
The Librarian and Lexical trees
(assigned 11/3/11, due 11/10/11)

The Librarian would like to be able to store data related to some of her favorite books, as well as a couple of thousand other volumes. Here are some of the titles:

1. 20,000 Leagues Under the Sea by Jules Verne
2. War of the Worlds by H. G. Wells
3. Childhood’s End by Arthur C. Clarke
4. Foundation by Isaac Asimov
5. Ringworld by Larry Niven
6. Ringworld Engineers by Larry Niven
7. Fahrenheit 451 by Ray Bradbury
8. Stranger in a Strange Land by Robert Heinlein
9. Dune by Frank Herbert
10. The Hitchhiker’s Guide to the Galaxy by Douglas Adams
11. Ender’s Game by Orson Scott Card

She would like her friend, the Programmer (that’s you), to help her with her task. Please help her design a scheme to organize her holdings. You remember (somewhat vaguely) learning about trees in class, and decide you’d like to try them out. Here’s the plan:

(1) Design a method to transform book titles into a suitable data format.
(2) Using (1), construct a lexical tree from the 10 titles listed above.

Here is an example of a lexical tree.











Here, # represents the start of a title, and a denotes a valid entry in the book list. Only entries with a need to be considered. Also, at a given node, we only need to consider the children nodes to find possibilities for the following letter. That is, after finding an instance of “i”, we only need to search whether the following letter is “s” or “t.” If the following letter is neither, then we can conclude that no further searches are necessary.

In this assignment, you will construct a lexical tree for the 10 book titles in given above. Then, you will implement a traversal of the tree to list all the books in alphabetical order. What type of tree traversal will give you the desired result?

You may choose to implement a lexical tree that is different from the one shown here. For example, you may construct a tree starting from the end of a title. Again, what type of tree traversal will result in an alphabetical listing of the dictionary entries?

You may refer to and use code related to trees and from the textbook, from Chapters 4.

The report should be written in English, and should not exceed 3 pages (excluding code).

The report should include
(1) Brief explanation of the problem
(2) Your view as to how it ties in with what we covered in class
(3) Short explanation of your code
(4) Your code (hard copy)
(5) Your code (soft copy)

Grades will not be based on English fluency or writing style.
Grades will be based on correctness of implementation and sincerity of effort.

Good luck!

참고자료

· 없음