好设计是简单的设计。
好设计是解决主要问题的设计。
好的设计并非一定要有趣,但是很难想象完全无趣的设计会是好设计。——Paul Graham《黑客与画家》

描述

两个长度超出常规整形变量上限的大数相减,请避免使用各语言内置大数处理库,如 Java.math.BigInteger 等。

输入

有 N 行测试数据,每一行有两个代表整数的字符串 a 和 b,长度超过百位。规定 a>=b,a, b > 0。 测试结果可以用 linux 小工具 bc进行测试是否正确。

输出

返回表示结果整数的字符串。

输入样例

1231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739870-89513312312312378127398789513312312312378127398789513312312312378127398789513
1231231237812739878951331231231237812739878951331231231237812739878951331230000000000000000000000001-331231231237812739878951331231231

输出样例

1231231237812739878951331231231237812739878951331231231237812650365639018918853110413950365639018918853110413950365639018918853110413950357
1231231237812739878951331231231237812739878951331231231237812739878620099998762187260121048668768770

AC代码:

#include <bits/stdc++.h>
using namespace std;

string ASubB(string a,string b){//默认A比B大
     int i = a.size();
     int j = b.size();
     string c;
     for(int k = 0;k<i-j;k++){
        c = c+"0";
     }
     c = c+b;
     //转化为位数相同的A-C的问题
     for(int k = c.size();k>=0;k--){
        if(a[k] == -1){
            a[k] = 0;
            a[k-1] = a[k-1] - 1;
        }
        if(a[k] < c[k]){
            a[k-1]--;
            a[k] = a[k] +10;
        }
        a[k] = a[k] - c[k]+48;
     }
     return a;
}


int main()
{
    string s;
    while(cin>>s){
      int k = s.find("-");
      //cout<<k<<endl;
      string a = s.substr(0,k);
      string b = s.substr(k+1,s.size());
      //cout<<a<<endl;
      //cout<<b<<endl;
cout<<ASubB(a,b)<<endl;
    }
}

 

It’s not a bug, it’s a feature.——Null

描述

给出N个数字。其中仅有一个数字出现过一次,其他数字均出现过两次,找出这个出现且只出现过一次的数字。要求时间和空间复杂度最小。

输入

输入多个数字,每个数字以空格分开。数字数量 N < 20,输入数字的最大值小于 256.

输出

输出内容为只出现过唯一一次的数字

输入样例

10 10 11 12 12 11 16

输出样例

16

AC代码:

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;
int main()
{

    map<int,int>a;
    int b;
    while(cin>>b)
    {
        a[b]++;
        if (cin.get() == '\n')
            break;
    }
    for(map<int,int>::iterator iter=a.begin();iter!=a.end();iter++){
          if(iter->second == 1){
            cout<<iter->first<<endl;
          }
	}
}

 

在 C 语言中,我们不能使用 goto 语句来跳转到另一个函数中,但提供了两个函数——setjmp 和 longjmp来完成这种类型的分支跳转。

我们都知道要想在一个函数内进行跳转,可以使用 goto 语句(不知怎么该语句在中国学生眼中就是臭名昭著,几乎所有国内教材都一刀切地教大家尽量不要使用它,但在我看来,这根本不是语言的问题,而是使用该语言的人,看看 Linux 内核中遍地是 goto 语句的应用吧!),但如果从一个函数内跳转到另一个函数的某处,goto 是不能完成的,那该如何实现呢?

函数原型

#include <setjmp.h>
int setjmp(jmp_buf env);

setjmp 函数的功能是将函数在此处的上下文保存在 jmp_buf 结构体中,以供 longjmp 从此结构体中恢复。

  • 参数 env 即为保存上下文的 jmp_buf 结构体变量;
  • 如果直接调用该函数,返回值为 0; 若该函数从 longjmp 调用返回,返回值为非零,由 longjmp 函数提供。根据函数的返回值,我们就可以知道 setjmp 函数调用是第一次直接调用,还是由其它地方跳转过来的。
