Transcript Data Organization

Data is organized
so that it can be found efficiently
Data can be indexed
• identified by number
• stored contiguously
Data
Index
Other uses for indexing?
• merchandise with SQU numbers
• U.S. Social Security Numbers
• scenes on a video DVD
0
1
2
3
4
5
6
7
mozzarella
pepperoni
sausage
onion
anchovy
green pepper
olive
red pepper
ADVANTAGES of indexing
0
• direct access -- fast
1
• efficient use of available space 2
3
4
5
6
7
DISADVANTAGES of indexing
• retrieving data requires an index
• fixed overall size
• inserting/removing in the middle is difficult
Computer Memory is indexed.
Memory
words
Memory
Addresses
0
1
2
3
4
5
Disks, CDs and DVDs are indexed.
7
0
8
6
91
5
2
4
33
Blocks
chunks
data + link
Data can be linked
• each chunk of data
contains one or more
links to other chunks
• generally, there is a
separate link to the
“first” chunk of data
(an anchor)
anchor
Other uses for linking?
• references in a research paper
• Facebook friends
• hyperlinks in Web pages
olive  green pepper  mozzarella  onion 
anchovy  pepperoni  red pepper  sausage
mozzarella
sausage
pepperoni
red pepper
onion
anchovy
olive
green pepper
Q: What is a link?
A: An address
chunks
data + link
Address
11 mozzarella
16
This data structure is
a linked list, because
- each data chunk
contains one link to
the next chunk.
Anchor
19
12 sausage
-1
13
14 pepperoni
15
15 red pepper
12
16 onion
17
17 anchovy
14
18
19 olive
20
20 green pepper
11
A tree data structure consists of data chunks
such that...
• Each chunk links to zero or more other chunks.
• One chunk has no links to it, all others have one link
to them.
• The tree has one more chunk than links.
a tree
not a tree
not a tree
Another Use for Trees
Computer File Systems
RileyStuff
Photos
myDog.jpg
exam1.doc
Classes
cs101
cs220
exam2.doc
Documents
cs555
vita.doc
Any data structure that links data chunks is a
graph.
Applications of graphs?
• highway maps
• hyperlinks in Web pages
• Consider storing the following tree in memory
– We have 30 memory slots
• Each slot can hold either a 'letter' or a 'number'
– Each 'node' is formatted as
• node value
• number of children N
• N links
Address
Value
Address
Value
100
A
118
H
101
2
119
0
102
104
120
I
103
124
121
0
104
B
122
J
105
3
123
0
106
109
124
C
107
112
125
1
108
114
126
127
109
D
127
G
110
1
128
0
111
118
129
-
112
E
130
-
113
0
131
-
114
F
132
-
115
2
133
-
116
120
134
-
117
122
135
-
Address
Value
Address
Value
100
A
118
J
101
1
119
0
102
103
120
G
103
B
121
0
104
3
122
D
105
108
123
0
106
120
124
E
107
122
125
1
108
C
126
127
109
2
127
H
110
112
128
0
111
120
129
112
F
130
113
2
131
114
116
132
115
118
133
116
I
134
117
0
135
A
B
C
E
F
D
Could we add an arc from F to F?
[0]
[1]
A
[2]
[3]
B
C
[4]
E
F
D
[5]
A
B
C
D
E
F
B
C
[0]
[1]
A
[2]
[3]
B
[4]
C
E
F
D
[5]
A
B
C
D
E
F
011000
101000
000000
000000
011100
000000