鼠年大吉

发表于 2020-01-24 更新于 2023-12-22 分类于 Miscellaneous 本文字数： 418 阅读时长 ≈ 2 分钟

不多说了, 就祝各位鼠年大吉吧.

#include<stdio.h>
int main(){int O=__LINE__;
#define OO putchar
#define Oo  *
#define O0 +
#define O00 -
#define OOO /
OO(O Oo  O Oo  O Oo  (O O0 O OOO O) Oo  (O O0 O OOO O));
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O00 O O00 O OOO O);
OO(O Oo  O Oo  O Oo  O Oo  (O Oo  O Oo  O O00 O OOO O));
OO(O Oo  O Oo  O Oo  O Oo  (O Oo  O Oo  O O00 O OOO O));
OO((O Oo  (O O0 O O0 O) O00  O  OOO  O) Oo  (O Oo  (O O0 O O0 O) O00 O OOO O));
OO(O Oo  O Oo  O Oo  O Oo  O);
OO((O Oo  O Oo  O O00 O OOO O) Oo  (O Oo  (O O0 O O0 O) O00 O OOO O));
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O0 (O Oo  (O O0 O O0 O) O00 O OOO O));
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O0 (O Oo  (O O0 O OOO O) Oo  (O O0 O OOO O)) O00 O OOO O);
OO((O Oo  O O0 O OOO O) Oo  (O Oo  O Oo  (O O0 O O0 O OOO O) O0 O O0 O OOO O));
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O0 O OOO O);
OO(O Oo  O Oo  O Oo  O Oo  O);
OO((O O0 O OOO O) Oo  (O O0 O OOO O) Oo  O Oo  (O O0 O O0 O OOO O) O00 O OOO O);
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O0 O OOO O);
OO(O Oo  O Oo  (O Oo  O O0 O OOO O) Oo  (O Oo  O O0 O OOO O) O00 O O00 O OOO O);
OO((O Oo  O O0 O OOO O) Oo  (O Oo  O Oo  (O O0 O O0 O OOO O) O0 O O0 O OOO O) O00 O OOO O);
OO(O Oo  O Oo  O Oo  O Oo  O O0 O OOO O);
}

链表参考实现

发表于 2019-11-12 更新于 2023-12-22 分类于教学本文字数： 628 阅读时长 ≈ 2 分钟

链表参考实现代码

处理了传入非法参数等大部分特殊情况.

#include <stdio.h>
#include <stdlib.h>

struct N{
    int value;
    struct N *next;
};
typedef struct N * nodePtr;
typedef struct N node;

/**
 * 根据数组创建长度为n的链表
 * @param value
 * @param n
 * @return
 */
nodePtr buildByArray(int value[], int n){
    nodePtr head = (nodePtr)malloc(sizeof(node));
    nodePtr tail = head;
    nodePtr t = NULL;
    int i = 1;
    head->next = NULL;
    head->value = value[0];
    tail = head;
    for(i = 1; i < n; ++ i){
        t = (nodePtr)malloc(sizeof(node));
        t->value = value[i];
        t->next = NULL;
        tail->next = t;
        tail = t;
    }
    return head;
}

/**
 * 构建一个值全部为0的长度为n的链表
 * @param n
 * @return
 */
nodePtr buildByZeros(int n){
    nodePtr head = (nodePtr)malloc(sizeof(node));
    nodePtr tail = head;
    nodePtr t = NULL;
    int i = 1;
    head->next = NULL;
    head->value = 0;
    tail = head;
    for(i = 1; i < n; ++ i){
        t = (nodePtr)malloc(sizeof(node));
        t->value = 0;
        t->next = NULL;
        tail->next = t;
        tail = t;
    }
    return head;
}

/**
 * 在链表头部添加一个节点
 * @param head
 * @param value
 * @return nodePtr
 */
nodePtr insertAsHead(nodePtr head, int value){
    nodePtr p = (nodePtr)malloc(sizeof(node));
    p->value = value;
    p->next = head;
    return p;
}

