-- MySQL dump 10.13 Distrib 5.6.30, for debian-linux-gnu (x86_64) -- -- Host: localhost Database: rire -- ------------------------------------------------------ -- Server version 5.6.30-1
/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */; /*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */; /*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */; /*!40101 SET NAMES utf8 */; /*!40103 SET @OLD_TIME_ZONE=@@TIME_ZONE */; /*!40103 SET TIME_ZONE='+00:00' */; /*!40014 SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0 */; /*!40014 SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0 */; /*!40101 SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='NO_AUTO_VALUE_ON_ZERO' */; /*!40111 SET @OLD_SQL_NOTES=@@SQL_NOTES, SQL_NOTES=0 */;
LOCKTABLES`user` WRITE; /*!40000 ALTER TABLE `user` DISABLE KEYS */; INSERTINTO`user`VALUES (7,'rire','15927382214','华中科技大学',0,'hhh'); /*!40000 ALTER TABLE `user` ENABLE KEYS */; UNLOCKTABLES; /*!40103 SET TIME_ZONE=@OLD_TIME_ZONE */;
/*!40101 SET SQL_MODE=@OLD_SQL_MODE */; /*!40014 SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS */; /*!40014 SET UNIQUE_CHECKS=@OLD_UNIQUE_CHECKS */; /*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */; /*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */; /*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */; /*!40111 SET SQL_NOTES=@OLD_SQL_NOTES */;
-- Dump completed on 2019-04-10 15:32:05
由于原表中存在外键，所以sql文件中的建表顺序会导致还原失败，应该在备份的时候指定备份表的顺序．
数据类型
整型
无符号则在其后加 UNSIGNED
浮点型
日期型
year
time
date
datetime
timestamp
字符型
联表查询
LEFT JOIN 左连接查询: 查询两个表中共有的数据，并以左边的表为基准显示左表的全部数据，显示右表符合条件的数据, 不足的地方显示NULL
RIGHT JOIN 右连接查询: 查询两个表共有的数据，并以右表为基准显示右表的全部数据，显示左表符合条件的数据不足的地方显示NULL
INNER JOIN 内连接查询: 显示两个表共有的数据
1 2 3
SELECT * FROM tbl_a AS a LEFTJOIN tbl_b AS b ON a.id=b.id; SELECT * FROM tbl_b AS a RIGHTJOIN tbl_a AS b ON a.id=b.id; SELECT * FROM tbl_a as a INNERJOIN tbl_b AS b ON a.id=b.id;
1>begin; 2>select * from user; >>1,h 2>update user set name='hh' where id=1; 1>select * from user; >>1,hh 2>update user set name='hhh' where id=1; 1>select * from user; >>1,hh 1>commit; 1>select * from user; >>1,hhh
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1>begin; 1>select * from user; >>1,h 2>select * from user; >>1,h 2>update user set name='hh' where id=1; 1>select * from user; >>1,h 2>update user set name='hhh' where id=1; 1>select * from user; >>1,h 1>commit; 1>select * from user; >>1,hhh
1 2 3 4 5 6 7 8 9 10 11 12
1>begin; 1>select * from user; >>1,h 2>select * from user; >>1,h 1>update user set name='hh' where id=1; 1>select * from user; >>1,hh 2>update user set name='hhh' where id=1; >>阻塞 1>commit; 2>update 成功
幻读：
会出现两条记录。
MySQL
begin
commit
rollback
SET [SESSION|GLOBAL] TRANSACTION ISOLATION LEVEL [READ UNCOMMITTED|READ COMMITTED|REPEATABLE READ|SERIALIZABLE]
1.publicStack() 创建一个空堆栈 2. publicbooleanempty() 测试堆栈是否为空 3. public E pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象 4. public E push(E item) 把项压入堆栈顶部 5. public E peek() 查看堆栈顶部的对象，但不从堆栈中移除它 6. publicbooleanempty() 测试堆栈是否为空
Queue
1 2 3 4 5 6 7 8 9 10
1.booleanadd() 增加一个元索，如果队列已满，则抛出一个 IIIegaISlabEepeplian 异常 2. booleanoffer() 添加一个元素并返回true，如果队列已满，则返回false 3. voidput() 添加一个元素，如果队列满，则阻塞 4. E remove() 移除并返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常 5. E poll() 移除并返问队列头部的元素，如果队列为空，则返回null 6. E take() 移除并返回队列头部的元素，如果队列为空，则阻塞 7. E element() 返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常 8. E peek() 返回队列头部的元素，如果队列为空，则返回null
二叉树
类型
满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点，节点数为 2^h-1。
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。一棵完全二叉树的两棵子树，至少有一棵是满二叉树。
voidCocktailSort(int A[], int n){ int left = 0; // 初始化边界 int right = n - 1; while (left < right) { for (int i = left; i < right; i++) { // 前半轮,将最大元素放到后面 if (A[i] > A[i + 1]) { Swap(A, i, i + 1); } } right--; for (int i = right; i > left; i--) { // 后半轮,将最小元素放到前面 if (A[i - 1] > A[i]) { Swap(A, i - 1, i); } } left++; } }
// 合并两个已排好序的数组[left...mid]和[mid+1...right] privatevoidmerge(int[] arr, int left, int mid, int right){ int len = right - left + 1; int i = left; // 前一数组的起始元素 int j = mid + 1; // 后一数组的起始元素 int[] tmp = newint[len]; int index = 0; while (i <= mid && j <= right) { tmp[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++]; } while (i <= mid) { tmp[index++] = arr[i++]; } while (j <= right) { tmp[index++] = arr[j++]; } for (int k = 0; k < len; k++) { arr[left++] = tmp[k]; } }
publicvoidmergeSort(int[] arr, int left, int right){ if (left == right) { return; // 当待排序的序列长度为1时，递归开始回溯，进行merge操作 } int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }
// 建堆，时间复杂度O(n) privateintbuildHeap(int[] arr){ int heapSize = arr.length; // 从每一个非叶结点开始向下进行堆调整 for (int i = heapSize / 2 - 1; i >= 0; i--) { heapify(arr, i, heapSize); } return heapSize; }
// arr[i]向下进行堆调整 privatevoidheapify(int[] arr, int i, int heapSize){ int left = 2 * i + 1; // 左孩子 int right = 2 * i + 2; // 右孩子 int max = i; if (left < heapSize && arr[left] > arr[max]) { max = left; } if (right < heapSize && arr[right] > arr[max]) { max = right; } if (max != i) { swap(arr, i, max); // 把当前结点和它的最大(直接)子节点进行交换 heapify(arr, max, heapSize); // 递归调用，继续从当前结点向下进行堆调整 } }
// 分类 ------------ 内部比较排序 // 数据结构 --------- 数组 // 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2) // 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n) // 稳定性 ---------- 不稳定 publicvoidquickSort(int[] arr, int left, int right){ if (left >= right) { return; } int index = patition(arr, left, right); quickSort(arr, left, index - 1); quickSort(arr, index + 1, right); }
privateintpatition(int[] arr, int left, int right){ int key = arr[left]; // 第一个数作为基准 int i = left; int j = right; while (i < j) { while (arr[j] >= key && i < j) { j--; // 从右往左找第一个小于基数的数 } while (arr[i] <= key && i < j) { i++; } swap(arr, i, j); } swap(arr, left, i); return i; }
voidCountingSort(int A[], int n, int d)// 依据元素的第d位数字，对A数组进行计数排序 { for (int i = 0; i < k; i++) { C[i] = 0; } for (int i = 0; i < n; i++) { C[GetDigit(A[i], d)]++; } for (int i = 1; i < k; i++) { C[i] = C[i] + C[i - 1]; } int *B = (int*)malloc(n * sizeof(int)); for (int i = n - 1; i >= 0; i--) { int dight = GetDigit(A[i], d); // 元素A[i]当前位数字为dight B[--C[dight]] = A[i]; // 根据当前位数字，把每个元素A[i]放到它在输出数组B中的正确位置上 // 当再遇到当前位数字同为dight的元素时，会将其放在当前元素的前一个位置上保证计数排序的稳定性 } for (int i = 0; i < n; i++) { A[i] = B[i]; } free(B); }
voidLsdRadixSort(int A[], int n)// 最低位优先基数排序 { for (int d = 1; d <= dn; d++) // 从低位到高位 CountingSort(A, n, d); // 依据第d位数字对A进行计数排序 }
intmain() { int A[] = { 20, 90, 64, 289, 998, 365, 852, 123, 789, 456 };// 针对基数排序设计的输入 int n = sizeof(A) / sizeof(int); LsdRadixSort(A, n); printf("基数排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return0; }
voidInsertionSort(int A[], int left, int right) { for (int i = left + 1; i <= right; i++) // 从第二张牌开始抓，直到最后一张牌 { int get = A[i]; int j = i - 1; while (j >= left && A[j] > get) { A[j + 1] = A[j]; j--; } A[j + 1] = get; } }
intMapToBucket(int x) { return x / 10; // 映射函数f(x)，作用相当于快排中的Partition，把大量数据分割成基本有序的数据块 }
voidCountingSort(int A[], int n) { for (int i = 0; i < bn; i++) { C[i] = 0; } for (int i = 0; i < n; i++) // 使C[i]保存着i号桶中元素的个数 { C[MapToBucket(A[i])]++; } for (int i = 1; i < bn; i++) // 定位桶边界：初始时，C[i]-1为i号桶最后一个元素的位置 { C[i] = C[i] + C[i - 1]; } int *B = (int *)malloc((n) * sizeof(int)); for (int i = n - 1; i >= 0; i--)// 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变) { int b = MapToBucket(A[i]); // 元素A[i]位于b号桶 B[--C[b]] = A[i]; // 把每个元素A[i]放到它在输出数组B中的正确位置上 // 桶的边界被更新：C[b]为b号桶第一个元素的位置 } for (int i = 0; i < n; i++) { A[i] = B[i]; } free(B); }
voidBucketSort(int A[], int n) { CountingSort(A, n); // 利用计数排序确定各个桶的边界（分桶） for (int i = 0; i < bn; i++) // 对每一个桶中的元素应用插入排序 { int left = C[i]; // C[i]为i号桶第一个元素的位置 int right = (i == bn - 1 ? n - 1 : C[i + 1] - 1);// C[i+1]-1为i号桶最后一个元素的位置 if (left < right) // 对元素个数大于1的桶进行桶内插入排序 InsertionSort(A, left, right); } }
intmain() { int A[] = { 29, 25, 3, 49, 9, 37, 21, 43 };// 针对桶排序设计的输入 int n = sizeof(A) / sizeof(int); BucketSort(A, n); printf("桶排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return0; }
