perm_gen.c (2594B)
1 /*** 2 * perm_gen.c 3 * 4 * adapted from http://cs/courses/fall2008/algorithms/code/c_examples/structs.c 5 * and http://cs/courses/fall2008/algorithms/code/c_examples/node_list.c 6 ***/ 7 8 #include <stdio.h> // printf 9 #include <stdlib.h> // for malloc 10 11 // link 12 // alias for pointer 13 typedef struct link_type *link; 14 // structure pointed to 15 struct link_type { 16 int value; 17 link next; 18 }; 19 // constructor 20 link new_link(int value, link next){ 21 link self = (link) malloc(sizeof(struct link_type)); 22 if (self){ // don't do this if memory wasn't allocated. 23 self->value = value; // set fields 24 self->next = next; 25 } 26 return self; 27 } 28 29 // build a chain of links 30 link new_chain(int links) { 31 // make an empty chain 32 link cur = NULL; 33 int i = 0; 34 for (i; i < links; i++) { 35 link next = new_link(0, cur); 36 cur = next; 37 } 38 return cur; // last link in chain 39 } 40 41 // chain utilities 42 43 // chain comparision 44 // 1 for true, 0 for false 45 int chains_equal (link first, link second) { 46 while (first->next != NULL) { 47 if (second->next == NULL) { // if first is longer than second 48 return 0; 49 } 50 else if (first->value != second->value) { 51 return 0; 52 } 53 first = first->next; // advance along chains 54 second = second->next; 55 } 56 // if second is longer than first 57 if (second->next != NULL) { 58 return 0; 59 } 60 // if they are the same length and each link has the same value 61 return 1; 62 } 63 64 // copy a chain 65 link chain_cpy(link target) { 66 if (target == NULL) { 67 return NULL; 68 } 69 link first = new_link(target->value, NULL); 70 link last = first; 71 link tmp_tar = target; 72 while (tmp_tar->next != NULL) { 73 tmp_tar = tmp_tar->next; // advance 74 link next = new_link(tmp_tar->value, NULL); 75 last->next = next; 76 last = next; 77 } 78 return first; 79 } 80 81 // print chain 82 int print_chain(link cur) { 83 while (cur != NULL) { 84 printf("%d ", cur->value); 85 cur = cur->next; 86 } 87 return 0; 88 } 89 90 int perm_gen_test() { 91 link first = new_chain(3); // two empty chains, length 3 92 link second = new_chain(3); 93 printf("Test (expect 1): %d\n", chains_equal(first, second)); // are equal 94 95 second = new_chain(2); // turn one of them into a chain of 2 96 printf("Test (expect 0): %d\n", chains_equal(first, second)); // no longer equal 97 98 first->next->next->value = 4; // set the value of the last link in the first chain 99 printf("Test (expect 4): %d\n", first->next->next->value); // print it 100 101 second = new_chain(3); // change second chain back to length 3 102 printf("Test (expect 0): %d\n", chains_equal(first, second)); // are not equal 103 104 // printing 105 printf("Test (expect 0 0 4): "); 106 print_chain(first); 107 printf("\n"); 108 return 0; 109 }