/**
 * 在链表尾部添加一个新节点
 * @param head
 * @param value
 * @return
 */
nodePtr insertAsTail(nodePtr head, int value){
    nodePtr h = head;
    nodePtr p;
    while(head->next != NULL){
        head = head->next;
    }
    p = (nodePtr)malloc(sizeof(node));
    p->value = value;
    p->next = NULL;
    head->next = p;
    return h;
}

/**
 * 在指定节点后面插入一个新节点
 * @param after
 * @param value
 * @return
 */
nodePtr insertAfter(nodePtr after, int value){
    nodePtr tmp;
    if(after == NULL){
        return NULL;
    }
    tmp = (nodePtr)malloc(sizeof(node));
    tmp->value = value;
    tmp->next = after->next;
    after->next = tmp;
    return tmp;
}

/**
 * 返回第一个指定值的value
 * @param head
 * @param value
 * @return
 */
nodePtr findByValue(nodePtr head, int value){
    nodePtr p = head;
    while(p != NULL){
        if(value == p->value){
            return p;
        }
        p++;
    }
    return NULL;
}


/**
 * 返回链表中的第ID个节点
 * @param head
 * @param id
 * @return
 */
nodePtr findByIndex(nodePtr head, int id){
    nodePtr p = head;
    if(id < 0) return NULL;
    while(id--){
        if(p == NULL) break;
        p = p->next;
    }
    return p;
}

/**
 * 删除链表中第一个指定值的节点
 * @param head
 * @param value
 * @return
 */
nodePtr delByValue(nodePtr head, int value){
    nodePtr p = head;
    nodePtr t;
    if(head == NULL){
        return NULL;
    }
    if(head->value == value){
        p = head->next;
        free(head);
        return p;
    }
    while(p->next != NULL){
        if(value == p->next->value){
            t = p->next;
            p->next = t->next;
            free(t);
            return head;
        }
        p++;
    }
    return head;
}

/**
 * 删除链表中第ID个节点
 * @param head
 * @param id
 * @return
 */
nodePtr delByIndex(nodePtr head, int id){
    nodePtr t = NULL;
    nodePtr p;
    if(head == NULL){
        return NULL;
    }
    p = NULL;
    if(id == 0){
        p = head->next;
        free(head);
        return p;
    }
    p = findByIndex(head, id-1);
    if(p == NULL){
        return head;
    }
    t = p->next;
    p->next = t->next;
    free(t);
    return head;
}

/**
 * 打印链表
 * @param head
 */
void printList(nodePtr head){
    while(head != NULL){
        printf("%d ", head->value);
        head = head->next;
    }
    printf("\n");
}

/**
 * 删除链表, 释放空间
 * @param head
 */
void freeList(nodePtr head){
    nodePtr p = head;
    while(p != NULL){
        free(head);
        head = p->next;
        p = p->next;
    }
}

int main(){
    nodePtr head = NULL;
    int values[] = {0,1,2,3,4,5,6,7,8,9,0};
    head = buildByArray(values,11);
    printList(head);
    insertAfter(head->next->next->next,5);
    printList(head);
    head = delByIndex(head,0);
    printList(head);
    head = delByValue(head,1);
    printList(head);
    printList(findByValue(head, 8));
    freeList(head);
    return 0;
}

字符串,字符数组,字符指针

发表于 2019-11-12 更新于 2023-12-22 分类于教学本文字数： 959 阅读时长 ≈ 3 分钟

字符, 字符数组, 字符指针和字符串.

上回说到, 有一种很常见的情境下我们一直在使用字符数组, 但调用函数的时候并没有传入数组的大小. 这个情景就是字符串.

实际上, c语言标准中并没有所谓的"字符串"类型, 所谓的字符串都是一定字符数组.

调用字符串相关函数的时候, 传入的都只是数组名字, 正如上篇推送所说的, 对于接受数组为参数的函数, 参数实际上是指针. 字符串相关函数都只是读取指针指向的值, 让指针+1, 等到指针指向的值为'\0'为止. 因此, 字符串必须以\0结尾.