void longjmp(jmp_buf env, int val);

longjmp 函数的功能是从 jmp_buf 结构体中恢复由 setjmp 函数保存的上下文,该函数不返回,而是从 setjmp 函数中返回。

  • 参数 env 是由 setjmp 函数保存过的上下文。
  • 参数 val 表示从 longjmp 函数传递给 setjmp 函数的返回值,如果 val 值为0, setjmp 将会返回1,否则返回 val。
  • longjmp 不直接返回,而是从 setjmp 函数中返回,longjmp 执行完之后,程序就像刚从 setjmp 函数返回一样。
#include <stdio.h>    
#include <setjmp.h>    
#include <windows.h>  
   
jmp_buf jmpbuffer;  
int i = 0;  
void test_jmp()  
{  
    ++i;  
    longjmp(jmpbuffer, i);  //跳转到setjmp处  
}  
   
int main(int argc, char **argv)  
{  
    int  ret = 0;  
    if ((ret = setjmp(jmpbuffer)) != 0) //类似于goto所用的tag,告诉longjmp应该返回到哪里    
    {  
        printf("jmp:%d\n", ret);  
        Sleep(200);  
    }  
    test_jmp();  
    return 0;  
}

 

以提取蝙蝠魔的攻击状态下的图片为例子。

首先使用WZCompare或者WZCompareR2等工具打开MapleStory的WZ文件。

Wz文件是MapleStory的基础文件,使用wizet公司为扩展名来加密、加压游戏资源,以减少游戏资源所占用的空间以及防止有人对wz文件作非法的修改,简单的说冒险岛这款游戏所有的图片、音乐、脚本等资源都包含在Wz文件中。

一个常规的MapleStory客户端内包括以下几个wz文件:

wz文件名
内容介绍
Base.wz
wz文件全体列表,不包括任何资源文件
Character.wz
游戏角色形象资源,包括人物发型、衣服、鞋子、武器等,另外坐骑、称号都在该文件内
Effect.wz
一些游戏效果,例如一些职业的剧情大图、人物身边的某些特效图
Etc.wz
这里包含的资源较少,列表数据较多
Item.wz
各种物品图标资源、椅子资源等
List.wz
暂不明用处的列表wz,后期已被删除
Map.wz
游戏地图资源,包括背景、前景、路面、摆设物、世界地图等
Mob.wz
怪物资源图
Morph.wz
角色变身形象资源图
Npc.wz
NPC的资源图
Quest.wz
游戏任务相关文字内容
Reactor.wz
敲击物(反应器)的资源图,例如一些需要普通攻击敲打的木箱等
Skill.wz
包含各职业技能图、怪物技能图等
Sound.wz
声音资源,包含各个地图的背景音乐、技能音效、界面音效等
String.wz
包含一些物品、地图、怪物、NPC名称等文字资源
TamingMob.wz
原用于归类坐骑图片资源,后来的坐骑图片资源都归类至Character.wz文件了
UI.wz
界面相关资源,包括游戏界面、职业创建界面、名片对话框、商城界面、鼠标指针等

在这里我们要提取的是怪物的资源图,所以应该去Mob.wz中寻找。

在这之前,我们先去String.wz中寻找到Mob.img.xml,从而能够找到怪物和对应结点的关系。

在这里我们发现蝙蝠魔的ID是9500171。

于是我们就可以去Mob.wz中寻找9500171.img啦。

如图所示,在9500171.img中还分有attack1,attack2,die1,fly,hit1等不同的分支,代表怪物在不同状态下的图。

MapleStory的怪物看起来都是动起来的,实际上是由图片一帧一帧连接起来的,需要gif的话把这些图按顺序拼起来就好啦。

 

按位运算

