PTA（栈和队列）1-3 用链栈实现将非负的十进制数转换为指定的进制数

1-3 用链栈实现将非负的十进制数转换为指定的进制数

分数 3

作者 CUIT通信DS课程组

单位 成都信息工程大学

利用链序栈将输入的非负的十进制数N转换为指定的d（二、八或十六）进制数。

链栈的定义如下：

1
2
3
4
5
typedef struct SNode
{  
     DataType data;      // 数据域
     struct SNode *next; // 指向后继结点的指针域
}SNode,*LinkStack;

函数接口定义：

1
int DecimalConvert(LinkStack s, int dec, int scale);

函数参数说明：形参–s、dec、scale，其中，s是存放转换后的scale进制数的各位数字，dec 主函数输入的待转换的十进制数，scale是指定的数制（只能是2、8或16）。 函数返回值：1，表示函数执行完成；0，表示函数未成功执行。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct SNode
{
    DataType data;        // 数据域
    struct SNode* next;        // 指向后继结点的指针域
}SNode, * LinkStack;

int InitLinkStack(LinkStack* top)
{  /* 初始化链栈 */
    *top = (LinkStack)malloc(sizeof(SNode));
    if (*top == NULL)
    {
        printf("初始化链栈出错");
        return 0;
    }
    (*top)->next = NULL;
    return  1;
}
int LinkStackEmpty(LinkStack top)
{ /* 判栈空函数 */
    if (top->next == NULL)
        return 1;
    else
        return 0;
}
int LinkStackPush(LinkStack top, DataType e)
{ /* 压栈函数 */
    SNode* p;
    p = (SNode*)malloc(sizeof(SNode));
    if (!p)
    {
        printf("入栈操作出错！\n");
        return 0;
    }
    p->data = e;
    p->next = top->next;
    top->next = p;
    return 1;
}
int LinkStackPop(LinkStack top, DataType* e)
{ /* 弹栈函数 */
    SNode* p;
    if (!top->next)
    {
        printf("栈已空，无法完成出栈操作！\n");
        return 0;
    }
    p = top->next;
    top->next = p->next;
    *e = p->data;
    free(p);
    return 1;
}
/* 本题要求函数 */
int DecimalConvert(LinkStack s, int dec, int scale);
int main()
{
    LinkStack s;
    char ch[] = "0123456789ABCDEF";  //二、八、十六进制所使用的数字
    unsigned dec, scale;
    DataType tmp;

    InitLinkStack(&s);
    scanf("%d %d", &dec, &scale);  // 某些编译器要求此处改为scanf_s

    if (DecimalConvert(s, dec, scale))
    {
        printf("十进制数:%d,转换为:%d进制数,结果为:", dec, scale);
        while (!LinkStackEmpty(s))
        {
            LinkStackPop(s, &tmp);
            printf("%c", ch[tmp]);
        }
    }
    else
        printf("数制转换未成功！");

    return 0;
}
/* 请在这里填写答案 */

输入样例：

1
20 2

输出样例：

1
十进制数:20,转换为:2进制数,结果为:10100

输入样例：

1
20 8

输出样例：

1
十进制数:20,转换为:8进制数,结果为:24

输入样例：

1
20 16

输出样例：

1
十进制数:20,转换为:16进制数,结果为:14

此题用的链栈存储结构，带头节点（因为我看到初始化链栈的时候分配了）

答案

1
2
3
4
5
6
7
8
9
10
int DecimalConvert(LinkStack s, int dec, int scale) {
    if (scale < 2 || scale > 16) {
        return 0;
    }
    while (dec != 0) {
        LinkStackPush(s, dec % scale); // 取余放入链栈中
        dec /= scale;
    }
    return 1;
}

一、unsigned是什么

  • unsigned 是一个类型修饰符（关键字），用于修饰整数类型，表明该类型的变量只存储非负整数（即取值范围从 0 开始），没有符号位

  • 当 unsigned 单独使用时（如 unsigned dec, scale;），默认修饰的是 int 类型，等价于 unsigned int dec, scale;，表示 dec 和 scale 是 “无符号整数” 变量。

二、*top == NULL为啥用*top

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct SNode
{
    DataType data;        // 数据域
    struct SNode* next;        // 指向后继结点的指针域
}SNode, * LinkStack;

int InitLinkStack(LinkStack* top)
{  /* 初始化链栈 */
    *top = (LinkStack)malloc(sizeof(SNode));
    if (*top == NULL)
    {
        printf("初始化链栈出错");
        return 0;
    }
    (*top)->next = NULL;
    return  1;
}
  • 为什么这里用*top？top不是指针吗，不应该直接top指向下个一个结点吗，直接top = …

1.核心原因：top 是 “指针的指针”（LinkStack* 类型）

在函数 InitLinkStack(LinkStack* top) 中：

  • LinkStack 是 struct SNode* 的 typedef 别名（即 LinkStack 本身就是一个指针类型，指向 SNode 结构体）。
  • 因此 LinkStack* top 等价于 struct SNode**top，表示 top 是一个 “指针的指针”—— 它指向的是一个 LinkStack 类型的指针（即 struct SNode* 类型的指针）。

2.为什么需要 “指针的指针”？

函数的目标是 初始化外部的栈顶指针（即让外部的 LinkStack 变量指向新分配的节点）。但 C 语言中函数参数是 值传递：如果直接传递 LinkStack top（一级指针），函数内部的 top 只是外部指针的一份拷贝，修用 *top 的作用：修改外部指针的值

top 是 “指针的指针”（指向外部的 LinkStack 指针），通过 *top 可以

3.间接访问并修改外部指针本身的值：

  • *top = (LinkStack)malloc(...)：给外部的栈顶指针分配内存，让它指向新节点。
  • (*top)->next = NULL：通过外部指针访问新节点，初始化其 next 为 NULL（表示栈为空）。

在c++中可以用LinkStack &top引用写

三、int LinkStackPop(LinkStack top, DataType* e)

image-20251024103553638

  • LinkStack 是 struct SNode* 的别名，即 top 是一个 一级指针参数（函数调用时传递的是外部栈顶指针的拷贝）。
  • 对于一级指针参数：
    1. 可以修改指针指向的内存内容（例如 top->next = p）：因为 top 拷贝了外部指针的地址，通过 top 能访问到同一块内存（栈顶节点），所以对 top->next 的修改会直接影响外部的链表结构（这正是压栈需要的操作）。