|
Data
Structure in C
"Data structure" is a generic term that refers to any pattern of data in a computer program.
A data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow a more efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure.In
C perhaps discussing basic data structures
like structure,union,etc.,Let's look upon
complex structures.
Linked List
Linked lists are a way to store data with structures so that the programmer can automatically create a new place to store data whenever necessary. Specifically, the programmer writes a struct definition that contains variables holding information about something and that has a pointer to a struct of its same type (it has to be a pointer--otherwise, every time an element was created, it would create a new element, infinitely). Each of these individual structs or classes in the list is commonly known as a node or element of the list. One way to visualize a linked list is as though it were a train.
Singly-linked list
The simplest kind of linked list is a
singly-linked list, which has one link per
node. This link points to the next node in
the list, or to a null value or empty list
if it is the final node.
Doubly-linked list
A more sophisticated kind of linked list is
a doubly-linked list or two-way linked list.
Each node has two links: one points to the
previous node, or points to a null value or
empty list if it is the first node; and one
points to the next, or points to a null
value or empty list if it is the final node.
BinaryTree
A binary tree is a rooted tree where each
node contains at most two children. Each
child can be identified as either a left or
right child. As shown in Figure,a binary
tree can be implemented where each node has
left and right pointer fields, an (optional)
parent pointer, and a data field.
The binary tree is a fundamental data
structure used in computer science. The
binary tree is a useful data structure for
rapidly storing sorted data and rapidly
retrieving stored data. A binary tree is
composed of parent nodes, or leaves, each of
which stores data and also links to up to
two other child nodes (leaves) which can be
visualized spatially as below the first node
with one placed to the left and with one
placed to the right. It is the relationship
between the leaves linked to and the linking
leaf, also known as the parent node, which
makes the binary tree such an efficient data
structure. It is the leaf on the left which
has a lesser key value (ie, the value used
to search for a leaf in the tree), and it is
the leaf on the right which has an equal or
greater key value. As a result, the leaves
on the farthest left of the tree have the
lowest values, whereas the leaves on the
right of the tree have the greatest values.
More importantly, as each leaf connects to
two other leaves, it is the beginning of a
new, smaller, binary tree. Due to this
nature, it is possible to easily access and
insert data in a binary tree using search
and insert functions recursively called on
successive leaves.
C++
C++ combines the best of two worlds: it is
object oriented and it is a version of C,
the single most popular programming language
for microcomputers. Originally developed by
Bjarne Stroustrup and others at AT&T
Bell Labs during the mid 1980s, C++ evolved
further in response to the real and
perceived needs of its users.
Why C++?
C++ has certain characteristics over other
programming languages. The most remarkable
ones are:
Object-oriented
programming
Classes and
Information Hiding
A goal of modern software design is thus to
keep a product's public interface as
constant as possible so that users remain
fluent in the product even as its private
implementation improves or otherwise
changes.
In an object-oriented language, a class is a
module that supports information hiding.
In a C++ class, we can use the keywords
public and private to control access to the
class's properties and operations. We can
use the keyword public to expose the class's
interface and the keyword private to hide
its implementation
Encapsulation
In object-oriented programming, the modules
are classes. Data and the procedures to
manipulate the data can be encapsulated
or contained within a class. Imagine a
String class that can be used to create
strings, con- catenate them, change the
characters they contain, check whether a
given character occurs in a String, and so
on. The String class would have data
members—variables—to rep- resent the
characters in a String and, perhaps, such
other information as a String's length. Such
variables are encapsulated within the class
in the sense that every String object has
the variables specified in the String class.
A String class also would have function
members to manipulate its data members.
Function members are commonly called
methods. For example, the String class
presumably would have a method to create a
new String object, another method to clone
one String object from another, another
method to check whether a String object
contains a character, and so on. Methods,
like data members, also are encap- sulated
within the class. A method is thus a
function encapsulated in a class. A
top-level function, such as a C++ program's
main, is not encapsulated in any class.
Inheritance
Classes can occur in inheritance
hierarchies, which consist of parent/child
relationships among classes. Inheritance
supports a form of code reuse, which we
explain through an example. Suppose that we
build a Window class to represent windows
that appear on a computer's screen. The
Window class has data members to represent a
window's width and height, its x and y
screen coordinates, its background and
foreground colors, its border width, its
style (e.g., framed), and so forth. We
encapsulate appropriate methods to provide
functionality for creating and destroying
windows, moving them, resizing and reshaping
them, changing their properties (e.g.,
background color), and so on. Once the
Window class is built, we decide to refine
or specialize it by building a MenuWindow
subclass that inherits all the Window data
members and methods but then adds some of
its own. For example, the MenuWindow
subclass has data members and methods to
support lists of menu items, user choices of
menu items, and so on. Other subclasses are
possible.
Inheritance supports code reuse in that a
child class has all of the functionality of
its parents. How to design and use
inheritance hierarchies are central issues
in object-oriented design and programming
Polymorphism
The term polymorphism is derived from Greek
and means having many forms. In an object-
oriented language, there can be many methods
with the same signature.
Inheritance between classes
A key feature of C++ classes is inheritance.
Inheritance allows to create classes which
are derived from other classes, so that they
automatically include some of its
"parent's" members, plus its own.
For example, we are going to suppose that we
want to declare a series of classes that
describe polygons like our CRectangle, or
like CTriangle. They have certain common
properties, such as both can be described by
means of only two sides: height and
base.
This could be represented in the world of
classes with a class CPolygon from which we
would derive the two other ones: CRectangle
and CTriangle.
The class CPolygon would contain members
that are common for both types of polygon.
In our case: width and height. And
CRectangle and CTriangle would be its
derived classes, with specific features that
are different from one type of polygon to
the other.
Classes that are derived from others inherit
all the accessible members of the base
class. That means that if a base class
includes a member A and we derive it to
another class with another member called B,
the derived class will contain both members
A and B.
c++
and java more
|