C语言有这些按位运算的运算符

  • &   按位的与
  • |    按位的或
  • ~  按位取反
  • ^   按位的异或
  • << 左移
  • >> 右移

按位与&

  • 如果x的第i位是1且y的第i位是1,那么(x&y)的第i位是1,否则的话(x&y)的第i位是0
  • 按位与常用于两种应用:
  • 让某一位或某些位为0
  • 取一个数中的一段

按位或|

  • 如果x的第i位是1或y的第i位是1,那么(x|y)的第i位是1,否则的话(x|y)的第i位是0
  • 按位或常用于两种应用:
  • 让某一位或某些位为1
  • 把两个数拼起来

按位取反~

  • 把1位变0,0位变1
  • 想要得到全部位为1的数:~0

逻辑运算VS按位运算

  • 对于逻辑运算,它只看到两个值:0和1
  • 可以认为逻辑运算相当于把所有非0值都变成1,然后做按位运算

按位异或

  • 如果x的第i位和y的第i位相等,那么(x^y)的第i位是0,否则的话(x^y)的第i位是1
  • 如果两个位相等,那么结果为0;不相等,结果为1
  • 对一个变量用同一个值异或两次,等于什么也没做

曾经面试金山WPS的时候有一道题问到:不使用额外的空间,交换两个整形数字。

有两种方法

方法一:算术方法

x = x + y;
y = x - y;
x = x - y;

方法二:异或方法

x = x^y;// 只能对int,char..
y = x^y;
x = x^y;

移位运算:左移<<

  • i << j
  • i中所有的位向左移动j个位置,而右边填入0
  • 所有小于int的类型,移位以int的方式来做,结果是int
  • x = x<<1 等价于 x = x*2
  • x = x<<n 在范围内等价于x = x*(2的n次方)

移位运算:右移>>

  • i >> j
  • i中所有的位向右移j位
  • 所有小于int的类型,移位以int的方式来做,结果是int
  • 对于unsigned的类型,左边填入0
  • 对于signed的类型,左边填入原来的最高位
  • x = x>>1 等价于 x = x/2
  • x = x>>n 等价于 x = x/(2的n次方)

no zuo no die

  • 移位的位数不要用负数,这是没有定义的行为

利用按位与和移位操作实现输出一个数的二进制:

#include<stdio.h>

int main(int argc,int *argv[])
{
    int number;
    scanf("%d",&number);
    unsigned int mask = 1;
    mask = mask << 31;
    while(mask)
    {
        if(number & mask)
        {
            printf("1");
        }
        else
        {
            printf("0");
        }
        mask = mask>>1;
    }
    return 0;
}

 

位段

把一个int的若干位组合成一个结构

如:

struct U0
{
    unsigned int leading : 3;
    unsigned int FLAG1:1;
    unsigned int FLAG2:1;
    int trailing :27;
};

 

  • 这样就可以直接用位段的成员名称来访问,以移位、与、或更方便
  • 编译器会安排其中的位的排列,不具有可移植性
  • 当所需的位超过一个int时会采用多个int

 

文件输入输出

  • 用>和<做重定向
  • 使用FILE

FILE

  • FILE *fopen(const char * restrict path,const char * restrict mode);
  • int fclose(FILE *stream);
  • fscanf(FILE* , …)
  • fprintf(FILE* , …)

打开文件的标准代码

FILE *fp = fopen("file","r");//文件名,只读模式
if(fp){
   fscanf(fp,...);
   fclose(fp);
  }else{
   ...
}

 

例子:(打开当前.c源代码目录下的1.txt文件中的数字并输出到终端。)

#include<stdio.h>

int main(int argc,int *argv[])
{
    FILE *fp = fopen("1.txt","r");
    if(fp)
    {
        int num;
        fscanf(fp,"%d",&num);
        printf("%d\n",num);
        fclose(fp);
    }
    else
    {
        printf("无法打开文件\n");
    }
    return 0;
}

 

fopen

