資料型態(tài)(data

1、資料型態(tài)(Data Type)-程式語(yǔ)言的變數(shù)所能表 示的資料種類(lèi)*基本型態(tài)(Primitive Type): integer, real, boolean, character(byte)*結(jié)構(gòu)化型態(tài)(Structured Type): string, array, record/structure,int i, j;char c;float

2、 r;int i1[10], j1[10];float r1[10]; i1[0]=20;i2[1]=90;…,串列(List) *有序串列可以是空的()或?qū)懗?a1, a2, ..., an) 串列的表示法(representation of lists) *順序?qū)?yīng)(Sequential mapping)-array *鏈結(jié)串列(Linked list)-pointer,堆疊與佇列(Stacks & Q

3、ueues) *堆疊是一個(gè)有序串列，所有的insertion和 deletion動(dòng)作均在頂端(top)進(jìn)行*具有後進(jìn)先出(LIFO-last in first out)特性 *佇列是一個(gè)有序串列，所有的insertion和 deletion是發(fā)生在串列的不同端，加入的一端 稱(chēng)為尾端(rear)，刪除的一端稱(chēng)為前端(front) *具有先進(jìn)先出(FIFO-first in first out)特性,Representa

4、tion of a stack: *a one-dimensional array: stack[0:n-1] *a variable: top *linked list *node: data, link *a variable: top,Representation of a queue: *a one-dimensional array: q[0:n-1] *two variables: front & r

5、ear *linked list *node: data, link * two variables: front & rear,Trees *A tree is a finite set of one or more nodes *樹(shù)是一個(gè)或多個(gè)節(jié)點(diǎn)(node)所組成的有限集合*有一個(gè)特殊的節(jié)點(diǎn)稱(chēng)為樹(shù)根(root)*每一個(gè)節(jié)點(diǎn)底下有零個(gè)或一個(gè)以上的子樹(shù) (subtree): T1, T2, …, Tn n?0

6、*節(jié)點(diǎn)(node) *分支(branch, edge) *樹(shù)根(root) *子點(diǎn)(children) *父點(diǎn)(parent) *終端節(jié)點(diǎn)(leaf, terminal nodes),Trees *非終端節(jié)點(diǎn)(nonterminal nodes) *兄弟(siblings) *祖先(ancestor of a node): all the nodes along the path from the root

7、 to that node *分支度(degree): the number of subtrees of a node *樹(shù)的分支度(degree of a tree): the maximum degree of the nodes in the tree *階度(level): initially let the root be at level one,Trees

8、 *高度(height, depth): the maximum level of any node in the tree *A forest is a set of n?0 disjoint trees *若一樹(shù)有n個(gè)nodes，則必有且唯有n-1個(gè) edges *A graph without a cycle,Representation of a T

9、ree: *linked list *node: data, link, tag *when tag=1, data field contains a pointer to a list rather than a data item,Binary Trees : *Any node can have at most two children *二元樹(shù)上每個(gè)節(jié)點(diǎn)的degree?2 *左子樹(shù)(left subtree)

10、& 右子樹(shù)(right subtree) *二元樹(shù)可以是空集合(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,

11、 if n0 is the number of terminal nodes and n2 is the number of nodes of degree 2, then n0=n2+1.,二元樹(shù)的特例 : *歪斜樹(shù)(skewed binary tree) left-skewed binary tree, right-skewed binary tree *全滿(mǎn)二元樹(shù)(full binary tree) T

12、he binary tree of depth k that has exactly 2k-1 nodes *完整二元樹(shù)(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

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

14、arent(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 n

15、o right child. *優(yōu)點(diǎn):處理簡(jiǎn)單，若為full binary tree，則相當(dāng)節(jié)省 空間。 *缺點(diǎn):若為skewed binary tree，則相當(dāng)浪費(fèi)空間。 不容易處理Insertion or deletion,Representation of a Binary Tree: *linked list node: lchild, data, rchild a va

16、riable: tree *優(yōu)點(diǎn):插入與刪除一個(gè)節(jié)點(diǎn)相當(dāng)容易。 *缺點(diǎn):缺點(diǎn):很難找到該節(jié)點(diǎn)的父點(diǎn)。,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 i

17、n 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,Bina

18、ry 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 Pr

19、iority 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-e

20、lement 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 n

21、ode is at least as large as the value at its children(任何一父點(diǎn)的值必大於*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,Heap sort 1)建立一b

22、inary tree 2)將binary tree轉(zhuǎn)成Heap (Heapify) 3)Output: Removing the largest number and restoring the heap (Adjust),Sets and Disjoint Set Union Set: *The sets are assumed to be pairwise disjoint. *Each s

23、et 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*Fin

24、d(i),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

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

26、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]

27、.,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,Undire

28、cted Graph(無(wú)方向圖形): (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 vert

29、ex G has n vertices and e edges, *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 *S

30、imple path:路徑上除了起點(diǎn)和終點(diǎn)可能相同外，其它 的頂點(diǎn)都是不同的,Undirected Graph(無(wú)方向圖形): (u,v)=(v,u) *Cycle: a simple path且此路徑上的起點(diǎn)和終點(diǎn)相同 且(u,v)是incident on u和v *In G, two vertices u and v ar

31、e said to be connected iff there is a path in G from u to v. *Connected graph:圖上每個(gè)頂點(diǎn)都有路徑通到其它 頂點(diǎn) *Connected component: a maximal connected subgraph

32、 (圖上相連在一起的最大子圖) *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

33、the same edge,Undirected Graph(無(wú)方向圖形): (u,v)=(v,u) *Eulerian walk(cycle):從任何一個(gè)頂點(diǎn)開(kāi)始， 經(jīng)過(guò)每個(gè)邊 一次，再回到原出發(fā)點(diǎn) (每個(gè)頂點(diǎn)的degree必須是偶數(shù))*Eulerian chain:從任一頂點(diǎn)開(kāi)始，經(jīng)過(guò)每個(gè)邊 一次，不一定要回到原點(diǎn) (只有兩個(gè)頂點(diǎn)的degree是奇數(shù)，其它必須是 偶數(shù)),Directed Graph(D

34、igraph,有方向圖形): ? *假如?E(G)，則稱(chēng)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

35、 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,有方向圖形): ?

36、*Directed Path:假如, , ..., ?E， 則u與v有一條Path(路徑)存在。*Path Length:路徑上所包含的有向邊的數(shù)目 *Simple directed path:路徑上除了起點(diǎn)和終點(diǎn)可能 相同外，其它的頂點(diǎn)都是不同的 *Directed Cycle(Circuit): A simple directed path 且路徑上的起點(diǎn)和終點(diǎn)相同,Directed Graph(Digraph,有方

37、向圖形): ? *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 conne

38、cted (有向圖上緊密相連在一起的最大有向子圖) *Complete digraph: if |V|=n then |E|=n(n-1),Graph Representations: *相鄰矩陣(adjacency matrix) *相鄰串列(adjacency list) *相鄰多元串列(adjacency multilist),Adjacency Matrix G(V, E): a graph with n vert

39、ices 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

40、 graph the degree of i is its row sum.*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 adjac

41、ency 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 n

42、odes 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-de

43、gree of i is 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 adjacen

44、t to the vertex it represents.,,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

45、*node[n+1]:=n+2e+2,,Orthogonal list Each node has four fields and represents one edge. Node structure: tailheadcolumn link for headrow link for tail,,Adjacency Multilist *One list for each vertex *node can be shared