资料型态(Data.ppt

1、資料型態(Data Type)-程式語言的變數所能表 示的資料種類 *基本型態(Primitive Type): integer, real, boolean, character(byte) *結構化型態(Structured Type): string, array, record/structure,int i, j; char c; float r; int i110, j110; float r110; i10=20; i21=90; ,串列(List) *有序串列可以是空的()或寫成(a1, a2, ., an) 串列的表示法(representation of lists) *順

2、序對應(Sequential mapping)-array *鏈結串列(Linked list)-pointer,堆疊與佇列(Stacks 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

3、 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 pirooti, then set pj to rooti.,Graph A graph G(V,E) is a structure which consists o

4、f 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,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

5、that vertex G has n vertices and e edges, *A subgraph of G is a graph G(V,E)，VV 且 EE *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且此路徑上的起點和終點相同

6、且(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)

7、 graph. *Self-edge(self-loop): an edge from a vertex back to itself *Multigraph: have multiple occurrences of the same edge,Undirected Graph(無方向圖形): (u,v)=(v,u) *Eulerian walk(cycle):從任何一個頂點開始， 經過每個邊 一次，再回到原出發點 (每個頂點的degree必須是偶數) *Eulerian chain:從任一頂點開始，經過每個邊 一次，不一定要回到原點 (只有兩個頂點的degree是奇數，其它必須是 偶數),

8、Directed Graph(Digraph,有方向圖形): *假如E(G)，則稱u is the tail and v the head of the edge u是adjacent to v，而v是adjacent from 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 Gra

9、ph(Digraph,有方向圖形): *Directed Path:假如, , ., E， 則u與v有一條Path(路徑)存在。 *Path Length:路徑上所包含的有向邊的數目 *Simple directed path:路徑上除了起點和終點可能 相同外，其它的頂點都是不同的 *Directed Cycle(Circuit): A simple directed path 且路徑上的起點和終點相同,Directed Graph(Digraph,有方向圖形): *Strongly connected graph: for every pair of distinct vertices u

10、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),Graph Representations: *相鄰矩陣(adjacency matrix) *相鄰串列(adjacency list) *相鄰多元串列(adjacen

11、cy multilist),Adjacency Matrix G(V, E): a graph with n vertices A two-dimensional n*n array: a1:n, 1:n *ai, 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 row s

12、um. *For a directed graph the row sum is the out-degree, and the column sum is the in-degree.,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

13、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

14、 to count the number of nodes in its adjacency list.,Adjacency List Inverse adjacency lists to count the in-degree easily *One list for each vertex *Each list contains a node for each vertex adjacent to the vertex it represents.,Array node1: n+2e+1 to represent a graph G(V, E) with n vertices and e edges - eliminate the use of pointers *The nodei gives the starting point of the list for vertex i, 1in *noden+1:=n+2e+2,Orthogonal list Each node has four fields and represents one edge. Node structure: tail