TeaPort

Zhejiang University Graph It is used to represent a many-to-many relationship. It is so powerful because it includes both linear lists(one to one) and trees(one to many). Components Vertex(V): the set of all vertexes. Edge: the set of all sides. (v, w). Double directions. . From v to w (single direction). No multiple edges or multiple loops. A Quick Review: Definition of Abstract Data Type Name: Graph DataSet: G(V, E). V is Nonempty E is limited. Operation Set Graph Create() Graph Insert ...

Zhejiang University Set Operations There are some basic operations about sets. Eg: Union, Intersection, Set Difference… Union-Find Set Problem: There are n nodes. Some of them are connected. How do we know whether arbitrary 2 of them are connected? Answer: Make n sets to include n nodes. Then union those connected. Find whether 2 given nodes are in the same set. Creating Union-Find Set How to Store a Set? Tree. The root will be a set. Each node will be an element. Parental Representation: The ...

Zhejiang University Huffman Tree Question: How can we fit a 100 mark test into a 5 standards judging system? We need to carefully arrange our if clauses in accordance with the frequency of the actual result. (Decision Tree) Cost: ∑ratio×layers\sum\rm ratio\times layers∑ratio×layers Definition Weighed Path Length: A binary tree with n nodes with weight w. The distance between root and each leaf is l. Then the WPL for each leaf node will be WPL=∑i=1nwklkWPL = \sum_{i=1}^nw_kl_k WPL=i=1∑n​wk​lk​ ...

Zhejiang University Heap What is heap? When a computer is doing many things at the same time, different tasks will have different priorities. Thus we have a special data structure: Priority Queue. Creating a heap We need 2 functions: insert and delete Array difficult to delete a element linked list Ordered Array difficult to insert Ordered linked list Tree Tree Tree has some great characteristics in realizing heap. The insert process is related to the height of a tree while the delete proces ...

Zhejiang University Binary Search Tree (BST) Properties Left subTrees’s values are smaller than their roots Right subTrees’s values are larger than their roots Left and Right subTrees are all BSTs API Position Find(ElementType X, BinTree BST) Position FindMin(BinTree BST) Position FindMax(BinTree BST) BinTree Insert(ElementType X, BinTree BST) BinTree Delete(ElementType X, BinTree BST) Find Recursion Loop 123456789while(BST){ if(X > BST->Data) BST = BST->Right; els ...

Zhejiang University Binary Tree Properties Degree = 2. L and R are different. Layer i has a maximum number of nodes 2^(i-1) Degree = K, node sum = 2^(k-1) For any not-null binary tree, n0 = leaf, n2 = nodes which have 2 non-leaf nodes, then n0 = n2+1 Operation Set Boolean IsEmpty(BinTree BT) void Traversal(BinTree BT) PreOrderTraversal:rLR InOrderTraversal:LrR PostOrderTraversal:LRr LevelOrderTraversal:UD,LR BinTree CreatBinTree() Special Binary Tree Skewed Binary Tree Perfect Binary T ...

Zhejiang University Tree A Structure used for managing and organizing different levels of data. Properties A special node: Root® The rest nodes can be divided into m nonoverlapping subsets called SubTree. SubTrees do not overlap. Every Node has one parent except r. A tree with N nodes has N-1 sides. Terms Degree: The number of SubTrees for a Node. Degree of a Tree: The maximum Degree for all nodes of a tree. Leaf Parent Child Sibling Path and the Distance of Path: From Node n1 to Node nk, t ...

Zhejiang University Queue A restricted linear table. Queue and Round-robin Queue Properties AddQ DeleteQ FIFO Operation Set Queue CreateQueue(int Maxsize) int IsFull(Queue Q, int MaxSize) void AddQ(Queue Q, ElementType item) int IsEmpty(Queue Q) ElementType DeleteQ(Queue Q) indicators front(begins with -1) rear(begins with -1) Round-robin Queue A more efficient way to make use of space. Questions: How to tell whether a queue is full? Why is it difficult to tell whther it is full? Wha ...

Zhejiang University Stack Problem How to make computer understand the priority of calculating? Expression Nifix Expression is what we are customed to use. But Postfix Expression is easier for a computer to understand. We need a structure to store numbers and operators in order and get them out in the reverse order. Eg:6 2 / 3 - 4 2 * + store 6->store 2->6 2 out and divide store 3 in-> store 3->3 3 out and minus store 0 in…… Properties of Stack It is a limited linear table. Push an ...

Zhe Jiang University Design Target: Find the sum and the product of 2 polynomials. Data Structure 123456typedef struct PolyNode *Polynomial;struct PolyNode{ int coef; int expon; Polynomial link;}; Structure of the program 12345678Polynomial P1, P2, PP, PS;P1 = ReadPoly();P2 = ReadPoly();PP = Multi(P1, P2);PrintPoly(PP);PS = Add(P1, P2);PrintPoly(PS); Some New Ideas If you want to pass in a variable and let the function change it, you have to pass in a more ‘fundamental’ thing ...