C++ Primer 字符串，向量和数组 标准库类型string 标准库类型string表示可变长的字符序列，使用string类型必须先包含头文件，string定
CMU 15-445 Database Systems Lecture #01: Course Overview & Relational Model Outline Course Logistics Relational Model Relational Algebra Course overiew This course is about the design/implementation of database management systems (DBMSs) This is not a course ($\rightarrow Key\ point\ is\ the\ theory\ and\ the\ concept$) about how to use a DBMS to build applications or how to administer a DBMS.→ See CMU 95-703 (Heinz College) PROJECTS All projects will use the CMU DB Group BusTub academic DBMS.
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 多处理器编程：从入门到放弃 Overview 复习 程序 (源代码S、二进制代码C) = 状态机 编译器 $C = \textrm{compile}(S)\newline$ 应用视角的操作系统 = syscall 指令 本次课回答的问题 Q: 在
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 操作系统上的程序 Overview 复习 什么是操作系统？ 应用视角 (设计): 一组对象 (进程/文件/…) + API 硬件视角 (实现): 一个 C 程序
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 操作系统概述 $Overvier\newline$ 为什么要学操作系统? $(why)\newline$ 到底什么是操作系统? $(what)\newline$ 怎么学操作系统? $(how)\newline$ 为什么学操作系统?$(why)\newline$ 每天
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.