也正因为如此, 一个字符指针可以作为参数传入如puts等相关函数. 如, 对于一个字符串数组(char的二维数组)char data[100][100], data[0]是这个二维数组的第0个元素, 也就是一个一维数组 (char [100]). data[0]就是指向这个一维数组首元素的指针. 比如, 求这个字符串数组中最长的一个字符串可以这么做:

char * getLongest(char strs[][200], int n){
    注释: 还记得为啥要写第二维的大小吗?
    char * ret = strs[0];
    int i = 0;
    for(i = 0; i < n; ++ i){
        if(strlen(s[i]) > strlen(ret)){
            ret = s[i];
        }
    }
    return ret;
}

值得注意的是, 返回的ret是一个指向字符串数组(char的二维数组)中的某个字符串的首元素的地址, 并不是复制了一份字符串返回. 如果修改了原先字符串数组中的值, 从ret指针读取到的值也会一样改变.

在字符串数组中, 漏写\0会引发更加奇怪的问题. 对于以下代码:

char strs[5][5] = {'\0'};
int i,j;
for(i = 0; i < 5; ++ i)
    for(j = 0; j < 5; ++ j){
        strs[i][j] = '*';
    }
for(i = 0; i < 5; ++ i){
    puts(strs[i]);
}

他会输出什么内容呢? 大概率是类似下面这样的东西:

*************************乱码乱码乱码
********************乱码乱码乱码
***************乱码乱码乱码
**********乱码乱码乱码
*****乱码乱码乱码

为什么会出现这种现象呢?

左滑查看答案--------------------------> puts函数会从传入的指针 
左滑查看答案--------------------------> 开始往后遍历输出, 遇到\0
左滑查看答案--------------------------> 才停止输出. 因此, 当他从strs[0][0]
左滑查看答案--------------------------> 打印到strs[0][4]时, 
左滑查看答案--------------------------> 下一个字节实际上是strs[1][0], 
左滑查看答案--------------------------> 仍然不是\0. 后面的几个字符串被
左滑查看答案--------------------------> 打印了好几次. 当打印完全部字符串后, 
左滑查看答案--------------------------> puts会接着往后打印, 由于后面是
左滑查看答案--------------------------> 未初始化的内存, 因此打印出来乱码, 
左滑查看答案--------------------------> 直到某个地方恰巧为\0才停止.

还有一个有意思的问题, 那就是以下代码是什么意思:

char str[100];
gets(str);
char * p = str;
while (*p){
    ...
    do something...
    ...
    ++p;
}

我们来逐层分析这一句: p是一个指向char*的指针, *p是这个char变量所存储的值. while(*p) 就是当这个char变量存储的值不为0的时候继续循环. (非0就是真). 又由于'\0的ascii码是0, 因此, 这句话的全部意思是当p指向的char为\0时退出循环.

下面是附录: 增强可读性后的几个字符串相关函数的实现.

int strlen(char *org)
{
    char *s = org;
    while (*s){
        s++;
    }
    s = s - 1;
    return s - org;
}
char *strcpy(char *ret, char *s2)
{
    char *s1 = ret;
    while ((*s1 = *s2) != '\0'){
        s1++;
        s2++;
    }
    return ret;
}
char *strcat(char *ret, char *s2)
{
    char *s1 = ret;
    while (*s1 != '\0'){
        s1++;
    }
    s1--;
    while (*s1 = *s2){
        s1++;
        s2++;
    }
    return ret;
}

指针数组指针数组和数组指针

发表于 2019-11-10 更新于 2023-12-22 分类于教学本文字数： 2.3k 阅读时长 ≈ 8 分钟

指针, 数组, 指针数组, 和数组指针

这里, 更多的并不是教给大家什么是数组, 什么是指针数组. 更多的, 是教给大家理解数组和指针的本质.

指针

详见/2019/11/09/zhi-zhen-shi-sha/

数组

一维数组

定义:

1	元素类型数字名称[数组大小];

使用:

