1votos

Listas palíndromas en C

por josejuan hace 6 años

Tail recursión en listas genéricas simplemente enlazadas.

Comprobar si una lista es palíndroma

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
#include <stdio.h> 
#include <malloc.h> 
 
typedef struct _SingleLinkedList { 
  struct _SingleLinkedList *next; 
  void *object; 
} SingleLinkedList; 
 
void SLL_insert(SingleLinkedList **list, void *object) { 
  SingleLinkedList *tail = *list; 
  *list = (SingleLinkedList *) malloc(sizeof(SingleLinkedList)); 
  (*list)->next = tail; 
  (*list)->object = object; 
 
// chequeados de palíndromas en listas simples (con tipo genérico) 
// se realiza tail-recursion ¡en pila! (cuidado con la longitud) 
  int SLL_isPalindrome_tailRec(SingleLinkedList *list, int (*areEquals)(void *, void *), SingleLinkedList **cursor) { 
    if(list->next) { 
      if(!SLL_isPalindrome_tailRec(list->next, areEquals, cursor)) return 0; 
      if(!*cursor) return 1; // fin de emparejamientos 
    if(list == *cursor) {*cursor = NULL; return 1;} // objeto central de una lista impar 
    int cmp = areEquals((*cursor)->object, list->object); 
    if((*cursor)->next == list) {*cursor = NULL; return cmp;} // objetos centrales de una lista par 
    *cursor = (*cursor)->next; 
    return cmp; 
int SLL_isPalindrome(SingleLinkedList *list, int (*areEquals)(void *, void *)) { 
  if(!list) 
    return 0; 
  SingleLinkedList *cursor = list; 
  return SLL_isPalindrome_tailRec(list, areEquals, &cursor); 
 
// test 
void SingleListPalindromeTest(char *test) { 
  int cmpChar(void *a, void *b) {return *(char *)a == *(char *)b;} 
  SingleLinkedList *list = NULL; 
  char *i = test; 
  while(*i) SLL_insert(&list, i++); 
  printf("La cadena '%s' %s es palíndroma.\n", test, SLL_isPalindrome(list, cmpChar) ? "si" : "no"); 
  // SSL_drop(list); 
 
int main(int argc, char **argv) { 
   
  SingleListPalindromeTest("abcba"); 
  SingleListPalindromeTest("abccba"); 
  SingleListPalindromeTest("abccbaa"); 
  SingleListPalindromeTest("abccb2a"); 
   
  return 0; 
1 comentario
0votos

Escrito por Raul GM hace 6 años

Esto es lo que decías en el comentario anterior.

Le voy a tener que dar a print y fijarme punto a punto.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.