Code:
/*
This program utilizes the Collatz conjecture. The program can input any integer and it can also tell you the cycle length as well. Although, this code might look complex at first. It is quite simple. There are two doubly linked lists going on at once. So there is basically two copies of each function for each doubly linked list. For example there is two addtails and two deletes. Everything to do with Case 2 is marked with a 2. Everything to do with Case 1 is just left alone.
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct node //my node for the 1st case. Listing cycle lengths
{
int cycle_length;
int num;
struct node *prev;
struct node *next;
} Node;
typedef struct node2 //2nd node. This is for the hailstone sequence
{
int num;
struct node2 *prev;
struct node2 *next;
} Node2;
Node * newnode(int number, int cycle); //function prototypes. ill go into details of each below
Node2 * newnode2(int number);
Node * addtail(Node * head, Node * tail, Node * new);
Node2 * addtail2(Node2 * head2, Node2* tail2, Node2 * new);
Node * delete(Node * head);
Node2 * delete2(Node2 * head2);
int case1(int start, int finish, Node * head, Node *tail);
int case2(int num, Node2 * head2, Node2 * tail2);
int cycle(int num);
int comparecycles(Node * head, Node * tail);
void printtable(Node * head, Node *tail);
void printnodes(Node2 * head2, Node2 * tail2);
void printmenu();
int main()
{
Node * head;
Node * tail;
head = newnode(0,0); //dummy head and tail node for the 1st doubly linked list
tail = newnode(0,0);
head -> next = tail; //linking
tail -> prev = head;
Node2 * head2;
Node2 * tail2; //dummy head and tail for 2nd list
head2 = newnode2(0);
tail2 = newnode2(0);
head2 -> next = tail2; //linking
tail2 -> prev = head2;
int menu_option = 0;
int i = 0; //variables for where to start and end 1st linked list
int j = 0;
int k = 0; //variables for the start of the 2nd linked list
while (menu_option != 3)
{
printmenu();
printf(">>");
scanf("%d", &menu_option);
switch(menu_option)
{
case 1:
printf("Enter i\n>>");
scanf("%d", &i);
printf("Enter j\n>>");
scanf("%d", &j);
case1(i,j,head,tail); //running the case 1 function
printtable(head,tail);
delete(head);
break;
case 2:
printf("Enter Number\n>>");
scanf("%d", &k);
case2(k, head2, tail2); //running case 2
break;
case 3:
return 0;
break;
default:
printf("Error");
break;
}
}
return 0;
}
//newnode: This function allocates memory and set data members for the 1st linked list
//input: an integer (the number), a 2nd integer (number of cycles)
//output: pointer to a node
Node * newnode(int number, int cycle) //1st list
{
Node * new;
new = malloc(sizeof(Node)); //allocating memory
new -> num = number;
new -> cycle_length = cycle;
new -> prev = NULL; //linking
new -> next = NULL;
return new;
}
//newnode2: This function allocates memory and sets data members for the 2nd linked list
//input: an integer (the number)
//output: pointer to a node
Node2 * newnode2(int number) //2nd list
{
Node2 * new;
new = malloc(sizeof(Node)); //allocating memory
new -> num = number;
new -> prev = NULL; //linking
new -> next = NULL;
return new;
}
//addtail: Adds the new node to the tail of the 1st linked list
//input: dummy head and tail node. The new node to be added
//output: the dummy tail node
Node * addtail(Node * head, Node * tail, Node * new) //1st
{
if(tail -> prev == head) //if list is empty
{
head -> next = new;
new -> prev = head;
tail -> prev = new;
new -> next = tail;
return tail;
}
else //if list has nodes
{
new -> prev = tail -> prev;
new -> next = tail;
tail -> prev -> next = new;
tail -> prev = new;
return tail;
}
return NULL; //should never reach here
}
//addtail2: This function add the new node to the tail of the 2nd linked list
Node2 * addtail2(Node2 * head2, Node2 * tail2, Node2 * new) //2nd
{
if(tail2 -> prev == head2) //list is empty
{
head2 -> next = new;
new -> prev = head2;
tail2 -> prev = new;
new -> next = tail2;
return tail2;
}
else //not empty
{
new -> prev = tail2 -> prev;
new -> next = tail2;
tail2 -> prev -> next = new;
tail2 -> prev = new;
return tail2;
}
return NULL; //just in case
}
//delete: This function deletes all nodes, then starts over like the first lines of main
//input: dummy head node
//output: the current node
Node * delete(Node * head) //1st list
{
Node * cur;
Node * prev;
prev = head -> next;
cur = head -> next -> next;
while(cur != NULL)
{
free(prev);
prev = cur;
cur = cur -> next;
}
free(prev);
free(head); //everything is freed
Node * tail; //dummy tail node
head = newnode(0,0);
tail = newnode(0,0);
head -> next = tail; //linking
tail -> prev = head;
return cur;
}
//delete2: This function deletes all nodes, then starts over
//input: dummy head node
//output: the cur node
Node2 * delete2(Node2 * head2) //2nd list
{
Node2 * cur;
Node2 * prev;
prev = head2 -> next;
cur = head2 -> next -> next;
while(cur != NULL)
{
free(prev);
prev = cur;
cur = cur -> next;
}
free(prev); //freeing everything
free(head2);
Node2 * tail2;
head2 = newnode2(0); //starting over. linking
tail2 = newnode2(0);
head2 -> next = tail2;
tail2 -> prev = head2;
return cur;
}
//case1: This function does everything case 1 needs. adds data members. adds them to the tail of the list, prints the table and frees memory
//input: the start (i), the finish (j), dummy head and tail node
//output: an integer
int case1(int start, int finish, Node * head, Node * tail)
{
for(start; start <= finish; start++)
{
Node * new = newnode(start, cycle(start));
addtail(head, tail, new);
}
return 0;
}
//case2: This function does a lot. Adds data members. Adds nodes to list. Prints nodes and frees memory
//input: The number to start with, dummy head and tail node
//output: An integer
int case2(int num, Node2 * head2, Node2 * tail2)
{
int cycle_length = cycle(num);
Node2 * new = newnode2(num);
addtail2(head2, tail2, new);
while(num !=1)
{
if(num != 1 && num % 2 ==1)
{
num = 3 * num + 1;
Node2 * new = newnode2(num);
addtail2(head2, tail2, new);
}
else if(num != 1 && num % 2 == 0)
{
num = num/2;
Node2 * new = newnode2(num);
addtail2(head2, tail2, new);
}
}
printnodes(head2, tail2);
printf("The cycle length is %d\n", cycle_length);
delete2(head2);
return 0;
}
//cycle: This function is for the 1st and 2nd list. It gets the number of cycle lengths for a number
//input: An integer
//output: the correct cycle length
int cycle(int num)
{
int cycle_length = 0;
while(num != 1)
{
if(num != 1 && num % 2 == 1) //if it is odd
{
num = 3 * num + 1;
}
else if(num != 1 && num % 2 == 0) //even numbers
{
num = num/2;
}
cycle_length++; //increment counter
}
return cycle_length + 1; //including 1
}
//comparecycles: This function is for the 1st linked list. It gets the min and max cycle lengths for the double linked list and prints them
//input: dummy head and tail
//output: an integer
int comparecycles(Node * head, Node * tail)
{
Node * cur;
Node * max;
Node * min;
for(cur = head -> next; cur != tail; cur = cur -> next) //running through nodes
{
if(cur -> cycle_length > max -> cycle_length) //finding the biggest cycle length
{
max = cur;
}
else if(cur -> cycle_length < min -> cycle_length && min -> cycle_length != 0) //finding smallest
{
min = cur;
}
else
{
//do nothing
}
}
printf("The min is %d from %d\n", min -> cycle_length, min -> num);
printf("The max is %d from %d\n", max -> cycle_length, max -> num);
return 0;
}
//printtable: This prints the table for the 1st linked list
//input: dummy head and tail
//output: void function
void printtable(Node * head, Node * tail)
{
Node * cur;
printf("Number\tCycle Length\n"); //table header
if(head -> next != tail)
{
for(cur = head -> next; cur != tail; cur = cur-> next) //run through nodes
{
printf("%d\t%d\n", cur -> num, cur -> cycle_length); //printing data members
}
}
else //if list is empty
{
printf("Empty List");
}
comparecycles(head, tail); //printing min and max
}
//printnodes: This function prints the hailstone sequence for the 2nd list
//input: dummy head and tail
//output: void function
void printnodes(Node2 * head2, Node2 * tail2)
{
Node2 * cur;
if(head2 -> next != tail2)
{
for(cur = head2 -> next; cur != tail2; cur = cur -> next) //run through
{
printf("%d\n", cur -> num); //prints data
}
}
else //if empty
{
printf("Empty List");
}
}
//printmenu: This function prints the main menu
//input: N/A
//output: void
void printmenu()
{
printf("1) Caculate cycle lengths between i and j\n");
printf("2) Generate hailstone sequence for any number\n");
printf("3) Exit the program\n");
}
