C语言链表遍历打印失败？

Question

C语言链表遍历打印失败？

发布于
2022-08-06 福建

更新于
2022-08-12

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef struct menu_t1
{
    struct menu_t1* father;
    struct menu_t1* bro_up;
    struct menu_t1* bro_down;
    struct menu_t1* son;
    char *s;
    void (*f)(void);
}menu_t;
menu_t *Create_Menu_Head(char *s,void (*f)(void))
{
    menu_t * p=(menu_t *)malloc(sizeof(menu_t));
    if(p!=NULL)
    {
        p->father=p;
        p->bro_down=NULL;
        p->bro_up=NULL;
        p->son=NULL;
        p->f=f;
        p->s=s;
        return p;
    }
}
menu_t *Create_Menu_Node(menu_t *Head,char *s,void(*f)(void))
{
    menu_t *newNode=NULL;
    menu_t *boo=NULL;
    boo=Head;
    while(boo->bro_down!=NULL) boo=boo->bro_down;
    newNode=(menu_t*)malloc(sizeof(menu_t));

    newNode->father=boo->father;
    newNode->s=s;
    newNode->f=f;
    newNode->bro_down=NULL;
    newNode->bro_up=boo;
    return newNode;
}
menu_t *Create_Menu_Tail(menu_t *Node,char *s,void(*f)(void))
{
    menu_t *tailNode=NULL;
    menu_t *boo=NULL;
    boo=Node;
    tailNode=(menu_t *)malloc(sizeof(menu_t));
    tailNode->father=boo->father;
    tailNode->bro_down=NULL;
    tailNode->bro_up=NULL;
    tailNode->son=NULL;
    tailNode->s=s;
    tailNode->f=f;
    return tailNode;
}
void showList(menu_t *List)
{
    menu_t *boo=NULL;
    boo=List;
    
        while (boo->bro_up!=NULL)
        {

            while(boo->son!=NULL)
            {
                boo=boo->son;
                printf("%s",boo->s);
            }
            boo=boo->bro_up;
        }
        
    
}
#define PO(x) printf("x")
int main(void)
{
    menu_t* head;
    menu_t* temp;
    menu_t* temp_Son;
    head=Create_Menu_Head("第一级\r\n",NULL);
    // printf("%s\r\n",head->s);
    temp=Create_Menu_Node(head,"第二级-1\r\n",NULL);
    // printf("%s\r\n",temp->s);    
    temp=Create_Menu_Node(head,"第二级-2\r\n",NULL);
    // printf("%s\r\n",temp->s);
    temp_Son=Create_Menu_Tail(temp,"第二级-1-1\r\n",NULL);
    // printf("%s\r\n",temp_Son->s);
    showList(head);
    system("pause");
}

请问，这个链表打印没能正确打印，是哪里出现问题？

更改于08/12

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

typedef struct menu_t {
    /** 上一节点 */
    struct menu_t* father;
    /** 上一兄弟节点 */
    struct menu_t* bro_up;
    /** 下一兄弟节点 */
    struct menu_t* bro_down;
    /** 下一节点 */
    struct menu_t* son;
    char * s;
    void (*f)(void);
} menu_t;

menu_t * create_node(menu_t* father, char* s, void (*f)(void)) {
    menu_t* p = (menu_t*) malloc(sizeof(menu_t));
    if (p == NULL) { return NULL; }

    // 先给数据赋值
    p->s = s;
    p->f = f;
    // 新节点不会有后面的兄弟（没有弟），也不会有子节点
    p->bro_down = NULL;
    p->son = NULL;
    // 连接父节点
    p->father = father;
    // 初始化上一兄弟为 NULL
    p->bro_up = NULL;

    // 父节点为 NULL 那就没别的事了
    if (father == NULL) {
        return p;
    }

    // 如果父节点没有子节点，直接接上，也没别的事了
    if (father->son == NULL) {
        father->son = p;
        return p;
    }

    // 接下来连接子节点，需要找到子节点的最后一环
    menu_t *son = father->son;
    while (son->bro_down != NULL) {
        son = son->bro_down;
    }
    // 连上，注意是双向
    son->bro_down = p;
    p->bro_up = son;

    return p;
}

void show_list(menu_t* node) {
    if (node == NULL) { return; }

    // 先打印当前节点
    printf("[%ld] %s (son: %ld) down:[%ld]\tup:[%ld]\tfather:[%ld]\n", (long) node, node->s, (long) node->son,(long)node->bro_down,(long)node->bro_up,(long)node->father);

    // 打印它的兄弟（递归）
    menu_t* boo = node->bro_down;
    while (boo != NULL) {
        show_list(boo);
        boo = boo->bro_down;
    }

    // 递归打印它的子节点
    show_list(node->son);
}

