블로그 이미지
Leeway is... the freedom that someone has to take the action they want to or to change their plans.
maetel

Notice

Recent Post

Recent Comment

Recent Trackback

Archive

calendar

 « 2024.5  »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
  • total
  • today
  • yesterday

Category

'data structure'에 해당되는 글 3건

  1. 2009.06.11 Sahni's ch.16 Graphs
  2. 2009.04.11 Sahni Chapter 8. Stacks
  3. 2008.03.24 tree (data structure)

Sahni's ch.16 Graphs

2009. 6. 11. 20:36 @GSMC/서용덕: Multimedia Programming C++
Sahni
Data Structures, Algorithms and Applications in C++, 2nd ed.
: Chapter 16 Graphs

graph data structure

terminology:
vertex, edge, adjacent, incident, degree, cycle, path, connected component, and spanning tree

types:
undirected / directed / weighted

representation:
adjacent matrix / array adjacency lists /  linked adjacency lists

standard graph search methods:
breadth-first / depth-first search

algorithms:



16.1 Definitions

graph
: an ordered pair of finite sets of vertices (or nodes or points) and edges (or arcs or lines)

http://en.wikipedia.org/wiki/Graph_(data_structure)

loop
: self-edge

digraph
: directed graph

network
: weighted undirected graph or digraph


16.2 Applications and More Definitions

example 16.1: path problems

example 16.2: spanning trees

A graph is connected iff there is a path between every pair of vertices in the graph.

cycle
: simiple path with the same start and end vertex

tree
: a connected undirected graph that contains no cycles

spanning tree
: a subgraph of a graph that contains all the vertices of the graph and is a tree

example 16.3: interpreters

bipartite graphs


16.3 Properties

http://en.wikipedia.org/wiki/List_of_graph_theory_topics

in-degree
out-degree

complete digraph


16.4 The ADT graph
16.5 Representation of Unweighted Graphs

adjacency matrix
linked adjacency list
array adjacency list

http://en.wikipedia.org/wiki/Adjacency_matrix

http://en.wikipedia.org/wiki/Adjacency_list
16.6 Representation of Weighted Graphs


cost-adjacency-matrix


16.7 Class Implementations

 
16.8 Graph Search Methods

cp. level-order traversal of a binary tree
http://en.wikipedia.org/wiki/Binary_search_tree#Traversal

cp. pre-order traversal of a binary tree
 
 


 

'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

merge sort  (0) 2009.06.01
Hill & Kelly [Computer Graphics Using OpenGL]  (0) 2009.04.18
Sahni Chapter 8. Stacks  (0) 2009.04.11
Sartaj Sahni <Data Structures, Algorithms, and Applications in C++> 2nd ed.  (0) 2009.03.09
Deitel <C++ How to program> Sixth ed.  (0) 2009.03.07
posted by maetel

Sahni Chapter 8. Stacks

2009. 4. 11. 17:12 @GSMC/서용덕: Multimedia Programming C++

Sartaj Sahni
Data Structures, Algorithms, and Applications in C++

Chapter 8 Stacks


http://cplusplus.com/reference/stl/stack/

http://en.wikipedia.org/wiki/Stack_(data_structure)

http://www.sgi.com/tech/stl/stack.html

http://www.cppreference.com/wiki/stl/stack/start


stack = a linear list with a last-in-first-out (LIFO) structure

recursion stack

return address = location of the program instruction to execute once the invoked method completes


http://en.wikipedia.org/wiki/Abstract_data_type
An abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations.

In software engineering, an abstract type is a type in a nominative type system which is declared by the programmer, and which has the property that it contains members which are also members of some declared subtype. In many object oriented programming languages, abstract types are known as abstract base classes, interfaces, traits, mixins, flavors, or roles.


http://cplusplus.com/reference/std/exception/exception/




'@GSMC > 서용덕: Multimedia Programming C++' 카테고리의 다른 글

Sahni's ch.16 Graphs  (0) 2009.06.11
merge sort  (0) 2009.06.01
Hill & Kelly [Computer Graphics Using OpenGL]  (0) 2009.04.18
Sartaj Sahni <Data Structures, Algorithms, and Applications in C++> 2nd ed.  (0) 2009.03.09
Deitel <C++ How to program> Sixth ed.  (0) 2009.03.07
posted by maetel

tree (data structure)

2008. 3. 24. 15:09 @GSMC/정문열: Generative Art

data structure

ref.
http://www.webopedia.com/TERM/d/data_structure.html

In programming, the term data structure refers to a scheme for organizing related pieces of information. The basic types of data structures include:
  • files
    • lists
  • arrays
  • trees

    • Each of these basic structures has many variations and allows different operations to be performed on the data.


    ref.
    http://en.wikipedia.org/wiki/Data_structure

    ref.
    http://cplusplus.com/doc/tutorial/structures.html




    tree structure


    사용자 삽입 이미지

    ref.
    http://www.webopedia.com/TERM/T/tree_structure.html

    ref.
    Steve Oualline, Practical C Programmin, 292-293p

    root
    node
    leaves

    "Recursion is extremely useful with trees. Our rules for recursion are:
    1. The function must make things simpler. This rule is satisfied by trees, because as you descend the hierarchy there is less to search.
    2. There must be some endpoint. A tree offers two endpoints, either you find a match, or you reach a null node.




    ref.
    http://en.wikipedia.org/wiki/Tree_%28data_structure%29


    binary search tree
    http://en.wikipedia.org/wiki/Binary_search_tree



    Eric F Charlton : Tree Data Structures


    '@GSMC > 정문열: Generative Art' 카테고리의 다른 글

    [이선애] study 1  (0) 2008.03.28
    class 3/27  (0) 2008.03.27
    class 3/20  (0) 2008.03.20
    references for basic programming  (0) 2008.03.17
    Inversion Method  (0) 2008.03.08
    posted by maetel

    티스토리툴바