Реализация дерева с картой без создания новых узлов - PullRequest
Новая
       11

Реализация дерева с картой без создания новых узлов

0 голосов
/ 05 июня 2018

Я пытался реализовать структуру данных Trie и написал следующий код: 

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

struct trie_node{
  map<char, trie_node> child;
  int pos=-1;
};

map<char, trie_node> baap;

void lex_insert(string s, int pos){ // lexiographically insert into map
  trie_node t = baap[s[0]];
  for(int i=1; i<s.size(); i++){
    t = t.child[s[i]];
  }
  t.pos = pos;
}

int find(string s, int r){  // find in trie structure
  trie_node t = baap[s[0]];
  int pos = t.pos;
  for(int i=1; i<s.size(); i++){
    if(t.child.find(s[i])!=t.child.end()){
      t = t.child[s[i]];
      if(t.pos<=r)
        pos = t.pos;
    }
    else
      return pos;
  }
  return pos;
}

void ans(int &found, string s){ // find lexiographically matching prefix
  trie_node t = baap[s[0]];
  if(found<0){
    while(t.pos<0){
      auto x = t.child.begin();
      t = x->second;
    }
    found = t.pos;
  }
}

int main(){
  int n;  cin>>n;
  vector<string> vs(n);
  for(int i=0; i<n; i++){
    cin>>vs[i];
    lex_insert(vs[i],i);
  }
  int found = 0;
  int q;  cin>>q;
  for(int i=0; i<q; i++){
    int r; string p;
    cin>>r>>p;
    found = find(p,r);
    ans(found, p);
    cout<<vs[found]<<'\n';
  }
}

Пожалуйста, обратите внимание на lex_insert() Код выполняется без ошибок, хотя при попытке разыменовать карту - baap, появляются ошибки сегментации.Я думаю, это потому, что я не создавал новые узлы на каждом уровне в lex_insert, как я видел в некоторых кодах.Но тогда карта должна делать динамическое размещение.Может кто-нибудь объяснить, почему я не могу получить доступ к элементам карты - baap?

Примечание. Это не точная трия, но вытекает из нее

1 Ответ

0 голосов
/ 05 июня 2018

Одна из возможных причин вашей проблемы: 

trie_node t = baap[s[0]];

Здесь t будет копией из baap[s[0]].Какие бы изменения вы ни внесли в t, они не будут отражены в оригинале.

Поскольку вы позже в цикле переназначаете t (снова копируете), вы не можете использовать ссылки (ссылка не может бытьотскок).Вместо этого вы должны использовать указатели .Либо сохраняйте указатели на картах, либо используйте оператор address-of, чтобы получить указатель: 

trie_node* t = &baap[s[0]];  // Get a pointer to the node

Что касается сбоя, то, если вышеперечисленное не решит его, тогда вам следует научитесь отлаживать ваши программы .Особенно в случае сбоев вы должны узнать, как использовать отладчик для обнаружения сбоя в действии и как определить, где в вашем коде это происходит.

...