I'm a Computer Engineering student in Brazil and I'm having Algorithms and Data Structure classes this semester. The subject I'm having now is "Generic Trees". I have an activity to simulate a cmd like program, and here is my code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
typedef int bool;
typedef struct No {
char nome[1025];
struct No *primFilho;
struct No *proxIrmao;
struct No *pai;
} No;
typedef struct TipoRaiz {
No *raiz;
} TipoRaiz;
int contador = 0;
No *CriaNovoNo(char nome[1025]) {
No *novoNo = (No*) malloc(sizeof(No));
strcpy(novoNo->nome, nome);
novoNo->primFilho = NULL;
novoNo->proxIrmao = NULL;
novoNo->pai = NULL;
return novoNo;
}
void inicializa(TipoRaiz *raiz) {
raiz->raiz = CriaNovoNo("\\root");
}
void printTree(No *root, int depth) {
if (root == NULL)
return;
for (int i = 0; i < depth; i++)
printf(" ");
printf("%s\n", root->nome);
printTree(root->primFilho, depth + 1);
printTree(root->proxIrmao, depth);
}
No *buscaNo(char nome[], No *raiz) {
if (raiz == NULL)
return NULL;
if (strcmp(raiz->nome, nome) == 0)
return raiz;
No *p = raiz->primFilho;
while (p) {
No *resp = buscaNo(nome, p);
if (resp)
return resp;
p = p->proxIrmao;
}
return NULL;
}
void insere(TipoRaiz *root, char novoNo[], char localPai[]) {
No *pai = buscaNo(localPai, root->raiz);
if (pai == NULL)
return;
No *inserido = CriaNovoNo(novoNo);
inserido->pai = pai;
if (pai->primFilho == NULL) {
pai->primFilho = inserido;
} else {
inserido->proxIrmao = pai->primFilho;
pai->primFilho = inserido;
}
contador++;
}
void removeNo(No *no) {
No *p = no->pai;
No *q = no->primFilho;
if (p != NULL) {
if (p->primFilho == no)
p->primFilho = no->proxIrmao;
else {
while(q->proxIrmao != no) {
q = q->proxIrmao;
}
q->proxIrmao = no->proxIrmao;
}
free(no);
}
}
void printCaminho(No* no) {
No* pilha[contador];
int top = -1;
while (no != NULL) {
pilha[++top] = no;
no = no->pai;
}
while (top >= 0) {
printf("%s ", pilha[top--]->nome);
}
}
int main() {
TipoRaiz root;
inicializa(&root);
int n;
char nome[1025], localPai[1025], comando[3], buscado[1025];
scanf("%d", &n);
scanf("%s", buscado);
for (int i = 0; i < n; i++) {
scanf("%s %s %s", comando, nome, localPai);
if (strcmp(comando, "-a") == 0)
insere(&root, nome, localPai);
else if (strcmp(comando,"-r") == 0) {
No *noParaRemover = buscaNo(nome, &root);
removeNo(noParaRemover);
}
else if (strcmp(comando, "-m") == 0) {
if (buscaNo(localPai, &root)) {
No *noParaMover = buscaNo(nome, &root);
removeNo(noParaMover);
insere(&root, nome, localPai);
}
}
}
// used for debugging purposes printTree(root.raiz, 0);
No *buscadoNo = buscaNo(buscado, root.raiz);
if (buscadoNo == NULL)
printf("Arquivo nao encontrado!\n");
else {
printCaminho(buscadoNo);
printf("\n");
}
return 0;
}
I have 10 entries that will be tested for my code, but in only 2 entries, I'm having problems, that are probably in my insere function, that inserts a new node in the tree, or in my remove function, that removes the node from the tree. The first entry gives me a Time Limit Exceeded and I do not know how to optimize the code to make it run faster, and the next one, gives me a wrong output, here are the tests (feel free to fix any more bugs that you find in my code):
Input number 1 (Time limit error):
30
file8
-a \dir1 \root
-a \dir2 \root
-a \dir3 \root
-a \dir4 \root
-a \dir5 \root
-a \dir6 \root
-a \dir7 \root
-a \dir8 \root
-a \dir9 \root
-a \dir10 \root
-a file1 \root
-a file2 \root
-a file3 \root
-a file4 \root
-a file5 \root
-a file6 \root
-a file7 \root
-a file8 \root
-a file9 \root
-a file10 \root
-r file1
-r file3
-r file5
-r file7
-r file9
-r file2
-r file6
-r file10
-r file4
-m file8 \dir10
The output 1 should be:
file8 \dir10 \root
Input number 2:
134
arq10
-a \dir1 \root
-a \dir2 \dir1
-a \dir3 \dir2
-a \dir4 \dir3
-a \dir5 \dir4
-a \dir6 \dir5
-a \dir7 \dir6
-a \dir8 \dir7
-a \dir9 \dir8
-a \dir10 \dir9
-a \dir11 \dir10
-a \dir12 \dir11
-a \dir13 \dir12
-a \dir14 \dir13
-a \dir15 \dir14
-a \dir16 \dir15
-a \dir17 \dir16
-a \dir18 \dir17
-a \dir19 \dir18
-a arq1 \dir1
-a arq2 \dir2
-a arq3 \dir3
-a arq4 \dir4
-a arq5 \dir5
-a arq6 \dir6
-a arq7 \dir7
-a arq8 \dir8
-a arq9 \dir9
-a arq10 \dir10
-a arq11 \dir11
-a arq12 \dir12
-a arq13 \dir13
-a arq14 \dir14
-a arq15 \dir15
-a arq16 \dir16
-a arq17 \dir17
-a arq18 \dir18
-a arq19 \dir19
-a \pasta1 \root
-a \pasta2 \pasta1
-a \pasta3 \pasta2
-a \pasta4 \pasta3
-a \pasta5 \pasta4
-a \pasta6 \pasta5
-a \pasta7 \pasta6
-a \pasta8 \pasta7
-a \pasta9 \pasta8
-a \pasta10 \pasta9
-a \pasta11 \pasta10
-a \pasta12 \pasta11
-a \pasta13 \pasta12
-a \pasta14 \pasta13
-a \pasta15 \pasta14
-a \pasta16 \pasta15
-a \pasta17 \pasta16
-a \pasta18 \pasta17
-a \pasta19 \pasta18
-m arq1 \pasta1
-m arq2 \pasta2
-m arq3 \pasta3
-m arq4 \pasta4
-m arq5 \pasta5
-m arq6 \pasta6
-m arq7 \pasta7
-m arq8 \pasta8
-m arq9 \pasta9
-m arq10 \pasta10
-m arq11 \pasta11
-m arq12 \pasta12
-m arq13 \pasta13
-m arq14 \pasta14
-m arq15 \pasta15
-m arq16 \pasta16
-m arq17 \pasta17
-m arq18 \pasta18
-m arq19 \pasta19
-a \novo1 \root
-a \novo2 \novo1
-a \novo3 \novo2
-a \novo4 \novo3
-a \novo5 \novo4
-a \novo6 \novo5
-a \novo7 \novo6
-a \novo8 \novo7
-a \novo9 \novo8
-a \novo10 \novo9
-a \novo11 \novo10
-a \novo12 \novo11
-a \novo13 \novo12
-a \novo14 \novo13
-a \novo15 \novo14
-a \novo16 \novo15
-a \novo17 \novo16
-a \novo18 \novo17
-a \novo19 \novo18
-m arq1 \nova1
-m arq2 \nova2
-m arq3 \nova3
-m arq4 \nova4
-m arq5 \nova5
-m arq6 \nova6
-m arq7 \nova7
-m arq8 \nova8
-m arq9 \nova9
-m arq10 \nova10
-m arq11 \nova11
-m arq12 \nova12
-m arq13 \nova13
-m arq14 \nova14
-m arq15 \nova15
-m arq16 \nova16
-m arq17 \nova17
-m arq18 \nova18
-m arq19 \nova19
-r arq1
-r arq2
-r arq3
-r arq4
-r arq5
-r arq6
-r arq7
-r arq8
-r arq9
-r arq10
-r arq11
-r arq12
-r arq13
-r arq14
-r arq15
-r arq16
-r arq17
-r arq18
-r arq19
-a arq10 \root
The output number 2 should be:
arq10 \root
main(): As @CraigEstey explained buscaNo()'s 2nd argument is a No * but you pass it &root which is a TipoRaiz *. I didn't do it below but I suggest you eliminate the TipoRaiz type. Resolve all compiler warnings; if you didn't get one here turn up the warning levels.
removeNo() segfaults. You need to start the search for the previous node at No *q = p->primFilho; then walk the linked list q = q->proxIrmao.
printCaminho() prints the result in reverse order. Rewrote the function to follow pai to the root and pulled the non-existing result into the function to simplify main().
Eliminate the global variable contador.
main(): The 2nd input fails because you expect each line to contain 3 words but the -r command only contains 2. Read a line with fgets() (or getline()) then use sscanf() to parse either 2 or 3 fields from that line. I didn't do it below but I suggest that you always check the return value of scanf() and sscanf() otherwise you may be operating on uninitialized variables.
Always specify a maximum field width when reading strings with scanf() to avoid buffer overflows.
Use symbolic constants instead of magic values (1025, 3). It makes it easier to change your program, say, you decide that you only need 32 bytes instead then it's one place to change it and all the uses including the derived for line just works.
(Not fixed) Memory leaks.
Don't cast the void * from malloc().
Prefer using the variable name instead of the type to sizeof. You end up repeating yourself less that way struct foo *bar = malloc(sizeof *bar).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define COMMAND_LEN 2
#define LEN 1024
#define str(s) str2(s)
#define str2(s) #s
typedef struct No {
char nome[LEN+1];
struct No *primFilho;
struct No *proxIrmao;
struct No *pai;
} No;
typedef struct TipoRaiz {
No *raiz;
} TipoRaiz;
No *CriaNovoNo(char *nome) {
No *novoNo = malloc(sizeof *novoNo);
strcpy(novoNo->nome, nome);
novoNo->primFilho = NULL;
novoNo->proxIrmao = NULL;
novoNo->pai = NULL;
return novoNo;
}
void inicializa(TipoRaiz *raiz) {
raiz->raiz = CriaNovoNo("\\root");
}
void printTree(No *root, int depth) {
if (root == NULL)
return;
for (int i = 0; i < depth; i++)
printf(" ");
printf("%s\n", root->nome);
printTree(root->primFilho, depth + 1);
printTree(root->proxIrmao, depth);
}
No *buscaNo(char nome[], No *raiz) {
if(raiz == NULL)
return NULL;
if(strcmp(raiz->nome, nome) == 0)
return raiz;
No *p = raiz->primFilho;
while(p) {
No *resp = buscaNo(nome, p);
if(resp)
return resp;
p = p->proxIrmao;
}
return NULL;
}
void insere(TipoRaiz *root, char *novoNo, char *localPai) {
No *pai = buscaNo(localPai, root->raiz);
if(!pai)
return;
No *inserido = CriaNovoNo(novoNo);
inserido->pai = pai;
if(pai->primFilho)
inserido->proxIrmao = pai->primFilho;
pai->primFilho = inserido;
}
void removeNo(No *no) {
No *p = no->pai;
if(!p)
return;
if(p->primFilho == no)
p->primFilho = no->proxIrmao;
else {
No *q = p->primFilho;
for(; q->proxIrmao != no; q = q->proxIrmao);
q->proxIrmao = no->proxIrmao;
}
free(no);
}
void printCaminho(No* no) {
if(!no) {
printf("Arquivo nao encontrado!\n");
return;
}
printf("%s", no->nome);
for(no = no->pai; no; no = no->pai)
printf(" %s", no->nome);
printf("\n");
}
int main() {
TipoRaiz root;
inicializa(&root);
int n;
char nome[LEN+1];
char localPai[LEN+1];
char comando[COMMAND_LEN+1];
char buscado[LEN+1];
scanf("%d", &n);
scanf("%" str(LEN) "s", buscado);
getchar();
char line[COMMAND_LEN+2*LEN+1];
for(int i = 0; i < n; i++) {
if(!fgets(line, sizeof line, stdin)) {
printf("input missing\n");
return 1;
}
sscanf(line, "%" str(COMMAND_LEN) "s %" str(LEN) "s %" str(LEN) "s", comando, nome, localPai);
if(!strcmp(comando, "-a") )
insere(&root, nome, localPai);
else if(!strcmp(comando,"-r")) {
No *noParaRemover = buscaNo(nome, root.raiz);
removeNo(noParaRemover);
}
else if (!strcmp(comando, "-m")) {
if(buscaNo(localPai, root.raiz)) {
No *noParaMover = buscaNo(nome, root.raiz);
removeNo(noParaMover);
insere(&root, nome, localPai);
}
}
}
printCaminho(buscaNo(buscado, root.raiz));
return 0;
}
and example run:
$ ./your_homework < input_1.txt
file8 \dir10 \root
$ ./your_homework < input_2.txt
arq10 \root