int main(void) {
    menu_t* head;
    menu_t* temp;
    menu_t* temp_Son;

    // 创建头节点，它没有 father
    head = create_node(NULL, "第一级", NULL);

    // 创建头的第 1 个子节点，因为要为它创建子节点，所以要留返回值，免得找
    temp = create_node(head, "第二级-1", NULL);
    // 创建头的第 2 个子节点，返回值可以不留（已经接在 head 上了）
    create_node(head, "第二级-2", NULL);
    create_node(head, "第二级-3", NULL);
    // 创建头的第 2 个子节点的子节点
    create_node(temp, "第二级-1-1", NULL);
    create_node(temp, "第二级-1-2", NULL);
    create_node(temp, "第二级-1-3", NULL);
    // 打印
    show_list(head);
}

[12922616] 第一级 (son: 12922648) down:[0]      up:[0]  father:[0]
[12922648] 第二级-1 (son: 12922744) down:[12922680]     up:[0]  father:[12922616]
[12922680] 第二级-2 (son: 0) down:[12922712]    up:[12922648]   father:[12922616]
[12922712] 第二级-3 (son: 0) down:[0]   up:[12922680]   father:[12922616]
[12922712] 第二级-3 (son: 0) down:[0]   up:[12922680]   father:[12922616]
[12922744] 第二级-1-1 (son: 0) down:[12922776]  up:[0]  father:[12922648]
[12922776] 第二级-1-2 (son: 0) down:[12922808]  up:[12922744]   father:[12922648]
[12922808] 第二级-1-3 (son: 0) down:[0] up:[12922776]   father:[12922648]
[12922808] 第二级-1-3 (son: 0) down:[0] up:[12922776]   father:[12922648]

对@边城这个的代码做了一些改动，发现最后一条记录会打印两遍。

更新于08/12-14：02
将

void show_list(menu_t* node) {
    if (node == NULL) { return; }

    // 先打印当前节点
    printf("[%ld] %s (son: %ld) down:[%ld]\tup:[%ld]\tfather:[%ld]\n", (long) node, node->s, (long) node->son,(long)node->bro_down,(long)node->bro_up,(long)node->father);

    // 打印它的兄弟（递归）
    // menu_t* boo = node->bro_down;
    // while (boo != NULL) {
    //     show_list(boo);
    //     boo = boo->bro_down;
    // }

    // 递归打印它的子节点
    show_list(node->son);
}

去掉循环，主程序内容保持不变，修改后打印内容如下：

[14036728] 第一级 (son: 14036760) down:[0]      up:[0]  father:[0]
[14036760] 第二级-1 (son: 14036856) down:[14036792]     up:[0]  father:[14036728]
[14036856] 第二级-1-1 (son: 0) down:[14036888]  up:[0]  father:[14036760]

相比上一版，却是缺失了兄弟结点。由于对链表也是刚接触，所以发现不了哪里出了问题。
附上网上找到的一个例程（最开头的程序就是对着抄改的，但是还是没成功，还是自己太菜啦#_#.
主要是用来生成一个菜单的，想移植到单片机上的）

#include <iostream>
#include <string>
#include<conio.h>
using namespace std;
 
struct menu//节点结构体
{
    menu* father;//上级父节点连接
    menu* brother_up;//同级兄节点连接
    menu* brother_down;//同级弟节点连接
    menu* son;//下级子节点连接
 
    string name;//节点名
    int ID;//节点级别号，但是我没有用
    void* fun;//节点功能函数指针，只有执行函数不为空
};
 
struct control
{
    menu* now;//需要实时标志现在菜单指针的位置
    void(*p)(void);//一个void类型的函数指针
    char  input;//哈哈哈这个我也没有用
}dir;
 
 
void getnow(menu* now);//跟踪指针位置，解析输入命令
void showmenu(menu* now);//显示函数
void controlMENU();//控制函数
 
menu* creat_head(string s, void* func);//创建头节点
menu* creat_brother(menu* brother, string s, void* func);//往下生成一个兄项（并列关系）
menu* creatson(menu* father, string s, void* func);//往右生成一个子项（从属关系）
 
//功能函数定义，各个子目录的功能函数
void func1();
void func2_1();
void func2_2();
void func2_3();
void func3();
void func4();
 
 
 
