Реализация стека CВопрос о разыменовании и двойных указателях - PullRequest
Новая
       15

Реализация стека CВопрос о разыменовании и двойных указателях

0 голосов
/ 30 октября 2019

Добрый день всем. Я новичок в C и переполнение стека, так что будьте осторожны со мной, пожалуйста :) У меня мало вопросов об этом коде стека в C:

1) push(&stackPtr, value);, почему stackPtr должен иметь & sign? а какая функция получится без нее?

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");
   } 
}

1 Ответ

0 голосов
/ 31 октября 2019

Это все довольно простой 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), так это назначает новый узел, делает его указателем на текущий 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.

То же самое в последнем коде.

Тем не менее, я могу думать о том, что реализовать стек намного проще ... ; -)

...