Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Data Structures Journal======
====AUG 29, 2013====
Joined class mailing list

Setup class chat, (screen)

Edited opus

====SEP 6, 2013====
Finished data type program

Cloned and updated repository with data type program

Created the linked list program

====SEP 10, 2013====
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,
<cli>
list.c list.c.save
</cli>
So 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
<cli>
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
</cli>
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.

====SEP 11, 2013====

Found where my mistake was, i forgot to subtract 1 from the input variable.
Finished code for Creating the list:
<code>
#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;
                        }
                }
        }
</code>


And displaying the list:


<code>
 input=0;
        tmp=list;
        while(tmp != NULL)
        {
                printf("[%d] %d -> ", input, tmp->value);
                tmp=tmp->next;
                input = input++;
        }
        printf("NULL\n");
</code>


Inserting before a node:


<code>
 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;
        }
</code>

Appending after a node:

<code>
        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;
</code>

Also added the executable and the source code to my repository.

====SEP 12, 2013====

Finished remove functionality by adding an if statement:
<code>
        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;
        }
</code>


====SEP 19, 2013====


Working on menu for singly linked list, meanwhile got doubly linked list build, display, and insert functions.


**Build function:**
<code>
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);
}
</code>

**Display (forward)**

<code>
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");
}
</code>

**Display (backwards)**
<code>
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");
}
</code>

**Insert** (includes seek function and building a new node)

<code>
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);
}
</code>

**Seek**

<code>
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);
}
</code>

**newNode**

<code>
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;
}
</code>

====SEP 19, 2013====


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**
<code>
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;
}
</code>

A quick check of the man pages told me that "remove" was already a function included in "<stdio>" hence the name remove1

==== SEP 24, 2013====

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.


==== Sometime in early October ====

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...  


==== November 5, 2013 ====

**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.

==== Stacks ====
**Header File:**
<code>
#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
</code>

**Stackops:**

<code>
#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);
}
</code>

**Pop:**

<code>
#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);
}
</code>

**Push:**

<code>
#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);
}
</code>

**Stack Test:**

<code>
#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);
}
</code>

The output generated if input "h - e - l - l - o" is input:

<cli>
String is: olleh
</cli>

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.

==== Queue ====

**Header:**
<code>
#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
</code>

**Make queue:**

<code>
#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);
}
</code>

**Enqueue:**

<code>
#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);
}
</code>

**Dequeue:**

<code>
#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);
}
</code>

**Queue Test:**

<code>
#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);
}
</code>

The output when the same string "h - e - l - l - o" is input:

<cli>
String is: hello
</cli>

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.

==== Binary Trees ====

I don't have as much done for binary trees yet. concept seems simple but i am having trouble grasping it. 


==== Cooking by the book ====

So my friend did a project with syncing lights to a song.
[[http://www.dropbox.com/s/21vr5d5eqdyskgs/PC050128.MP4]]
Lab46 Wiki

User Tools

Site Tools

Page Tools