对于定义如下的一个数组:

1	int data[10] = {0};

使用元素:

1	data[i] = 1;

使用名字:

data 是数组"首元素"的指针

1 2	printf("%p", data); printf("%p", &data[0]);

注意, data是"右值", 不可赋值.

~~不知道右值是啥的快去看上一篇推送~~

地址运算:

+ 1```在数值上等于`data`的值+4. (int占4个字节)


复习: 指针+1, 实际指向的地址加了`sizeof(指向的类型)`.

#### 二维数组

二维数组就是"数组的数组". 如何理解这一点呢?

##### 二维数组的定义:
```cpp
int data[5][10];

上述代码定义了一个数组, 这个数组的元素是"10个int类型构成的数组". 如何理解? 数组定义的阅读要"从里向外阅读". 例如:

int data[5][10];

定义一个数组, 名字叫data, 大小为5

int data[5][10];

数组的元素的类型是int [10], 也就是大小为10的int数组.

数据类型: 如果不好理解 int [10] 是一个类型, 只需要记住去掉定义变量时候的变量名字, 剩下的东西就是一个类型. 如:

对于 int data[10], 去掉data后剩下的部分int [10] 就是变量类型.

同理, 下面要讲到的 int (*)[10] 也是变量类型

二维数组元素的使用和一位数组基本相同, 这里不再赘述.

二维数组的地址的使用:

小问答: 对于定义如下的数组:

1	int data[10][20] = {0};

data+1的地址数值上等于多少?

1
2
3

A. data + 4(数值上)
B. data + 40(数值上)
C. data + 80(数值上)

1	左滑查看答案 ----------------------------------------> 由于data是"元素为int [20]"的数组, 所以 sizeof(data的元素) 是 20*4 = 80, 所以 data+1 的地址数值上等于 data + 80.

复习: 对于如上定义, data 的元素的类型为"int [20]". 实际上, 如果通过下标计算地址, 应该如下计算:

1	data[i][j] == *(data + i) + j;

如何理解上面的代码? *(data + i) 的类型又是什么?

1
2

左滑查看答案 ----------------------------------------> data的元素为 int[20], 因此 *(data + i) 是 data数组的第i个元素, 也就是第i个大小为20的int数组.
左滑查看答案 ----------------------------------------> data[i][j] 是data中的第i个元素的第j个元素. (data的第i个元素是一个一维数组.)

(复习: *运算符是"根据地址取所在那个地址的元素")

通过上面的练习, 相信大家也理解了"二维数组就是元素是数组的数组".

这样子, 也就很容易能理解为什么二维数组作为参数要传入"第二维"的大小了. 对于以下代码:

int func1(int data[]){
这个函数的参数data是一个数组, 元素是int
并不需要知道数组的大小
}
int func2(int data[][20]){
这个函数的参数data是一个数组, 元素是 int[20]
因为需要知道元素的类型, 因此必须知道数组第二维的大小.
}

多维数组

多维数组的理解和二维数组相同, 比如三维数组是"元素为二维数组的数组". 因为并不常用, 这里不再赘述.

数组作为函数参数

首先, 需要说明的一点是, 数组作为函数参数的时候, 对于被调用的函数, 参数是一个指针. 无论传入什么数组, 对于被调用者, 参数的类型都是一个指针. 因此, 以下几个函数原型是等价的:

1
2
3

int foo(int *a, int n);
int foo(int a[], int n);
int foo(int a[10], int n);

而同时, 对于被调用的函数, 参数永远是一个指针, 因此对于上面的第三个函数原型, 传入一个类型为int[20]的数组也是可以编译通过的.

也正因为这个原因, 被调用的函数没有办法知道传入的数组的大小, 也没有办法限制传入的数组的大小, 因此只能显式的传入另一个参数n作为数组大小.

同理, 参数是一个指针, 需要知道指针指向的类型是什么. 这一点也同样可以理解为什么二位数组传参的时候要指定第二维的大小:

1 2	int func2(int data[][20]); int func2(int (*)data[20]);

