二叉查找树

关于传参的两种方式 传值与传址 的深入理解 (附 hdu3999

Posted on

真的真的真的真的好久没码了………………

最近因为要复习数据结构所以才兴起想要码一些跟考试相关的

于是找了一下 BST 和 AVL 的题做做 结果一下搜就找到了 hdu3999

解法很简单 只要建立一个 BST 再对其先序遍历即可
然而…………

问题出在这个代码上

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(root,tmp);
            if(root==NULL)
                cout<<1111<<endl;
        }
        FirstOrderSearch(root);
        puts("");
    }
    return 0;
}

插入函数如下

void InsertNode(node* now,int value)
{
    if(now==NULL)
    {
        now = new node;
        now -> value = value;
        return ;
    }
    else if(value < now -> value)
        InsertNode(now->left,value);
    else if(value > now -> value)
        InsertNode(now -> right, value);
}

咋看下真的没什么问题 然而实际上还是会输出n个 1111
这就说明 root 它一直都没有变化

“纳尼不是只要传地址 , 那么这个变量就一定会随之改变的不是么。。。”

想了一下才想通 传参在本质上来说完全只有一种方法 就是传值

传址传址 也只是把指针这个变量的值 给传了过去 而如果我们对这个地址取值那么自然而然的就可以改变这个变量的值

以这里的代码为例 我在主函数中的 root变量初始化为 NULL 传给 InsertNode 变量now拥有了 NULL 但是在这里now的所有变化将根本不会影响到main中的root

换言之 对于指针的传参 只有 *指针(指针所指的值)才会能在全局变化

所以如果要继续我以上的写法 解法有二:

  1. 只要将这个root 这个指针的地址传给函数处理即可
  2. 当然 我也可以在最开始的时候就先把根节点给定义了 再对根节点传参也可

综上

传参在本质上只有将实参的值传给形参 而所谓的传址 我们只能理解成一个小技巧 否则会带来很多习惯性误导

AC Code

法 1 :(因为第一次这么写 运算符的等级忘了 所以保险点就都加了括号…………)

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
int n;

struct node
{
    int value;
    node *left;
    node *right;
    node():left(NULL),right(NULL) {}
};

void InsertNode(node** now,int value)
{
    if(*now==NULL)
    {
        *now=new node;
        (*now)->value=value;
        return ;
    }
    if(value < (*now) -> value)
        InsertNode(&((*now)->left),value);
    else if(value > (*now) -> value)
        InsertNode(&((*now) -> right), value);
}

void FirstOrderSearch(node* now,node* root)
{
    if(now==root)
        printf("%d",now->value);
    else printf(" %d",now->value);
    if(now->left)
        FirstOrderSearch(now->left,root);
    if(now->right)
        FirstOrderSearch(now->right,root);
    delete now;
}

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        node* root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(&root,tmp);
        }
        FirstOrderSearch(root,root);
        puts("");
    }
    return 0;
}
C

setjmp 与 longjmp

Posted on

最近看到C看到一个很让人费解的函数组合 setjmp 和 longjmp 使用方法还是比较简单的
setjmp设置跳跃点 longjmp表示跳跃

具体的操作如下
首先定义一个 唯一的标志性 flag jmp_buf变量
再加上 函数申明 int setjmp(jmp_buf env); void longjmp(jmp_buf env, int value);
当设置 jmp 即第一次执行 setjmp时 函数的返回值都为 0
通过longjmp 跳跃至相同jmp_buf 的setjmp函数里并执行 set_jmp的返回值将变成 long_jmp设置的 value
理解起来后发现实际上是跟 goto 差不多的 但long_jmp 跳得更远一些 goto只限于同一函数内 long_jmp无限制 包括文件

附个代码理解一下

#include <stdio.h>
#include <setjmp.h>
jmp_buf buf;
void haha()
{
    printf("in haha()\n");
    longjmp(buf,1);
    printf("kaonima\n");
}
int tim=0;

int main()
{
    if(setjmp(buf))
    {
        printf("back in main\n");
        tim++;
    }
    else
    {
        printf("first time through\n");
        haha();
    }
    if(tim<3) longjmp(buf,1);
    return 0;
}

结果是

first time through
in haha()
back in main
back in main
back in main

另外 这两个函数一般来说 可用于C中的异常处理

顺便贴个wiki的 告诫 (太专业 也不是很明白……)

longjmp实现了非本地跳转,微软的IA32程序设计环境中正常的"栈卷回"("stack unwinding")因而没有发生,所以诸如栈中已定义的局部变量的析构函数的调用(用于销毁该局部变量)都没有执行。所有依赖于栈卷回调用析构函数所做的扫尾工作,如关闭文件、释放堆内存块等都没有做。但在微软的X64程序设计环境,longjmp启动了正常的"栈卷回"。
如果setjmp所在的函数已经调用返回了,那么longjmp使用该处setjmp所填写的对应jmp_buf缓冲区将不再有效。这是因为longjmp所要返回的"栈帧"(stack frame)已经不再存在了,程序返回到一个不再存在的执行点,很可能覆盖或者弄坏程序栈

值得深究一下的是 jmp_buf 变量在这里立个flag 吧 以后会来补充

C

关于open操作的O_EXCL的存在应用价值理解

Posted on

在我最近学习Linux C的过程中 总是看到这样的打开方式 open(const* pathname,O_CREAT|O_EXCL);

O_CREAT 简单 就是想打开的文件如果不存在的话就会自动创建文件

而 O_EXCL 他的作用就是如果要创建一个文件 并且这个文件已经存在的话 会直接返回 并且 如果打开的文件是符号链接文件的话 也会直接返回

一开始真的感觉莫名其妙

之后搜了一下才知道自己的菜逼思维

如果不加O_EXCL 的话 如果文件存在 那么这个文件依旧会被打开

此时我们假设有这样的一个需求:某个任务只能单个进程处理执行 多进程会影响到该任务的执行

为了不让多进程打开处理这个文件 并且不用O_EXCL的话

可能会这样写

if( access(file, R_OK) == -1 ) /* 首先检查文件是否存在 /
open(file, O_RDWR | O_CREAT,0666); /
如果不存在,那我创建一个这样的文件 /
... /
继续执行任务 */

其实这个逻辑存在一个潜在性错误的

如果当我的进程1执行了access并判断这个文件并不存在 由于操作系统关于多进程的调度策略 若此时进程1暂停 进程2执行 那么进程2也会判定这个文件不存在

结果自然是有两个进程会打开这个文件 这与我们的目标相违背

而相对的 如果我们用了 O_EXCL 我们就把判断和创建放在了一起 就能避免这个错误的发生

小白的粗浅理解,欢迎指正

另外说个题外的内容 傻逼了 看这些源代码的时候一直看到 errno 的判断 然后就傻兮兮的去记所有的错误代码 记到恶心

然后有个煞笔告诉我直接 对 errno.h grep 不就好了

恍然大悟 我真是个智障