わざと零した 夢で描いた，今に寝そべったままで 時効を待っている
Data Structure Sorting QuickSort Idea $Process\ after\ dividing \rightarrow$(like MergeSort in thought)
Divide the sequence into two subsequences $$ S=S_L+S_R $$ Downsizing $$ max(|S_L|,|S_R|) < n $$ Be independent of each other $$ max(S_L) \leq min(S_R) $$ After the subsequences are sorted recursively, the original sequence is ordered naturally $$ Sorted(S)=Sorted(S_L)+Sorted(S_R) $$ A trivial solution: With a single element, is itself a solution$\rightarrow Recursive\ base\newline$
Problem How to delimit subsequence?
Data Structure Searching Read Map Static Search Table Sequential Search Binary Search Indexing Search Binary Search Trees (Dynamic Search Table) Binary search tree AVL tree B-Tree Hash Table What is hashing Hash Function Collision Resolution Closed Hashing Open Hashing Analysis of Hashing Search Table Definition A set of the same type of data elements Key The value of data item in the data element. It is used to identify the
Data Structure Graph Definition: A graph G consists of two sets
a finite, nonempty set of vertices V(G)
a finite, possible empty set of edges E(G)
G(V,E) represents a graph
The number of vertices is written $|V|(n)$, and the number of edges is written $|E|(e)$
General graphs differ from trees
need not have a root node no implicit parent-child relationship may be several (or no) paths from one vertex to another Definition For a Directed graph $if\ u, v\ are\ two\ vertices,then\ <u, v> is\ an\ arc(edge), u\ is\ called\ as\ tail, v\ is\ called\ head$
Something About Dynamic Programming $Fibonacci\ By\ Dynamic\ Programming$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /* * In this program, we will calculate the Fibonacci by dynamic programming * The definition of the Fibonacci: Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) (n >= 2) * Fibonacci(1) = 1 and Fibonacci(0) = 0 * we can find the program is faster than the recursion's * T(n) = O(n) and S(n) = O(1) */ #include <iostream> std::size_t FibonacciByDynamicProgramming(std::size_t n) { std::size_t f{0}, g{1}; for (std::size_t i = 0; i < n; i++) { g = g + f; f = g - f; } return f; } int main() { for (std::size_t i = 0; i <= 64; i++) std::cout << "Fibonacci(" << i << ") = " << FibonacciByDynamicProgramming(i) << std::endl; return 0; } $Longest\ Common\ Subsequence\ By\ Dynamic\ Programming$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 /* * In this program, we will use dynamic programming to find the length * of the longest common subsequence in two arrays * T(m + n) = O(m * n) and S(m + n) = O(m * n) */ /* * Example: array1[] = {1, 2, 3, 4, 5, 6, 7} * array2[] = {2, 5, 6, 7} * we should make a matrix(n * m) and make the element in array1 and array2 in the top and left of the matrix * like this case: 1 2 3 4 5 6 7 * 2 0 0 0 0 0 0 0 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * Then we will fill the matrix top line and leftest column * The measuring of the matrix[1, x] x -> [1, m]: * The length of the longest common subsequence in array2[0] and the array1[x - 1] * and in the same way, we can easy to understand the measuring of the matrix[x, 1] x -> [1, n]: * The length of the longest common subsequence in array1[0] and the array2[x - 1] * so after fill, the matrix: * 1 2 3 4 5 6 7 * 2 0 1 1 1 1 1 1 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * the base elements are ok, so we will use dynamic programming * if array1[x] == array2[y],we can know that it is form the "decreasing and conquer" * so we should make matrix[y - 1, x - 1] = matrix[y - 2, x - 2] + 1 * else array1[x] !
Data Structure String $Structure\rightarrow list$ linked String Arrayed String General Concepts of String $Null\ String(\emptyset)：Nothing\ in\ the\ string, the\ length\ is\ zero.$ $Blank(Space)string：Only\ includes\ one\ or\ more\ blanks(spaces)in\ the\ string.$ $Substring: sub-sequence\ of\ one\ string.$ ADT {
ADT String {Data Object：D＝{ ai | ai∈CharacterSet,i=1,2,...n, n≥0 } Data Relationship：R1＝{ < ai-1, ai > | ai-1, ai∈D,i=2,...,n } Operation： …… } ADT String
Operations {
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 StrAssign (&T, chars) //string assignment Initial：chars are character constant.
Data Structure Stack and Queue Stack Definition: Lists with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list. Access the list from the top. First in, last out (FILO) lists Or last in, first out (LIFO) lists. Basic Concepts Top: the end of the list, namely, the operation end. Bottom: the head of the list Push: Insert an element into
Data Structure List Definition A list is a finite sequence of N elements $write\ as\newline$ $L = (a_1, a_2, a_3，…a_n)\newline$ $The\ size\ of\ this\ list\ is\ n\newline$ $n=0 \rightarrow empty\ list\newline$ element The first element(No predecessor),called “head” The ith element(has only one predecessor and only one successor) The last element(No successor),called “tail” ADT
Data Structure Algorithms Analysis Algorithm Define: A finite, clearly specified sequence of instructions to be followed to solve a problem.(not a program)
Five features Finiteness Definiteness Effectiveness Input Output Design Requirements Correctness Readability Robustness High efficiency and low memory capacity Algorithm Analysis Computing time and memory space are two important resources.
Running time Analysis The estimation of the running time of algorithms.
The running times of algorithms can be changed because of the platform, the properties of the computer, etc.
Data Structure Introduction Data Define: The set of all the symbols can be processed or stored by a computer Example: A data set in a classroom = { desk 1, desk 2,…chair 1, chair2…,stud 1, stud 2,…}
Data Element Define: The term data element is an atomic unit of data that has:
An identification such as a data element name A clear data element definition Example: desk i; chair j; project n…
Data Structure Tree Definition One natural way to define a tree is recursively.
A tree is a collection of nodes. The collection can be empty;
otherwise, a tree consists of a distinguished node r,called root, and zero or more nonempty (sub)trees $T_1, T_2, … T_k$, each of whose roots are connected by a direct edge from r.
Terminology Parent: Node A is the parent of node B, if B is the root of one subtree of A.
