daily pastebin goal
43%
SHARE
TWEET

PI 2016/2017 Parte B

a guest Jun 13th, 2018 105 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int MAXc = 3;
  5.  
  6. typedef struct chunk {
  7.     int vs[3];
  8.     struct chunk *prox;
  9. } *CList;
  10.  
  11. typedef struct stackC {
  12.     CList valores;
  13.     int sp;
  14. } StackC;
  15.  
  16. /* NOTA INICIAL: A forma C da stack suscitou-me algumas dúvidas quanto à ordem na stack. Vou deixar aqui a forma que entendi que funciona, que é a
  17. * forma que tive sempre em consideração durante a implementação dos exercícios:
  18. *
  19. * Ordem pela qual os valores foram inseridos : 1 -> 12 -> 23 -> 34 -> 45 -> 56 -> 67
  20. * Fazendo pop, retira o último inserido: 67. Fazendo pop outra vez, o valor retirado seria 56.
  21. * Fazendo reverse, o resultado seria o mesmo que se obteria caso a inserção fosse feita da seguinte forma: 67 -> 56 -> 45 -> 34 -> 23 -> 12 -> 1
  22. */
  23.  
  24.  
  25. /* Pergunta 1
  26. * Esta função vai introduzir um valor novo na stack. Recebe um apontador para a stack e o valor a ser introduzido
  27. */
  28. int push(StackC *stack, int value){
  29.  
  30.     // Se o valor armazenado em 'sp' é igual a MAXc, entao o array em stack->valores está cheio. É preciso entao criar um novo
  31.     // e ligar esse novo ao array no topo da lista, sem perder a continuidade das listas ligadas
  32.     if(stack->sp == MAXc){
  33.  
  34.         // O novo valor de sp vai ser 1, já que o novo array terá 1 elemento
  35.         stack->sp = 1;
  36.         // Reserva espaço na memória para alocar um novo CList
  37.         CList newCList = malloc(sizeof(struct chunk));
  38.  
  39.         // Insere o valor no novo CList
  40.         newCList->vs[0] = value;
  41.         //  Liga o nov CList à cabeça da lista
  42.         newCList->prox = stack->valores;
  43.         // Actualiza o apontador da stack para a nova cabeça da lista ligada
  44.         stack->valores = newCList;
  45.     } else {
  46.         // Se o valor em 'sp' é menor que MAXc, então o array na cabeça da lista não está cheio. Vai então colocar o valor nesse
  47.         // array, e incrementar o valor de 'sp'
  48.         stack->valores->vs[stack->sp++] = value;
  49.     }
  50.  
  51.     return 0;
  52. }
  53.  
  54.  
  55. /* Pergunta 2
  56. * Esta função vai retirar o último valor adicionado à stack. Recebe um apontador para a stack, e um apontador para um inteiro,
  57. * que irá armazenar o valor retirado da stack
  58. */
  59. int pop(StackC *stack, int *value){
  60.     // Primeiro coloca em 'value' o último valor da stack
  61.     *value = stack->valores->vs[stack->sp - 1];
  62.  
  63.     // Agora vai efectivamente retirar esse valor da stack. Se o valor de 'sp' for igual a 1, então significa que o array na cabeça da
  64.     // lista apenas tem um valor, que vai ser retirado. Significa que basta apontar 'stack->valores' para o próximo array da lista ligada
  65.     // e fazer free à cabeça da lista
  66.     if(stack->sp == 1){
  67.         // Actualiza o valor de 'sp' para MAXc
  68.         stack->sp = MAXc;
  69.  
  70.         // Guarda a cabeça da lista, para se fazer free mais tarde
  71.         CList toRemove = stack->valores;
  72.  
  73.         // Actaliza a cabeça da lista para o próximo array da lista
  74.         stack->valores = stack->valores->prox;
  75.         // Faz free à antiga cabeça da lista
  76.         free(toRemove);
  77.     } else {
  78.         // Se o valor de 'sp' for maior que 1, então basta colcar o último valor do array da cabeça da lista a NULL e decrementar o valor de 'sp'
  79.         stack->valores->vs[--stack->sp] = NULL;
  80.     }
  81.  
  82.     return 0;
  83. }
  84.  
  85.  
  86. // Funcao auxiliar para popular a stack com os valores dados no teste
  87. void initializeStack(StackC *stack){
  88.     push(stack, 1);
  89.     push(stack, 12);
  90.     push(stack, 23);
  91.     push(stack, 34);
  92.     push(stack, 45);
  93.     push(stack, 56);
  94.     push(stack, 67);
  95. }
  96.  
  97.  
  98. // Funcao auxiliar para imprimir os valores na stack
  99. void printStack(StackC *stack){
  100.     int first = 1;
  101.     CList currentArray = stack->valores;
  102.  
  103.     while(currentArray != NULL){
  104.         int i = 0;
  105.         int size = first ? stack->sp : MAXc;
  106.  
  107.         while(i < size){
  108.             printf("%d\n", currentArray->vs[i++]);
  109.         }
  110.         printf("--------\n");
  111.  
  112.         currentArray = currentArray->prox;
  113.         first = 0;
  114.     }
  115. }
  116.  
  117.  
  118. /* Pergunta 3
  119. * Esta função recebe a stack, e conta quantos elementos tem.
  120. */
  121. int size(StackC stack){
  122.     // Primeiro conta quantos arrays completos tem na lista ligada
  123.     int numberOfLinkedCLists = 0;
  124.  
  125.     CList nextCList = stack.valores->prox;
  126.  
  127.     while(nextCList != NULL){
  128.         numberOfLinkedCLists++;
  129.         nextCList = nextCList->prox;
  130.     }
  131.  
  132.     // Esses arrays completos têm MAXc elementos cada um, portanto basta retornar a seguinte conta
  133.     return numberOfLinkedCLists * MAXc + stack.sp;
  134. }
  135.  
  136.  
  137. /* Pergunta 4
  138. * Esta função faz o reverse à stack utilizando as funções push e pop implementadas.
  139. */
  140. void reverse(StackC *stack){
  141.     int stackSize = size(*stack);
  142.     int popdedValues[stackSize];
  143.    
  144.     // Primeiro vamos retirar todos os elementos da stack, e armazená-los num array
  145.     for(int i = 0; i < stackSize; i++){
  146.         pop(stack, &popdedValues[i]);
  147.     }
  148.  
  149.     // Depois percorremos o array, e fazemos push dos seus valores. Isto vai colocar os valores na stack pela ordem inversa que tinha antes
  150.     for(int i = 0; i < stackSize; i++){
  151.         push(stack, popdedValues[i]);
  152.     }
  153. }
  154.  
  155.  
  156. // Função auxiliar para buscar um valor numa determinada posição da stack (para a pergunta 5)
  157. int getValueInPosition(StackC stack, int position){
  158.     CList currentArray = stack.valores;
  159.     int limit = stack.sp;
  160.  
  161.     while(position >= limit){
  162.         currentArray = currentArray->prox;
  163.         position -= limit;
  164.         limit = MAXc;
  165.     }
  166.  
  167.     return currentArray->vs[limit - 1 - position];
  168. }
  169.  
  170.  
  171. // Função auxiliar para fazer set de um valor numa determinada posição da stack (para a pergunta 5)
  172. void setValueInPosition(StackC *stack, int position, int value){
  173.     CList currentArray = stack->valores;
  174.     int limit = stack->sp;
  175.  
  176.     while(position >= limit){
  177.         currentArray = currentArray->prox;
  178.         position -= limit;
  179.         limit = MAXc;
  180.     }
  181.  
  182.     currentArray->vs[limit - 1 - position] = value;
  183. }
  184.  
  185.  
  186. /* Pergunta 5
  187. * Esta função faz o reverse da stack sem utilizar as funções push e pop. Não percebi muito bem o que o professor quis dizer com
  188. * "que reutiliza as células da lista". Creio que isso apenas é para dizer para não usar o push e o pop. O que eu fiz foi simplesmente
  189. * trocar o primeiro valor pelo último, o segundo pelo penúltimo, etc.
  190. */
  191. void alternativeReverse(StackC *stack){
  192.     int beginning = 0, end = size(*stack) - 1;
  193.     int aux;
  194.  
  195.     while(beginning < end){
  196.         aux = getValueInPosition(*stack, beginning);
  197.         setValueInPosition(stack, beginning++, getValueInPosition(*stack, end));
  198.         setValueInPosition(stack, end--, aux);
  199.     }
  200. }
  201.  
  202.  
  203.  
  204. int main(void){
  205.     // Inicializacao da stack. Inicialmente o valor em sp é 0, porque nao tem nenhum valor.
  206.     StackC stack;
  207.     stack.sp = 0;
  208.  
  209.     CList clist = malloc(sizeof(struct chunk));
  210.     clist->prox = NULL;
  211.     stack.valores = clist;
  212.  
  213.     // Passa um apontador para a stack, para que possamos mudar o seu valor (passar o objecto por referência). Esta funcao vai
  214.     // colocar os valores dados no teste na stack.
  215.     initializeStack(&stack);
  216.  
  217.     // Imprime a stack, tal como é dada no teste, e o seu tamanho.
  218.     printf("Initialized stack: \n");
  219.     printStack(&stack);
  220.     printf("Current size: %d\n", size(stack));
  221.  
  222.  
  223.  
  224.     // Variável que terá o último valor retirado da stack.
  225.     int popedValue;
  226.  
  227.     // Retira o primeiro valor da stack. É passado apontadores para ambas stack e vairável 'popedValue', para que possamos
  228.     // modificar as variáveis (a stack terá menos um valor, e a variável terá esse valor)
  229.     pop(&stack, &popedValue);
  230.     printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
  231.     printStack(&stack);
  232.     printf("Current size: %d\n", size(stack));
  233.  
  234.     pop(&stack, &popedValue);
  235.     printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
  236.     printStack(&stack);
  237.     printf("Current size: %d\n", size(stack));
  238.  
  239.     pop(&stack, &popedValue);
  240.     printf("\n\nPopedValue: %d\nNew state of the stack:\n", popedValue);
  241.     printStack(&stack);
  242.     printf("Current size: %d\n", size(stack));
  243.  
  244.  
  245.     // Faz o reverse da stack, utilizando as funcoes push e pop implementadas
  246.     reverse(&stack);
  247.     printf("\n\nReversed stack: \n");
  248.     printStack(&stack);
  249.     printf("Current size: %d\n", size(stack));
  250.  
  251.  
  252.     // Faz o reverse da stack apenas trocando valores (o primeiro pelo último, o segundo pelo penúltimo, etc.)
  253.     alternativeReverse(&stack);
  254.     printf("\n\nAlternative reversed stack: \n");
  255.     printStack(&stack);
  256.     return 0;
  257. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top