Lab46 Wiki

information

lab46:~$ screen 
lab46:~$ irssi
[(status)] /server irc
[(status)]/join #data
lab46:~/src/data$ svn add example.c
A         example.c
lab46:~/src/data$ svn commit -m "Submitted example.c"
Adding         data/example.c
Transmitting file data .....
Committed revision 40.
lab46:~/src/data$
  1 #include<stdio.h>
  2
  3 int main()
  4 {
  5    int number = 10;//int variable number
  6    int *pointer = &number;//int pointer pointing to the address of number
  7    printf("number is: %d\n",number);
  8    printf("number is stored at 0x%x\n", &number);
  9    printf("pointer points to 0x%x\n", pointer);
 10    printf("The value of pointer is: %d\n", *pointer);//dereferencing a pointer
 11
 12    return 0;
 13 }
lab46:~/src/data$ ./pointer
number is: 10
number is stored at 0x594780d4
pointer points to 0x594780d4
The value of pointer is: 10
lab46:~/src/data$
#include<stdio.h>
#include<stdlib.h>
int main()
{
   int array1[10];//static allocation of an array of 10 elements
   int *array2;//declaration of an integer pointer
   array2 = (int*)  malloc(sizeof(int)*10);//dynamically allocating memory for 10 integers
   int i,j = 0;

   for( i = 0; i < 10; i++)//This loop displays the address of the first element of the array
   {                       //and then increments i by one to move to the next location
      printf("Element %d is stored at 0x%x\n", i , &array1[i]);
   }
   printf("\n");
   for( i = 0; i < 10; i++)//This next loop uses pointer arithmetic to display the memory addresses
   {
      printf("Element %d is stored at 0x%x\n", i , array2);
      array2++;
   }

   return 0;
}
lab46:~/src/data$ ./example
Element 0 is stored at 0x2b5e9a0
Element 1 is stored at 0x2b5e9a4
Element 2 is stored at 0x2b5e9a8
Element 3 is stored at 0x2b5e9ac
Element 4 is stored at 0x2b5e9b0
Element 5 is stored at 0x2b5e9b4
Element 6 is stored at 0x2b5e9b8
Element 7 is stored at 0x2b5e9bc
Element 8 is stored at 0x2b5e9c0
Element 9 is stored at 0x2b5e9c4

Element 0 is stored at 0xfa4010
Element 1 is stored at 0xfa4014
Element 2 is stored at 0xfa4018
Element 3 is stored at 0xfa401c
Element 4 is stored at 0xfa4020
Element 5 is stored at 0xfa4024
Element 6 is stored at 0xfa4028
Element 7 is stored at 0xfa402c
Element 8 is stored at 0xfa4030
Element 9 is stored at 0xfa4034
lab46:~/src/data$
#include<iostream>
using namespace std;
int main()
{
   int **num1;//declaration of a double pointer
   int *num2;//declaration of a single pointer
   int num3 = 0;//setting value of num3 to 0
   num2 = &num3;//assigning num3's address to num2
   num1 = &num2;//assigning the address of the single pointer to the double pointer

   //now **num1, *num2 and num3 all = 0
   cout << "**num1 = " << **num1 << endl;
   cout << "*num2 = " << *num2 << endl;
   cout << "num3 = " << num3 << endl;
   return 0;
}
int x = 4;
void* q = &x;
int* p = q;  /* void* implicitly converted to int*: valid C, but not C++ */
int i = *p;
int j = *(int*)q; /* when dereferencing inline, there is no implicit conversion */
int exampleFunc(int x, int y)
int (*exampleFunc)(int x, int y)
int number;//allocates 4 bytes for the int variable number
char ch;//allocates two bytes for char variable ch
double db;//allocates 8 bytes for double variable db
int *number = NULL;
char *ch = NULL;
double *db =NULL;

number = malloc(sizeof(int));
ch = malloc(sizeof(char));
db = malloc(sizeof(double));
int *number;
char *ch;
double *db;

number = new int;
ch = new char;
db = new double;
free(number);
free(ch);
free(db);
delete number;
delete ch;
delete db;
struct studentType
{
    string studentFName;
    string studentLName;
    int testScore;
    char grade;
};
studentType student;//struct variable declaration
//StructVariableName.membername
//in our example. to print the students last name you write this line
cout << "The students last name is " << student.studentLName << endl;
#include "linkedlist.h"
#include <stdlib.h>

struct node {
   char value;
   struct node *next;
   struct node *prev;
};
typedef struct node Node;

