Defined

Sunday, March 1, 2009

Defined Data Structure
a. A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide.
b. Data structures represent implementations or interfaces: A data structure can be viewed as an interface between two functions or as an implementation of methods to access storage that is organized according to the associated data type.
c. A data structure is an actual implementation of a particular abstract data type. Example: The abstract data type Set has the operations EmptySet(S), Insert(x,S), Delete(x,S), Intersection(S1,S2), Union(S1,S2), MemberQ(x,S), EqualQ(S1,S2), SubsetQ(S1,S2).
d. In computer science, data structures are an important way of organizing information in a computer. Just like the diagrams above illustrate, there are many different data structures that programmers use to organize data in computers. Some data structures are similar to the tree diagram because they are good for representing relationships between data. Other structures are good for ordering data in a particular way like the list of employees. Each data structure has unique properties that make it well suited to give a certain view of the data.
e. A means of storing a collection of data. Computer science is in part the study of methods for effectively using a computer to solve problems, or in other words, determining exactly the problem to be solved. This process entails (1) gaining an understanding of the problem; (2) translating vague descriptions, goals, and contradictory requests, and often unstated desires, into a precisely formulated conceptual solution; and (3) implementing the solution with a computer program. This solution typically consists of two parts: algorithms and data structures.
f. Way in which data are stored for efficient search and retrieval. The simplest data structure is the one-dimensional (linear) array, in which stored elements are numbered with consecutive integers and contents are accessed by these numbers. Data items stored nonconsecutively in memory may be linked by pointers (memory addresses stored with items to indicate where the "next" item or items in the structure are located). Many algorithms have been developed for sorting data efficiently; these apply to structures residing in main memory and also to structures that constitute information systems and databases.
g. The physical layout of data. Data fields, memo fields, fixed length fields, variable length fields, records, word processing documents, spreadsheets, data files, database files and indexes are all examples of data structures.
h. In Geographic Information Systems, a representation of the data model as a diagram, list, or array, showing the human implementation orientation of the data.
A data structure is a group of data elements grouped together under one name. These data elements, known as members, can have different types and different lengths.
i. In programming, the term data structure refers to a scheme for organizing related pieces of information. The basic types of data structures include(1)files, (2) lists, (3) arrays, (4) records, (5)trees, (6) tables.Each of these basic structures has many variations and allows different operations to be performed on the data.


2. Data Structures(3):

a.Stack

In computer science, a stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine, and the Java language itself has a class called "Stack", which can be used by the programmer. The stack is ubiquitous.
A stack-based computer system is one that stores temporary information primarily in stacks, rather than hardware CPU registers (a register-based computer system).
Basic architecture of a stack

A typical stack is an area of computer memory with a fixed origin and a variable size. Initially the size of the stack is zero. A stack pointer, usually in the form of a hardware register, points to the most recently referenced location on the stack; when the stack has a size of zero, the stack pointer points to the origin of the stack.
The two operations applicable to all stacks are:
a push operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;
a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.
There are many variations on the basic principle of stack operations. Every stack has a fixed location in memory at which it begins. As data items are added to the stack, the stack pointer is displaced to indicate the current extent of the stack, which expands away from the origin (either up or down, depending on the specific implementation).
For example, a stack might start at a memory location of one thousand, and expand towards lower addresses, in which case new data items are stored at locations ranging below 1000, and the stack pointer is decremented each time a new item is added. When an item is removed from the stack, the stack pointer is incremented.
Stack pointers may point to the origin of a stack or to a limited range of addresses either above or below the origin (depending on the direction in which the stack grows); however, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at address 1000 and the stack grows downwards (towards addresses 999, 998, and so on), the stack pointer must never be incremented beyond 1000 (to 1001, 1002, etc.). If a pop operation on the stack causes the stack pointer to move past the origin of the stack, a stack underflow occurs. If a push operation causes the stack pointer to increment or decrement beyond the maximum extent of the stack, a stack overflow occurs

A typical stack, storing local data and call information for nested procedures. This stack grows downward from its origin. The stack pointer points to the current topmost datum on the stack. A push operation decrements the pointer and copies the data to the stack; a pop operation copies data from the stack and then increments the pointer. Each procedure called in the program stores procedure return information (in yellow) and local data (in other colors) by pushing them onto the stack. This type of stack implementation is extremely common, but it is vulnerable to buffer overflow attacks (see the text).


b.Scene graph

A scene graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.
The scene graph is a structure that arranges the logical and often (but not necessarily) spatial representation of a graphical scene. The definition of a scene graph is fuzzy because programmers who implement scene graphs in applications and in particular the games industry take the basic principles and adapt these to suit particular applications. This means there is no hard-and-fast rule as to what a scene graph should be.
A scene graph is a collection of nodes in a graph or tree structure. A node may have many children but often only a single parent, with the effect of a parent apparent to all its child nodes; an operation applied to a group automatically propagates its effect to all of its members. In many programs, associating a geometrical transformation matrix (see also transformation and matrix) at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes/objects into a compound object which can then be moved, transformed, selected, etc. as easily as a single object.
It also happens that in some scene graphs, a node can have a relation to any node including itself, or at least an extension that refers to another node (for instance Pixar's PhotoRealistic RenderMan because of its usage of Reyes rendering algorithm, or Adobe Systems's Acrobat 3D for advanced interactive manipulation).
Scene graph implementation
The simplest form of scene graph uses an array or linked list data structure, and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see which shape intersects the mouse pointer (e.g., in a GUI-based applications) are also done via linear searches. For small scene graphs, this tends to suffice.
Larger scene graphs cause linear operations to become noticeably slow and thus more complex underlying data structures are used, the most popular being a tree. This is the most common form of scene graph. In these scene graphs the composite design pattern is often employed to create the hierarchical representation of group-nodes and leaf-nodes.
Group Nodes - Can have any number of child nodes attached to it. Group nodes include transformations and switch nodes.
Leaf Nodes - Are nodes that are actually rendered or see the effect of an operation. These include objects, sprites, sounds, lights and anything that could be considered 'rendered' in some abstract sense.


c. Hash Table

In computer science, a hash table, or a hash map, is a data structure that associates keys with values.
The primary operation that hash functions support efficiently is a lookup: given a key (e.g., a person's name), find the corresponding value (e.g., that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be.
In most cases the hash function is deliberately chosen to have pseudo-random properties, so that small changes of key gives a large and apparently random effect (although of course reproducible effect) on the hash returned. Because of this random effect in some cases the calculated index can be the same for two different keys (a "collision"); different hash table designs handle this issue in different ways.
Hash tables support the efficient lookup, insertion and deletion of elements in constant time on average (O(1)) that does not vary with the number of elements stored in the table; although may vary somewhat depending on how full the table is.
Basic operation
A hash table works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be. The number is normally converted into the index by taking a modulo operation, or sometimes bit masking is used where the array size is a power of two. The optimal hash function for any given use of a hash table can vary widely, however, depending on the nature of the key.
Typical operations on a hash table include insertion, deletion and lookup (although some hash tables are precalculated so that no insertions or deletions, only lookups are done on a live system). These operations are all performed in amortized constant time, which makes maintaining and accessing a huge hash table very efficient.
It is also possible to create a hash table statically where, for example, there is a fairly limited fixed set of input values - such as the values representable by a single byte (or possibly two bytes ) from which an index can be constructed directly (see section below on creating hash tables). The hash table can also be used simultaneously for tests of validity on the values that are disallowed

0 thoughtfulness:

Related Posts Plugin for WordPress, Blogger...