Introduction to Data Structure

Download Report

Transcript Introduction to Data Structure

Data Structure: Chapter 1
Min Chen
School of Computer Science and Engineering
Seoul National University



What is Data Structure
The Importance of Data Structure
Type of Data Structure


Data structures are ways in which data is
arranged in your computer’s memory (or
stored on disk).
Algorithms are the procedures a software
program uses to manipulate the data in these
structures.
Program = Data Structure + Algorithm


Almost every computer program, even a
simple one, uses data structures and
algorithms.
Example:
 Program: To print a address list
▪ Data Structure: Array
▪ Algorithm: Loop

Arrays
 Ordered Array


Stacks
Queues
 Priority Queues


Linked Lists
Tree
 Binary Tree


Hash Table
Heap

A container to be filled with elements

Each element can be accessed via unique remark
0
1
6 7
5
4
2 3
0
1
2
3
4
5
6
7
(0,0)
(4,2)
Fig.1 A 2-Dimensional Array


You can only eat the top apple first
FILO (First In Last Out)
Fig.2 An Apple Stack


The one came first can get the ticket first
FIFO(First In First Out)
Fig.3 A Queue for Tickets


A linear sequence, but the Storage of
elements is always not linear
Each record contains a reference (i.e., a link)
to the next record in the sequence
Link
Data
Fig.4 A Gold Chain


Start from the root, end at the leaves
No loop allowed
Fig.5 A Family Tree of Abram
Fig.6 An Unusual Family Tree