第一个字符串参数为文件名,第二个字符串参数为模式

  • r   打开只读
  • r+   打开读写,从文件头开始
  • w   打开只写。如果不存在则新建,如果存在则清空
  • w+   打开读写。如果不存在则新建,如果存在则清空
  • a   打开追加。如果不存在则新建,如果存在则从文件尾开始
  • 在上述后面可以加x,代表只新建,如果文件已存在则不能打开

二进制文件

  • 其实所有的文件最终都是二进制的
  • 文本文件无非是用最简单的方式可以读写的文件
  • 而二进制文件是需要专门的程序来读写的文件
  • 文本文件的输入输出是格式化,可能经过转码

文本文件VS二进制文件

  • 文本的优势是方便人类读写,而且跨平台
  • 文本的缺点是程序输入输出需要经过格式化,开销大
  • 二进制的缺点是人类读写困难,可能因为int的大小不一致,大小端等问题导致不跨平台
  • 二进制的优点是程序读写快

程序为什么要文件

  • 配置:Unix用文本,Windows用注册表
  • 数据:稍微有点量的数据都放数据库了
  • 媒体:通过二进制,现实是程序通过第三方库来读写文件,很少直接读写二进制文件了

printf()

格式:%[flags][width][.prec][hlL]type

flag

  • –   左对齐
  • +   在前面放+或者-
  • (space) 正数留空
  • 0   0填充

width和pres

  • number   最小字符数
  • *   下一个参数是字符数
  • .number   小数点后面的位数
  • .*   下一个参数是小数点后的位数

hlL

  • hh   单个字节
  • h   short
  • l   long
  • ll   long long
  • L   long double

type

  • i或d   int
  • u   unsigned int
  • o   八进制
  • x   十六进制
  • X   大写十六进制
  • f或F   float
  • e或E   指数
  • g或G   float
  • a或A   十六进制浮点
  • c   char
  • s   字符串
  • p   指针
  • n   读入/写出的个数

scanf()

格式:%[flag]type

flag

  • *   跳过
  • 数字   最大字符数
  • hh   char
  • h   short
  • l   long,double
  • ll   long long
  • L   long double

type

  • d   int
  • i   整数,可能为十六进制或者八进制
  • u   unsigned int
  • o   八进制
  • x   十六进制
  • a,e,f,g   float
  • c   char
  • s   字符串
  • […]   所允许的字符
  • p   指针

printf()和scanf()的返回值

  • 读入的项目数
  • 输出的字符数
  • 在要求严格的程序中,应该判断每次调用scanf()或printf()的返回值,从而了解程序运行中是否存在问题

在程序的世界里,我们往往在做一些分而治之的事情。

一开始我们写的所有程序都在main()里面,然后写着写着呢我们会觉得main()太大了,于是我们会分出一些函数出来,所以我们有了函数,把一个又一个功能从main()中剥离出来放在函数里面。

后来我们会发现一个.c文件里函数越来越多,于是我们开始把函数从一个.c文件里拿出来放到很多个.c文件中去,可是当我们把函数从一个.c文件里拿出来放到很多个.c文件中去之后,又该怎么组合成一个有效的程序呢?

从编译器的角度来看,一个.c文件是一个编译单元,编译器每次编译只处理一个编译单元,编译完之后形成.o文件(目标代码文件),然后由链接器去链接起来。

头文件

把函数原型放到一个头文件(以.h结尾)中,在需要调用这个函数的源代码文件(.c文件)中#include这个头文件,就能让编译器在编译的时候知道函数的原型,否则程序有可能编译成功,但参数类型是由编译器推测出来的,导致出现异常的情况。

#include

  • #include是一个编译预处理指令,和宏一样,在编译之前就处理了
  • 它把那个文件的全部文本内容原封不动地插入到它所在的地方
  • 所以也不是一定要在.c文件的最前面用#include

