In the beginning of class we went over the new notes system, and point give-away system.

From that point we moved to attaching to the class chat.

Class Chat: screen -l uf “No Socket” –>Screen

 irssi
 /server irc
 /join #csci (Class chat)
 /join lab46 (Bot talk)

to disconnect:

ctrl-a then d

to reconnect from this point onward: screen -r

Then we moved on to The Great C Review.

Pointers (Supposedly we will see the true power behind these in data structures) Pointers are what give C its incredible cosmic power. it is very small, yet very powerful.

Pointers refer to memory (RAM, Storage)

int a;

In memory, represented as a square. The square is broekn up into units called bytes. (1 Byte is 8 bits…some machines actually used to be 7 bits to a byte.)

We use Hexedecimal digits to show the memory address such as: 0x32 (1 Byte Address) and 0xdeadbeef (Which is a 4 byte address)

int *c;

*- dereferencing operator

int a=5; int *c;

c=&a;

We started the day from a program unfinished from Tuesday

The first node is a variable without the “variable”

Data is then stored inside of the first node via a struct pointer
pointer→member = something;

tmp —> Null
tmp —> balloon (12) —> Null
tmp —> balloon (12) —> balloon
tmp —> balloon (12) —> balloon (3) —> Null

The code that we worked on throughout class:

#include<stdio.h>
#include<stdlib.h>
struct node {
char value; value bucket
struct node *next;
};
typedef struct node Node; for us to make typing easier

int main()
{
char input;
Node *tmp = NULL, *tmp2 = NULL;
tmp = (Node*)malloc(sizeof(Node));
tmp→value = 12;
tmp→next = (Node*)malloc(sizeof(Node));
tmp→next→value = 3;
tmp→next→next = (Node*)malloc(sizeof(Node))
tmp→next→next→value = 42;
tmp→next→next→next = NULL;
tmp2 = tmp;
tmp = tmp→next;

For Unix: Relative Reference

Linked List | Array
——————————————–
unending, dynamic | performance

space-time ←- solutions are bounded by these

Looking forward to these topics in the future! :
Hashtables
Que's
Mixtures of Array's and Linked lists

We went over the sll0 project. More information can be obtained from the projects page on the wiki. We also learned a little bit about the debugger.

To compile with debugger support you type in gcc -g -o executable “name” “file_name” To run the program with the debugger you type gdb ./“file_name” You can also run the program normally without debugger support

• run : runs the program

Reading symbols from ./sll...done.
(gdb) run

• break : sets a break point so the program will run all lines up until the line that the break point was set

(gdb) break 55
Breakpoint 1 at 0x4008e8: file sll-debug.c, line 55.

• list : lists the first 10 of the program(with line #)

(gdb) list
6               struct node *next;
7       };
8       typedef struct node Node;
9       void display(Node *);
10      int main()
11      {
12              Node *start, *end, *tmp, *tmp2;
13              char input;
14
15              start        = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1);
(gdb)

• display : displays the value of the specified variable and it is updated each step in the program

(gdb) display tmp2->value
1: tmp2->value = 1 '\001'
(gdb)
(gdb) s
56                      tmp2 = tmp2 -> next;
1: tmp2->value = 1 '\001'
(gdb) s
55              while (tmp2 -> next -> value != input)//used to be tmp -> value)
1: tmp2->value = 2 '\002'
(gdb) s
56                      tmp2 = tmp2 -> next;
1: tmp2->value = 2 '\002'
(gdb)

• print : prints what value the variable holds at that moment

(gdb) print tmp2->next->value
$1 = 3 '\003'
(gdb)

• [s]tep : runs the next step of the program (will step inside function calls)

Breakpoint 1, main () at sll-debug.c:15
15              start        = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1);
(gdb) s
16              tmp -> value = 0;
(gdb) s
17              tmp -> next  = NULL;
(gdb) s
19              fprintf(stdout, "Enter a value (-1 to complete): ");
(gdb) s
20              fscanf(stdin, "%hhd", &input);
(gdb)