void append(Node** end, char input)
{
      Node* tmp;
      tmp = *end;

      tmp = (Node *) malloc (sizeof(Node));
      (*end) -> next = tmp; // tack new node onto end of list
      tmp -> prev =(*end); // new node points to current end
      (*end) = (*end) -> next; // advance end to new end
      (*end) -> value = input; // put input in node
      (*end) -> next = NULL; // nothing beyond end
}
struct node1 {
   char value;//1 byte

};
struct node2 {
   char value;//1 byte
   int number;//4 bytes
};
typedef struct node1 Node1;
typedef struct node2 Node2;
#include<stdio.h>
int main()
{

   char v1 = 0;
   int v2 = 0;

   printf("char is %d bytes\n", sizeof(v1));
   printf("int is %d bytes\n", sizeof(v2));
   printf("node1 is %d bytes\n", sizeof(Node1));
   printf("node2 is %d bytes\n", sizeof(Node2));

   return 0;                                                                                                                                                  
}
lab46:~/src/data$ ./sizelab46:~/src/data$ ./size
char is 1 bytes
int is 4 bytes
node1 is 1 bytes
node2 is 8 bytes
lab46:~/src/data$
struct node1 {
   char value;
   struct node1 *tmp1;
};
struct node2 {
   char value;
   int number;
   struct node2 *tmp1;
   struct node2 *tmp2;
   struct node2 *tmp3;
};
typedef struct node1 Node1;
typedef struct node2 Node2;
lab46:~/src/data$ ./size
char is 1 bytes
int is 4 bytes
node1 is 16 bytes
node2 is 32 bytes
lab46:~/src/data$
#include<stdio.h>
struct node1 {
   int value;
   struct node1 *tmp1;
};
typedef struct node1 Node1;
int main()
{
   int array[10000];
   int i;
   for (i = 0; i < 10000; i++)
   {
      array[i] = i;
   }

   printf("node1 is %d bytes\n", (sizeof(Node1)*10000));
   printf("array is %d bytes\n", (sizeof(array[0])*10000));

   return 0;
}
lab46:~/src/data$ ./size
node1 is 160000 bytes
array is 40000 bytes
lab46:~/src/data$
#include<stdio.h>
#include<stdlib.h>

int main()
{
   int x = 0;
   int a,b,c,d,e,f,g,h,i,j;
   int iterations = 0;
   while (x == 0)
   {

      a = (int)malloc(sizeof(int));
      b = (int)malloc(sizeof(int));
      c = (int)malloc(sizeof(int));
      d = (int)malloc(sizeof(int));
      e = (int)malloc(sizeof(int));
      f = (int)malloc(sizeof(int));
      g = (int)malloc(sizeof(int));
      h = (int)malloc(sizeof(int));
      i = (int)malloc(sizeof(int));
      j = (int)malloc(sizeof(int));
      iterations = iterations + 10;
      printf("iterations: %d\n",iterations);
   }
   return 0;
}
lab46:~$./malloc
iterations: 1
.
.
.
.
.
.
iterations: 38220610
iterations: 38220620
iterations: 38220630
iterations: 38220640
iterations: 38220650
iterations: 38220660
iterations: 38220670
Killed
lab46:~/src/data$
lab46:~$ ps
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
dschoeff  1152  0.0  0.0  13660    12 pts/7    SNs  Sep16   0:00 /bin/bash
dschoeff  1155  0.0  0.1  42544  1428 pts/7    SN+  Sep16   1:59 irssi
dschoeff  3547  0.0  0.0  13632   864 pts/47   SNs  21:42   0:00 -bash
dschoeff 19715  0.0  0.1  13624  1488 pts/45   SNs  23:43   0:00 -bash
dschoeff 20561  9.0 80.0 1054040 836352 pts/47 SN+  23:49   0:32 ./malloc
dschoeff 21328  0.0  0.0   8584  1028 pts/45   RN+  23:55   0:00 ps u
lab46:~$ 
#include<stdio.h>
#include<stdlib.h>

struct node
{
   int value;
   struct node *next;
};
typedef struct node Node;