“”还是<>

  • #include有两种形式来指出要插入的文件
  • “”要求编译器首先在当前目录(.c文件所在的目录)寻找这个文件,如果没有,到编译器指定的目录去找
  • <>让编译器只在指定的目录去找
  • 编译器知道自己的标准库头文件在哪里
  • 环境变量和编译器命令行参数也可以指定寻找头文件的目录

#include的误区

  • #include不是用来引入库的
  • stdio.h里只有printf()的原型,printf()的代码在另外的地方,某个.lib(Windows)或.a(Unix)中
  • 现在的C语言编译器默认会引入所有的标准库
  • #include<stdio.h>只是为了让编译器知道printf()函数的原型,保证你调用时给出的参数值是正确的类型

不对外公开的函数

  • 在函数前面加上static就使得它成为只能在所在的编译单元中(当前.c文件中)被使用的函数
  • 在全局变量前面加上static就使得它成为只能在所有的编译单元中被使用的全局变量

变量的声明

  • int i;//变量的定义
  • extern int i;//变量的声明

声明和定义

  • 声明是不产生代码的东西
  • 定义是产生代码的东西

标准头文件结构

  • 运用条件编译和宏,保证这个头文件在一个编译单元中只会被#include一次
  • #pragma once也能起到相同的作用,但是不是所有的编译器都支持

编译预处理指令

  • #开头的是编译预处理指令
  • 它们不是C语言的成分,但是C语言离不开它们
  • #define用来定义一个宏
  • #include用来包含一个头文件

C语言程序在编译之前会进行编译预处理,在编译预处理过程中会把所有的#define定义的宏进行替换。

C语言编译过程中会产生一些临时文件,在GCC编译器编译过程中如下:

main.c->main.i->main.s->main.o->a.out

  1. 由源代码main.c进行编译预处理得到main.i
  2. 由编译预处理后的代码文件main.i进行编译得到汇编代码文件main.s
  3. 汇编代码文件main.s做汇编得到目标代码文件main.o
  4. 目标代码文件main.o进行链接形成可执行文件a.out

#define

  • #define <名字><值>
  • 注意没有结尾的分号,因为不是C的语句
  • 名字必须是一个单词,值可以是各种东西
  • 在C语言的编译器开始编译之前,编译预处理程序会把程序中的名字换成对应的值,仅仅是做的完全的文本替换
  • 使用gcc –save-temps可以保存编译过程中的临时文件

  • 如果一个宏的值中有其他的宏的名字,也是会被替换的
  • 如果一个宏的值超过一行,最后一行之前的行末要加\
  • 宏的值后面出现的注释不会被当作宏的值的一部分

没有值的宏

  • #define _DEBUG
  • 这类宏是用于条件编译的,后面有其他的编译预处理指令来检查这个宏是否已经被定义过了
  • 在金山WPS实习开发WPS for Mac的时候遇到过,只有在Mac环境下编译才执行的一段代码

预定义的宏

  • __func__ //函数的函数名
  • __LINE__ //源代码文件的行号
  • __FILE__ //源代码文件的文件名
  • __DATE__ //编译时的日期
  • __TIME__ //编译时的时间
  • __STDC__ //判断该文件是不是标准C程序,当要求程序严格遵循ANSIC标准时该标识符被赋值为1
#include<stdio.h>

int dxf(void);

int main(int argc,int *argv[])
{
    dxf();
    return 0;
}

int dxf(void)
{
    printf("%s:%d\n",__FILE__,__LINE__);//输出源代码文件名和目前的行号
    printf("%s\n",__func__);//输出函数名
    printf("%s,%s\n",__DATE__,__TIME__);//输出编译的日期和时间
}

 

运行结果如下:

带参数的宏和像函数的宏

  • #define cube(x) ((x)*(x)*(x))
  • 宏可以带参数

由于预编译过程中#define仅仅是简单的文本替换,所以容易出现运算优先级问题,因此在定义带参数的宏的时候应该遵循一些原则

