Part 3

Spent the better part of Data Structures reading through the fork manual, called by “man 2 fork”. We then wrote ~/src/SysProg/fork/forkify.c , a simple program to demonstate the uses and returns of the fork function along with sleep, wait, and get pid. We also covered the pid_t data type. The program demonstrated a couple of good ways to check to see what child has what PID, and to make sure the children don't do anything the parent is supposed to, and vice versa.

To use the fork function, you need to include the unistd.h header file, called by “#include<unistd.h>”. accepts a void parameter returns the PID of the forked process

wait() will wait for PID's to die, and will clean up what they did.

Today was a good day. We spent a decent amount of time on sorting algorithms, and then each implemented our own algorithms. I used a bubble sort that sorted an integer value array.The bubble sort is found in ~/src/DataS/bubble.c and the bubble sort part is below:

 while(swap == 0)
        {
                swap=1;
                for(i=1;i<count;i++)
                {
                        if(*(list+(i-1)) > *(list+i))
                        {
                                c = *(list+(i-1));
                                *(list+(i-1))=*(list+i);
                                *(list+i) = c;
                                swap = 0;
                        }
                }
                count--;
        }

While this is a simple algorithm, it has a lot wrapped up in it. It compares the elements of an array with each other and if they are equal, it swaps them by use of a dummy variable. One the for loop ends, the highest unsorted value is at the end of the array, therefore we can reduce how far into the array we need to compare.

Also, revenge is sweet ;)

I am pretty sure I am going to devote this whole journal entry to Thanksgiving because this year, it was pretty special. This is the first holiday that my extended family has “hung around” before or after the meal. My mom accidentally turned the oven off while messing with the turkey timer, so food was delayed about an hour. Because of that, my family had to arrive early and i dont know if they enjoyed staying, but they stayed after aswell and we had a lot of quality family time for once. And the food, ohhhh…. Stuffing is the best part of thanksgiving, fo sho son. Not to mention that but the deserts we will have for decades! We had apples pies, chocolate pies, white chocolate cheesecake and pumpkin bars, soooo good!

This is a sample format for a dated entry. Please substitute the actual date for “Month Day, Year”, and duplicate the level 4 heading to make additional entries.

As an aid, feel free to use the following questions to help you generate content for your entries:

• What action or concept of significance, as related to the course, did you experience on this date?
• Why was this significant?
• What concepts are you dealing with that may not make perfect sense?
• What challenges are you facing with respect to the course?

Remember that 4 is just the minimum number of entries. Feel free to have more.

A hash table is a data structure that maps values known as keys, like an age, to the profiles of everyone that age. These tables use a hash function that turns the key into the index of the main array.

These tables are usually comprized of an array of linked lists, allowing you to create structures like directories fairly simple.

In a well-made hash table, the average iterations for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at a constant average cost per operation. photo courtesy of wikipedia

Graph structures consist of a set of ordered pairs, formaly called arcs, or edges of entities called nodes. These nodes can be part of the graph structure, or be external entities represented by integer indices.

A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

The basic operations provided by a graph data structure G usually include:

• adjacent(G, x, y): tests whether there is an edge from node x to node y.
• neighbors(G, x): lists all nodes y such that there is an edge from x to y.
• add(G, x, y): adds to G the edge from x to y, if it is not there.
• delete(G, x, y): removes the edge from x to y, if it is there.
• get_node_value(G, x): returns the value associated with the node x.
• set_node_value(G, x, a): sets the value associated with the node x to a.

Structures that associate values to the edges usually also provide:

• get_edge_value(G, x, y): returns the value associated to the edge (x,y).
• set_edge_value(G, x, y, v): sets the value associated to the edge (x,y) to v.

Different data structures for the representation of graphs are used in practice:

• Adjacency list - Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices.
• Incidence list - Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows the storage of additional data on vertices and edges.
• Adjacency matrix - A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
• Incidence matrix - A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

Some information derrived and simplified from wikipedia