int main()
{

   Node *start, *tmp;
   int input,i;

   start = tmp = NULL;

   printf("Enter a value -1 to exit: ");
   scanf("%d", &input);

   while( input != -1)
   {
      if(start == NULL)
      {
         start = (Node *)malloc(sizeof(Node));
         start->next=NULL;
         tmp = start;
         start->value=input;
      }
      else
      {
         tmp->next = (Node *)malloc(sizeof(Node));
         tmp = tmp->next;
         tmp->next = NULL;
         tmp->value=input;
      }
      printf("Enter a value -1 to exit: ");
      scanf("%d", &input);
   }

   printf("The list contains the following elements\n");
   tmp = start;
   while (tmp != NULL)
   {
      printf("[%d]value = %d\n", i, tmp -> value);
      tmp = tmp -> next;
      i++;
   }

   return 0;
}
lab46:~/src/data$ ./linkedlist
Enter a value -1 to exit: 1
Enter a value -1 to exit: 2
Enter a value -1 to exit: 3
Enter a value -1 to exit: 4
Enter a value -1 to exit: 5
Enter a value -1 to exit: 6
Enter a value -1 to exit: -1
The list contains the following elements
[0]value = 1
[1]value = 2
[2]value = 3
[3]value = 4
[4]value = 5
[5]value = 6
lab46:~/src/data$ 
struct node
{
   int value;
   struct node *next;
   struct node *prev;
};
typedef struct node Node;
struct stack {
   int count;
   struct node *top;
   struct node *data;
   struct node *tmp;
};
typedef struct stack Stack;
/***********************************************************
* Function push() will create a stack if no stack currently*
* exists. If a stack does exist, push() will add a node to *
* the top of the stack. It will then return the updated    *
* stack.                                                   *
* Compile with: gcc -c push.c                              *
*                                                          *
***********************************************************/
#include "stack.h"
#include<stdio.h>
#include<stdlib.h>
Stack *push(Stack *start, char input)
{
   Node *tmp;
   if(start == NULL)// if no stack, create one
   {
      start = (Stack *) malloc (sizeof(Stack));
      start -> data = malloc(sizeof(Node));
      start -> top = malloc(sizeof(Node));
      start -> tmp = malloc(sizeof(Node));
      start -> top -> value = input;
      start -> top -> next = NULL;
      start -> data = start -> top;
   }
   else//if there is a stack, add node to top of it
   {
      tmp = (Node *) malloc (sizeof(Node));
      tmp -> value = input;
      tmp -> next = start -> top;
      start -> top = tmp;
   }
   return (start);
}
/******************************************************************
* Function pop() accepts as an argument a stack. It will then pop *
* the node that is currently on the top and make the node under   *
* that the new top. It will then return the value that from the   *
* popped node as a character. If the stack that is passed is NULL *
* (meaning it does not exist), the function cannot pop a node that*
* doesn't exist. Therefore, the function will return the null     *
* terminating character.                                          *
*                                                                 *
* Compile with: gcc -c pop.c                                      *
*                                                                 *
**************************************************************** */
#include "stack.h"
#include <stdlib.h>
char pop(Stack *start)
{
  char chartmp;
  start -> tmp = start -> top;
  if(start -> tmp != start -> data)
  {
     start -> top = start -> top -> next;
     start -> tmp -> next = NULL;
     chartmp = start -> tmp -> value;
  }
  else if(start -> data == NULL)
  {
     chartmp = '\n';
  }
  else
  {
     chartmp = start -> top -> value;
     start -> top = start -> tmp = start -> data = NULL;
  }

  return(chartmp);
}
lab46:~/src/data/stackProject$ ./stack
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: a
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
3
The top node contains the value: a
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: b
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
3
The top node contains the value: b
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
q
lab46:~/src/data/stackProject$
int testArray[100];
for(int i = 0; i< 200; i++)
{
    testArray[i] = i;
}
lab46:~/src/data/stackProject$ ./stack
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: a
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: a
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: 

Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
q
lab46:~/src/data/stackProject$
//compile with: gcc -c enqueue.c                                                                                               
//
//Function enqueue() enqueues anode to the queue. If there is no queue in existance
//it will create one. This function is almost exactly like the insert function in my 
//doubly linked library.
#include "queue.h"
#include <stdlib.h>
void enqueue(Node** start, Node** end, int index, char ch) 
{

   int i;
   Node* tmp;
   Node* tmp2;
   tmp  = *start;

   if (*start == NULL) // if our queue is empty
   {   
      (*start) = (Node *) malloc (sizeof(Node));
      (*end) = tmp = *(start);
      (*start) -> prev = NULL;
      (*end) -> prev = NULL;
      (*start) -> value = ch; 
   }   
   else// we are enqueing a node
   {   
      tmp2 = (Node *) malloc (sizeof(Node));
      tmp2 -> next = (*start); // point new node's next at (*start)
      (*start) -> prev = tmp2; // point (*start)'s prev at tmp2
      (*start) = (*start) -> prev; // move (*start) to new node
      (*start) -> value = ch; // put value in node
   }   
}
//compile with: gcc -c dequeue.c
//
// Function dequeue() removes a node from a given queue and frees the
// memory for that node
#include "linkedlist.h"
#include <stdlib.h>
char dequeue(Node** start, Node** end, int index)
{
   int i;
   char ch;
   Node* tmp;
   tmp = *start;
   if((*start) != NULL)
   {
      // Move tmp to exact node we wish to delete
      for( i=0; i<index; i++)
      {
         tmp = tmp -> next;
      }
      ch = tmp -> value;
      if ((tmp != *start) && (tmp != *end))
      {
         tmp -> next -> prev = tmp -> prev;
         // The node after points to the node before tmp
         tmp -> prev -> next = tmp -> next;
         // Now, the now before points to the node after tmp
         tmp -> prev = NULL;
         tmp -> next = NULL;
         // tmp is now disconnected from the queue
         free (tmp); // deallocate the node tmp is pointing to
      }
      else if (*start == *end) // queue is only a single node
      {
         free(tmp);
         (*start) = (*end) = NULL;
      }
      else if (tmp == *start)
      {
         tmp -> next -> prev = NULL;
         // The node following tmp is no longer pointing to us
         (*start) = (*start) -> next;
         tmp -> next = NULL; // Disconnect tmp from the queue
         free(tmp); // deallocate the node tmp is pointing to
      }
      else // tmp is equal to end
      {
         tmp -> prev -> next = NULL;
         // The node preceding tmp is no longer pointing to us
         (*end) = (*end) -> prev;
         // Adjust end to point to the new end of the queue
         tmp -> prev = NULL; // Disconnect tmp from the queue
         free(tmp); // deallocate the node tmp is pointing to
      }
   }
   else
   {
      ch = '\n';
   }
   return(ch);
}
#include<iostream>
using namespace std;
int main()
{

   int num ;
   cout << "Enter integer: ";
   cin >> num;
   cout << " Int is " << num << endl;
   return 0;
}
lab46:~/src/data$ ./inttest
Enter integer: 1
 Int is 1
