注册 登录
编程论坛 数据结构与算法

字典树模板代码里关于链表指针的一个小疑问

lxs_nicecode 发布于 2016-02-17 20:37, 3081 次点击
以HDU的1247题为例
http://acm.hdu.edu.cn/showproblem.php?pid=1247
这是一道字典树的模板题,小弟的AC代码如下:
程序代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 500007
using namespace std;

struct node
{
    int e;
    struct node* next[26];
};
node* root;
char str[MAX][50];

void Insert(char* s)
{
    node* ptr = root;
    for(;*s != '\0';s++)
    {
        int n = *s-'a';
        if(ptr->next[n] == NULL)
            ptr->next[n] = new node();
        ptr = ptr->next[n];
        /*看这里~~~~~

        ptr = ptr->next[n];
        if(ptr == NULL)
            ptr = new node();
        
*/

    }
    ptr->e = 1;
}

bool find2(char* s)
{
    node* ptr = root;
    for(;*s != '\0';s++)
    {
        int n = *s-'a';
        ptr = ptr->next[n];
        if(ptr != NULL) {
            if(ptr->e==1 && *(s+1)=='\0')
                return true;
        }
        else
            return false;

    }
    return false;
}

bool find1(char* s)
{
    node* ptr = root;
    for(;*s != '\0';s++)
    {
        int n = *s-'a';
        ptr = ptr->next[n];
        if(ptr->e==1 && find2(s+1))
            return true;
    }
    return false;
}

int main()
{
    int i = 0;
    root = new node();
    while(scanf("%s",str[i]) != EOF) {
        Insert(str[i]);
        i++;
    }
    for(int j = 0;j < i;j++)
        if(find1(str[j]))
            cout<<str[j]<<endl;
    return 0;
}
我的问题是在Insert函数中的for循环体里面,有两部分代码,一部分是我现在写的(A),一部分是被我注释掉了的(B)
我认为A和B的作用是相同的,但是用A提交的话就能AC而用B提交在自己电脑上测试都不过
不太理解指针一定要先判断有无然后再赋值吗?
3 回复
#2
azzbcc2016-02-18 12:16
程序代码:
#include <iostream>

struct node
{
    int *next;
};

node *root = new node();

int main(void)
{
    int *a = root->next;
    std::cout << a << std::endl;
    std::cout << root->next << std::endl;

    a = new int;
    std::cout << a << std::endl;
    std::cout << root->next << std::endl;
    return 0;
}

#3
lxs_nicecode2016-02-20 11:16
回复 2楼 azzbcc
我懂您的意思,但是为什么会这样?
#4
azzbcc2016-02-22 14:05
a是指针,原本指向的是 root的后驱。new 之后,a的指向改变,不再指向root的后驱。此时再对a进行操作,不会对root的后驱产生任何影响。

是问这个么?
1