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

requests_001
  • 1
福建新手上路,请多包涵
#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]

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

回复
阅读 407
1 个回答
边城
  • 54.8k
四川

这结构不是单纯的链表结构,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 函数用的 PascalCasesnake_case 混用。C 语言用 snake_case 比较多,建议统一成这种风格。即 create_head_nodeshow_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);
}

image.png


更新2022-8-12

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

原来的代码 (✗)

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

改为 (✓)

去掉循环即可
    // 打印它的兄弟(递归)
    show_list(node->bro_down);
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