|
|
|
Excerpts from C Notes ... Defining
types We
can create our own types in C by using the typedef keyword.
Having done this, we can use them to declare variables as we would the
standard C types like int, float and char.
Here's how we would do it with our student record example: /*
Inform the compiler of a type definition called <Student> */ /*
No memory is allocated
*/ typedef
struct {
char *name;
float mark;
int age; }
Student; Student
r[3]; /* Allocate three student
records in memory */ We
can even create types within types. Consider
a definition of a Class which uses the Student type as a subfield. typedef
struct {
char *teacher;
char *courseDescription;
Student *s;
}
Class; And
an even greater aggregate School which includes Class which
includes Student: typedef
struct {
char *name,*address,*telephone;
Class *classes; }
School; It
is also possible to typedefine standard types into other names: typedef
char Buffer[80]; /*
define Buffer as an 80 byte char space */ typedef
unsigned char Byte; /* define Byte
as a value from 0-255 */ Tip
Run
time memory model
So
far we have written programs using a static memory model, static meaning
fixed, meaning that as we code the program, we make assumptions as to the worst
case size of the data we expect. Recall
our storage paradigm for a series of student names: #define
MAX_CHARS 80 #define
MAX_STUDENTS 20 char
s[MAX_STUDENTS][MAX_CHARS]; The
student name array <s> has a fixed size, 80 chars being allotted for each
student for the duration of the program. In
memory this is called a smooth array:
012345.....79
‑‑‑‑‑‑‑‑‑‑‑ Row
0 |Joe\0 |
Total space = 20 x 80 chars = 1600 bytes Row
1 |Mary\0 | ...
|
| (poor memory
management) Row19|
|
‑‑‑‑‑‑‑‑‑‑‑ There
is a problem here in that too much memory is being wasted on names, considering
that most of the time they will be less than 80 characters.
Twenty strings means we need a worst case of all 20 * 80 = 1600
characters. Rather
we would like to allocate the worst case once, say 80 characters, and after that
allocate exactly the number of characters for each string at run-time.
This is a dynamic memory model, or run‑time memory model.
To create a run-time memory model, we must make use of the run-time
memory functions in <stdlib.h>:
void * malloc(int nBytes); /* allocate memory while program is running
*/
void free(void *);
/* deallocate memory while program is running */ How
do we use malloc() and free()? malloc()
returns a pointer to a safe address in memory in heap, or run-time space
of a buffer of size which you must specify. free()
gives a malloced buffer back to the system for reuse.
Let's
consider a simple example where we wish to read one student's name from the
keyboard and store it optimally in memory: /*
Ex 1 */ #include
<stdio.h> #include
<stdlib.h> #define
MAX_CHARS 80 void
main() {
char temp[MAX_CHARS]; /*
worst case size temporary buffer */
char *name; /*
pointer to an exact length string */
printf("Please enter your name: MAX %d",MAX_CHARS);
/* put user name in temp buffer */
scanf("%s",temp);
/* allocate exactly enough space for name */
name = (char*)malloc(strlen(temp)+1);
/* put the name in the exact length buffer */
strcpy(name,temp);
printf("stored result is %s\n",name);
/* deallocate name once we are done with it */
free(name); } Memory
map
‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑ temp
‑> | ... 80 chars ... |
Compile time allocation
‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑
--- name
| . |
---
||
\/
‑‑‑‑‑‑‑‑‑‑
|Jonathon\0|
Run time allocation
‑‑‑‑‑‑‑‑‑‑ /*
Ex 2 : we can extend Ex 1 to read in a series of names
and store them optimally */ #define
MAX_CHARS 80 #define
NNAMES 5 void
main() {
char *names[NNAMES];
/* allocate 5 ptrs to exact length strings */
char temp[MAX_CHARS];
/* temporary buffer
*/
int i;
/* read and allocate the names */
for (i = 0; i < NNAMES; i++)
{
printf("Enter name %d:",i);
scanf("%79s",temp);
name[i] = (char*)malloc(strlen(temp)+1);
strcpy(name[i],temp);
}
/* print and deallocate names */
for (i = 0; i < NNAMES; i++)
{
printf("Name %d: %s\n",i,name[i]);
free(name[i]);
} } Memory
Map TEXT
... CODE
... HEAP
(works forward in memory,
contains malloced memory
or run-time memory)
Greg\0
<---
Nancy\0
<---|-
Fred\0
<---|-|-
Joe\0
<---|-|-|-
Allison\0
<---|-|-|-|-
| | | | | STACK
(works backwords in memory,
contains local variables)
|
| | | |
| | | | |
int i
| | | | |
temp ‑>
|...80 chars |
| | | | |
names ‑> names[0] ‑------------
| | | | [
<names> is a ragged array,
names[1] ‑--------------
| | |
much more memory efficient
names[2] ‑----------------
| |
than the smooth array model ]
names[3] ------------------- | names[4] ‑-------------------
...
PROJECT
3: Catering company ingredient manager You
are hired by Karake food catering Co. to develop an automated system that
manages weekly shopping requirements. Karake's
scenario is the following:
ADVANCE ORDERS Shopping
for meal
COME IN ===> ingredients must be done
in advance so banquets can
be prepared on time This
means that specific food and quantities must be purchased at the
appropriate times throughout the week. This
may be complex. Mistakes
can be made by erring/sleepy personell. Better
to let the
computer perform optimal allocation of meal ingredients. Karake
promotes the following menu: ================================================= KARAKE
CATERING CO.
Delicacies offered:
1 ‑ Combo 1, veggie platter
2 ‑ Combo 2, fish platter with greek salad ================================================= The
type of report they would like to be generated is: Attention
: shoppers Report
generated on Mar 09/96 You
have the following shopping schedule(s): Mar
3/96
Item
Amount Price/unit
Expected price
‑‑‑‑
‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑‑‑‑‑
Onion
40
$0.10
$400
Lettuce 50
$1.12
$65
Tomato
43
Cucumber 21
...
Potatoe 100
Rice
12 kg
Beverage 100
‑‑‑‑‑‑‑‑
$312.12 Mar
5/96
Item
Amount Price/unit
Expected price
‑‑‑‑
‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑‑‑‑‑
Halibut 5 kg
5.00
$25
Cream 3 kg
1.50
$ 4.50
‑‑‑‑‑‑‑‑‑
29.50
Warning: the following foods may spoil before next usage!!
Cream $4.50 Mar
10/96
Item
Amount Price/unit
Expected price
‑‑‑‑
‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑
‑‑‑‑‑‑‑‑‑‑‑‑‑‑
Tomatoes .... ..
etc.
Attention:
managers, stats (for week ending Mar 10/96): Total
# combos : 150 #
Mouths to feed : 150 Total
Revenue :
$1202.56 Total
Food expenses: $ 401.22 Gross
profit :
$ 801.34 Sample
time line Let
us look at a time line for a typical week in the life of Karake: (O)
Mar 01/96 Karake gets two orders
for catering
One due
Mar 04/96
Another due Mar 09/96 | (S)
Mar 03/96 Shopping day, ingredients
purchased | (B)
Mar 04/96 Banquet served | (S)
Mar 05/96 Shopping day, more
ingredients purchased | (0)
Mar 06/96 Another order for Mar
12/96 | (B)
Mar 09/96 Banquet served | (S)
Mar 10/96 Shopping day, more
ingredients purchased | (B)
Mar 12/96 Feast! ... According
to the codes listed above,
O = Order received
S = Shopping day
B = Banquet we
will need several files to organize orders, meal combos, specific
food info and shopping times. Let's
propose them working
from high to low level. DATA
FILES: combo‑details {
"Combo 1, veggie platter"
Salad 1
Fries 1
RiceDelight 1
Beverage 1 } {
"Combo 2, fish platter with greek salad"
Halibut 1
Fries 2
Beverage 1 } {
"Combo 3, cocktail delight"
ShrimpTray 1
CheeseAndCrackers 1
Wine
1 } combo‑primitives Salad {
Lettuce 0.3
Tomato 0.5
Cucumber 0.1 } Fries {
Potato 2; } RiceDelight {
Tomato 0.5
Rice 0.2
Onion 0.4 } Basic‑ingredients #
NAME Units Expected price/unit SPOIL
TIME(in days) #‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑ #
N = # of units #
K = # of kgs Tomato
N 0.3
5 Cucumber
N 0.25
3 Onion
N 0.4
30 Potatoes
N 0.05
20 Broccoli
N 1.25
4 SwissChar
N 2.00
3 Halibut
K 5.00
4 Rice
K 0.45
365 Spagghetti
K 0.32
365 Milk
K 0.50
5 Cream
K 0.70
3 orders #
each order has following format #
# of combo orders, Delivery required #
the details of the record are #
date, # persons, meal #, delivery 1
YES
02/03/09 10
2 2
YES
02/03/11 25
1
02/03/11 15
2 regular‑runs
done on the following days Mon Wed NOTE: By
setting up the control information in various files, the program is quite
general. The user can restructure
meal plans, adjust ingredient prices, etc by changing these control files and
rerunning the program. Suggested
definitions: MEAL
COMBOS (MC.IN) struct
Plate {
char *itemName;
float quantity; }; struct
MealCombo {
char *comboName;
struct Plate *pList; }; ORDERS
(ORDERS.IN) struct
SubCombo {
int comboStyle;
int totalPeople; }; struct
Order {
char *name;
char *address;
char *phone;
char *orderDate;
char *banquetDate;
int nCombos;
struct SubCombo *scList;
char *payment;
int delivery; }; MEAL
COMBO INFO (MCI.IN) struct
MealIngredient {
char *ingredient;
float quantity; }; struct
MealComboInfo {
char *mealChoice;
struct MealIngredient *ingrList; }; INGREDIENTS
(ING.IN) enum
{PASTA,DAIRY,MEAT,VEG}; // this is
for typeOfIngredient struct
Ingredient {
char *name;
char unit;
float price;
int keepDuration;
int typeOfIngredient; }; REGULAR
RUNS (SHOPTIME.IN) char*
shopDays[MAX_DAYS]; shopDays[0]
= "Mon"; shopDays[1]
= "Wed"; shopDays[2]
= 0; The
above describes two regular shopping days |