A binary tree is a node based data structure that has two main branches, one to the left with lesser keys, and one to the right with greater keys. The placement of each node is based on it's key, and not the other values of the node. The tree is formed based on a root node that is assigned a pivot key. All other keys entered then go either to the left or right of that root node based on the rank of that key. and so on and so forth through the tree until they reach the bottom of their branch where they become a leave of the tree.

This is an effective method of data searching because after the first check, at the root node, half of the tree is no longer a possibility because the check will send the tmp variable to either the lesser or greater value branch of the root node.

Below is a sample of code that is used in a node based tree.

                Node *grep;
                grep = malloc(sizeof(Node *));
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller != NULL)
                                        mytree -> tmp = mytree -> tmp -> smaller;
                                else
                                        mytree -> tmp -> smaller = grep;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger != NULL)
                                        mytree -> tmp = mytree -> tmp -> bigger;
                                else
                                        mytree -> tmp -> bigger = grep;
                        }

Insertion is where a value, or key is added at an arbitrary point in a list. Observe a single-dimension array for example. This array contains the values 3, 7, 13, 21, 45, 93 and we wish to insert the value 33. If the list is ordered, the value will be inserted between the values 21 and 45. If not, the value can be inserted at any point in the array.

Tree *add(Tree *mytree, char val)
{
        if(mytree -> root != NULL)
        {
                Node *grep;
                grep = malloc(sizeof(Node *));
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller != NULL)
                                        mytree -> tmp = mytree -> tmp -> smaller;
                                else
                                        mytree -> tmp -> smaller = grep;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger != NULL)
                                        mytree -> tmp = mytree -> tmp -> bigger;
                                else
                                        mytree -> tmp -> bigger = grep;
                        }
                }
        }
        return mytree;
}

Removal is pretty straight forward, just as insertion was. Removal refers to the removing, pop, or displacement of an arbitrary value/key or node. If we go back to the example of an array, this time containing the values 3,7,13,21,33,45,93 with 33 added from the insertion operation. And we remove an arbitrary value, say 33, we will then turn the array back to the starting array of 3,7,13,21,45,93, showing that insert and remove are opposites.

#include"tree.h"
 
Tree *del(Tree *mytree, char val)
{
        if(mytree -> root != NULL)
        {
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> smaller;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> smaller;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> bigger;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> bigger;
                        }
                }
        }
        return mytree;
}

Searching means to move about a data structure to see if a given value or key is in that data arrangement. This can be best explained through an example of a linked list search.

#include"linkedlist.h"
Node *find(List *mylist, char f) //Mylist is the list we are looking through, f is the value to find.
{
        Node *test2; // tmp node for moving about the list.
        test2 = mylist -> start;
        while((test2 != NULL)  && (test2 -> value != f)) //while list is populated and test2 does not find the value
        {
                if(test2 -> next != NULL) //while list is populated
                {
                        test2 = test2 -> next;  //move to next spot
                }
        }
        if(test2 -> value != f)
        {
                test2 -> value = #;
        }
        return test2; //returns the address of the node that contains the value, or # if not found.
}

Tree traversal is visiting each node in a tree structure to examine or update those nodes. Three traversal structures are classified by the way each node is visited.

1. Visit the root
2. Visit the left branch
3. visit the right branch

1. Visit the left branch
2. Visit the right branch
3. Visit the root

1. Visit the left branch
2. Visit the root
3. Visit the right branch

Merge sort is a “divide to conquer” sorting algorithm that operates on a O(n logn) comparison basis.

A merge sort works like so:

1. If the list only has 0 or 1 elements, then it is already sortd
2. If not, then the list is recursively divided into two sublists about half the size
   1. 2 lists, then 4 lists, then 8 lists, etc… till each list has 1 element.
3. The list is then compared element by element, recursively grouping the lists into pairs
   1. 8 lists, then 4 lists, then 2 lists, then 1
4. Once the lists are all combined, the merge sort is complete.

