CS计算机代考程序代写 python data structure compiler flex c++ One of Four Title Slide Options

One of Four Title Slide Options

Because learning changes everything.®

From Bits and Gates to C and Beyond

Dynamic Data Structures in C

Chapter 19

© 2019 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom.
No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education.

Complex Data Types

Can represent simple data with native types (int, char, double) and
arrays of native types, including strings.
Sometimes we want to represent/model things that require multiple types
of data:

• bank account = owner (string), balance (floating pt), account
number (integer or string), …

• song in a playlist = artist (string), title (string), year (integer),
downloads (integer), …

• airplane = position (floating pt), speed (floating pt), altitude (floating
pt), airline (string), …

In C, a structure allows us to describe types that represent these kinds
of complex entities.

Example: Airplane

Suppose we want to write a program that deals with one airplane.
We could create a variable for each attribute of the airplane.
char ID[6]; // max 6 characters
int altitude; // in meters
int longitude; // in tenths degrees
int latitude; // in tenths of degrees
int heading; // in tenths of degrees
double airspeed; // in km/hr

Now suppose we want to deal with a fleet of airplanes.
We could (a) create a separate set of variables for each, or
(b) create an array for each attribute, with one value per airplane.
Approach (b) is better, because we can at least write a loop that performs
some calculation for all planes, but it’s still cumbersome.

Define a Structure

Instead, we want to capture all of the information about an airplane in a
single memory object. (We are using the word “object” very informally here. It’s not the same
as an object in a language like C++ or Python.)

Essentially, we define a new type and tell the compiler what the
components of that type are:
struct flightType {

char ID[6]; // max 6 characters
int altitude; // in meters
int longitude; // in tenths degrees
int latitude; // in tenths of degrees
int heading; // in tenths of degrees
double airSpeed; // in km/hr

};

Struct Definition and Declarations

struct flightType {
char ID[6]; // max 6 characters
int altitude; // in meters
int longitude; // in tenths degrees
int latitude; // in tenths of degrees
int heading; // in tenths of degrees
double airSpeed; // in km/hr

};

The keyword struct is used to tell the compiler that we are definining a
new type, and struct flightType is the name of that type. Each
component (field) of the new type of value has a type and a name.
This definition does not allocate any memory. It simply describes the
struct to the compiler. To allocate a variable of the new type:
struct flightType plane;
// allocates memory for a variable named “plane”

Fields

};

Once we have a variable, we use the dot operator (.) to access the
various components (fields) of the value.
struct flightType plane; // allocates a variable

plane.airspeed = 800.0;
plane.altitude = 10000;
x = plane.heading;

Memory Allocation

A struct is allocated in a contiguous
block of memory. The fields are allocated
in the order in which they appear in the definition.
struct flightType {

char ID[6];
int altitude;
int longitude;
int latitude;
int heading;
double airSpeed;

};

// local variables
int x;
struct flightType plane;
int y;

Note: In this illustration, a double is assumed to be one word.

Using typedef to Name a Type

To simplify code, or to make it more expressive, we can give a new user-
defined name to any type.
typedef type_spec name ;

This allows us to create a name for our struct type, so that we don’t have
to type struct each time we declare a variable.

typedef struct flightType Flight;

Flight plane; // declare a variable of type Flight
// allocates a struct flightType

By convention, a user-defined type starts with an upper-case letter.

Implementing Structures

The size of a struct variable is determined by the size of its fields.
• LC-3: Size of a Flight is 12 words: 7 char, 4 int, 1 double.

Each field has a constant offset from the beginning of the struct.
Compiler knows the offset from the definition; kept in the symbol table.
To access a field:

1. Get the base address of the struct object.

2. Add the offset to the base address.

3. Load/store to read/write the field.

Generally, steps 2 and 3 can be done in one instruction (LDR/STR).

Implementation Example

int x;
Flight plane;
int y;

plane.altitude = 0;

; memory layout: slide 7

AND R0, R0, #0 ; create zero
ADD R1, R5, #-12 ; base addr of plane
STR R0, R1, #7 ; store to altitude

; offset = 7

Array of Structures

Now we want a program that handles 100 airplanes.
Allocate an array:
Flight aircraft[100];

Each element of the array is a struct flightType.
Each element of the array is 12 words (LC-3).
To get to the next element of the array, add 12.