lab46:~/src/data$ ./inttest
Enter integer: q
 Int is 0
lab46:~/src/data$ 
#include<time.h>                                                                          
#include<stdio.h>
#include<stdlib.h>
int main()
{
   unsigned long int i = 0;
   unsigned long int abc = clock();
   while(i < 1000000000)
   {   
      i++;
   }   

   abc = clock();
   abc = abc/CLOCKS_PER_SEC;
   printf("time in seconds = %llu\n",abc);
   return (0);
}
lab46:~/src/data$ ./clock
time in seconds = 4
lab46:~/src/data$
int main()
{
   double i = 0;
   while(i < 1000000000)
   {
      i = i + .025;;
   }
   return (0);
}
public class Cvsjava
{
   public static void main(String[] args)
   {
      double i = 0;
      while(i < 1000000000)
      {
           i = i + .025;
      }
   }
}
lab46:~/src/data$ time ./clock

real    4m13.026s
user    4m12.956s
sys     0m0.036s
lab46:~/src/data$
lab46:~/src/data$ time java Cvsjava

real    3m47.261s
user    3m47.230s
sys     0m0.076s
lab46:~/src/data$
 26       tmp2 = (Node *) malloc (sizeof(Node));
 27       tmp2 -> next = (*start); // point new node's next at (*start)
 28       (*start) -> prev = tmp2; // point (*start)'s prev at tmp2
 29       (*start) = (*start) -> prev; // move (*start) to new node
 30       (*start) -> value = ch; // put value in node
char dequeue(Node** start, Node** end, int index)
{
   int i;
   char ch;
   Node* tmp;
   tmp = *start;
   if((*start) != NULL)
   {
        //STUFF
   }
   else
   {
      ch = '\n';
   }
   return(ch);
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
   int *array;
   array = (int*) malloc(sizeof(int)*10);
   int i = 0,input=0,junk;   
   int swapped = 1, tmp;
   //loads ten values from the user into the array
   for(i = 0; i < 10; i++)
   {   
      printf("enter 10 different integers: ");
      scanf("%d",&input);
      *(array+i) = input;
   }   
   //meat of the bubble sort
   while( swapped == 1)
   {   
      swapped = 0;
      for(i = 1; i < 10; i++)
      {   
         if(*(array+(i-1)) > *(array+i))//this statements checks to see
         {                              //if the elements are out of order
            tmp = *(array+i);
            *(array+i) = *(array+(i-1));
            *(array+(i-1)) = tmp;
            swapped = 1;
         }   
      }   
   }   
   //displays the array
   for(i = 0; i < 10; i++)
   {   
      printf("[%d]: %d\n", i , *(array+i));
   }   

   return (0);
}
lab46:~/src/data/sorts$ ./bubble
enter 10 different integers: 5
enter 10 different integers: 2
enter 10 different integers: 8
enter 10 different integers: 6
enter 10 different integers: 1
enter 10 different integers: 0
enter 10 different integers: 7
enter 10 different integers: 3
enter 10 different integers: 6
enter 10 different integers: 9
[0]: 0
[1]: 1
[2]: 2
[3]: 3
[4]: 5
[5]: 6
[6]: 6
[7]: 7
[8]: 8
[9]: 9
lab46:~/src/data/sorts$
binary_search(Array[0..N-1], value, low, high):
       if (high < low):
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value):
           return binary_search(A, value, low, mid-1)
       else if (A[mid] < value):
           return binary_search(A, value, mid+1, high)
       else:
           return mid // found