A binary search is a O(1) best case, O(logn) worst case sorting algorithm that works off from an already sorted array. This method takes a given key and compared it to the middle key of the array. If the given key is greater, the index of the array is moved one to the right. If the given key is less, the index is moved to the left one. This operation is repeated until the desired key is found, or the array index's next is null. In this case a special “end of file” indicator is returned.

1. Computational complexity is a theory in computer science that classifies problems based on their difficulty.
2. A computational problem is a problem that can be solved by a computer through a set of mathematical instructions.

These computational problems are given a complexity level based on the amount of resources need to perform. The computer defines these levels based on a set of models of computation that project how much time and storage needed for the problem to complete.

This Notation is used to classify different algorithms based on the time they take to complete. Each algorithm has three recorded times, a worse case, best case, and average case. The time it takes for each case is given in a mathmatical expression like (nlogn) or n^2 where n is the number of iterations of the algorithm.

1. Best case is when the time taken to evaluate the algorithm is the minimum. In a sorting algorithm this would mean a best case would be just n.
2. Worst case would be, well, lets just say someone actually made an algorithm that take n^infinity.
3. Average case is just as it sounds, the average time it takes for x number of algorithms to evaluate. Evaluated by:
   1. (total time for all algorithms)/(x number of algorithms)

Big-O is roughly affirmed with the upper bound asymptote or as the worst possible case.

Describes the case where the upper and lower bounds of a function are on the same order of magnitude.

Describes the lower bound, or best case.

Memory is managed statically, automatically, and dynamically. In this example we will look at static versus dynamic allocation.

Static memory is not adequate for all situations. You might want to make a variable that could contain one word, or 1000 sentances, but you don't want to allocate enough memory for 1000 sentances if you are just storing one word. That is where Dynamic memory allocation comes in and Malloc() is an example of this. Dynamic memory is allocated from the heap, so as long as there is memory left to allocate, a program can use as much as needed, or as little as needed. A linked list is a great example of Dynamic memory allocation. If the user wants to use more memory storage the program can allocate memory like so:

        Node* tmp3;
        tmp3 = (Node *) malloc (sizeof(Node));
        tmp3 -> value = d;

This will create a node structure based on some Struct, and allocate memory of a pre-defined size, the size of the Node, and place a specified value in that node. This can be called recursively or in a loop as needed, thus creating dynamic memory allocation. Since this memory was allocated via Malloc(), it can be removed with the free() function, thus freeing up the space used my malloc().

Static memory is allocated and fixed for the lifetime of the program. This memory is allocated on the stack and comes and goes as the functions call for it, but still exists whether called or not. This can be useful for programs that know exactly how much memory will be used during the lifetime of the program, and will never need to allocate more that a given amount of memory.

   int input;
   printf("please enter input");
   scanf("%d", input);

This will allocated static memory and same input into it, which will then exist for the lifetime of the program whether it is used or not, and cannot be freed by functions like free().

A named pipe is a more indepth pipe from unix computer systems, and is an inter-process communicator. A regular pipe is usually unnamed because it only exists and acts anonymously while the program is runnning. A named pipe exists after the life on the program and must be deleted. It is called System-Persistent.

mkfifo my_pipe
gzip -9 -c < my_pipe > out.gz
cat file > my_pipe
rm my_pipe

File locking restricts access to one user or process at a time to avoid changes being over written (interceding updates).

• If John checks the file out
• Then Mark checks the same file out
• Then john changes the phone number in the file and saves it
• Then Mark, who has an original copy changes the address and saves the file
• johns changes are lost

Most systems support file locking to prevent updates happening in this fashion. Therefore Mark must wait for John to finish before he can check a copy of the file out. Use of file locking should be monitored as a poor use of it can cause a gridlock in the system.

ID's are numbers assigned to users and groups on a Linux system(and possibly others) so that the kernel has a way to address them. This is used mainly for permissions. One can set individual permission levels or group levels and place individuals into that group.

A users UID and GID can both be attained through the id command.

lab46:~$ id
uid=5689(bkenne11) gid=5000(lab46) groups=5000(lab46),1734(sys),1738(data),5689(bkenne11)
lab46:~$

