如何通过递归正确打印城市？求修复递归打印城市代码

Hey there! Let's work through this recursive city printing issue step by step. Looking at your code, I spot several small bugs and logical issues that are keeping it from working as expected. Let's break them down and fix them.

Key Issues in Your Code #

• Type Mismatch in newcity: You tried to cast malloc's return value to cities instead of cities*—that's a critical pointer error that'll cause crashes or unexpected behavior.
• Wrong Recursive Call for North Direction: In the north check, you're passing cityHead->s (south) instead of cityHead->n (north) to the recursive printcity call. That's a simple typo but breaks north direction handling.
• Incorrect Print Order: Your current code prints the directions first, but you specified we should print the current center city first before checking its four directions.
• No Cycle Prevention: Since city pointers are bidirectional (e.g., if City A's west is City B, City B's east is City A), your recursive calls will loop infinitely without tracking which cities we've already printed.
• Direction Flags Are Unnecessary: The e/w/s/n flags you're passing don't solve the cycle problem and complicate the logic—we can replace them with a visited tracking mechanism instead.

Fixed Code #

First, let's fix the newcity function and rewrite the printcity function to meet your requirements:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct cities{
    char name[100];
    struct cities *e,*w,*s,*n;
}*cityHead,*city[100];

// Helper function to check if a city has been visited
int isVisited(struct cities *target, struct cities **visited, int count) {
    for(int i = 0; i < count; i++) {
        if(visited[i] == target) {
            return 1;
        }
    }
    return 0;
}

void printcity(struct cities *current, struct cities **visited, int *visitedCount) {
    if(!current || isVisited(current, visited, *visitedCount)) {
        return;
    }

    // Mark current city as visited first to prevent cycles
    visited[*visitedCount] = current;
    (*visitedCount)++;

    // Print the current city first (as per your requirement)
    printf("Current City: %s\n", current->name);

    // Define the order: West → East → South → North
    // For each direction, check if exists and not visited, then print and recurse
    if(current->w != NULL) {
        printf("--West: %s\n", current->w->name);
        printcity(current->w, visited, visitedCount);
    } else {
        printf("--West: None\n");
    }

    if(current->e != NULL) {
        printf("--East: %s\n", current->e->name);
        printcity(current->e, visited, visitedCount);
    } else {
        printf("--East: None\n");
    }

    if(current->s != NULL) {
        printf("--South: %s\n", current->s->name);
        printcity(current->s, visited, visitedCount);
    } else {
        printf("--South: None\n");
    }

    if(current->n != NULL) {
        printf("--North: %s\n", current->n->name);
        printcity(current->n, visited, visitedCount);
    } else {
        printf("--North: None\n");
    }
}

struct cities * newcity(char name[]) {
    struct cities *temp = (struct cities*)malloc(sizeof(struct cities));
    if(!temp) { // Always check malloc success!
        printf("Memory allocation failed\n");
        exit(1);
    }
    strcpy(temp->name, name);
    temp->e = temp->n = temp->s = temp->w = NULL;
    return temp;
}

// Example usage to test
int main() {
    // Create some test cities
    city[0] = newcity("Central City");
    cityHead = city[0];
    city[1] = newcity("West Town");
    city[0]->w = city[1];
    city[1]->e = city[0]; // Bidirectional link to simulate real scenario
    city[2] = newcity("East Village");
    city[0]->e = city[2];
    city[2]->w = city[0];
    city[3] = newcity("South Port");
    city[0]->s = city[3];
    city[3]->n = city[0];

    // Initialize visited array (assuming max 100 cities as per your city array)
    struct cities *visited[100];
    int visitedCount = 0;

    // Start printing from the head city
    printcity(cityHead, visited, &visitedCount);

    // Clean up memory (important to avoid leaks)
    for(int i = 0; i < 4; i++) {
        free(city[i]);
    }
    return 0;
}

What We Fixed & Improved #

1. Fixed newcity Pointer Cast: Changed (cities) to (struct cities*) and added a check for malloc failure (always good practice to handle memory allocation errors).
2. Added Visited Tracking: The isVisited helper and visited array prevent infinite recursion caused by bidirectional city links. We mark a city as visited as soon as we print it so we don't process it again.
3. Corrected Print Order: Now we print the current city first, then check each direction in your specified order (West → East → South → North).
4. Fixed North Direction Typo: Replaced cityHead->s with cityHead->n in the north recursive call.
5. Removed Unnecessary Flags: The direction flags are gone—we use visited tracking instead, which is a cleaner solution for cycle prevention.

内容的提问来源于stack exchange，提问作者Reve