归并排序
时间复杂度: O(nlogn)空间复杂度: O(n)稳定性: 稳定实现语言: C/C++
原理思想这里采用的是分治的思想,但与快速排序相反的是,归并排序采用的是先分治再合并。
已知在有额外空间的情况下,合并两个有序数组得到一个新的较长有序数组是很高效的。 所以能不能把一个任意数组分成由左右两个有序数组组成然后合并成有序数组呢?
显然不能,大部分情况并不能分成两个有序数组,但如果在此之前用同样的方法(这里采用递归)事先排序左右两部分呢?大部分情况依然不能,因此这个递归会一直递推下去,最终待排序区间不断缩小,到只剩一个或零个元素,此时就可以将其看为有序数组了,也就是说递归在这里停止,可以一路合并有序数组一路回归上去了
分治这里使用左右指针控制待排序区间(迭代器也行),并采用递归的方式形象地完成分治操作
123456789101112131415161718void _MergeSort(vector<int>& arr,int left,int right,vector<int>&tmp){ //分治 if(le ...
=Linux=一步步自己写一个shell程序
系统:阿里云服务器Linux CentOs 7
编辑器: vim
编译器: gcc (支持C99)
文件本次写的程序较为简单,所以只使用一个源文件
所以在shell中touch一个makefile和一个myshell.c
shell
12touch makefiletouch myshell.c
然后编辑makefile文件
makefile
1234561 myshell:myshell.c gcc -o $@ $^ -std=c99.PHONY:cleanclean: rm -f myshell
头文件本程序因函数较杂,会include较多头文件
myshell.c
12345#include <stdio.h>#include <stdlib.h>#include <string.h>#include <unistd.h>#include <assert.h>
宏定义为了统一修改部分参数,以及使参数更易读,这里使用部分宏定义
myshell. ...
堆排序
背景知识
知道什么是大堆/小堆
掌握如何将数组与完全二叉树的映射关系
掌握向上调整法和向下调整法
大堆/小堆大堆的特性:每一个节点的值都比左右孩子都大,根的值是整个大堆中最大的小堆的特性:每一个节点的值都比左右孩子都小,根的值是整个大堆中最小的
后面以大堆为例
数组映射成完全二叉树任何一个数组可以看成一个完全二叉树,下标0为二叉树的根
而非常方便的是,已知一个节点的下标,可以利用数学关系求出根或孩子的下标
下标关系如下(变量均为下标)
parent = (child-1)/2
left_child = parent*2+1
right_child = parent*2+2
建堆方法向上调整法在已有一个大堆的前提下,把一个新的数据插入到堆的最后一个节点(此时破坏大堆的结构),再一路向上调整,可以重新建堆
123456789101112131415161718template<class T>void adjust_up(vector<T>& arr, int child){ int parent = (child - ...
C++文件操作
注:追求代码简洁,有一致的C++风格,可参阅本篇博客,若追求更高的读写效率,建议参阅C语言篇 但文章还没写
本篇文章主要研究头文件fstream中的函数和类
目前C++文件操作主要有两种流派,一种是声明fstream对象,另一种是分开声明ifstream和ofstream
注意,本文代码为了简洁,都是在展开std命名空间的前提下书写
fstream的使用先写一段示例代码
12345678910111213141516171819202122#include <iostream>#include <fstream>using namespace std;int main(){ fstream f("file.txt", ios::out);//调用构造函数以out模式打开文件file.txt 注:out模式下file.txt 会自动创建 string str = "This is a sentence";//在内存中准备一段字符串 f << str;//将字符串从内存写入文件 f.close();//关 ...
通过设计list类深入理解iterator迭代器
前置博客:从构建一个Date类入门C++类与对象
下面先迅速地搓一个list类
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859template <class T>//先用模板创建一个节点类struct ListNode{ T _val; ListNode<T>* _next; ListNode<T>* _prev; //提供全缺省的默认构造函数 ListNode(const T& val = T()) :_val(val), _next(nullptr), _prev(nullptr) {}};//用ListNode构造list类template <class T>class list{ typedef ListNode<T> Node;//用typedef简化代码public: list()// ...
vim基础指令集
Vim是一款文本编辑器,下面介绍在vim界面中的常用指令
三种模式:命令模式(Command Mode) 插入模式(Insert Mode 命令行模式(Command-Line Mode)(这里称命令行模式为底行模式)
三者关系如下图
命令模式vim界面中多摁几次ESC就能退出其它模式回到命令模式,在这个模式下可以使用一系列vim快捷键
底行模式tips:不管目前是什么模式,先狂按ESC,回到命令模式,然后输入:进入底行模式,准备开始输命令
命令组成
保存:w->强制保存!w
退出:q->强制退出:!q
保存并退出:wq-.强制保存并退出:!wq
对比:vs +(源文件路径)
插入模式在命令模式下按键盘i进入插入模式,执行正常的文本编辑功能
从构建一个Date类入门C++类与对象
类的定义12345678910111213141516171819class Date{public: void Init(int year = 1,int month = 1,int day = 1) { _year = year; _month = month; _day = day; } void Print() { cout << _year << ":" << _month << ":" << _day << endl; }private: int _year; int _month; int _day;};
抽象数据类型(类)通过如上代码,我们就在源代码中通过class声明了一个抽象数据类型Date,简称类,那么封装一个类有什么好处呢?好处是类把相关的操作分为两类:
类的设计者:负责考虑类的具体 ...
指针详解
这篇质量不太行:(
内存和地址在了解指针之前,先讲讲内存是如何管理的
首先因为内存很大(一般有几个G),所以为了高效管理,有了内存单元的概念。而这个单元的大小,正好是一个字节。
因为一个比特位就是一个二进制位,太小了,超过一个字节,在处理char这样一个字节长的变量很麻烦。
定下长度后,就可以给内存单元编号,而每个内存单元获得的独一无二的编号,便是它的地址,以声明了一个变量a为例,示意图如下
变量的地址上图中a占4个字节,每个字节都有自己的地址,但要找到a其实只需要找到第一个地址就行了,实际上在C语言中也是如此,a的地址就是首字节地址,即图中的0x000000AF88DFF6A4
关于几个名词在C语言中称地址为指针,储存地址的变量叫指针变量,平时也简称指针,此时强调的是指针变量里储存的地址,而不是这个变量。
指针变量的组成指针变量也要拆成两部分来看
一个是变量的值,在同一个程序中,所有指针变量的值的长度都是一样的,都指向了某一个内存中的字节, 至于具体多长,取决于环境:32位程序是4个字节,64位程序是8个字节
另一个是变量的类型,类型决定编译器从值所指向的字节,向后总共读几个字节 ...
=C入门=深入研究 字符串与字符数组
什么是字符串初见字符串我们最先遇到的字符串,一般是hello_world程序中用到的"hello world",也就是两个双引号括起来的一串字符,输出时的占位符是%s,可以直接拿去传值,代码如下
1printf("%s","hello world");
声明字符串变量有时我们想要先把字符串存起来,再进行操作,那么就使用字符数组,并在初始化的时候把字符串传给它,这样在创建数组时会编译器会自动分配内存给它,代码如下
1char str[] = "abcdef";
此时我们也可以开启VS的调试,并打开内存和监视窗口观察字符串是如何在内存中储存的,如下图
通过观察可以发现,C语⾔字符串的字符串有个规定(特点),就是以字符\0结尾,无论是初始化数组时,还是在分配内存时,都有\0的位置。
strlen()函数依据以\0为字符串结尾的规则,strlen函数就可以计算字符串的长度,它会从字符串的第一个字符向后扫描,直到遇到\0结束,且\0不进入计数,最后返回字符串的长度,代码如下
1234#include <st ...
=C语言实践= 手把手教你做高端cmd简单扫雷
直接开始吧!多文件项目扫雷项目内容较多,需要调用的函数也较多,采用多文件的方式,可以使代码条理清晰,并且易于管理和维护。文件如下
game.h用于宏定义,函数声明,引入头文件等
game.c用于函数的具体实现
front.c用于实现程序的主干部分
other.c用于实现其他杂项函数,这里我用于实现menu()函数,主要内容太花了
注 .c结尾的源文件均需加一句#include "game.h"
头文件本次用到的头文件有stdio.h stdlib.h time.h windows.h和自己建的game.h
均在文件game.h中#include
define宏定义为了便于阅读和维护代码,在game.h中的宏定义如下
1234567891011121314151617181920//显示行列#define ROW 9#define COL 9//实际数组大小#define ROWS ROW+2#define COLS COL + 2//地雷信息#define Bomb '*'#define Blank ' '//难度#defi ...