// calculate average air speed
sum = 0.0;
for (i = 0; i < 100; i++) { sum += aircraft[i].airSpeed; } sum = sum / 100.0; 11 aircraft[0] aircraft[0]aircraft[1] aircraft[2] ... aircraft[99] © McGraw-Hill Education Pointer to a Structure Since a structure is a type of memory object, we can create a pointer to it. Flight *aircraftPtr; aircraftPtr = &aircraft[34]; // pt to a particular plane How would we access the longitude field of that aircraft? (*aircraft).longitude Parentheses are required, because the field operator (.) has a higher precedence than the dereference operator (*). Since we use pointers a lot, and this notation is rather awkward and ugly, C provides a special operator (->) that dereferences a struct pointer
before accessing a field.
aircraftPtr->longitude

Key point: Use dot (.) with a struct value, and arrow (->) with a struct pointer.

Code Example

For each flight, find the nearest airplane.
void NearestNeighbor(Flight aircraft[TOTAL_AIRCRAFT]) {

double minD;
Flight *closest;

for (int i = 0; i < TOTAL_AIRCRAFT; i++) { closest = NULL; minD = MAX_DISTANCE; for (int j = 0; j < TOTAL_AIRCRAFT; j++) { if (i != j) { double dist = AirDistance(&aircraft[i], &aircraft[j]); if (dist < minD) { closest = &aircraft[j]; minD = dist; } } } printf("The closest flight to %s is %s.\n", aircraft[i].ID, closest->ID);
}

}

Passing a Structure to a Function

Structures are passed by value.
If we pass a structure as an argument, a copy of the structure is created.
For this reason, we usually choose to pass a pointer to a structure, rather
than the structure itself.
double AirDistance(Flight *plane1, Flight *plane2);

// in the function implementation,
// use plane1->longitude, etc.

Dynamic Memory Allocation

Suppose we don’t know how many planes to allocate?
The user of our program will tell us, but we won’t know the size of the
array until the program runs.
We can specify a maximum allocate for that — wasteful.

Instead, we use dynamic memory allocation to allocate exactly the
amount of memory we want, exactly when we want to use it.
Two main concepts:
• The heap is where dynamic memory objects are allocated.
• We use standard functions malloc and free to allocate and

deallocate memory.

The Heap

Recall the LC-3 memory map.
We have two areas to allocate variables:
1. Global data section:

fixed size, determined when we compiler
the program

2. Runtime stack:
variable size, push/pop local variables and
temporaries during function calls, grows
downward in memory in a LIFO fashion

Now we add a third area:
The heap grows upward in memory.
It is not LIFO. The operating system keeps
track of what memory is available and what is
allocated. Program asks OS to allocate and
deallocate memory as needed.

Memory Allocation: malloc

The malloc function allocates a block of memory and returns a pointer
to the allocated block.
Argument = number of bytes to allocate
If the allocation cannot be performed, returns NULL.
int numAircraft;
Flight *planes;

printf(“Total number of aircraft?\n”);
scanf(“%d”, &numAircraft);

planes = malloc(24 * numAircraft);
// allocate an array of Flighs, each takes 24 bytes on LC-3

Bytes? Now our code is not portable! We would have to change it for
each different platform. Instead, use the compiler operator sizeof.
planes = malloc(sizeof(Flight) * numAircraft);

Casting the Pointer from malloc

The malloc function has no idea what it is allocating, just its size.
So how does it know what kind pointer to return? It doesn’t.
It is defined to return a generic pointer type: void*

It’s legal to assign a void* value to any kind of pointer value, but we
want to “cast” the pointer to the correct type, like this:
planes = (Flight*) malloc(sizeof(Flight) * numAircraft);

Casting specifies an explicit type conversion. This allows the compiler to double-
check that we’re doing the right thing.

Finally, we should always check to be sure that memory was actually allocated.
scanf(“%d”, &numAircraft);
planes = (Flight*) malloc(sizeof(Flight) * numAircraft);
if (planes == NULL) {

printf(“Memory allocation error!\n”);
// could return or do something else…

}

Memory Deallocation: free

If we keep allocating memory, we will eventually run out of space.
When we are finished with memory that was allocated, we should give it
back to the operating system to use for other parts of the program.
The free function does this.
Argument = pointer that was previously returned by malloc
Return value: none
free(planes);

It’s important to use exactly the same pointer value that was returned.
The OS remembers the size that was allocated for that pointer, so it can
correctly return the right amount of memory to the heap.
Best practice: Always free memory when it is no longer being used.

Memory Allocation Bugs

Using malloc and free correctly can be tricky, and is a notorious
source of bugs in complex programs.

Example: The variable that holds the pointer gets changed, and the value is lost.
This is known as a memory leak, because there is no way to ever deallocate
the memory without having the pointer.

