Сбалансированная функция поиска в двоичном дереве поиска
Я пишу код для фруктового магазина, где данные каждого пользователя хранятся в двоичном дереве. когда пользователь хочет войти в систему, он должен ввести свое имя пользователя. программа должна найти имя пользователя в дереве и выполнить соответствующую функцию.
Функция поиска возвращает правильное значение, когда имя пользователя отсутствует, и показывает соответствующее сообщение, но не отображает ни сообщения, ни ошибки, когда имя пользователя найдено (в соответствии с программой должно отображаться "Hello"). Используя функцию "inorder", я проверил, правильно ли формируется дерево - оно правильно сформировано. Прикрепленный код.
#include <iostream>
#include<fstream>
#include<string.h>
using namespace std;
class node //Create a class for node.
{ public:
char First_Name[30];
char Last_Name[30];
char Email_id[50];
int long Phone;
char Username[20];
char Location[25];
node *lc;
node *rc;
int h;
friend class avl;
};
class avl //Create a class for avl.
{public:
node* root;
avl()
{
root=NULL; //Initialise root to NULL.
}
node *insert(node *root,char[],char[],char[],char[],char[],int long);
void insert1();
int height(node *);
int bal_fac(node*);
node *LL(node*);
node *LR(node*);
node *RL(node*);
node *RR(node*);
int search(char[]);
node *getinfo(char[]);
void inorder(node*);
};
void avl::inorder(node *root) //To print the inorder sequence.
{
if(root==NULL)
return ;
else
{
inorder(root->lc);
cout<<root->Username<<" ";
inorder(root->rc);
}
}
void avl:: insert1() //Insert1 function to read file contents.
{
char firstname[30]=" ";
char lastname[30]=" ";
char email_id[50]=" ";
int long contact=0;
char name[20];
cout<<endl<<"Enter your First name: ";
cin>>firstname;
cin.ignore();
cout<<endl<<"Enter your Last name: ";
cin>>lastname;
cin.ignore();
cout<<endl<<"Enter your Email id: ";
cin>>email_id;
cin.ignore();
cout<<endl<<"Enter your phone number: ";
cin>>contact;
cin.ignore();
cout<<endl<<"Enter your User name: ";
cin>>name;
cin.ignore();
int len=strlen(name);
len+=4;
char file[len];
fstream myfile;
int i;
for (i=0;i<strlen(name);i++)
{
file[i]=name[i];
}
file[i++]='.';
file[i++]='t';
file[i++]='x';
file[i++]='t';
file[i]='\0';
myfile.open(file,ios::app); //To read from file using object myfile.
if(myfile.is_open())
{
myfile<<"Item\t\tQuantity\t\tTime "<<endl;
root=insert(root,firstname,lastname,email_id,name,file,contact);
myfile.close();
}
else
cout<<"Unable to open file"<<endl;
}
int avl::search(char username[20])
{
int flag=0;
node *ptr;
ptr=root;
while(ptr!=NULL)
{
int a=strcmp(ptr->Username,username);
if (a>0) //if the entered word is smaller than ptr
ptr=ptr->lc; //traverse left sub-tree
else
if (a<0) //if the entered word is greater than ptr
ptr=ptr->rc; //traverse right sub-tree
else
if(a==0) //if ptr is the entered word
{
flag=1;
cout<<"Heyy!!";
return flag;
}
}
return flag;
}
node* avl::getinfo(char username[20])
{
node *ptr;
node *temp;
ptr=root;
while(ptr!=NULL)
{
int a=strcmp(ptr->Username,username);
if (a>0) //if the entered word is smaller than ptr
ptr=ptr->lc; //traverse left sub-tree
else
if (a<0) //if the entered word is greater than ptr
ptr=ptr->rc; //traverse right sub-tree
else
if(a==0) //if ptr is the entered word
{
temp=ptr;
}
}
return temp;
}
node *avl::insert(node *root,char firstname[30], char lastname[30], char email_id[50], char username[20], char filename[25], long int number)
{
int bal;
if(root==NULL) //Initial node
{
root=new node;
strcpy(root->First_Name,firstname);
strcpy(root->Last_Name,lastname);
strcpy(root->Email_id,email_id);
root->Phone=number;
strcpy(root->Username,username);
strcpy(root->Location,filename);
root->lc=NULL;
root->rc=NULL;
root->h=0;
return(root);
}
if(strcmp(username,root->Username)<0)//Inserted node is smaller than root.
{
root->lc=insert(root->lc,firstname,lastname,email_id,username,filename,number);
bal=bal_fac(root); //Calculate balance factor.
if(bal==2) //Left child of unbalanced node is affected.
{
if(strcmp(username,root->lc->Username)<0)
{
root=LL(root); //Left sub-tree is affected.
}
else
root=LR(root); //Right sub-tree is affected.
}
}
else //Inserted node is greater than root.
{
root->rc=insert(root->rc,firstname,lastname,email_id,username,filename,number);//Insert to the right.
bal=bal_fac(root); //Calculate balance factor.
if(bal==-2) //Right child of unbalanced node is affected.
{
if(strcmp(username,root->rc->Username)>0)
root=RR(root) ; //Right sub-tree is affected.
else
root=RL(root); //Left sub-tree is affected.
}
}
root->h=height(root); //Calculate height of node.
return(root);
}
int avl::height(node*root)
{
int lh,rh;
if(root==NULL)
{
return 0;
}
if (root->lc==NULL)
lh= 0;
else
lh= 1+root->lc->h;
if (root->rc==NULL)
rh= 0;
else
rh= 1+root->rc->h;
if(lh>rh)
return lh;
else
return rh;
}
int avl::bal_fac(node *root)
{
if (root== NULL)
return 0;
int lh=0;
if (root->lc==NULL)
lh= 0;
else
lh= 1+height(root->lc);
int rh=0;
if (root->rc==NULL)
rh= 0;
else
rh= 1+height(root->rc);
int bf=lh-rh;
return bf;
}
node *avl::LL(node *root)
{
node *temp;
temp=root->lc;
root->lc=temp->rc;
temp->rc=root;
temp->h=height(temp);
root->h=height(root);
cout<<"LL"<<endl;
return temp; //Return the new root.
}
node *avl::RR(node *root)
{
node *temp;
temp=root->rc;
root->rc=temp->lc;
temp->lc=root;
temp->h=height(temp);
root->h=height(root);
cout<<"RR"<<endl;
return temp; //Return the new root.
}
node *avl::LR(node *root)
{
root->lc=RR(root->lc);
root=LL(root);
cout<<"LR"<<endl;
return root; //Return the new root.
}
node *avl::RL(node *root)
{
root->rc=LL(root->rc);
root=RR(root);
cout<<"RL"<<endl;
return root; //Return the new root.
}
int main() {
avl a;
int user=0;
char ch,uname[20]=" ",choice;
cout<<endl<<"Welcome to XYZ Fruit Mart!!!"<<endl;
do
{
cout<<"Are you an existing customer?"<<endl;
cout<<"(Press y/Y for yes or n/N for no): ";
cin>>ch;
if(ch=='y'||ch=='Y')
{
cout<<endl<<"Enter your Username: ";
cin>>uname;
user=a.search(uname);
if(user==0)
{
cout<<endl<<"THIS USERNAME DOES NOT EXIST. PLEASE CHECK YOUR USERNAME AGAIN";
}
else
{
cout<<"Hello";
a.activity(uname);
}
}
if(ch=='n'||ch=='N')
{
cout<<endl<<"Create your own login with us to use our services.";
a.insert1();
cout<<endl<<"Your Account is now created. Login again to acess services.";
}
cout<<endl<<"Do you want to login again? (Press y/Y for yes or n/N for no): ";
cin>>choice;
}while(choice=='y'||choice=='Y');
return 0;
}
1 ответ
У вас есть повреждение памяти в insert1(),
Когда вы создаете имя файла, вы добавляете 4 к длине имени, чтобы иметь возможность добавить ".txt". К сожалению, вы не учитываете окончание '\0', и это может привести к значительному побочному ущербу.
Исправьте длину:
int len = strlen(name);
len += 5;
Я немного поиграл с исправленным кодом, и он работает как положено (я закомментировал a.activitiy(), потому что он не был определен).
Важные замечания:
Вы используете массивы переменной длины (char file[len];). Это может работать на некоторых компиляторах, но не является частью стандарта C++ и не является переносимым. Лучше забудь об этом. Вместо использования таких массивов символов и стиля C strxxx() функции, серьезно подумайте об использовании C++ std::string
С точки зрения дизайна, не оптимально управлять командами ввода-вывода или приложения в функциях класса AVL. Здесь ввод-вывод больше связан с узлами и должен управляться как функция-член узла или как перегрузка стандартного экстрактора.