int  main()
{
    menu* head;
    menu* temp;
 
    //菜单定义区，只有最末端的菜单才拥有执行函数，像“选项2”这样的中继菜单，不用执行函数直接给null
    head = creat_head("选项1", func1);//创建头节点
 
    temp=creat_brother(head, "选项2",NULL);//头节点往下建立一个与头节点同级的兄弟节点
            temp = creatson(temp,"选项2的子选项1", func2_1);//兄弟节点创建子节点
            temp = creat_brother(temp, "选项2的子选项2", func2_2);//由兄弟节点的子节点创建子节点的同级节点
            temp = creat_brother(temp, "选项2的子选项3",func2_3);
    creat_brother(head, "选项3", func3);
    creat_brother(head, "选项4", func4);
 
    dir.now = head;
 
    controlMENU();
 
    return 0;
}
 
//功能函数定义，各个子目录的功能函数
void func1()
{
    system("cls");
    cout << "选项1功能调用！" << endl;
    cout << "选项1功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}
void func2_1()
{
    system("cls");
    cout << "选项2.1功能调用！" << endl;
    cout << "选项2.1功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}void func2_2()
{
    system("cls");
    cout << "选项2.2功能调用！" << endl;
    cout << "选项2.2功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}
void func2_3()
{
    system("cls");
    cout << "选项2.3功能调用！" << endl;
    cout << "选项2.3功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}void func3()
{
    system("cls");
    cout << "选项3功能调用！" << endl;
    cout << "选项3功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}
void func4()
{
    system("cls");
    cout << "选项4功能调用！" << endl;
    cout << "选项4功能调用完毕，按任意键返回上级菜单！" << endl;
    system("pause");
}
 
 
 
void getnow(menu* now)//跟踪指针位置，解析输入命令
{
    dir.now = now;
 
    switch (_getch())
    {
        //上移
    case 'w':
    case 'W':
        if (dir.now->brother_up != NULL)
            dir.now = dir.now->brother_up;
        break;
 
        //下移
    case's':
    case'S':
        if (dir.now->brother_down != NULL)
            dir.now = dir.now->brother_down;
        break;
 
        //左移返回上一级菜单
    case 'a':
    case 'A':
        if (dir.now->father != NULL)
            dir.now = dir.now->father;
        break;
 
        //右移去到下一级菜单
    case'd':
    case'D':
        if (dir.now->son != NULL)
            dir.now = dir.now->son;
        break;
 
    case '\r'://换行和回车还不一样，换行符\n,回车符\r，如果你要检测键盘输入的回车，就要输入\r，而不是\n
        if (dir.now->fun != NULL)//注意，不能在switch语句内部定义变量，语法不允许，会报错！！！所以这个p就在外面定义了
        {
            dir.p = (void(*)(void))dir.now->fun;//强制类型转换，void*模糊类型强制转换为void(*)(void)函数指针的类型
            dir.p();
        }
        break;
 
    default:
        break;
    }
}
 
menu* creat_head(string s, void* func)//创建头节点，他没有父亲，我规定他的父亲就是自己。。。太可怜了
{
    menu* p = new menu;
 
    p->father = p;
    p->brother_down = NULL;
    p->brother_up = NULL;
    p->son = NULL;
 
    p->name = s;
    p->ID = 1;
    p->fun = func;
 
    return p;
}
 
menu* creat_brother(menu* brother, string s, void* func)//往下生成一个兄项（并列关系）
{
    menu* p;
    menu* p1;
 
    p = brother;
    p1 = new menu;
 
 
    while (p->brother_down != NULL)
        p = p->brother_down;
 
    p->brother_down = p1;
 
    p1->father = p->father;//既然是兄弟，他们的老爹肯定是一样的
    p1->brother_down = NULL;
    p1->brother_up = p;
    p1->son = NULL;
 
    p1->name = s;
    p1->ID = p->ID;
    p1->fun = func;
 
    return p1;
}
 
menu* creatson(menu* father, string s, void* func)//往右生成一个子项（从属关系）
{
    menu* p;
    menu* p1;
 
    p = father;
    p1 = new menu;
 
    p->son = p1;
 
    p1->father = p;
    p1->brother_up = NULL;
    p1->brother_down = NULL;
    p1->son = NULL;
 
    p1->name = s;
    p1->ID = p->ID + 1;
    p1->fun = func;
 
    return p1;
}
 
void showmenu(menu* now)
{
    menu* show;
    show = now;
 
    cout << "请通过键盘控制选项！" << endl;
    while (show->brother_up != NULL)//先依次往最上面找大哥
        show = show->brother_up;
 
    while (show != NULL)//从大哥开始往下显示所有小弟
    {
        if (now->name == show->name)//标记现在指针指向的位置
            cout << "--》";
 
        cout << show->name << endl;
        show = show->brother_down;
    }
}
 
void controlMENU()
{
    showmenu(dir.now);//先显示最初信息后等待输入
 
    while (1)//逻辑是：等待输入命令、清除旧信息、显示新信息
    {
        getnow(dir.now);
        system("cls");
        showmenu(dir.now);
    }
}
//g++ .\menu-1.cpp -o menu.exe -fpermissive -fexec-charset=gbk

更新于 08/12-16：54

void show_list(menu_t* node) {
    menu_t *temp_node;
    if (node == NULL) { return; }

    // 先打印当前节点
    printf("[%ld] %s (son: %ld) down:[%ld]\tup:[%ld]\tfather:[%ld]\n", (long) node, node->s, (long) node->son,(long)node->bro_down,(long)node->bro_up,(long)node->father);

    // 打印它的兄弟（递归）
    menu_t* boo = node->bro_down;
    // while (boo != NULL) {
    //     show_list(boo);
        
    //     boo = boo->bro_down;
    // }

    // // 递归打印它的子节点
    show_list(node->bro_down);
}

根据提醒，去掉show_list里的while部分，主函数中不变，打印结果如下：

[13184760] 第一级 (son: 13184792) down:[0]      up:[0]  father:[0]

只有一条记录。太怪了---@_@

c 链表

阅读 1.6k

1 个回答

发布于
2022-08-06 四川

✓ 已被采纳

这结构不是单纯的链表结构，father 和 son 看起来比较像是树形结构。由于 son 只有一个节点，所以应该还有一个节点来连接兄弟，看样子 bro_up 和 bro_down 分别前后兄弟节点。

Create_Menu_Head 是创建头节点，这里有两个问题，

第一，if 分支中有 return，但没有 else 分支，也没有默认（最后）的返回语句，所以当 p == NULL 的时候，返回值是不确定的。编译器虽然能通过，但在最后，或者 else 分支里应该有明确的 return NULL。

第二，p->father = p，自己的父节点是自己。这样的确可以作为一种“没有父节点”的描述方式，但是判断起来会比较麻烦，容易即使忘记判断也不会出现错误。通常的做法是用 NULL 表示没有，即 p->father = NULL。

接下来，Create_Menu_Node 创建一个菜单节点，这里用了一个 boo 去找到 Head 的最后一个兄弟，然后呢？虽然有 newNode -> bro_up = boo 将 boo 作为新节点的前序节点连上了，但是并没有将新节点作为 boo 的后序节点连上 —— 代码里没找到 boo->bro_down = ... 这样的语句。

接下来的 Create_Menu_Tail 中甚至都没有对兄弟节点进行连接。从这三个 Create 来看，都最多只进行了兄弟节点的连接，没有进行父子节点的连接。—— 所以三个 Create 到底分别是想干啥呢？姑且认为它们就是为了创建兄弟链表用，与父子无关，那么——

如果只是想创建一个节点，并进行兄弟连接，只需要一个Create 函数就可以了。除创建头节点时需要传入 NULL 作为 head 外，其他节点都是一样的逻辑。因为你每连上一个新节点，它都是当前状态下的尾节点。至于这个 Create 函数该怎么写，我觉得你自己想一想应该能想明白，可以先试着写一写，不成，再把代码更新到问题中继续问。

接下来看 showList。理论上这里应该给一个头节点，按 bro_down 的顺序就可以把所有节点打印出来。如果是给的任意节点，可以先按 bro_up 把头节点找出来，再按 bro_down 依次打印，都是单循环，不会出现嵌套循环。根据上面的 Create 代码，son 根本就没用过，所以原代码的内循环其实啥也没干。

最后提一点代码风格上的问题，一般情况下，不同语言有不同的函数命名风格，比如 PascalCase 风格，camelCase 风格和 snake_case 风格。这里 showList 用了 camelCase，几个 Create 函数用的 PascalCase 和 snake_case 混用。C 语言用 snake_case 比较多，建议统一成这种风格。即 create_head_node、show_list 等。

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

typedef struct menu_t {
    /** 上一节点 */
    struct menu_t* father;
    /** 上一兄弟节点 */
    struct menu_t* bro_up;
    /** 下一兄弟节点 */
    struct menu_t* bro_down;
    /** 下一节点 */
    struct menu_t* son;
    char * s;
    void (*f)(void);
} menu_t;

menu_t * create_node(menu_t* father, char* s, void (*f)(void)) {
    menu_t* p = (menu_t*) malloc(sizeof(menu_t));
    if (p == NULL) { return NULL; }

    // 先给数据赋值
    p->s = s;
    p->f = f;
    // 新节点不会有后面的兄弟（没有弟），也不会有子节点
    p->bro_down = NULL;
    p->son = NULL;
    // 连接父节点
    p->father = father;
    // 初始化上一兄弟为 NULL
    p->bro_up = NULL;

    // 父节点为 NULL 那就没别的事了
    if (father == NULL) {
        return p;
    }

    // 如果父节点没有子节点，直接接上，也没别的事了
    if (father->son == NULL) {
        father->son = p;
        return p;
    }

    // 接下来连接子节点，需要找到子节点的最后一环
    menu_t *son = father->son;
    while (son->bro_down != NULL) {
        son = son->bro_down;
    }
    // 连上，注意是双向
    son->bro_down = p;
    p->bro_up = son;

    return p;
}

void show_list(menu_t* node) {
    if (node == NULL) { return; }

    // 先打印当前节点
    printf("[%ld] %s (son: %ld)\n", (long) node, node->s, (long) node->son);

    // 打印它的兄弟（递归）
    show_list(node->bro_down);

    // 递归打印它的子节点
    show_list(node->son);
}

int main(void) {
    menu_t* head;
    menu_t* temp;
    menu_t* temp_Son;

    // 创建头节点，它没有 father
    head = create_node(NULL, "第一级", NULL);

    // 创建头的第 1 个子节点，因为要为它创建子节点，所以要留返回值，免得找
    temp = create_node(head, "第二级-1", NULL);
    // 创建头的第 2 个子节点，返回值可以不留（已经接在 head 上了）
    create_node(head, "第二级-2", NULL);
    // 创建头的第 2 个子节点的子节点
    create_node(temp, "第二级-1-1", NULL);

    // 打印
    show_list(head);
    // show_list(head, 0);   // 用下面深度优化的 show_list 需要多一个参数
}

改了个尝试优先遍历的打印，带缩进，打印出来看起来比较好看

void show_list(menu_t *node, int indent)
{
    if (node == NULL)
    {
        return;
    }

    for (int i = 0; i < indent; i++)
    {
        printf("    ");
    }

    // 先打印当前节点
    printf("[%ld] %s (son: %ld)\n", (long)node, node->s, (long)node->son);

    // 递归打印它的子节点（深度优先）
    show_list(node->son, indent + 1);

    // 打印它的兄弟（递归）
    show_list(node->bro_down, indent);
}

更新^2022-8-12

原来的代码创建没有问题，但是在打印兄弟节点的时候，即使用了循环，又使用了递归，造成了对兄弟节点的重复打印，兄弟越多现象越明显。上面的代码已经修正了此错误，这里做个记录：

原来的代码 (✗)

    // 打印它的兄弟（递归）
    menu_t* boo = node->bro_down;
    while (boo != NULL) {        // 这里通过循环打印了后面的每一个兄弟
        show_list(boo);          // 这里递归进去又会执行这个循环再打印一次
        boo = boo->bro_down;
    }

改为 (✓)

去掉循环即可

    // 打印它的兄弟（递归）
    show_list(node->bro_down);

撰写回答

你尚未登录，登录后可以

和开发者交流问题的细节
关注并接收问题和回答的更新提醒
参与内容的编辑和改进，让解决方法与时俱进

推荐问题

相似问题

找不到问题？创建新问题

C语言链表遍历打印失败？

更新^2022-8-12

你尚未登录，登录后可以

c++模板类链表链接错误？

c++98环境循环单链表类的私有结构体与引用其的成员函数顺序问题？

未来有量子CPU，请问是否使用C/C++的项目现在采用Python这样方便的语言也可以有很好的运行效率（用户体验）呢？

pkg-config编译安装时提示需要glib库的支持？

链表的指针为什么有两种不同含义？

C语言 链表遍历打印失败？

更新2022-8-12

你尚未登录，登录后可以

c++模板类链表链接错误？

c++98环境循环单链表类的私有结构体与引用其的成员函数顺序问题？

未来有量子CPU，请问是否使用C/C++的项目现在采用Python这样方便的语言也可以有很好的运行效率（用户体验）呢？

pkg-config编译安装时提示需要glib库的支持？

链表的指针为什么有两种不同含义？

C语言链表遍历打印失败？

更新^2022-8-12