Transcript 資料結構: Data Structure

資料型態(Data Type)-程式語言的變數所能表
示的資料種類
*基本型態(Primitive Type):
integer, real, boolean, character(byte)
*結構化型態(Structured Type):
string, array, record/structure
int i, j;
char c;
float r;
int i1[10], j1[10];
float r1[10];
i1[0]=20;
i2[1]=90;
…
串列(List)
*有序串列可以是空的()或寫成(a1, a2, ..., an)
串列的表示法(representation of lists)
*順序對應(Sequential mapping)-array
*鏈結串列(Linked list)-pointer
堆疊與佇列(Stacks & Queues)
*堆疊是一個有序串列，所有的insertion和
deletion動作均在頂端(top)進行
*具有後進先出(LIFO-last in first out)特性
*佇列是一個有序串列，所有的insertion和
deletion是發生在串列的不同端，加入的一端
稱為尾端(rear)，刪除的一端稱為前端(front)
*具有先進先出(FIFO-first in first out)特性
Example of a stack and a queue
E
D
C
B
A
stack
top
A B C D E
front
rear
queue
Representation of a stack:
*a one-dimensional array: stack[0:n-1]
*a variable: top
*linked list
*node: data, link
*a variable: top
top
D
E
data link
C
B
A 0
Representation of a queue:
*a one-dimensional array: q[0:n-1]
*two variables: front & rear
*linked list
*node: data, link
* two variables: front & rear
data link
A
front
B
C
D 0
rear
Circular Queue
[4]
‧
‧
J4
[3]
[4]
‧
J3
[2] J2
[n-1]
front = 0 ; rear = 4
‧
[3]
[n-4]
[n-3]
[2]
J1 [n-3]
J2
J4 J3
[n-2]
[n-1]
[0]
[n-2]
[0]
‧
[n-4]
J1
[1]
‧
[1]
front = n-4 ; rear = 0
Circular queue of capacity n-1 containing four elements J1,
J2, J3, and J4
Trees
*A tree is a finite set of one or more nodes
*樹是一個或多個節點(node)所組成的有限集合
*有一個特殊的節點稱為樹根(root)
*每一個節點底下有零個或一個以上的子樹
(subtree): T1, T2, …, Tn n0
*節點(node)
*分支(branch, edge)
*樹根(root)
*子點(children)
*父點(parent)
*終端節點(leaf, terminal nodes)
Trees
*非終端節點(nonterminal nodes)
*兄弟(siblings)
*祖先(ancestor of a node): all the nodes along
the path from the root to that node
*分支度(degree): the number of subtrees of a
node
*樹的分支度(degree of a tree): the maximum
degree of the nodes in the tree
*階度(level): initially let the root be at level one
a Sample Tree
level
1
A
B
F
E
K
C
L
G
2
D
H
M
I
J
3
4
Trees
*高度(height, depth): the maximum level of any
node in the tree
*A forest is a set of n0 disjoint trees
*若一樹有n個nodes，則必有且唯有n-1個
edges
*A graph without a cycle
Representation of a Tree:
*linked list
*node: data, link, tag
*when tag=1, data field contains a pointer to
a list rather than a data item
A
0
B
E
F0
C
K
L0
G0
D
I
H
J0
M0
The tag field of a node is one if it has a down-pointing arrow;
otherwise it is zero.
Binary Trees :
*Any node can have at most two children
*二元樹上每個節點的degree2
*左子樹(left subtree) & 右子樹(right subtree)
*二元樹可以是空集合(empty)
*The maximum number of nodes on leve i of a
binary tree is 2i-1
*The maximum number of nodes in a binary
tree of depth k is 2k-1, k>0.
*For any non-empty binary tree, if n0 is the number of
terminal nodes and n2 is the number of nodes of
degree 2, then n0=n2+1.
二元樹的特例 :
*歪斜樹(skewed binary tree)
left-skewed binary tree, right-skewed binary tree
*全滿二元樹(full binary tree)
The binary tree of depth k that has exactly 2k-1 nodes
*完整二元樹(complete binary tree)
A binary tree with n nodes and depth k is complete iff
its nodes corresponds to the nodes that are
numbered one to n in the full binary tree of depth k.
In a complete tree, leaf nodes occur on at most two
adjacent levels.
Representation of a Binary Tree:
*a one-dimensional array: tree[1:n]
the node numbered i is stored in tree[i]
1. parent(i) is at i/2 if i1.
If i=1, i is the root and has no parent.
2. lchild(i) is at 2i if 2in.
If 2i>n, i has no left child.
3. rchild(i) is at 2i+1 if 2i+1n.
If 2i+1>n, i has no right child.
*優點:處理簡單，若為full binary tree，則相當節省
空間。
*缺點:若為skewed binary tree，則相當浪費空間。
不容易處理Insertion or deletion
Binary Trees
level
A
A
B
B
D
C
H
D
E
(a)
1
C
E
F
I
2
G 3
4
(b)
5
Sequential Representation
Tree
A B - C -
Tree
A B C D E F G H I
(1)
(2)
(3)
(4)
(5)
-
(6)
- D -
(7)
(8)
(9)
…
E
…
(16)
Sequential representation of the binary trees
Representation of a Binary Tree:
*linked list
node: lchild, data, rchild
a variable: tree
*優點:插入與刪除一個節點相當容易。
*缺點:缺點:很難找到該節點的父點。
Linked Representations
tree
tree
A 0
A
B 0
B
C 0
D 0
0 E 0
(a)
D
0 H 0
C
0 E 0 0 F 0
0 G 0
0 I 0
(b)
Linked representation of the binary trees
Binary Search Trees
*A binary search tree is a binary tree.
1. All the keys are distinct.
2. The keys in the left subtree are smaller than
the key in the root.
3. The keys in the right subtree are larger than
the key in the root.
4. The left and right subtrees are also binary
search trees.
*Search by key value
*Node: lchild, rchild and data
Binary trees
20
15
12
30
25
10
(a)
5
22
60
40
2
70
65
(b)
(c)
80
Binary Search Trees
*Search by rank(find the kth-smallest element)
*Node: lchild, rchild, data and leftsize
*Leftsize: one plus the number of elements in
the left subtree of the node
Representation of a Priority Queue:
*Any data structure that supports the operations
of search max, insert, and delete max is
called a priority queue.
Priority Queues
*unordered linear list
insert time: (1)
delete time: (n) n-element unordered list
*ordered linear list
insert time: O(n)
delete time: (1) n-element ordered list
*heap
insert time: O(log n)
delete time: O(log n)
MAX Heap
*a complete binary tree
*the value at each node is at least as large as
the value at its children(任何一父點的值必大於
*The largest number is in root node
*A max heap can be implemented using an
array a[].
*Insertion into a heap
*Deletion from a heap
Insertion into a Heap
80
45
40
80
70
35 50
45
90
40
90
35 50
70
90
45
40
80
35 50
70
Action of Inset inserting 90 into an existing heap
Heap sort
1)建立一binary tree
2)將binary tree轉成Heap (Heapify)
3)Output: Removing the largest number and
restoring the heap (Adjust)
100,119,118,171,112,151,32,40,80,35,90,45,50,70
Forming a Heap
40
40
80
80
40
(a)
40
(b)
80
40
80
(c)
90
35
90
80
90
35
35
80
40
40
35
45
(d)
(e)
90
80
40
90
35
45
80
50
40
(f)
90
50
45
35
80
40
90
50
45
35
80
70
40
70
45
35
(g)
Forming a heap from the set{40,80,35,90,45,50,70}
50
Heapify
100
119
171
118
112 151
119
132
171
151
112 118
(a)
(b)
100
171
171
119
100
151
112 118
(c)
119
132
100
132
151
112 118
132
(d)
Action of Heapify(a,7) on the data (100, 119, 118, 171, 112,
151, and 132)
Sets and Disjoint Set Union
Set:
*The sets are assumed to be pairwise disjoint.
*Each set is represented as a tree.
*Link the nodes from the children to the parent
Ex: S1={1, 7, 8, 9}, S2={2, 5, 10}, S3={3, 4, 6}
Set Operations:
*Disjoint set union
Make one of the trees a subtree of the other
*Find(i)
Representations of Union
1
7
5
8
10
2
9
S1
S2
1
7
8
5
1
5
9
2
S1∪S2
10
7
or
2
8
9
S1∪S2
Possible representations of S1∪S2
10
Weighting rule for Union(i, j):
If the number of nodes in the tree with root i is
less than the number in the tree with root j, then
make j the parent of i; otherwise make i the
parent of j.
*Maintain a count in the p field of the roots as a
negative number.
*Count field: the number of nodes in that tree.
Lemma 2.3
Assume that we start with a forest of trees, each
having one node. Let T be a tree with m nodes
created as a result of a sequence of unions
each performed using WeightedUnion. The
height of T is no greater than log m+1.
Collapsing rule:
If j is a node on the path from i to its root and
p[i]root[i], then set p[j] to root[i].
Graph
A graph G(V,E) is a structure which consists of
1. a finite nonempty set V(G) of vertices
(points, nodes)
2. a (possible empty) set E(G) of edges (lines)
V(G): vertex set of G
E(G): edge set of G
有序樹(ordered tree)
Sample Graphs
1
1
2
1
3
4
(a) G1
2
4
2
3
5
6
7
3
(b) G2
Three sample graphs
(c) G3
Undirected Graph(無方向圖形): (u,v)=(v,u)
*假如(u,v)E(G)，則u和v是adjacent vertices，
且(u,v)是incident on u和v
*Degree of a vertex: the number of edges
incident to that vertex
n
G has n vertices and e edges, e  ( d i ) / 2
i 1
*A subgraph of G is a graph G'(V',E')，V' V 且
E' E
*Path:假如(u,i1), (i1,i2), ..., (ik,v)E，則u與v有一條
Path(路徑)存在。
*Path Length: the number of edges on the path
*Simple path:路徑上除了起點和終點可能相同外，其它
的頂點都是不同的
Undirected Graph(無方向圖形): (u,v)=(v,u)
*Cycle: a simple path且此路徑上的起點和終點相同
且(u,v)是incident on u和v
*In G, two vertices u and v are said to be connected
iff there is a path in G from u to v.
*Connected graph:圖上每個頂點都有路徑通到其它
頂點
*Connected component: a maximal connected subgraph
(圖上相連在一起的最大子圖)
*Complete graph: if |V|=n then |E|=n(n-1)/2
*A tree is a connected acyclic(no cycles) graph.
*Self-edge(self-loop): an edge from a vertex back to itself
*Multigraph: have multiple occurrences of the same edge
Connected Components
H1
H2
1
3
5
6
2
7
8
4
G4
A graph with two connected components
Subgraphs
1
1
2
1
3
2
2
3
3
4
4
(i)
(ii)
(iii)
(iv)
(a) Some of the subgraphs of G1
1
(i)
1
1
1
2
2
2
3
3
3
(ii)
(iii)
(b) Some of the subgraphs of G3
Some subgraphs
(iv)
Graphlike Structures
1
1
2
3
(a) Graph with a self edge
2
4
3
(b) Multigraph
Examples of graphlike structures
Undirected Graph(無方向圖形): (u,v)=(v,u)
*Eulerian walk(cycle):從任何一個頂點開始，
經過每個邊 一次，再回到原出發點
(每個頂點的degree必須是偶數)
*Eulerian chain:從任一頂點開始，經過每個邊
一次，不一定要回到原點
(只有兩個頂點的degree是奇數，其它必須是
偶數)
Directed Graph(Digraph,有方向圖形): <u,v><v,u>
*假如<u,v>E(G)，則稱u is the tail and v the
head of the edge
u是adjacent to v，而v是adjacent from v
<u,v>是incident to u和v
*in-degree of v: the number of edges for which v is
the head
*out-degree of v: the number of edges for which v is
the tail.
*Subgraph:G'=(V', E')， V' V 且 E' E
Directed Graph(Digraph,有方向圖形): <u,v><v,u>
*Directed Path:假如<u,i1>, <i1,i2>, ..., <ik,v>E，
則u與v有一條Path(路徑)存在。
*Path Length:路徑上所包含的有向邊的數目
*Simple directed path:路徑上除了起點和終點可能
相同外，其它的頂點都是不同的
*Directed Cycle(Circuit): A simple directed path
且路徑上的起點和終點相同
Directed Graph(Digraph,有方向圖形):
<u,v><v,u>
*Strongly connected graph: for every pair of
distinct vertices u and v in V(G), there is a
directed path from u to v and also from v to u.
*Strongly connected component: a maximal
subgraph that is strongly connected
(有向圖上緊密相連在一起的最大有向子圖)
*Complete digraph: if |V|=n then |E|=n(n-1)
Strongly Connected Components
1
1
2
2
3
3
(a)
(b)
A graph and its strongly connected components
Graph Representations:
*相鄰矩陣(adjacency matrix)
*相鄰串列(adjacency list)
*相鄰多元串列(adjacency multilist)
Adjacency Matrix
G(V, E): a graph with n vertices
A two-dimensional n*n array: a[1:n, 1:n]
*a[i, j]=1 iff (i, j)E(G)
*Space: O(n2)
*The adjacency matrix for an undirected graph
is symmetric.
Use the upper or lower triangle of the matrix
*For an undirected
graph the degree of i is its
n
row sum.  a[i, j ]
j 1
*For a directed graph the row sum is the out-degree,
and the column sum is the in-degree.
Adjacency Matrices
1
1
5
1
2
3
2
3
2
6
7
4
4
8
3
1 2 3 4 5 6 7 8
1 2 3 4
1 0
2 1
3 1