带参数的宏的原则

  • 一切都要括号(整个值要括号,参数出现的每个地方都要括号)
  • #define RADTODEG(x) ((x)*57.29578)

带参数的宏

  • 可以带多个参数,如#define MIN(a,b) ((a)>(b)?(b):(a))
  • 也可以组合嵌套使用其他宏
  • 在大型程序的代码中使用非常普遍
  • 部分宏会被inline函数替代

宏的缺点

  • 宏的参数没有类型检查,处理不了特殊的输入,而内联函数inline的引入正是为了解决这个问题

宏展开的灵活运用

在Arduino的Ethernet库的w5100.cpp里有这样的函数调用:

writeTMSR(0x55);

但是遍寻整个.cpp和对应的w5100.h也找不到这个writeTMSR()函数,即使把所有的源代码目录拿来搜索一遍都没有。但是,编译显然是通过了的,那么,这个函数在哪里呢?

在w5100.h,我们发现了这样的代码:

#define __GP_REGISTER8(name, address)             \
  static inline void write##name(uint8_t _data) { \
    write(address, _data);                        \
  }                                               \
  static inline uint8_t read##name() {            \
    return read(address);                         \
  }

于是,在w5100.h里接下去的代码:

__GP_REGISTER8 (TMSR,   0x001B);    // Transmit memory size

在编译预处理后,就会被展开成为:

static inline void writeTMSR(uint8_t _data) {
    write(0x001B, _data);            
}
static inline uint8_t readTMSR() {
    return read(0x001B);             
}

其中##是一种分隔连接方式,它的作用是先分隔,然后进行强制连接。

全局变量

  • 定义在函数外面的变量是全局变量
  • 全局变量具有全局的生存期和作用域,它们与任何函数都无关,在任何函数内部都可以使用它们

例子:

#include<stdio.h>

int f(void);
int gAll = 12;

int main(int argc,int *argv[])
{
    printf("in %s gAll=%d\n",__func__,gAll);
    f();
    printf("in %s gAll=%d\n",__func__,gAll);
    return 0;
}

int f(void)
{
    printf("in %s gAll=%d\n",__func__,gAll);
    gAll = gAll + 2;
    printf("in %s gAll=%d\n",__func__,gAll);
    return gAll;
}

其中__func__为当前函数的名字。

该代码的输出

说明全局变量和任何函数都没有关系。

全局变量初始化

  • 没有做初始化的全局变量会得到0值
  • 没有做初始化的指针会得到NULL值
  • 只能用编译时刻已知的值来初始化全局变量
  • 它们的初始化发生在main函数之前

被隐藏的全局变量

  • 如果函数内部存在与全局变量同名的变量,则全局变量被隐藏

静态本地变量

  • 在本地变量定义时加上static修饰符就成为静态本地变量
  • 当函数离开的时候,静态本地变量会继续存在并保持其值(生存期全局,作用域本地)
  • 静态本地变量的初始化只会在第一次进入这个函数时做,以后进入函数时会保持上次离开时的值
  • 静态本地变量实际上是特殊的全局变量,它们位于相同的内存区域

例子:

#include<stdio.h>

int f(void);

int main(int argc,int *argv[])
{
    f();
    f();
    f();
    return 0;
}

int f(void)
{
    static int all = 1;
    printf("in %s all=%d\n",__func__,all);
    all = all + 2;
    printf("in %s all=%d\n",__func__,all);
    return all;
}

 

运行结果如下:

 

返回指针的函数

  • 返回本地变量的地址是危险的
  • 返回全局变量或静态本地变量的地址是安全的
  • 返回在函数内malloc的内存是安全的,但是容易造成问题
  • 最好的做法是返回传入的指针

Tips

  • 不要使用全局变量来在函数间传递参数和结果
  • 尽量避免使用全局变量
  • 使用全局变量和静态本地变量的函数是线程不安全的