Example: The memory object is allocated inside a function and passed out for the
rest of the program to use. Who “owns” this pointer? How do you know when
it should be freed?

Example: We have a variable that points to an allocated object. We have called
free, but the variable still contains the pointer. This is known as a “dangling
pointer.” We can still dereference the pointer — at best, it now points to
garbage data and the program crashes; at worst, we get garbage data that
looks legitimate and we use it, creating a very hard-to-find error.

Linked List: A Dynamic Data Structure

Suppose we want to only represent planes that are in the air.
Planes take off and land all the time, so the number changes dynamically.
Array?
• Size of array is fixed when we create it.

Can keep track of # elements actually used in the array.
• Can be expensive to remove an item from the middle of an array.

(Move elements to fill in “empty” slot.)

A linked list is a data structure designed to hold a dynamic collection of
data elements.
• Size changes dynamically as items are added and removed.
• Efficient to add/delete at any position in the list.

Linked List

Instead of pre-allocating a number of items (e.g., array), we allocate an
item whenever we need it (using malloc).
An item is typically called a node of the list.
The items are allocated in arbitrary places
in memory (on the heap). Each node
has a pointer that tells where to find
the next node in the list.
A head pointer points to the
beginning of the list.
A null pointer means that we’re at
the end of the list: there is no
next node.

Linked List

Conceptually, we don’t need to worry about where the list nodes are
allocated. We simply start at the beginning and follow the pointers to
access the nodes.

Array vs. Linked List

Array Linked List
Size is fixed.
All memory allocated when array is
created. If more items are needed,
must create a new array and copy data.

Size is dynamic.
Memory for each node is allocated
when added to the list. List can grow
and shrink as needed, without moving
data.

Fast random access.
Calculate location of array[i] and access
it directly.

Sequential access.
Must follow pointers to get to the i-th
node of the list.

No storage overhead. Pointer stored with each item.
Adding and removing items in the
middle can require data movement.

Adding and removing items anywhere
in the list does not require data
movement.

C Implementation of a Linked List

A linked list node must have (a) data and (b) a pointer to the next node.
typedef struct flightType Flight;

struct flightType {
char ID[6];
int altitude;
int longitude;
int latitude;
int heading;
double airSpeed;
Flight *next;

};

Flight *list = NULL; // list is represented by head pointer
// initially, the pointer is NULL
// because the list is empty

Create a List Node

Flight * CreateFlight(char *ID, int longitude, int latitude,
int altitude, double airSpeed) {

Flight *newFlight;

// allocate a new node
newFlight = (Flight*)malloc(sizeof(Flight));

// initialize node data
strcpy(newFlight->ID, ID);
newFlight->longitude = longitude;
newFlight->latitude = latitude;
newFlight->altitude = altitude;
newFlight->airSpeed = airSpeed;

// initialize pointer
newFlight->next = NULL;

return newFlight;
}

Traversing a Linked List

Suppose we have a linked list created already. (We’ll see how in the next
slides.) We often want to visit each node in the list, either to do
something to each node or to look for a particular node.
void PrintAirspace(Flight *list) {

// list points to the head of a linked list of Flights
int count = 1;
printf(“Aircraft in Airspace———————\n”);
while (list != NULL) { // while not at the end

printf(“Aircraft: %d\n”, count);
printf(“Longitude: %d\n”, list->longitude);
printf(“Latitude: %d\n”, list->latitude);
// etc. etc.
count = count + 1;
list = list->next; // move to next node

}
printf(“\n\n”);

}

Adding a New Item to a List

To add to the list, create (allocate) a new node.
Determine where the node should be placed in the list.
Then adjust pointers to add node to the sequence.

In this example, we determine that node B should be added between
node A and node C. Node B’s pointer is set to C. Node A’s pointer
is set to B. (Changing A’s pointer removes the linke from A to C.)

Example: Adding a Flight

We want to keep our list of flights sorted by ID.
When adding a new flight, we must find the correct position.
Because we do this every time, assume that the list is always sorted.
To add B to the list:
1. Starting at the head, traverse the list until we find a node (C) whose

ID is greater than B’s.
2. The previous node (A) must now point to B, and B must point to C.

NOTE: Since ID is a string, we can’t use the usual comparison operators (<, >, ==).
Instead we must use the strcmp function from the Standard Library. See text.

Adding a Flight: 1st attempt

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

Adding a Node: Scenarios

The actions required to add a node to the list vary slightly, according to
where the node is being added.
Code for adding a node must account for all of the scenarios below:
add to an empty list, add to middle, add to head, add to tail.