4 1
1
0
1
1
1
1
0
1
(a) G1
1
1
1

0
1 2 3
1 0 1 0 
2 1 0 1
3 0 0 0
(b) G3
1 0
2 1
3 1

4 0
5 0

6 0
7 0

8 0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
(c) G4
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0

0
0

0
1

0
Adjacency List
G(V, E): a graph with n vertices and e edges
*the n rows of the adjacency matrix are represented
as n linked lists
*There is one list for each vertex in G
node: vertex, link
*Each list has a head node
*Space: n head nodes and 2e nodes for an undirected graph
n head nodes and e nodes for a directed graph
Use the upper or lower triangle of the matrix
*For an undirected graph the degree of i is to count the
number of nodes in its adjacency list.
*For a directed graph the out-degree of i is to count the
number of nodes in its adjacency list.
head nodes vertex link
1
2
3
4
[1]
4
2
3
0
[2]
3
4
1
0
[3]
2
4
1
0
[4]
1
2
3
0
(a) G1
1
2
head nodes
vertex link
[1]
2
[2]
3
[3]
0
3
(b) G3
0
1
0
head nodes vertex link
1
3
3
2
0
[2]
4
1
0
[3]
1
4
0
[4]
2
3
0
[5]
6
[6]
7
5
0
[7]
6
8
0
[8]
7
5
2
4
[1]
6
7
8
(c) G4
0
0
Adjacency List
Inverse adjacency lists – to count the indegree easily
*One list for each vertex
*Each list contains a node for each vertex
adjacent to the vertex it represents.
Inverse Adjacency Lists
1
2
3
[1]
2
0
[2]
1
0
[3]
2
0
Inverse adjacency lists for G3
Array node[1: n+2e+1] to represent a graph
G(V, E) with n vertices and e edges eliminate the use of pointers
*The node[i] gives the starting point of the list
for vertex i, 1in
*node[n+1]:=n+2e+2
Sequential representation
1
3
5
2
4
6
7
8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 12 14 16 18 19 21 23 24 3 2 4 1 1 4 2 3 6 7 5 6 8 7
Sequential representation of graph G4：Array node[1：n + 2e + 1]
Orthogonal list
Each node has four fields and represents one
edge.
Node structure:
tail
head column link for head row link for tail
Orthogonal list representation
Head nodes
(shown twice)
1
1
2
2
3
3
1
2
3
1 2 0 0
2 1 0
0
Orthogonal list representation for G3
2 3 0 0
Adjacency Multilist
*One list for each vertex
*node can be shared among several lists
*for each edge there is exactly one node, but
the node is in two lists
*node strucure
m vertex1 vertext2 list1 list2
Adjacency Multilist
head nodes
1
2
[1]
N1
1
2
N2 N4
edge (1,2)
[2]
N2
1
3
N3 N4
edge (1,3)
[3]
N3
1
4
[4]
N4
2
3
N5
2
4
0
N6
edge (2,4)
N6
3
4
0
0
edge (3,4)
0
N5
edge (1,4)
N5 N6
edge (2,3)
3
4
The lists are
vertex 1:
vertex 2:
vertex 3:
vertex 4:
N1N2N3
N1N4N5
N2N4N6
N3N5N6
Adjacency multilists for G1