Once you log into a Linux system you become a number to the kernel. This number is your user ID. This ID helps to set permissions for what user number # can do. Exapmles of this in affect are user ID 0. The Zero user is Root and enjoys unlimited/unrestricted access to the system.

A group can be created with special permissions that allows it's member to have the permissions of the group. You then can create a group with permissions to manage the mail client of a system so that those users and those users only have special rights to manage or maintain the mail client.

A deivce file, or special file, is like an interface for software to interact with device drivers via standard input and output. These usually conect periferals like printers, mice, keyboards and serial ports but can also be used to access more specific things like disk partitions.

There are two general kinds of device files in Unix-like operating systems, known as character special files and block special files. The difference between them lies in how data written to and read from them is processed by the operating system and hardware.

A typical file system may contain thousands upon thousands of files which can be organized by Directories(often called folders). These directories can hold files and or other directories making a tree system of files. The files contained within a folder are called subfiles or subfolders. For example:

You have a file system that is phone book. You can have a directory call phbook that contains directories for all leters of the alphabet, which contain directories for all people with the last name -blank-, which are files of the information of each person.

On unix based systems:

A buffer is a place where data you have just recieved is stored once downloaded from somewhere like the internet. This given you an opportunity to work on that data in real time incase your download speed is too slow to work on the data as it is recieved. This is useful when rendering videos off from the internet on sites like youtube or hulu, but can also be used in file reading. On unix-like system the command read-partial can be used to read a file to a buffer up to a certain point where it can then be read to another file or etc.

Shared memory is memory that can be simultaneously accessed by multiple programs on a running system to provide communication between those programs.

Shared memory can also be refered to as a large block of RAM that can be accessed by multiple CPU's on a multi-cpu system.

Also called an IPC socket, a Unix domain socket is an endpoint for data communications that allows processes operating in the same system to exchange data. The APL for these sockets is similar to an internet socket, meaning the processes don't have to have the same ancestry.

These sockets are usually found on POSIX operating systems.

Coroutines are a pretty cool thing. As far as i've read they generalize subroutines like generators do, but are more powerful. They allow lots of entry points for suspending and resuming at different points.

The C programming guide says that Coroutines are best used when implementing components such as iterators, infinite lists, cooperative tasks and pipes.

A good time to use a file link is when you have several different programs that need to use the same data, but are in different directories. The programs can of course call the files with their complete file name, but that can get slopy and can be hard to change if the file is moved. This is when file links come in handy.

A file link is a directory entry that refers to a file. There are a few ways to do this, but the most common is a symbolic link. A symbolic link is a special file that contains a refrence to another file or directory by it's pathname. Any program that uses a symbolic link treats it as if it is operating on the target file.

The process of keeping consistency with data from a source to a target storage device and vice versa is called data synchronization. In english, this process harmonizes data contained in data storage spaces such as files or file servers. A good example of file synchronization is a USB flash drive or a hard drive of a home computer. This process prevents copying already identical files, saving a lot of time.

To sum it up, It creates one big data storage of one copy of all the files, instead of copying every source and having multiples of each file.

My last keyword for my fall 2011 opus, almost sad, but deffinitely not! I have chosen threads because it is something that has always avoided my grasp. I have wanted to learn about and understand a thread for a long time, so here we go!

A thread is a thread of execution, or a unit of processing that can be scheduled by the operating system to evaluate at the scheduled time. Since a thread is the smallest unit of processing, a thread is actually contained within a process. Not just that, but there can be multiple threads inside of a process which can share resources like memory, but only inside that process. Multithreading can be expressed like multiple contractors building the same house, at the same house, and working off from the same building plan, but maybe not the same pages.

A few notes about threads:

1. They share their address space
2. they exist as subsets of a process
3. context switching between threads is faster than processes.

Describe common applications for each data structure described in class

As each data structure appears, i will ask questions and record programs and applications of each data structure that is given in class in an attempt to have each of the structure described to me in an understandable way.

