Data Structure to Implement Text Editor?
Recently I was asked this question in an interview. The exact question was
What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc ?
At that point of time, I tried to convince him using many different approaches like stack, Doubly Linked list and all.
From that point of time,This question is buzzing me.
It looks like they'd like to know if you were aware of the flyweight pattern and how to use it correctly.
A text editor is a common example while describing that pattern.
Maybe your interviewer was a lover of the GOF book. :-)
In addition to the previous answers, I would like to add that in order to get to the data structures, you need first to know your design - otherwise the options will be too broad selected.
As example let's assume that you'll need an editing functionality. Here the State and Memento design patterns will be a good fit. Very suitable structure will be the Cord, since it's
composed of smaller strings that is used for efficiently storing and manipulating a very long string.
In our case the text editing program
may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.
An open-ended question like this is designed more to see if you can think cogently about making a design that hangs together well, rather than having one, specific answer.
One specialized answer to the question is to use DOM/XML ("Document Object Model"). Markup "languages" are intended to solve this exact problem. You could store the data for the editor in a DOM. One of the advantages of using a DOM is that there are libraries like Xerces that have extensive support for building and managing DOMs, so a lot of your work is done for you. It is possible the interviewer intended this to be the ideal answer.
A more general answer is that any nested sequence structure can be used. The text can be seen as a sequence of strings. Each elment of the sequence, like rows in a database, can have multiple attributes (font type, font size, italic, bold, strikethrough, etc). Nesting (hierarchy) is useful because the document might have structure such as chapters, sections, paragraphs. For example, if a paragraph has its own styling (indent), then it may need to have its own level. So you have something like this:
Document
Chapter
Paragraph
Text
To implement this, you would use a tree and each node of the tree would have multiple attributes. You would require different kinds of nodes (Chapter nodes, Paragraph nodes, etc). So, for example, a document like a paper would have multiple Section nodes and a Notes node inside a Document node, but a book-like document might have Chapter nodes inside a document node. The advantage of this approach is that it is more specific and hand-tailored to the problem than using a DOM, which is a more flexible approach.
You could also combine the two approaches, using a DOM as your base structure and the hierarchical structure described above as your DOM implementation.
(Note: in the future you should post questions like this to https://softwareengineering.stackexchange.com/)
链接地址: http://www.djcxy.com/p/87574.html上一篇: Git for Windows不知道％USERPROFILE％
下一篇: 数据结构来实现文本编辑器？