Zach Dann
Green Bastard from parts unknown
Joined class mailing list
Setup class chat, (screen)
Edited opus
Finished data type program
Cloned and updated repository with data type program
Created the linked list program
Was in class friday the seventh minding my own business when my station was turned off by a person who will remain unnamed. Logged back in to lab46 to see my data saved in a .c.save file which was awesome. It looked something alon the lines of this,
list.c list.c.saveSo i didn't have to retype all the code. I did notice after compiling and trying to run a few times the insertion function seemed to be off by one. It printed out something similar to
Which node would you like to insert before: 3 eneter a value: 5 [0] 15 -> [1] 25 -> [2] 36 -> [3] 44 -> [4] 5 -> [5] 67 -> NULL
It would insert after the desired node. (makes a great append function if you are adding just one node) Thought maybe because we set “tmp = list” that instead of starting at the beginning it was starting at the first node. Attempted to fix this in a couple of ways and got a segmentation fault.
Found where my mistake was, i forgot to subtract 1 from the input variable. Finished code for Creating the list:
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
typedef struct node Node;
int main()
{
int input;
Node *list, *tmp;
list = tmp = NULL;
while( input != -1)
{
printf(" enter a value (-1 to end):");
scanf("%d", &input);
if(input != -1)
{
if(list == NULL)
{
list=tmp= (Node *)malloc(sizeof(Node));
tmp->next=NULL;
list->value=input;
}
else
{
tmp->next=(Node *)malloc(sizeof(Node));
tmp->next->next=NULL;
tmp->next->value=input;
tmp=tmp->next;
}
}
}
And displaying the list:
input=0;
tmp=list;
while(tmp != NULL)
{
printf("[%d] %d -> ", input, tmp->value);
tmp=tmp->next;
input = input++;
}
printf("NULL\n");
Inserting before a node:
printf("which node would you like to insert before? ");
scanf("%d", &input);
int seeker;
tmp=list;
Node *tmp2=NULL;
for(seeker=0;seeker<(input-1);seeker++)
{
tmp=tmp->next;
}
if( input == 0 )
{
printf("Enter value for new Node: ");
scanf("%d", &input);
tmp2=(Node *)malloc(sizeof(Node));
tmp2->value=input;
tmp2->next=NULL;
tmp2->next=tmp;
list=tmp2;
}
else
{
printf("Enter a value to insert: ");
scanf("%d", &input);
tmp2=(Node *)malloc(sizeof(Node));
tmp2->value=input;
tmp2->next=tmp->next;
tmp->next=tmp2;
}
Appending after a node:
printf("which node would you like to append after? ");
scanf("%d", &input);
tmp=list;
Node *tmp3=NULL;
for(seeker=0;seeker<input;seeker++)
{
tmp=tmp->next;
}
printf("Enter a value to append: ");
scanf("%d", &input);
tmp3=(Node *)malloc(sizeof(Node));
tmp3->value=input;
tmp3->next=tmp->next;
tmp->next=tmp3;
Also added the executable and the source code to my repository.
Finished remove functionality by adding an if statement:
tmp=list;
printf("Enter a node to remove ");
scanf("%d", &input);
for(seeker=0;seeker<(input-1);seeker++)
{
tmp=tmp->next;
}
if(input == 0)
{
tmp=list;
tmp2=tmp;
tmp->next=tmp2->next;
list=tmp=tmp->next;
tmp2->next=NULL;
}
else
{
tmp2=tmp->next;
tmp->next=tmp2->next;
tmp2->next=NULL;
}
Working on menu for singly linked list, meanwhile got doubly linked list build, display, and insert functions.
Build function:
List *build()
{
Node *tmp = NULL;
List *mylist = (List *) malloc(sizeof(List));
mylist->start = mylist->end = NULL;
int input = 0;
printf("Enter a value(-1 to end): ");
scanf("%d", &input);
while (input != -1)
{
if (mylist->start == NULL)
{
mylist->start = mylist->end =
(Node *) malloc(sizeof(Node));
mylist->start->value = input;
mylist->next=mylist->prev=NULL;
}
else
{
mylist->end->next = (Node *) malloc(sizeof(Node));
mylist->end->next->value = input;
mylist->end->next->next = NULL;
mylist->end->next->prev = mylist->end;
mylist->end = mylist->end->next;
}
printf("Enter a value(-1 to end): ");
scanf("%d", &input);
}
return (mylist);
}
Display (forward)
void displayf(List * mylist)
{
Node *tmp = NULL;
int input = 0;
tmp = mylist->start;
while (tmp != NULL)
{
printf("[%d] %d -> ", input, tmp->value);
tmp = tmp->next;
input = input++;
}
printf("NULL\n");
}
Display (backwards)
void displayb(List * mylist)
{
Node *tmp = NULL;
int input = 0;
tmp = mylist->end;
while (tmp != mylist->start)
{
printf("[%d] %d -> ", input, tmp->value);
input = input++;
tmp = tmp->prev;
}
tmp = mylist->start;
printf("[%d] %d ->", input++, tmp->value);
printf("NULL\n");
}
Insert (includes seek function and building a new node)
List *insert(List * mylist, Node * place, Node * newNode)
{
if (place == mylist->start)
{
newNode->next = place;
place->prev = newNode;
newNode->prev = NULL;
mylist->start = newNode;
}
else
{
newNode->next = place;
place->prev->next = newNode;
newNode->prev = place->prev;
place->prev = newNode;
}
return (mylist);
}
Seek
Node *seek(List *mylist)
{
Node *place;
int input;
int seeker;
printf("Which node would you like to insert before: ");
scanf("%d", &input);
place=mylist->start;
for(seeker=0;seeker<input;seeker++)
{
place=place->next;
}
return (place);
}
newNode
Node *newNode()
{
int input;
printf("Enter a value for the new node: ");
scanf("%d", &input);
Node *newNode;
newNode= (Node *) malloc(sizeof(Node));
newNode->value=input;
}
Worked on singly linked list menu functionality in calculus lab. Got it to work mostly, if you try to insert append or remove without a built list you get a segmentation fault. An “if” statement would probably solve this problem.
Main Function
int main()
{
Node *list;
int input = 0;
while (input != 6)
{
printf("Singly linked list menu \n");
printf("what would you like to do: \n");
printf("1: Build list\n");
printf("2: Display list\n");
printf("3: Insert a node\n");
printf("4: Append a node\n");
printf("5: Remove a Node\n");
printf("6 to quit\n");
scanf("%d", &input);
if (input != 6)
{
if (input == 1)
{
list = build();
}
if (input == 2)
{
display(list);
}
if (input == 3)
{
list = insert(list);
}
if (input == 4)
{
list = append(list);
}
if (input == 5)
{
list = remove1(list);
}
}
}
return 0;
}
A quick check of the man pages told me that “remove” was already a function included in “<stdio>” hence the name remove1
Worked on singly linked list sort functionality. Had a tough time as i didn't completely grasp how we were able to get two outputs from the remove function with passing by reference. So far my sort functionality can remove the smallest node of the list and put it at the beginning, when it wants to.
Haven't been updating because i am fighting an ever growing fire( my code ). That said sll(singly linked list) menu still not operational, cannot figure out insert for whatever reason it doesn't like inserting before 1 or something. that said dll(doubly linked list) is ready for menu functionality just needs to be implemented, which brings me too stacks, which was liking throwing gas onto a hay fire, everything is strewn everywhere and nothing seems to make sense. Hopefully i can get things sorted and upload some functional code…
Mega Upload Haven't updated in ages but i have been working i just don't like uploading super broken and code riddled with seg faults.
Header File:
#ifndef _STACK_H
#define _STACK_H
#include "list.h"
struct stack {
List *data;
Node *top;
int size;
};
typedef struct stack Stack;
Stack *mkstack(int);
Stack *push (Stack *, Node *);
Node *pop (Stack **);
Node *peek (Stack *);
#endif
Stackops:
#include "stack.h"
Stack *mkstack(int size)
{
Stack *myStack;
myStack = (Stack *) malloc (sizeof(Stack));
myStack -> data = mklist();
myStack -> size = size;
myStack -> top = myStack -> data -> end;
return (myStack);
}
Pop:
#include "stack.h"
Node *pop(Stack **myStack)
{
Node *tmp = NULL;
if ((*myStack) != NULL)
{
tmp = (*myStack) -> data -> end;
(*myStack) -> data = getNode((*myStack) -> data, (&tmp));
(*myStack) -> top = (*myStack) -> data -> end;
}
return (tmp);
}
Push:
#include "stack.h"
Stack *push(Stack *myStack, Node *newNode)
{
if ((myStack -> size <= 0) || ((myStack -> data -> qty) < (myStack -> s$
{
myStack -> data = append(myStack -> data, myStack -> data -> en$
myStack -> top = myStack -> data -> end;
}
return(myStack);
}
Stack Test:
#include <stdio.h>
#include "stack.h"
int main()
{
Node *tmp;
Stack *myStack;
myStack = mkstack(0);
tmp = create(1);
tmp -> value = fgetc(stdin);
fgetc(stdin);
myStack = push(myStack, tmp);
myStack->data->start = tmp;
myStack->data->start->prev = NULL;
while(tmp->value != '\n')
{
tmp->next = create(1);
tmp->next->value = fgetc(stdin);
tmp->next->prev = tmp;
fgetc(stdin);
tmp=tmp->next;
myStack = push(myStack, tmp);
myStack->data->end=tmp;
}
fprintf(stdout, "String is: ");
myStack->data->end=myStack->data->end->prev;
while(tmp != NULL)
{
tmp = pop(&myStack);
fprintf(stdout, "%c", tmp->value);
rmnode((&tmp));
if(myStack->top == myStack->data->start)
{
tmp = NULL;
}
}
fprintf(stdout, "%c", myStack->data->start->value);
fprintf(stdout, "\n");
return(0);
}
The output generated if input “h - e - l - l - o” is input:
String is: olleh
Some notes: This functionality is not complete, the “h” or first value is hard coded to print. Otherwise it just kept giving me olle and then the newline. Hopefully this can be remedied but at the mach speed the class has now escalated to it's might be interesting.
Header:
#ifndef _QUEUE_H
#define _QUEUE_H
#include "stack.h"
struct queue {
List *data;
Node *front;
Node *back;
int bufsize;
};
typedef struct queue Queue;
Queue *mkqueue(int);
Queue *enqueue (Queue *, Node *);
Node *dequeue (Queue **);
#endif
Make queue:
#include "queue.h"
#include "stack.h"
#include "list.h"
Queue *mkqueue(int size)
{
Queue *myQueue= (Queue *)malloc(sizeof(Queue));
myQueue->data = mklist(size);
myQueue->front=myQueue->data->start;
myQueue->back=myQueue->data->end;
return(myQueue);
}
Enqueue:
#include "queue.h"
#include "stack.h"
#include "list.h"
Queue *enqueue(Queue *myQueue, Node *newNode)
{
if ((myQueue -> bufsize <= 0) || ((myQueue -> data -> qty) < (myQueue -> bufsize)))
{
myQueue -> data = append(myQueue -> data, myQueue -> data -> end, newNode);
myQueue -> back = myQueue -> data -> end;
}
return(myQueue);
}
Dequeue:
#include "queue.h"
#include "stack.h"
#include "list.h"
Node *dequeue(Queue **myQueue)
{
Node *tmp = NULL;
if ((*myQueue) != NULL)
{
tmp = (*myQueue) -> data -> start;
(*myQueue) -> data = getNode((*myQueue) -> data, (&tmp));
(*myQueue) -> front = (*myQueue) -> data -> start;
}
return (tmp);
}
Queue Test:
#include <stdio.h>
#include "queue.h"
#include "stack.h"
int main()
{
Node *tmp;
Queue *myQueue;
myQueue = mkqueue(0);
tmp = create(1);
tmp -> value = fgetc(stdin);
fgetc(stdin);
myQueue = enqueue(myQueue, tmp);
myQueue->data->start = myQueue -> front = tmp;
myQueue->data->start->prev = NULL;
while(tmp->value != '\n')
{
tmp->next = create(1);
tmp->next->value = fgetc(stdin);
tmp->next->prev = tmp;
fgetc(stdin);
tmp=tmp->next;
myQueue = enqueue(myQueue, tmp);
myQueue->data->end=myQueue->back = tmp;
}
fprintf(stdout, "String is: ");
while(tmp != NULL)
{
tmp = dequeue(&myQueue);
fprintf(stdout, "%c", tmp->value);
rmnode((&tmp));
if(myQueue->back == myQueue->front)
{
tmp = NULL;
}
}
fprintf(stdout, "\n");
return(0);
}
The output when the same string “h - e - l - l - o” is input:
String is: hello
Some notes on queues, some arbitrary includes in the source files because i was having some compiler errors. Note, the includes did absolutely nothing to remedy this but i haven't taken them out yet. Also liked queues better because i didn't have as many seg faults or logical errors, that is most likely due to the solutions I found while working with stacks.
I don't have as much done for binary trees yet. concept seems simple but i am having trouble grasping it.
So my friend did a project with syncing lights to a song. http://www.dropbox.com/s/21vr5d5eqdyskgs/PC050128.MP4