完全二叉树之堆
堆排序和快速排序一样，时间复杂度为Ο(N㏒N)。以升序排序为例，可以先建立最小堆，然后每次删除顶部元素并将顶部元素输出或者放入一个新的数组中，直到堆空为止。最终输出的或者存放在新数组中的数就已经是排序好的了。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 1 //第一种方法 2 #include <stdio.h> 3 4 int h[101]; //用来存放堆的数组 5 int n; //用来存储堆中元素的个数，也就是堆的大小 6 7 //交换函数，用来交换堆中的两个元素的值 8 void swap(int x, int y) { 9 int t;10 t = h[x];11 h[x] = h[y];12 h[y] = t;13 }14 15 //向下调整16 void sif ...
分别用DFS和BFS实现图的遍历
DFS模板：
1234567891011 1 void dfs(int step) { 2 if (...) //判断边界,到达边界则返回 3 return; 4 for (循环所有方向) { 5 if (...) { //可能需要判断条件 6 book[...] = 1; //标记 7 dfs(step+1); 8 book[...] = 0; //取消标记 9 }10 }11 }
用DPS遍历图。我们用一个二维数组e来储存图。
我们用上面二维数组中的(i, j)储存的数字来表示顶点i到顶点j是否有边——1表示有边，∞表示没有边，0表示自己到自己（即i等于j）。
12345678910111213141516171819202122232425262728293031323334353637383940414243 1 //图的遍历 - 深度优先 2 #include <s ...
栈
直接看实例吧，用栈判断回文
1234567891011121314151617181920212223242526272829303132333435363738 1 #include <stdio.h> 2 #include <string.h> 3 int main() { 4 char a[101], s[101]; 5 int i, len, mid, next, top; 6 7 gets(a); //读入一行字符串 8 len = strlen(a); //求字符串的长度 9 printf("%d\n", len);10 mid = len/2-1; //求字符串的中点11 printf("%d\n", mid);12 13 top = 0; //栈的初始化14 //将mid前的字符依次入栈15 for (i = 0; i <= mid; i++)16 s[++top] = a[i];17 18 ...
链表
2021-07-14 09:54:08
来填坑了。 链表是如何实现的呢？如下。
12345678910111213141516171819202122232425262728293031323334353637 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 //创建一个结构体用来表示链表的结点类型 5 struct node { 6 int data; 7 struct node *next; 8 }; 9 10 int main() {11 struct node *head, *p, *q, *t;12 int n, a;13 scanf("%d", &n);14 head = NULL; //头指针初始为空15 for (int i = 1; i <= n; i++) { //循环读入n个数16 scanf("%d", &a);17 ...
三种排序算法
三种排序算法 从小到大排序
桶排序 - 时间复杂度为Ο(M+N)，快，但空间复杂度高
12345678910111213141516 1 #include<stdio.h> 2 3 int main() { 4 int book[1001], n, t; 5 for(int i = 1; i <= 1000; i++) 6 book[i] = 0; 7 scanf("%d", &n); //输入一个数n，表示接下来有n个数 8 for(int i = 1; i <= n; i++) { //循环读入n个数，并进行桶排序 9 scanf("%d", &t); //把每一个数读到变量t中10 book[t]++; //进行计数，对编号为t的桶放一个小旗子11 }12 for(int i = 1; i <= 1000; i++) //依次判断编号1000~0的桶13 ...