C语言中稀疏数组与稠密数组的打印实现问题

首先，先明确你已经定义的链表结构体：

typedef struct arr {
    int position;
    int value;
    struct arr *next;
} ARR;

接下来我们分两种场景来实现打印逻辑：

一、从稀疏数组打印为稠密数组 #

稀疏数组的链表节点只存储有非零值的位置，要转成稠密形式，我们需要补全所有从0到最大位置的节点，缺失的位置值填0。

实现思路： #

1. 先遍历稀疏链表，找到最大的position，确定稠密数组的长度；
2. 从position=0开始逐个遍历，同时用指针遍历稀疏链表，匹配当前位置：
   • 如果当前位置和链表节点的position一致，打印该节点的value，并移动链表指针；
   • 如果不一致，打印0；
3. 处理链表为空的边界情况（直接打印空数组即可）。

代码示例： #

#include <stdio.h>

// 你的结构体定义
typedef struct arr {
    int position;
    int value;
    struct arr *next;
} ARR;

void printDenseFromSparse(ARR *sparseHead) {
    if (sparseHead == NULL) {
        printf("[]\n");
        return;
    }

    // 第一步：找到最大的position
    ARR *temp = sparseHead;
    int maxPos = temp->position;
    while (temp != NULL) {
        if (temp->position > maxPos) {
            maxPos = temp->position;
        }
        temp = temp->next;
    }

    // 第二步：打印稠密数组
    printf("[");
    ARR *current = sparseHead;
    for (int i = 0; i <= maxPos; i++) {
        // 匹配当前位置
        if (current != NULL && current->position == i) {
            printf("(%d,%d)", current->position, current->value);
            current = current->next;
        } else {
            printf("(%d,0)", i);
        }
        // 控制逗号，最后一个元素不加逗号
        if (i != maxPos) {
            printf(",");
        }
    }
    printf("]\n");
}

小提示： #

• 这里假设你的稀疏链表是按position升序排列的，如果不是，建议先对链表按position排序，否则匹配逻辑会出错；
• 如果稀疏链表有重复的position节点，你可能需要先做去重处理（比如保留最后一个或者第一个节点）。

二、从稠密数组打印为稀疏数组 #

稠密数组的链表包含所有位置（包括值为0的），转成稀疏形式只需要过滤掉所有value=0的节点，只保留非零值的节点。

实现思路： #

1. 遍历稠密链表的每一个节点；
2. 仅当节点的value != 0时，打印该节点的(position, value)；
3. 处理链表为空的边界情况。

代码示例： #

void printSparseFromDense(ARR *denseHead) {
    if (denseHead == NULL) {
        printf("[]\n");
        return;
    }

    printf("[");
    ARR *current = denseHead;
    int first = 1; // 标记是否是第一个非零节点，控制逗号
    while (current != NULL) {
        if (current->value != 0) {
            if (!first) {
                printf(",");
            }
            printf("(%d,%d)", current->position, current->value);
            first = 0;
        }
        current = current->next;
    }
    printf("]\n");
}

小提示： #

• 这里不要求稠密链表的position连续，哪怕是离散的位置，只要value非零就会被打印；
• 如果稠密链表有重复的position节点，同样需要先处理（比如合并值或者去重）。

测试示例 #

我们用你给出的例子来测试：

// 构建稀疏链表：[(2,4),(3,5),(4,5)]
ARR node3 = {4, 5, NULL};
ARR node2 = {3, 5, &node3};
ARR node1 = {2, 4, &node2};
ARR *sparseHead = &node1;

// 打印稠密数组
printf("稀疏转稠密结果：");
printDenseFromSparse(sparseHead); // 输出：[(0,0),(1,0),(2,4),(3,5),(4,5)]

// 构建稠密链表：[(0,0),(1,0),(2,4),(3,5),(4,5)]
ARR dNode4 = {4,5,NULL};
ARR dNode3 = {3,5,&dNode4};
ARR dNode2 = {2,4,&dNode3};
ARR dNode1 = {1,0,&dNode2};
ARR dNode0 = {0,0,&dNode1};
ARR *denseHead = &dNode0;

// 打印稀疏数组
printf("稠密转稀疏结果：");
printSparseFromDense(denseHead); // 输出：[(2,4),(3,5),(4,5)]

运行这段代码就能得到你想要的输出啦～如果还有其他特殊情况（比如链表无序、有重复位置），可以再调整逻辑。

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