So far so good, I have had linked lists explained to me in many ways by recording programs and using them to ask multiple questions to ensure that i understand the data structure that was being taught.

The method used to complete this objective seems to be an effective one. It falls in line with my teachers objectives for the course and for our learning and has so far provided much valid information reguarding the data structures being taught. I believe it will continue to be an effective method of learning that will help not only me, but others to convert to this style aswell.

explore efficient solutions to data- and processing- intensive problems.

Exploring Asymptotic algorithms for data processing.

Going very well, i have seen a lot of algorithms for data processing and I can see how it is very important to be consistently developing solutions to data and processing intensive problems.

• How did you do? very well
• Room for improvement? Always, there will always be a need and room for improvement in data processing.
• Could the measurement process be enhanced to be more effective? If I knew it could, i would have.
• Do you think this enhancement would be efficient to employ? N/A
• Could the course objective be altered to be more applicable? How would you alter it? Yes, remove the last two questions.

Can I implement a tree program through a library and not use function prototypes? What will happen if I don't?

• www.cprogramming.com/thread%2
• C pocket guide
• http://en.wikipedia.org/wiki/Function_prototype

I think that I will be able to compile and run my program properly without using prototypes, but i am guessing i will get some warning considering so.

I am going to use a previously written tree library and remove it's prototypes, then compile.

Bingo! When recompiling this tree structure without function prototypes it went through! I ran the program and everything worked properly, give or take getting 2 unrelated compiler warnings. It looks like the compiler doesn't need prototypes.

#include"tree.h"
 
int main()
{
        int input;
        Tree *mytree;
        mytree = malloc(sizeof(Tree *));
        while(input != -1)
        {
                printf("Enter a positive integer value: ");
                scanf("%d", &input);
                if (input != -1)
                        mytree = add(mytree, input);
        }
        printf("Enter - 1 - to add a node\n");
        printf("Enter - 2 - to delete a node\n");
        printf("Enter - 3 - to print the nodes in post order\n");
        scanf("%d", &input);
        if(input == 1)
        {
                printf("Enter a positive integer value: ");
                scanf("%d", &input);
                mytree = add(mytree, input);
        }
        else if(input == 2)
        {
                printf("These are the values in the tree,\n");
                printf("please enter a value to delete: ");
                postpr(mytree -> root);
                scanf("%d", &input);
                del(mytree, input);
        }
        postpr(mytree -> root);
        printf("\n");
        return 0;
}

*
* add.c, a tree manipulation function.
* Made by Brandon Kennedy for Data Structures
* Semester: Fall: 2011
*
* prototype: Tree *add(Tree *, char);
* Returns a tree struct containing the address of the root, tmp, tmp2, and solo nodes..
*/
#include"tree.h"
 
Tree *add(Tree *mytree, int val)
{
        Node *grep;
        grep = malloc(sizeof(Node *));
        grep -> value = val;
        if(mytree -> root != NULL)
        {
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller != NULL)
                                {
                                        mytree -> tmp = mytree -> tmp -> smaller;
                                        printf("smaller\n");
                                }
                                else
                                        mytree -> tmp -> smaller = grep;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger != NULL)
                                {
                                        mytree -> tmp = mytree -> tmp -> bigger;
                                        printf("bigger\n");
                                }
                                else
                                        mytree -> tmp -> bigger = grep;
                        }
                }
        }
        else
        {
                mytree -> root = grep;
        }
        return mytree;
}

#include"tree.h"
 