这两种声明等价. 第二种声明的参数类型是"指向一个int[20]"的指针(也就是下面会讲到的数组指针), 显然, 需要知道指向的数组多大, 因此必须说明第二维的大小.

指针数组

指针数组, 从字面意思来看, 就是元素是指针的数组.

定义:

1	int *data[10] = {NULL};

注意, 一定要初始化, 否则会有问题.

使用:

for(int i = 0; i < 10; ++ i){
    data[i] = (int*)malloc(sizeof(int) * 10);
    还记得为啥要(int*)吗?
}
data[1][2] = 1;

阅读:

对于上面的定义和初始化, data是指针数组的名字, 也就是指向指针数组首元素的指针. (指针的指针). data[i] 是data这一个数组的第i个元素, 也就是一个指向int的指针. 指针可以当成数组来使用, data[i][j] 和 *(data[i] + j)是等价的.

经过上述代码创建的一个指针数组data的使用和int data[10][10]基本相同, 区别在于后者保证数组和数组之间的内存地址是连续的. data[0][9] 和 data[1][0] 是连续的, 而如果使用指针数组方式创建的data, 不能保证 data[0][9] 和 data[1][0] 在内存上连续.

数组指针

数组指针, 从字面意思来看就是"指向数组的指针".

定义

1	int data(*)[10] = NULL;

上述代码定义了一个指向长度为10的int数组(int [10])的指针.

使用

一般, 我们并不会使用到数组指针. 当且仅当一个情况下我们会在我们不知不觉的时候使用数组指针:

1 2	int func(int data[][20]){ }

前面提到过, 数组作为参数传入函数的时候, 对于被调用的函数参数就是指针. 因此, 这里参数是一个"元素为int[20]"的数组(数组的数组), 因此, 在函数内部, data实际上就是一个"指向int[20]"的指针(int (*)[20]).

一般并不需要使用数组指针的性质, 当编译器报错有int (*)[20]相关的东西时, 知道这是一个指向数组的指针即可.

注意

数组指针和指针数组的定义特别相似.

1 2	int data[10] = {NULL}; int ()data1[10] = NULL;

上述代码中, data是指针数组(指针的数组), data1是数组指针(数组的指针)

不要对数组和指针使用sizeof.

上面提到过, 对于被调用的函数, 数组参数实际上就是一个指针, 在函数内部对数组进行sizeof获取到的其实是指针占用的内存的大小(4字节或8字节). 同时, 对数组和指针使用sizeof会导致各种神奇的行为, 因此尽量不要对数组和指针使用sizeof. 当且仅当如malloc(10 * sizeof(int))时使用sizeof.

小测验

1	int data[10];

上述代码中, data的类型是?

1	左滑查看答案 ----------------------------------------> int*

1 2	int ()[5] int [5]

上述两个类型中, 哪个是数组指针, 哪个是指针数组?

(复习: 定义变量的语句去掉变量名字剩下的部分就是变量类型. 如int *data[5]去掉data后剩下的int *[5] 是一个类型.)

1	左滑查看答案 ----------------------------------------> 前者是数组指针, 后者是指针数组

1	int data[5][5];

上述代码中, data的类型是?

1	左滑查看答案 ----------------------------------------> int (*)[5], 也就是指向 int[5] 的指针

1	int data[10][20];

data+1的值和 data的值在数值上差多少?

1	左滑查看答案 ----------------------------------------> 差一个 sizeof(int [20]), 也就是80字节.

鸣谢:

感谢云朵学长对本人不厌其烦的教导.

感谢优秀的Z同学在我找C语言文档时慷慨提供的C Primer Plus.

感谢我的舍友以及另一位优秀的Z同学的审稿.

(你居然看到了这里, 那就说一下吧). 有一个很常见的, 数组名字作为参数同时不传入数组大小的使用情景, 同学们知道是什么吗?

字符串相关函数. gets, puts, strlen, scanf等函数均只接受字符串名字作为参数, 他们是怎么获取字符串长度信息的呢?

~~明天再发~~

