Transcript Chao-Hsien Lee (李昭賢)

PRACTICAL DATA
STRUCTURES USING
C/C++
Chapter 1
Introduction
Email: [email protected]
Tel: 04-7232105 ext.3242
彰師大 數學系
蔡政容 (Cheng-Jung
Tsai)
textbook
2


Practical Data Structure Using C/C++
Fundamentals of Data Structures in C++, E.
Horowitz, S. Sahni and D. Mehta, 2nd Edition,
Silicon Press.
About C and C++ textbook
3

C

The C Programming Language, 2/e, Brian W. Kernighan and Dennis
M. Ritchie;(K&R), Prentice-Hall (C Bible)


C PRIMER PLUS, Fifth Edition, Stephen Prata, 2005.


C Primer Plus 5/e中文精華版,蔡明志, 碁峰, 2005
C HOW TO PROGRAM 5/E, DEITEL, Prentice Hall, 2007


C 語言程式設計, 蔡文能 譯
C程式設計藝術(第五版), 陳大任、陳心瑋, 全華科技, 2008
C++
 The C++ Programming Language (3rd), Bjarne Stroustrup, Addison
Wesley, 1997 (C++ Bible)


C++ 程式語言經典增訂版, 葉秉哲, 儒林
C++ Primer Plus (5th Edition), Stephen Prata


C++ Primer 4/e中文版C++ Primer 4/e中文版, 侯捷 譯, 碁峰, 2008.
C++ Primer Plus 5/e中文精華版, 蔡明志, 碁峰, 2005
Outline
4








Introduction
1.1 What is a data structure
1.2 Static and dynamic data structures
1.3 Why do we need data structures
1.4 Typical data structures
1.5 Operations on data structures
1.6 Choosing a data structure
1.7 A note about C++
Introduction
5



Some programs will use a lot of memory, while
others will need to access data stored on disk
A data structure is used to access the memory
and disk in a way that saves or retrieves
information efficiently
Data structure
 Bulit-in
to a programming language
 Variable, array
 User specified
 Created by the programmer to meet the needs and
requirements of his program
1.1 What is a data structure
6

A predefined arrangement of one or more pieces of
data
 Three
characters c+a+t are grouped
 Array:
 Store
the distances between four towns
 see Fig 1.1 in page 3
 Can
be one or more items of the same type or a
mixture of many different types

char, int, float in C/C++ can be thought as the
simplest data structure
1.2 Static and dynamic data structures
7

Static data structures



Dynamic data structures





Its allocated memory size is fixed
float, integer, array
Start out empty
Grow until they occupy as much space as they need to
See the code in page 5
Common to use a pointer when dealing with a dynamic data
structure
If you know in advance the number of pieces of data used
by the application, static allocation is acceptable.
1.3 Why do we need data structures
8

Simplify our programming chores
1.4 Typical data structures
9

Common data structure: See Fig 1.2 in page 7
 Strings and array
 User defined
 static
 Linked-list
 dynamic
 link static variable together (nodes)
 Stacks (LIFO) and queues (FIFO)
 Trees and graphs
 Search problem
 Hash table
 Hash function
 Collision: bad design
 Fast access time
 Files, Heaps, Sets, Lookup Tables
1.5 Operations on data structures
10




See pages 9 to 11 and Table 1.1 in page 11
Strings
Array
User defined


Linked-list



Structure name
pointer
Stacks (LIFO)


Structure name. variable name
push(), pop(), empty()
Queues (FIFO)

en_queue(), de_queue(), empty()
Operations on data structures (con.)
11

Trees
Child node, parent node
 Level
 Post-order
 Depth-first search vs. breadth-first search


Graphs
A tree but no level
 A node in a graph can connect to any other node in the
graph
 Require different search algorithms than trees do


Hash table
1.6 Choosing a data structure
12


A mismatched data structure will actually lower the
performance of a program
Consider the following questions to decide
 Is
memory being used efficiently
 Static
 What
 If
or dynamic
is the search time
your program frequently search some elements among a
lot ones, tree is much more efficiently than array
 1024 times in a array vs about 10 times in a tree
Choosing a data structure (con.)
13

Consider the following questions to decide
 How
 Of
 Can
easy is it to use the structure
course, a array or a queue are easier than a tree
the access method be tested
 A bad
hash function may be more inefficient than an array
 Using testing data to test your hash function
 What
are the tradeoffs
Time
 Memory usage
 Change your source code

1.7 A note about C++
14

See pages 13
Class
 Public vs private
 Instantiation