• [n]ext : runs the next step of the program (does not step inside function calls (will treat a function call as a single line)

• [c]ontinue : runs the program normally from the last stoping point

Starting program: /home/mb006142/src/data/classtest/sll
Enter a value (-1 to complete): 1
Enter a value (-1 to complete): 2
Enter a value (-1 to complete): 3
Enter a value (-1 to complete): 4
Enter a value (-1 to complete): -1
1 -> 2 -> 3 -> 4 -> NULL
Enter value for new node: 5
Enter value of node you want to insert new node before: 4

Breakpoint 1, main () at sll-debug.c:55
55              while (tmp2 -> next -> value != input)//used to be tmp -> value)
(gdb) c
Continuing.
1 -> 2 -> 3 -> 5 -> 4 -> NULL
[Inferior 1 (process 11161) exited normally]
(gdb)

• quit : exits debugger

• help : get additional details about the commands

(gdb) help
List of classes of commands:

aliases -- Aliases of other commands
breakpoints -- Making program stop at certain points
data -- Examining data
files -- Specifying and examining files
internals -- Maintenance commands
obscure -- Obscure features
running -- Running the program
stack -- Examining the stack
status -- Status inquiries
support -- Support facilities
tracepoints -- Tracing of program execution without stopping the program
user-defined -- User-defined commands

Type "help" followed by a class name for a list of commands in
that class.
Type "help all" for the list of all commands.
Type "help" followed by command name for full documentation.
Type "apropos word" to search for commands related to "word".
Command name abbreviations are allowed if unambiguous.
(gdb)

We continued with the debugger, learning some new commands as well as stepping through the sll-debug program to see where the segmentation fault problem is.

A few more commands for the debugger:

• whatis “variable name” - shows the data type of the specified variable
• x “variable name” - prints the variable value in hex
• set var “var name”=“new value” will set the specified variable to the new value that you type in.
• disas /m “function name” - disassembles the given function and displays it in assembly code

Step by step guide to debugging sll-debug.c: step 1: compile with debug support

       gcc -g -o sll-debug sll-debug.c
       

step 2: launch the debugger (gdb)

       gdb ./sll-debug
       

step 3: gdb run

      this will run the program and tell what line the seg fault       occured

step 4: set breakpoints and analyze

      (gdb) break 55 (this is where the seg fault occured)
      (gdb) run
      

step 5: check variable status

      print tmp2 -> next -> value
      print tmp -> value
      print tmp2
      print tmp
      print tmp -> next
      

step 6: setup auto display of variables

      display tmp2 -> next -> value
      display tmp -> value
      display tmp2 -> next
      display tmp2
      display tmp
      

step 7: watch it loop

      [s]tep or [n]ext
      

as we loop through the program we see that the line

while(tmp2->next->value != tmp->value)

is the problem: we should be looking for the input that we had just typed in, and not tmp's value.

1.bmp

badswapnode.c

Node *tmp3 = mknode(tmp->value);
tmp->value=tmp2->value;
tmp2->value=tmp3->value;
free(tmp3);

2.bmp

Pulls node from list, patches hole in list, keeps pulled node. 3.bmp

obtain_1.c

myList = obtain(myList, &tmp)
{
    int pos       = getpos(myList, &tmp);
    Node          *tmp2;
    tmp2          = setpos(myList, pos-1);
    tmp2->next    = tmp->next;
 
    *(tmp)->next  = NULL;
 
    myList->qty--;
 
    return(myList);
}

obtain_1_optimized.c

myList = obtain(myList, &tmp)
{
    Node *tmp     = setpos(myList, getpos(myList, tmp)-1);
    tmp2->next    = tmp->next;
 
    *(tmp)->next  = NULL;
 
    myList->qty--;
 
    return(myList);
}

4.bmp

use.c

myList = obtain(mylist, &tmp);

(*tmp)->value

Obtain is the only function in our linkedlist library where we will pass by value;

1. Pass by value
   • Passes copy
   • myList=insert(myList,tmp,tmp2);
2. Pass by address/reference
   • changes happen outside of the function
   • pointers!

Most of our focus was on preparing for the assessment. This was simply what I had worked on to prepare for it.

struct thing {
        char value;
        int num;
        struct thing *up;
        struct thing *down;
};
typedef struct thing Thing;
 
 
Thing *mkthing(char zebra, int dog)
{
 
        Thing *tmp = (Thing *)malloc(sizeof(Thing));
        tmp -> value = zebra;
        tmp -> num = dog;
        tmp -> up = NULL;
        tmp -> dowm = NULL;
 
        return(tmp);
}       //Thing *tmp = mkthing('c', 42); //makes tmp point to a thing that has the character 'c' and the integer 42 inside of it.

Thing *rmthing(Thing *oldThing)
{
 
        if(oldThing != NULL)
        {
                oldThing -> value = NULL;
                oldThing -> num = NULL;
                oldThing -> up = NULL;
                oldThing -> down = NULL;
                free(oldThing);
        }
 
        return(NULL);
}       //tmp = rmthing(tmp); //Unallocates tmp and sets tmp equal to NULL

Thing *cpthing(Thing *something)
{
        if( something != NULL)
        {
                Node *copiedthing = mkthing( something -> value, something -> num);
                copiedthing -> up = something -> up;
                copiedthing -> down = something -> down;
                return(copiedthing);
        }
        else
        {
                return(NULL);
        }
}       //randomthing = cpthing(tmp); //Copies tmp into randomthing.
 
 
sruct stuff {
        char name;
        struct stuff *bottom;
        struct stuff *top;
};
typedef struct stuff Stuff;

===Stuff Creation=== mklist.c

Stuff *mkstuff(char bob)
{
        Stuff *newStuff = (Stuff *)malloc(sizeof(Stuff));
        newStuff -> name = bob;
        newStuff -> top = NULL;
        newStuff -> bottom = NULL;
 
        return(newStuff);
}       //Stuff *zebras = mkstuff('z'); //This makes zebras point to a stuff that contains character 'z'.

Stuff *appendthing(Stuff *myStuff, Thing *place, Thing *newThing)
{
        if(myStuff == NULL)
        {
                myStuff -> bottom = newThing;
                myStuff -> top = newThing;
        }
        else
        {
                place -> up = newThing;
                newThing -> down = place;
                if(place == myStuff -> top)
                {
                        myStuff -> top = newThing;
                }
        }
        return(myStuff);
}       //zebras = appendthing(zebras, zebra1, newZebra); //This puts newZebra after zebra1 in zebras.

Stuff *insertthing(Stuff *myStuff, Thing *place, Thing *newThing)
{
        if(myStuff == NULL)
        {
                myStuff -> bottom = newThing;
                myStuff -> top = newThing;
        }
        else
        {
                place -> down = newThing;
                newThing -> up = place;
                if(place == myStuff -> bottom)
                {
                        myStuff -> bottom = newThing;
                }
        }
}

for(i=1; i<=96; i+=7)
{
	if((i % 6)==3)
	{
		status=push(&s, mknode(i+1));
		if(status==0)
		{
			n1=peek(s);
			push(&s,mknode(n1->data)-1));
		}
		else if(status = -1)
		{
			pop(&s, &n1);
			if((i%2)==0)
			pop(&s, &n2);

Think: Stopping at a red light in an order, instead of mass chaos…not just the common sense but 'Why?'

A tree is a data structure associated with the visualization of a parent-child relationship. The set up is similar to the vertical structure of a stack except the nodes branch out from a root instead of being stacked on top of each other. The root has a next and prev to a node, in which the next branches a node to the right and the prev branches a node to the left. The node struct contains the same as before except with an added other pointer. Specifically, the other pointer will be used for iterative and stack-based operations like trying to traverse back up the tree. We can traverse through the list in a stack-based, iterative, or recursive manner. We'll use an addnode function to add a given node to a tree. With the root being at height zero, each added layer of branched nodes adds to the height. The max_height places a limit on the number of nodes you can put into the tree.