C++与C的区别

发表于 2019-11-09 更新于 2023-12-22 分类于教学本文字数： 315 阅读时长 ≈ 1 分钟

CPP 与 C

给算法竞赛入门阶段的同学的快速 c 转 c++ 速效救心丸。不适合系统学习使用。

区别1: 头文件不同

C++头文件没有.h

C语言:
#include <stdio.h>

C++语言:
#include <cstdio>
#include <stack> // C++头文件

如果要在c++代码中引用c语言的库, 去掉.h, 并在最前面加上c.

string.h >>> cstring
stdio.h  >>> cstdio
stdlib.h >>> cstdlib
...

区别2: 读入输出方式不同.

c++语言中只要引用了库就仍然可以用c语言的输入输出函数.

C++:
#include <iostream>
using namespace std;
int main(){
    int a;
    char b;
    char str[100] = {0};
    cin>>a>>b>>str;
    // 读入 cin 右箭头 变量名
    // 不需要&
    cout<<a<<b<<str<<endl;
    // 输出 cout 左箭头 变量名
    // endl和输出"\n"几乎等价
}

区别3: 命名空间

死记硬背即可, c++代码需要在引用头文件后添加一行

1	using namespace std;

~~非竞赛代码不推荐使用，会污染命名空间。~~

区别4: 布尔类型

c++语言自带布尔类型. 存储的是真和假两种情况.

bool a = false; //假, 与0等价
a = true; // 真, 与1等价
// 注意不要写为ture和flase
if(a){
    foo();
}else{
    bar();
}

~~c语言引用stdbool.h后也有, 但是课内不讲~~

Lecture1 笔记

发表于 2019-11-09 更新于 2023-12-22 分类于教学本文字数： 589 阅读时长 ≈ 2 分钟

递归

把大问题分解为多个相似的小问题.

电影院问题: 获取人数, 如何获取?

1
2
3

函数 获取人数:
    如果 前面没人 返回1
    否则 问前面的人 前面有几个人 返回这个数+1

汉诺塔问题:

定义一个函数, 移动n个饼. 如果n=1, 直接移动即可. 如果n!=1, 那么对于上面的n-1个饼, 最下面的饼 并不会影响上面n-1个饼的移动. 所以, 可以递归调用此函数, 移动n-1个饼.

定义函数 移动饼(从哪儿,到哪儿,借助哪儿,饼数量):
    如果 饼数量 == 1 
        那么 把这个饼从"从哪儿"移动到"到哪儿"
    否则
        把 n - 1 个饼 从"从哪儿"移动到"借助哪儿"
        这个时候"从哪儿"这根柱子上的最后一个饼可以直接移动到"到哪儿".
        所以这时候, 移动第n个饼从"从哪儿"移动到"到哪儿"
        然后移动 n - 1 个饼从"借助哪儿"到"到哪儿"
        这个时候就完成了移动n个饼.

放苹果问题:

定义一个函数用于解决"n个苹果放到m个盘子里"问题.

那么这个问题, 可以分解为以下两种子情况:

每一个盘子内都放一个苹果
接下来不再对某个盘子放苹果

定义函数 放苹果(苹果数, 盘子数):
    如果 苹果数 == 0 或者 盘子数 == 1
        返回1
    如果苹果数小于盘子数:
        // 肯定至少有盘子数-苹果数个盘子空着
        返回 放苹果(苹果数, 苹果数)
    返回 放苹果(苹果数-盘子数, 盘子数) // 每一个盘子内都放一个苹果
         + 放苹果(苹果数, 盘子-1) // 接下来不再对某个盘子放苹果

括号匹配问题:

给出一个括号序列, 判断是否是匹配的括号序列.

先读入字符串, 每次处理一个字符. 如果是左括号, 就入栈. 如果是右括号, 首先判断栈中是否有元素(s.size() > 0), 如果有元素再判断栈顶元素是否是当前右括号对应的左括号. 如果是, 就把左括号出栈. 如果不是, 说明这个括号序列并不美观.