Some help with structures
CSCI 515
Purpose of a structure:
To create a record holding various data types that is not
necessarily the same (i.e... student-id, name, grade) all
in one variable.
Example:
struct student_type { short id;
char name[20];
double gpa;
};
student_type jim_major; // single student variable
student_type class_515[100]; // array holding up to 100 students.
student_type class_520[80]; // array holding up to 80 students.
Accessing:
jim_major.id = 1;
strcpy(jim_major.name,"Jim Major");
jim.major.gpa = 1.4; // poor guy
class_515[0].id = 0; // 1st student's id
class_515[15].gpa = 3.8; // 16th student's gpa
Enhancing student_type some:
struct student_type { short id;
char name[20];
double gpa;
short exam_grades[3];
short lab_grades[15];
short clab_grades[15];
};
Now, we can do :
student_type jim_major;
student_type class_515[100];
student_type class_520[80];
jim_major.exam_grades[0] = 34; // jim failed the 1st exam.
class_520[3].lab_grades[4] = 5; // 5 assigned as grade for 5th
student in 520 class
Extending a bit more:
struct address_type { char street[30];
char city[40;
char state[2];
char zipcode[5];
char country[10];
}
struct student_type { short id;
char name[20];
address_type home_address; // nested structures
address_type school_address; // nested structures
double gpa;
short exam_grades[3];
short lab_grades[15];
short clab_grades[15];
};
Access ( assuming same variables created) :
// each dot below seperates a struct nesting
strcpy(jim_major.home_address.street,"1818 Hunt Street # 1");
strcpy(class_520[3].home_address.city,"Banglore");
but we are still being sloppy...
let's add one more structure...
struct class_type { char department[20];
char class_name[15];
char class_id[6];
char instructor_name[25]; // or a structure holding info on an
instructor
short number_students;
student_type students[100]; // max of 100 students in the class
};
now we can create
class_type csci515;
class_type csci520;
and add information about the instructor, # students, student names
etc...
for a class... or an array of classes
class_type computer_science[20]; // 20 computer science departments
One thing -> all these compile type (fixed size) arrays is
inefficient...
When we learn pointers - we can size these as we wish.
When we learn data structures, we can be even more efficient, as we
can
hold pointers to other structures in a structure definition
(used
for linked lists and trees amongst other things. Well, that's
520
and we are getting ahead of ourselves... and 520 tips for
structures are at the very bottom of this text file :)
In reference to the above algorithms .. one could use the following
structures:
// hold the 2 sizes in one structure
struct size_type { int size;
int newsize;
};
size_type sizes;
Access:
sizes.size = 50;
sizes.newsize = 30;
// hold the raw data as an structure array or table
struct raw_data_type { int orig_data; // store number
int sales; // sales $ amount
}
raw_data_type data[500];
Access:
data[0].orig_data = 5;
data[1].orig_data = 5;
data[2].orig_data = 25;
data[0].orig_sales = 50;
data[1].orig_sales = 350;
data[2].orig_sales = 150;
etc..
// hold the processed data results as an structure array or table
struct processed_data_type { int nd; // store number
int count; // count of store sales days
int total_sales; // total sales for this store ( all days )
}
processed_data_type new_data;
new_data[0].nd = 5;
new_data[0].count = 2;
new_data[0].total_sales = 400;
new_data[1].nd = 25;
new_data[1].count = 1;
new_data[1].total_sales = 150;
etc..
Calling functions with a structure:
#include <iostream>
#include <iomanip>
int main() {
...
function_name(sizes,data,new_data);
...
...
return 0;
}
Defining a function (function_name) to receive structure parameters:
// --------------------------------------------
// Created: June 13, 2007 - Mary Johnson
// Last Modified: June 21, 2007 - Joe Smith
/* this function does .....
and
this
and
that
*/
// --------------------------------------------
void function_name(size_type &sizes, raw_data_type data[],
processed_data_type new_data[])
{
// code .....
int i;
for(i=0;i<sizes.size;i++) }
// ...
sizes.newsize = 15;
// ...
} // end of for(i=0;i<sizes.size;i++) }
}
// --------------------------------------------
// end of function_name
// --------------------------------------------
NOTES: sizes variable passed by reference so main will receive updates.
Arrays can not be passed by reference. Main will receive
updates automatically.
One can have a structure return type for a function.
One can not have an array return type for a function.
A structure element can be assigned to another similiar
structure element.
All elements or components will be assigned or copied.
i.e. new_data[15] = new_data[0]; is legal
and is better than
new_data[15].nd = new_data[0].nd;
new_data[15].count = new_data[0].count;
new_data[15].total_sales = new_data[0].total_sales;
as it reads easier and if the structure change (additional
elements), the assignment statement does not have to change to
accomodate.
520 tips:
----------------------
Ok... review this structure below...
struct node_type { short id;
node_type* next; // pointer that holds address of this or
// any other instantiated object of type
// "node_type"
}
therefore, with this structure, i can create "nodes"...
node_type node; // create a node at compile time
or
node_type* node = new node; // create dynamically
and
if i have 5 of these nodes - i might have them
lined up as follows in a stack...
null <--- node1 <--- node2 <--- node3 <--- node4 <---- node5
or diagramically in a queue with 2 seperate pointers
called qf and qr used to store the memory addresses
of the front and rear of the queue respectively.
node_type* qf,qr; // create simple pointers
node1---> node2 ---> node3 ---> node4 ---> node5
node 1 pointer points to (holds address of ) node2, etc..
how do i get access to node 1 or node5 ?
we store them separately (not as full objects with no data).
the separate node_type*s are qf and qr... with qf holding
address of node1, and qr holding address of node5
Ok - so much for a node_type with only one node_type*...
what if we have
struct class_type { short id;
// pointer that holds address of this or
// any other instantiated object of type
// "class_type"
class_type* class_next;
// pointer that holds address of any
// instantiated object of type
// "student_type"
student_type* student_next;
};
struct student_type {
short id;
char name[30];
student_type* student_next;
};
Confused ?
Look at this structure....
classes (515,520,530)
students (1,2,3,4,5)
class515 ---> class520 ---> class530 ---> null (simple linked list)
| | |
| | |
student1 student2 NULL
| |
| |
NULL student3
|
|
student1
|
|
NULL
In this diagram, the classes 515,520,and 530 are lined up
based on the class_type* class_next.
Class515 also has a pointer that points to the students in
the 515 class (the structure for the students is not shown)
Class 520 has 3 students in them - students 1,2,and 3 which
are linked to each other as shown.
class 530 has no students yet - so the 530 student-next pointer
is holding a memory value of NULL.
Notice that the class type structure or objects can point both
to one other class and one student, whereas the students can only
point to students
Can it get more complicated ? Of course... :)
I could decide to hold an entire linked list in an array...
struct student_type {
short id;
char name[30];
student_type* student_next;
};
student_type students[100]; // array of 100 students, with each
// element (0-99) able to point at
// another element via a pointer
This is called a linked list in an array in the class, and also
could have been written as follows...
struct student_type {
short id;
char name[30];
short student_next; // simply a short to hold an offset
};
In this simplified version of a lla (linked list array), the
short offset holds an offset for which element a row of data
will be linked to next (i.e. .. the rows might be ordered 1,9,3,13,
32,null in that order
The lecture will clarify this very well...
*** Trees ***
Binary trees have 2 pointers ( one to the left and one to the right).
( Root__Node )
| |
| |
node1 node3
| | | |
node5 node7 node8 NULL
This tree is 3 levels deep with only one slot not occupied,
the right "child" node of node3.
Structure declaration is as follows:
struct student_type {
short id;
char name[30];
student_type* left; // a student_type* called left
student_type* right; // a student_type* called right
};
Could we have tree nodes with more than a left and right
pointer ? - such as another pointer to a stack coming off
each node ??? (there is no limit to your design).
---------------------
End of 520 tips
Any corrections or comments... please get back to me by
email.
End of Document
Jim Major
Graduate Assistant
June 13, 2007