C 堆栈实现。关于解引用和双指针的问题

Question

大家好。我是 C 语言新手，而且堆栈溢出，所以请放轻松:)我对 C 中的堆栈代码有几个疑问:

1) push(&stackPtr, value); 为什么 stackPtr 必须有 & 符号？如果没有它，会得到什么功能？

2) topPtr = newPtr; 为什么 topPtr 必须是 *topPtr ？如果没有它，代码会发生什么？

3) *topPtr = (*topPtr)->nextPtr; 为什么 *topPtr 必须有 * ？没有 * 符号会怎样？

感谢您的提前答复。

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

// self-referential structure                     
struct stackNode {                                   
   int data; // define data as an int             
   struct stackNode *nextPtr; // stackNode pointer
};

typedef struct stackNode StackNode; // synonym for struct stackNode
typedef StackNode *StackNodePtr; // synonym for StackNode*

// prototypes
void push(StackNodePtr *topPtr, int info);
int pop(StackNodePtr *topPtr);
void printStack(StackNodePtr currentPtr);
void instructions(void);

// function main begins program execution
int main(void)
{ 
   StackNodePtr stackPtr = NULL; // points to stack top
   int value; // int input by user

   instructions(); // display the menu
   printf("%s", "? ");
   unsigned int choice; // user's menu choice
   scanf("%u", &choice);

   // while user does not enter 3
   while (choice != 3) {

      switch (choice) { 
         // push value onto stack
         case 1:      
            printf("%s", "Enter an integer: ");
            scanf("%d", &value);
            push(&stackPtr, value);
            printStack(stackPtr);
            break;
         // pop value off stack
         case 2:      
            // if stack is not empty
            if (stackPtr != NULL) {
               printf("The popped value is %d.\n", pop(&stackPtr));
            }

            printStack(stackPtr);
            break;
         default:
            puts("Invalid choice.\n");
            instructions();
            break;
      } // end switch

      printf("%s", "? ");
      scanf("%u", &choice);
   }

   puts("End of run.");
}

// display program instructions to user
void instructions(void)
{ 
   puts("Enter choice:\n"
      "1 to push a value on the stack\n"
      "2 to pop a value off the stack\n"
      "3 to end program");
}

// insert a node at the stack top
void push(StackNodePtr *topPtr, int info)
{ 
   StackNodePtr newPtr = malloc(sizeof(StackNode));

   // insert the node at stack top
   if (newPtr != NULL) {           
      newPtr->data = info;
      newPtr->nextPtr = *topPtr;
      topPtr = newPtr; 
   }                     
   else { // no space available
      printf("%d not inserted. No memory available.\n", info);
   } 
}

// remove a node from the stack top
int pop(StackNodePtr *topPtr)
{ 
   StackNodePtr tempPtr = *topPtr;             
   int popValue = (*topPtr)->data;  
   *topPtr = (*topPtr)->nextPtr;
   free(tempPtr);               
   return popValue;
}

// print the stack
void printStack(StackNodePtr currentPtr)
{ 
   // if stack is empty
   if (currentPtr == NULL) {
      puts("The stack is empty.\n");
   } 
   else { 
      puts("The stack is:");

      // while not the end of the stack
      while (currentPtr != NULL) { 
         printf("%d --> ", currentPtr->data);
         currentPtr = currentPtr->nextPtr;
      }

      puts("NULL\n");
   } 
}

Answer 1

这都是非常基础的 C 语言，因此我会尽力尽可能清晰，但我建议您仔细阅读有关该主题的引用书。

这段代码定义了一个结构stackNode其中包含一些数据，以及指向同一结构的“指针”。

因为stackNode是一个结构体，当您将其作为参数传递给函数时，编译器会创建它的副本并将其传递给函数。这称为“通过复制传递参数”。示例:

StackNode node;
foo(node) ;

void foo(StackNode  n) {
   /* foo() function can use the parameter n which is a local copy of node.
      you can modify n in the foo() function, that will not modify the node variable */
}

这意味着该函数无法修改您的原始数据。它可以修改函数的本地副本，该副本在函数结束时丢失。

如果要修改给定的参数，必须“通过地址”而不是“通过复制”传递参数。你这样做:

StackNode node;
foo(&node) ;

void foo(StackNode  *n) {
   /* foo() function accesses the node variable via its address n. (*n) represents
      the content at address n, which is node. */
}

在此代码中，函数 foo() 获取 StackNode 的地址(而不是 StackNode 的副本)。通过“取消引用”地址，您可以访问指针“指向”的内容，从而“真正”修改它。 “取消引用”由“*”运算符执行，而“&”运算符给出变量的“引用”(地址)。

现在，开始编写您的代码。我会以稍微不同的顺序回答您的问题，以便更清楚(我认为)。

什么void push(StackNodePtr *topPtr, int info)所做的就是malloc一个新节点，使其指向当前的topPtr，然后修改topPtr以指向这个新节点。

因此它修改了topPtr。

因此topPtr需要通过引用传递。

因此你需要void push(StackNodePtr *topPtr, int info)而不是void push(StackNodePtr topPtr, int info)

因此你需要用 push(&stackPtr ,value) 来调用它

如果您调用push(stackPtr ,value) ，然后:

• 首先，您的编译器应该提示(至少发出警告)
• 有一天你会崩溃，因为你将修改未知的内存区域

您现在还应该明白为什么需要 (*topPtr) = newPtr而不是topPtr = newPtr 。因为你想要修改stackPtr，并且你需要取消引用topPtr。

后面的代码相同。

这就是说，我可以想到更容易实现堆栈......;-)