我的 C 数据结构无法正常工作

问题描述 投票：0回答：1

我是巴西的一名计算机工程专业的学生，本学期我将学习算法和数据结构课程。我现在的主题是“通用树”。我有一个模拟 cmd 之类的程序的活动，这是我的代码：

#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 debuging 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;
}

我有 10 个条目将针对我的代码进行测试，但在只有 2 个条目中，我遇到了问题，这可能是在我的“insere”函数中，该函数在树中插入一个新节点，或者在我的“删除”函数中函数，从树中删除节点。第一个条目给了我一个超过时间限制的信息，我不知道如何优化代码以使其运行得更快，而下一个条目给了我一个错误的输出，这里是测试（请随意修复您发现的更多错误）在我的代码中找到）v:

输入数字1（时限错误）：

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

输出1应该是：

file8 \dir10 \root

输入数字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

输出数字2应该是：

arq10 \root
c data-structures tree
1个回答
0
投票

  1. 正如 @CraigEstey 在 

    main()
    中所解释的那样，函数 
    buscaNo()
    的第二个参数是 
    No *
    ，但是你传递了它 
    &root
    ，它是 
    TipoRaiz *
    。

  2. 正如@CraigEstey 解释的那样，你的程序会出现段错误。这是因为搜索

    removeNo()
    有错误。您需要从 
    No *q = p->primFilho;
    开始搜索前一个节点，然后遍历链表 
    q = q->proxIrmao
    。

  3. 第二个输入失败，因为您期望每行包含 3 个单词，但 

    -r
    命令只包含 2 个。我建议您读一行然后使用 
    sscanf()
    。

  4. （未修复）虽然两个程序现在都返回正确的输出，但顺序错误。我把它留给你作为练习。

  5. 使用 

    scanf()
    读取字符串时始终指定最大字段宽度。

#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; // son
    struct No *proxIrmao; // brother
    struct No *pai; // far
} No;

typedef struct TipoRaiz {
    No *raiz;
} TipoRaiz;

int contador = 0;

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;
    contador++;
}

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) {
    No* pilha[contador];
    int top = -1;
    while (no) {
        pilha[++top] = no;
        no = no->pai;
    }
    while(top >= 0)
        printf("%s ", pilha[top--]->nome);
}

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, COMMAND_LEN+2*LEN+1, 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);
            }
        }
    }

    // used for debuging purposes printTree(root.raiz, 0);
    No *buscadoNo = buscaNo(buscado, root.raiz);
    if(buscadoNo) {
        printCaminho(buscadoNo);
        printf("\n");
    } else
        printf("Arquivo nao encontrado!\n");
    return 0;
}

示例运行：

$ ./a.out < input_1.txt
\root \dir10 file8
$ ./a.out < input_2.txt
\root arq10
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.