关于堆的一些知识点回顾 堆是一个完全二叉树 完全二叉树即是:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 堆满足两个性质: 堆的每一个父节点数值都大于(或小于)其子节点,堆的每个左子树和右子树也是一个堆。 堆分为最小堆和最大堆。最大堆就是每个父节点的数值要大于孩子节点,最小堆就是每个父节点的数值要小于孩子节点。排序要求从小到大的话,我们需要建立最大堆,反之建立最小堆。 堆的存储一般用数组来实现。假如父节点的数组下标为i的话,那么其左右节点的下标分别为:(2*i+1)和 (2*i+2)。如果孩子节点的下标为j的话,那么其父节点的下标为(j-1)/2。 完全二叉树中,假如有n个元素,那么在堆中最后一个父节点位置为(n/2-1)。 算法思想 建立堆 调整堆 交换堆顶元素和堆的最后一个元素 假如现在有一个数组a[8]={100,33,3,7,11,6,8,5};首先我们要建立完全二叉树,通过 继续阅读 >>


胡佳露 18/05/09 23:52:56
桶排序 第一次了解桶排序的时候,是在C语言课本的一个题目。题目大概意思是要将三万个学生的成绩进行排名,分数从0分到100分。桶排序的时间复杂度时O(M+N)。所以就可以申请一个大小为100的为int类型的数组,然后将数组初始化为0,再将数组的下标看作为分数,把数组元素中存储的数值对应着获得该分数的人数,这样分数就自己在数组中有了排名,最后再用循环依次输出,只是输出的时候要看该分数有多少人获得,就重复输出多少次。 实现代码如下 #include<stdio.h> int main() { int score; int a[100]; /*初始化数组 */ for(int i=0; i<100; i++) { a[i] = 0; } /*输入学生成绩,加入有十个人的成绩*/ for(int i=0; i<10; i++) { scanf("%d",&sco 继续阅读 >>


胡佳露 18/05/08 17:00:42
互斥锁(互斥量) 互斥量可以帮助线程同步对共享资源的使用,防止线程A试图访问一个共享变量的时候,此时线程B正在对这个共享变量进行修改。目的保护共享变量的的访问。 死锁 死锁情况一般是一个线程需要访问多个不同的共享资源的时候,但是每一个资源又都由不同的互斥量来管理,当超过一个线程(比如子线程已经对互斥量b进行量加锁后,此时主线程试图对互斥量b进行加锁时候,要等待子线程中的b解锁,若此时子线程的下一步执行操作是对互斥量a加锁,而如果一开始主线程就已经在先给互斥量a加锁后才试图给互斥量b加锁的话,并且此时互斥量a还没有解锁,那么此时的主线程和子线程都在等待状态中,造成了死锁现象)对一个互斥量加锁的时候就有可能因为先后顺序的原因造成死锁现象的产生。 死锁例子 #include<iostream> #include<pthread.h> #include<unistd.h> #include<stdio.h> using namespace std; 继续阅读 >>


胡佳露 18/02/02 21:28:22
几个不同于引入第三方变量的交换方法。。 利用异或运算实现 #include<iostream> using namespace std; int main() { int a = 4; int b = 5; cout << "a= " << a << endl; cout << "b= " << b <<endl; a = a ^ b; b = a ^ b; a = a ^ b; cout << "改变后:\n"; cout << "a= " << a << endl; cout << "b= " << b <<endl; return 0; } 利用位运算交换 #include<iostream> using names 继续阅读 >>