Tree *del(Tree *mytree, char val)
{
        if(mytree -> root != NULL)
        {
                mytree -> tmp = mytree -> root;
                while(mytree -> tmp -> value != val)
                {
                        if(val < mytree -> tmp -> value)
                        {
                                if(mytree -> tmp -> smaller -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> smaller;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                        {
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        }
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = mytree -> solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> smaller;
                        }
                        else
                        {
                                if(mytree -> tmp -> bigger -> value = val)
                                {
                                        mytree -> solo = mytree -> tmp -> bigger;
                                        mytree -> tmp2 = mytree -> solo -> bigger;
                                        while(mytree -> tmp2 -> smaller != NULL)
                                        {
                                                mytree -> tmp2 = mytree -> tmp2 -> smaller;
                                        }
                                        mytree -> tmp2 -> smaller = mytree -> solo -> smaller;
                                        mytree -> tmp -> smaller = mytree -> solo -> bigger;
                                        mytree -> solo -> smaller = NULL;
                                        mytree -> solo -> bigger = NULL;
                                        free(mytree -> solo);
                                }
                                else
                                        mytree -> tmp = mytree -> tmp -> bigger;
                        }
                }
        }
        return mytree;
}

#include"tree.h"
 
void postpr(Node *lantro)
{
        if(lantro != NULL)
        {
                postpr(lantro -> smaller);
                printf("%d, ", lantro -> value);
                postpr(lantro -> bigger);
 
        }
}

#ifndef _TREE_H_ #define _TREE_H_ #include<stdlib.h> #include<stdio.h>
 
struct node{
        char value;
        struct node *bigger;
        struct node *smaller;
};
typedef struct node Node;
 
struct tree{
        struct node *root;
        struct node *tmp;
        struct node *tmp2;
        struct node *solo;
};
typedef struct tree Tree;
 
#endif

Based on the data collected:

• was your hypothesis correct? Not entirely. I was able to run the program, but i didn't get any related compile time errors.
• was your hypothesis not applicable? no.
• is there more going on than you originally thought? Yes. It isn't that the compiler should spit out errors, but that the compiler cannot see the errors that are happening.
• what shortcomings might there be in your experiment? If i knew, I would have changed them!
• what shortcomings might there be in your data? If i knew, I would have collected the data!

It appears(by reading and reviewing data) that if you don't include function prototypes, the compiler cannot see potential errors like:

• If you call a function that expect 2 arguments, and you only give it one.
  • In this case, the function will have to get that argument from the stack, which could be anything!

In conclusion, include prototypes! It only takes a line per prototype, and saves you from a lot of potential trouble.

How much more memory does a linked list use than an array?

The C programming guide Cprogramming.com/threads%read\input

I don't feel that a linked list should take up very much more memory than an array.

They have the same basic structure, a next and a previous. they may be incrememnted differently, but they hold the same basic structure.

To test this hypothesis i am going to write a quick program that will create an array with an integer value, and a struct with an integer value. I will then use the sizeof command to retrieve the size of both data structures and multiply then by 100 to show a decent difference in their memory uses.

#include<stdio.h>
struct node {
   int value;
};
typedef struct node Node;
int main()
{
   int array[10];
   int i;
   for (i=0;i<10;i++)
      array[i] = i;
   printf("node size is %d in bytes\n", (sizeof(Node)*100));
   printf("array is %d bytes\n", (sizeof(array[3])*100));
   return 0;
}

Done with the above code:

lab46:~$ ./exper
node size is 400 in bytes
array is 400 bytes
lab46:~$

Done with the code manipulated so that the array is of type char.

lab46:~$ ./exper
node size is 400 in bytes
array is 100 bytes
lab46:~$

Based on the data collected:

• was your hypothesis correct? No, The array and linked list took up the same amount of memory.
• was your hypothesis not applicable? No
• is there more going on than you originally thought? No

As far as I can conclude from this experiment, the data structure used matter none in reference to the memory space allocated when creating/using that structure. The only thing that affects the memory used is the data type of the variable being allocated. In this experiment, I gace two command line examples. The first was a linked list node and an array slot both of type int. They, when sized, use the same amount of memory to store the integers they are given. In the second CLI example the node structure in of type int, and the array is of type char and this is where we can see some change. The node of type int takes up four bytes while the array slot of type char takes up 1 byte, showing that these data structure are only the size (memory wise) of the data types allocated inside of them.

Thought this experiment was over? Well think again!

The above experiment is correct in it's context, but only because the node structure created is for a linked list of one node. What happens while i make it a singly linked list? or a doubly linked list?

Lab46 is a 64 bit system that has char value of 1 byte and int value of 4 bytes, this is important. That means that when you created a variable with the data type char, the system allocates it a block size of 1 byte, same for an integer, but of block size 4. The next block size after that is 8 then 16, also important. When the node structure for the above linked list was created:

#include<stdio.h>
struct node {
   int value;
};
typedef struct node Node;

Inside of the structure there is only an integer value, nothing else, causing this node to only use 4 bytes of data. This is fine for a list of one node, but what about an 10 nodes? or 100? Since linked lists use pointers to nodes to keep track of the address of other nodes, these pointers must be taken into account also. On lab46, the system allocates 8 bytes for a pointer to a node.

#include<stdio.h>
struct node {
   int value;
   struct node *next;
};
typedef struct node Node;

This singly linked list will take up memory for two things:

1. A data type of int 1 byte
2. A pointer to a node 8 bytes

total bytes: 9 Since the block sizes around this are 8 and 16, the system will allocate 16 bytes of data and pad the unneeded space. But what does that mean for a doubly linked list?

#include<stdio.h>
struct node {
   int value;
   struct node *next;
   struct node *prev
};
typedef struct node Node;

This doubly linked list will take up memory for:

1. A data type of int 1 byte
2. a pointer to a node 8 bytes
3. a pointer to a node 8 bytes

total bytes: 17 Since this is above 16, we have to go to the next block size, which is 32.

So, to REALLY conclude, while a data type is worth it's respective bytes no matter the data structure it is contained in, the data structure can need other data types allocated to operate. Therefore:

1. A linked list will always require at least 8 bytes of data to operate
2. A doubly linked list will always require at elast 16 bytes of data to operate
3. an array, well, doesn't need squat…

I think that covers everything…

Karl Kraus.

Question: After learning about enum I was curious as to what value it starts at, is it 0 or 1? Or possibly some other random value?

Evaluate their resources and commentary. Answer the following questions:

• Do you feel the given resources are adequate in providing sufficient background information? yes, the material is very straight forward, no gaps for questions.
• Are there additional resources you've found that you can add to the resources list? The manual page for emun()
• Does the original experimenter appear to have obtained a necessary fundamental understanding of the concepts leading up to their stated experiment? Yes, enum is a simple function, and there was an adequate understanding of it prior to the project.
• If you find a deviation in opinion, state why you think this might exist. N/A

State their experiment's hypothesis. Answer the following questions: there was no hypothesis stated

• Do you feel their hypothesis is adequate in capturing the essence of what they're trying to discover? N/A
• What improvements could you make to their hypothesis, if any? I would actually write a hypothesis

Follow the steps given to recreate the original experiment. Answer the following questions:

• Are the instructions correct in successfully achieving the results? There are no instructions, but the code given suffices.
• Is there room for improvement in the experiment instructions/description? What suggestions would you make? Nothing to say, the project is straight forward enough
• Would you make any alterations to the structure of the experiment to yield better results? What, and why? No

#include <stdio.h>
 
int main()
{
    enum days{sunday, monday, tuesday, wednesday, thursday, friday, saturday};
    printf("%d\n", sunday);
    printf("%d\n", monday);
 
    return 0;
}

lab46:~/src$ ./karlretest
0
1
lab46:~/src$

Answer the following:

• Does the data seem in-line with the published data from the original author? yes
• Can you explain any deviations? none
• How about any sources of error? none
• Is the stated hypothesis adequate? there is no stated hypothesis

Answer the following:

• What conclusions can you make based on performing the experiment? The enum function gives the given set elements a numberic value that can be manipulated with mathmatical expressions like +,=,-.
• Do you feel the experiment was adequate in obtaining a further understanding of a concept? Yes
• Does the original author appear to have gotten some value out of performing the experiment? yes
• Any suggestions or observations that could improve this particular process (in general, or specifically you, or specifically for the original author). none