Example: Adding a Flight

ID is greater than B’s.
2. The previous node (A) must now point to B, and B must point to C.

Special cases:
• There is no node greater than B. Then B is added to the end of the list.
• There is no node less than B. Then B is added to the beginning of the list.
• The list is empty. Then B becomes the only node in the list.
• Node B already exists. Then we don’t add it.

Problems with Code

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

If B is larger than any existing node,
this test will never pass. Function
will exit loop without adding node
to list.

Problems with Code

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

If B is smaller than any node,
then previous will be NULL
and code will crash.

Problems with Code

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

If list is empty, loop will never
executed and nothing will be
added.

Problems with Code

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

If B is already in the list,
will pass over it and add a
duplicate.

Problems with Code

// add newPlane to list in sorted order, return 0 if success
int AddFlight(Flight *newPlane, Flight* list) {

Flight *previous = NULL; // ptrs for traversing the list
Flight *current = list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare < 0) { // current comes after newPlane newPlane->next = current;
previous->next = newPlane;
return 0;

}

previous = current; // continue traversing list
current = current->next;

}
}

If B added to beginning, then
head pointer must change.
If we do this locally, then caller’s
head pointer will not change.
Must pass head pointer
by reference.

Adding a Flight: Correct Version

int AddFlight(Flight *newPlane, Flight **list) {
Flight *previous = NULL;
Flight *current = *list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(newPlane->ID, current->ID);

if (IDCompare == 0) {
return -1; // flight already in list

}

else if (IDCompare > 0) {
newPlane->next = current; // newPlane before current
if (previous == NULL)

*list->next = newPlane; // add to beginning
else

previous->next = newPlane; // add after previous
return 0; // done

}
// next slide

Adding a Flight: Correct Version (part 2)

else {
previous = current;
current = current->next; // continue looking

}
} // end of list is reached

if (previous == NULL)
*list = newPlane; // empty list

else
previous->next = newPlane; // add to tail

return 0;
}

Deleting a Node

Removing a node from the list has a similar structure, with similar
scenarios.
1. Traverse the list, looking for the node (and remembering the previous

node).
2. When found, change previous node to point to next node.

Scenarios to consider:
Remove from middle, remove from head, remove from tail, empty list.

Node 0 Node 1 Node 2

NULL

Deleting a Flight

int DeleteFlight(char *planeID, Flight **list) {
Flight *previous = NULL;
Flight *current = *list;
int IDCompare;

while (current != NULL) {
IDCompare = strcmp(planeID, current->ID);

if (IDCompare < 0) { return -1; // flight not in list } else if (IDCompare == 0) { // current is flight to remove if (previous == NULL) *list = current->next; // remove from head
else

previous->next = current->next; // remove
free(current); // deallocate memory – no longer needed
return 0; // done

}
// next slide

Deleting a Flight (part 2)

else {
previous = current;
current = current->next; // continue looking

}
} // end of list is reached

// traversed entire list without finding a match
return -1;

}

Dynamic Data Structures

Array = static data structure
+ Efficient bulk allocation and random access
– Not flexible

Linked List = dynamic data structure
+ Size is determined dynamically
+ Easy to manipulate without moving data
– Sequential access
– Repeated allocation and deallocation of data items
– Space overhead for pointers

Linking elements with pointers is fundamental.
Many other pointer-based data structures: tree, hash table, graph, …

Because learning changes everything.®

www.mheducation.com

From Bits and Gates to C and Beyond
Complex Data Types
Example: Airplane
Define a Structure
Struct Definition and Declarations
Fields
Memory Allocation
Using typedef to Name a Type
Implementing Structures
Implementation Example
Array of Structures
Pointer to a Structure
Code Example
Passing a Structure to a Function
Dynamic Memory Allocation
The Heap
Memory Allocation: malloc
Casting the Pointer from malloc
Memory Deallocation: free
Memory Allocation Bugs
Linked List: A Dynamic Data Structure
Linked List
Linked List
Array vs. Linked List
C Implementation of a Linked List
Create a List Node
Traversing a Linked List
Adding a New Item to a List
Example: Adding a Flight
Adding a Flight: 1st attempt
Adding a Node: Scenarios
Example: Adding a Flight
Problems with Code
Problems with Code
Problems with Code
Problems with Code
Problems with Code
Adding a Flight: Correct Version
Adding a Flight: Correct Version (part 2)
Deleting a Node
Deleting a Flight
Deleting a Flight (part 2)
Dynamic Data Structures
End of Main Content

Related Posts