lab46:~/src/data/sorts$ time ./bubbleTest > test.txt

real    1m44.096s
user    1m43.898s
sys     0m0.004s
lab46:~/src/data/sorts$ 
[0]: 900001
[1]: 900002
.
.
.
.
.
[99992]: 999993
[99993]: 999994
[99994]: 999995
[99995]: 999996
[99996]: 999997
[99997]: 999998
[99998]: 999999
[99999]: 1000000
lab46:~/src/data/sorts$ time ./bubbleTest > random.txt

real    1m49.129s
user    1m48.951s
sys     0m0.012s
lab46:~/src/data/sorts$
lab46:~/src/data/sorts$ time ./bubbleTest > test.txt

real    0m0.300s
user    0m0.072s
sys     0m0.012s
lab46:~/src/data/sorts$ 
lab46:~/src/data/sorts$ time ./selectionTest > test.txt

real    0m33.734s
user    0m33.494s
sys     0m0.016s
lab46:~/src/data/sorts$ 
[0]: 900001
[1]: 900002
.
.
.
.
.
[99992]: 999993
[99993]: 999994
[99994]: 999995
[99995]: 999996
[99996]: 999997
[99997]: 999998
[99998]: 999999
[99999]: 1000000
lab46:~/src/data/sorts$ time ./selectionTest > random.txt

real    0m32.299s
user    0m32.082s
sys     0m0.004s
lab46:~/src/data/sorts$
lab46:~/src/data/sorts$ time ./selectionTest > test.txt

real    0m32.272s
user    0m32.082s
sys     0m0.012s
lab46:~/src/data/sorts$
lab46:~/src/data/sorts$ time ./bubbleTest > test.txt

real    1m44.096s
user    1m43.898s
sys     0m0.004s
lab46:~/src/data/sorts$ 
lab46:~/src/data/sorts$ time ./selectionTest > test.txt

real    0m33.734s
user    0m33.494s
sys     0m0.016s
lab46:~/src/data/sorts$ 
lab46:~/src/data/sorts$ time ./bubbleTest > random.txt

real    1m49.129s
user    1m48.951s
sys     0m0.012s
lab46:~/src/data/sorts$
lab46:~/src/data/sorts$ time ./selectionTest > random.txt

real    0m32.299s
user    0m32.082s
sys     0m0.004s
lab46:~/src/data/sorts$
lab46:~/src/data/sorts$ time ./bubbleTest > test.txt

real    0m0.300s
user    0m0.072s
sys     0m0.012s
lab46:~/src/data/sorts$ 
lab46:~/src/data/sorts$ time ./selectionTest > test.txt

real    0m32.272s
user    0m32.082s
sys     0m0.012s
lab46:~/src/data/sorts$

Table of Contents

Introduction

Me

Some more stuff about me

Part 1

Entries

September 5th, 2011

September 18th, 2011

September 27th, 2011

September 30th, 2011

DATA Topics

Version Control

Pointers

arrays, pointer arithmetic

pointers to pointers

Null pointer

Void pointers

Function pointers

Static allocation vs. Dynamic allocation

Memory allocation (malloc(), new)

Memory De-allocation (free(), delete)

structures(structs/records)

Structure pointers

DATA Objectives

Write a program that uses linked lists

Method

Measurement

Analysis

Experiments

Experiment 1

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions

Experiment 2

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions

Experiment 3

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions

Part 2

Entries

October 20th, 2011

October 24th, 2011

October 27th, 2011

October 28th, 2011

Data Topics

Linked lists

Doubly Linked List

Stacks

Pushing

Popping

Top

Overflow Condition

Underflow condition

LIFO

Queue

Enqueuing

Dequeuing

Data Objective

Write a program that uses stacks

Method

Measurement

Analysis

Experiments

Experiment 1

Question