胡佳露 17/12/12 22:45:38
DFS深度优先遍历 深度遍历就是在图中从一个顶点开始,按照一个规则不重复地走下去。就是不撞南墙不回头一样。假如从A顶点开始,按照一个规则去走(假如我们按照一直字典顺序走)那么就从A走到B再从B走到了C,走到C后再按照字典顺序的时候,发现A已经走过,那么此时就退回到C点,选择另一个D走下去。就和树的前序遍历是一样的。 实现方式 1、递归实现(通过邻接矩阵来实现) void DFS(MGrap G. int i) { int j = 0; visited[i] = 1; count++; for(j=0; j<G.numVertexes; j++) { if(G.arc[i][j]==1 && !visited[j])//i和j有关系相邻,并且j顶点没有被访问过 { DFS(G, j); } } } void dfs(MGrap G,int v) 继续阅读 >>


胡佳露 17/12/04 11:56:54
基础定义 无向图:没有方向的图 连通图:任意两个顶点可以直接或者通过其他顶点走通,那么就是连通图,和完全图需要区别(完全图是需要任意两个顶点直接有路) 遍历图的基本方法来判断是否连通 DFS和BFS有的步骤都是从一个顶点开始,然后判断该顶点是否被访问,而且该顶点和其他顶点是否有关系,若有关系并且没有访问过,就往下访问,要是无向图是连通的,那么这个过程会依次下去遍历所有节点。所以通过这个特性,就可以设置一个全局变量count去记录,看最后count的值和顶点数是否相同,若相同则说明是无向连通图,反之则不是。 int count = 0; void DFS(MGrap G. int i) { int j = 0; visited[i] = 1; count++; for(j=0; j<G.numVertexes; j++) { if(G.arc[i][j]==1 && !visited[j])//i和j有关系相邻 继续阅读 >>


胡佳露 17/11/27 22:18:30
#include<iostream> #include<algorithm> #include<iomanip> #define MAXSIZE 30 using namespace std; /*哈夫曼编码的存储方式*/ typedef struct Node { char ch; int weight; int parent,Lchirld,Rchirld; }Huff; void prinhuffman(Huff *HF,int m); Huff *huffman(Huff *HF, int n, int m); Huff *select(Huff *HF, int i, int *n, int *m); int select_min(Huff *HF,int i); /*创建哈夫曼树*/ Huff *cretahuffman(int n) //传入叶子节点的个数 { int i = 0; int m = 2* 继续阅读 >>


胡佳露 17/11/19 14:15:49
#include<stdio.h> #include<stdlib.h> #include<unistd.h> #define Size 100 #define False 0 #define Ture 1 /*树的存储结构*/ typedef struct Tree { char data; struct Tree *Lift; struct Tree *Right; }Tree,*Btree; /*栈的建立*/ typedef struct stack { int top; Btree data[Size]; }sepstack; /*栈的初始化*/ sepstack *init(sepstack *stack) { stack = malloc(sizeof(sepstack)); stack -> top = -1; return stack; } /*判断栈空*/ int em 继续阅读 >>


胡佳露 17/11/19 14:08:22
开始学习cin, cin.get( ), cin.getline( )觉得还好。直到昨天错误地写了一个代码的时候,发现输入不正确了。然后对这个问题进行了一些总结。 cin(输入是以回车键结束,遇到空格停止读取) cin是从缓冲区读取数据的,那么当缓冲区有残留的数据的时候,按理来说cin也应该从缓冲区读取,并会跳过键盘输入的这个过程。 代码: #include<iostream> using namespace std; int main() { char ch1,ch2,ch3; int count = 0; string st1,st2; char c[20],b[20]; cout << "please intput the string1:\n"; cin >> c; cout << "please input the string2:\n"; cin >> 继续阅读 >>


胡佳露 17/11/13 14:44:12
指针好像一直都是一个头疼的问题,从一级指针到二级指针的运用,总是经常出错。今天遇到的一个二级指针的问题,花了很多时间,想了一个比较合理的解释。 今天在数据结构的实验中,用一个二级指针作为参数来写了一个二叉树的建立。大概的函数代码如下: 存储结构如下: /*树的存储结构*/ typedef struct Tree { char data; struct Tree *Lift; struct Tree *Right; }Tree,*Btree; /*二级指针建立二叉树*/ void crea(Btree *root) { printf("%p\n",root); char ch; ch = getchar(); if(ch=='#') { (*root) = NULL; } else { *root=(Tree *)malloc(sizeof(Tree)); 继续阅读 >>


胡佳露 17/11/09 20:24:55