CS计算机代考程序代写 data structure chain compiler flex assembler algorithm COMP9024: Data Structures and Algorithms

COMP9024: Data Structures and Algorithms

COMP9024: Data Structures and
Algorithms

Week 2: Dynamic Data Structures

1

Contents

• Dynamic Memory Management
• Singly Linked Lists
• Doubly Linked Lists

2

Storage Classes in C

• Automatic variables auto
• Register variables register
• External variables extern
• Static variables static

3

Automatic Variables

Any variable defined in a function
• Also called local variable
• Its lifetime is the execution period of

the function
• Its scope is within the function
• The keyword auto can be used to

define a local automatic variable.
However, it’s not required.

void DemoFunction(void);
{

auto float Local_variable=0;

}

int main(void) {
Automatic_Variable = 10;
DemoFunction();

return 0;

}

4

Register Variables

• A register variable is stored in a
register by the compiler
 Specified by the key word

register

register int Global_Variable=1;

int main(void) {
register int Local_Variable = 10;
…;
return 0;

}

5

External Variables
File1:
int Global_Variable;
void DemoFunction(void);

int main(void) {
Global_Variable = 10;
DemoFunction();
return 0;

}

File2:
extern int Global_Variable;
void DemoFunction(void) {

++Global_Variable;
}

• An external variable is a variable defined
outside any function block, also called global
variable.
 Its lifetime is the entire program.
When a function in one file references an

external variable in another file, the key word
extern must be used.

6

Static Variables

• A static variable is a
variable that is allocated
statically, meaning that its
lifetime is the entire run of
the program.

• A static variable is
initialized only once.

#include

void func() {
static int x = 0;
// x is initialized only once across five calls of func()
x++;
printf(“%d\n”, x); // outputs the value of x

}

int main() {
func(); // prints 1
func(); // prints 2
func(); // prints 3
func(); // prints 4
func(); // prints 5
return 0;

}
7

Memory Layout of A C Program (1/4)

• Text (code) segment
 Stores the machine instructions that

the CPU executes
• Initialized data segment
 containing global variables and static

local variables that are specifically
initialized in the program. For
example, maxcount and i are in this
segment:

int maxcount = 99;

int main()

{ static int i=0;

} 8

Memory Layout of A C Program (2/4)
• Uninitialized data segment
 Called the “bss” segment, named after an ancient

assembler operator that stood for “block started by
symbol“.

 bss contains all the global variables and static local
variables that are not initialised. Data in this
segment is initialized to 0 or null pointers. The C
declaration

long sum[1000];

appearing outside any function causes this global
variable to be stored in the uninitialized data
segment. 9

Memory Layout of A C Program (3/4)

• When to initialize uninitialized data segment bss?
 Typically only the length of the bss section, but no

data, is stored in the object file. The program loader
of the operating system allocates memory for the
bss section when it loads the program.

 In embedded software, the bss segment is mapped
into memory that is initialized to zero by the C run-
time system before main() is entered.

10

Memory Layout of A C Program (4/4)

• Stack
 where automatic variables are stored, along with information that is saved

each time a function is called. Each time a function is called, the address of
where to return to and certain information about the caller’s environment,
such as some of the machine registers, are saved on the stack. The newly
called function then allocates room on the stack for its automatic and
temporary variables. This is how recursive functions in C can work. Each time
a recursive function calls itself, a new stack frame is used, so that the
variables of one instance of the function do not interfere with the variables of
another instance.

• Heap
 where dynamic memory allocation takes place.

11

Example

int numbers[] = { 40, 20, 30 };

void insertionSort(int array[], int n) {
int i, j;
for (i = 1; i < n; i++) { int element = array[i]; while (j >= 0 && array[j] > element) {

array[j+1] = array[j];
j–;

}
array[j+1] = element;

}
}

int main(void) {
insertionSort(numbers, 3);
return 0;

}

Which memory section are the following objects located
in?

1. insertionSort()
2. numbers[0]
3. i
4. element

_________________________________

1. Code segment
2. Initialized data segment
3. Stack segment
4. Stack segment

12

Dynamic Memory Allocation (1/3)

So far, we have considered static memory allocation
• all objects completely defined at compile-time
• sizes of all objects are known to compiler

Examples:

int x;
char *cp;

typedef struct {float x; float y;} Point;
Point p;
char s[20];

13

Dynamic Memory Allocation (2/3)

In many applications, fixed-size data is ok.
In many other applications, we need flexibility.
Examples:

char name[MAXNAME];
char item[MAXITEMS];
char dictionary[MAXWORDS][MAXWORDLENGTH];

With fixed-size data, we need to guess sizes (“large enough”).

14

Dynamic Memory Allocation (3/3)

Fixed-size memory allocation:
• allocate as much space as we might ever possibly need

Dynamic memory allocation:
• allocate as much space as we actually need
• determine size based on inputs

But how to do dynamic memory allocation in C?

15

The malloc() Function (1/3)

malloc() function interface
void *malloc(size_t n);

What the function does:
• attempts to reserve a block of n bytes in the heap
• returns the address of the start of this block
• if insufficient space left in the heap, returns NULL

Note: size_t is essentially an unsigned int
• but has specialised interpretation of applying to memory sizes measured in

bytes

16

The malloc() Function (2/3)

Example use of malloc:

17

The malloc() Function (3/3)

Things to note about void *malloc(size_t):
• it is defined as part of stdlib.h
• its parameter is a size in units of bytes
• its return value is a generic pointer (void *)
• the return value must always be checked (may be NULL)

Required size is determined by #Elements * sizeof(ElementType)

18

Example
Create a dynamic m×n-matrix of floating point numbers, given m and n.
How many bytes need to be reserved?

Matrix:
float *matrix = malloc(m * n * sizeof(float));
assert(matrix != NULL);

4mn bytes allocated

void assert(int expression) is a C built-in macro. If expression evaluates to TRUE, assert()
does nothing. If expression evaluates to FALSE, assert() displays an error message on
stderr (standard error stream to display error messages and diagnostics) and aborts
program execution.

19

Example

Create space for 1,000 speeding
tickets (cf. Lecture Week 1)
How many bytes need to be
reserved?

Speeding tickets:
typedef struct {

int day, month, year;
} DateT;
typedef struct {

int hour, minute;
} TimeT;
typedef struct {

char plate[7];
DateT d;
TimeT t;

} TicketT;

TicketT *tickets = malloc(1000 * sizeof(TicketT));
assert(tickets != NULL);

28,000 bytes allocated
20

More about malloc() (1/2)

malloc() returns a pointer to a data object of some kind.

Things to note about objects allocated by malloc():
• they exist until explicitly removed (program-controlled lifetime)
• they are accessible while some variable references them
• if no active variable references an object, it is garbage

The function free() releases objects allocated by malloc()

21

More about malloc() (2/2)

Usage of malloc() should always be guarded:

int *vector, length, i;

vector = malloc(length*sizeof(int));

assert(vector != NULL);

for (i = 0; i < length; i++) { … vector[i] … } Alternatively: int *vector length, i; … vector = malloc(length*sizeof(int)); if (vector == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } for (i = 0; i < length; i++) { … vector[i] … } • fprintf(stderr, …) outputs text to a stream called stderr (the screen, by default) • exit(v) terminates the program with return value v 22 Memory Management (1/5) void free(void *ptr) • releases a block of memory allocated by malloc() • *ptr is a dynamically allocated object • if *ptr was not malloc()'d, chaos will follow Things to note: • the contents of the memory block are not changed • all pointers to the block still exist, but are not valid • the memory may be re-used as soon as it is free()'d 23 Memory Management (2/5) Warning! Warning! Warning! Warning! Careless use of malloc() / free() / pointers • can mess up the data in the heap • so that later malloc() or free() cause run-time errors • possibly well after the original error occurred Such errors are very difficult to track down and debug. Must be very careful with your use of malloc() / free() / pointers. 24 Memory Management (3/5) If an uninitialized or otherwise invalid pointer is used, or an array is accessed with a negative or out-of-bounds index, one of a number of things might happen: • program aborts immediately with a "segmentation fault" • a mysterious failure much later in the execution of the program • incorrect results, but no obvious failure • correct results, but maybe not always, and maybe not when executed on another day, or another machine The first is the most desirable, but cannot be relied on. 25 Memory Management (4/5) Given a pointer variable: • you can check whether its value is NULL • you can (maybe) check that it is an address • you cannot check whether it is a valid address 26 Memory Management (5/5) Typical usage pattern for dynamically allocated objects: Type *ptr = malloc(sizeof(Type)); assert(ptr != NULL); free(ptr); int nelems = NumberOfElements; ElemType *arr = malloc(nelems*sizeof(ElemType)); assert(arr != NULL); free(arr); 27 Memory Leaks Well-behaved programs do the following: • allocate a new object via malloc() • use the object for as long as needed • free() the object when no longer needed A program which does not free() an object before the last reference to it is lost contains a memory leak. Such programs may eventually exhaust available heap space. 28 Singly Linked Lists in C (1/18) A singly linked list is a chain of nodes, where each node contains a pointer to the next node To represent a chained (linked) list of nodes: • we need a pointer to the first node and possibly a tail pointer to the last node • each node contains a pointer to the next node • the next pointer in the last node is NULL 29 Singly Linked Lists in C (2/18) A node has two components: • data, which can be a single value ( e.g. int), or a collection of values, depending on specific application • a pointer to the next node An example node in C: struct NodeT { int data; struct NodeT *next; }; 30 Singly Linked Lists in C (3/18) Typical operations on singly linked lists: • Create a new linked list • Create a new node • Delete a node • Insert a node • Find a node containing particular data 31 Singly Linked Lists in C (4/18) Create a new node: NodeT * createNode(int v) { NodeT *new = malloc(sizeof(NodeT)); assert(new != NULL); new->data = v;
new->next = NULL;
return new;

}

32

Singly Linked Lists in C (5/18)

Create a new singly linked list of three nodes:

NodeT *list = createNode(1);
list->next = createNode(42);
list->next->next = createNode(9024);

33

Singly Linked Lists in C (6/18)

NodeT* addNode(NodeT *head, int v){ // head points to the first node
NodeT *temp, *p; // declare two node pointers temp and p
temp = createNode(); //create a new node
temp->data = v; // add element’s value to data part of node
if(head == NULL){

head = temp; //when linked list is empty
}

else {
p = head; //assign head to p
while (p->next != NULL){

p = p->next; //traverse the list until p is the last node
}
p->next = temp; // Make the previous last node point to the new node

}
return head;

}

Add a node at the end:
1. Create a new node
2. Find the last node
3. Make the last node

point to new node

If we maintain a tail
pointer in the list, we
can locate the last node
directly.

34

Singly Linked Lists in C (7/18)

NodeT *list;
NodeT *p;

p = list;
while (p != NULL) {

printf(“%d”, p->data);
p = p->next;

}

for (p = list; p != NULL; p = p->next) {
printf(“%d”, p->data);

}

Iterate over a singly linked list:
• set p to point to first node (head)
• examine node pointed to by p
• change p to point to next node
• stop when p reaches end of list

(NULL)

35

Singly Linked Lists in C (8/18)

36

Singly Linked Lists in C (9/18)

37

Singly Linked Lists in C (10/18)

Find an element in a singly linked list:
int findElement(NodeT *list, int d) {

NodeT *p;
for (p = list; p != NULL; p = p->next)

if (p->data == d)
return 1;

return 0;
}

Print all elements:
showElements(NodeT *list) {

NodeT *p;
for (p = list; p != NULL; p = p->next)

printf(“%6d”, p->data);
} 38

Singly Linked Lists in C (11/18)

Linked list nodes are typically located
in the heap
• because nodes are dynamically

created
Variables containing pointers to list
nodes
• are likely to be local variables (in

the stack)
Pointers to the start of lists are often
• passed as parameters to function
• returned as function results

39

Singly Linked Lists in C (12/18)

Linked lists are more flexible than arrays:
• values do not have to be adjacent in memory
• values can be rearranged simply by altering pointers
• the number of values can change dynamically
• values can be added or removed in any order

Disadvantages:
• it is not difficult to get pointer manipulations wrong
• each value also requires storage for next pointer
• creating a node needs OS support, and thus is slow.

40

Singly Linked Lists in C (13/18)

What does this code do?
1 NodeT *p = list;
2 while (p != NULL) {
3 printf(“%6d”, p->data);
4 if (p->next != NULL)
5 p = p->next->next;
6 else
7 p = NULL;
9 }
What is the purpose of the conditional statement in line 4?
________________________________________
Every second list element is printed.
If *p happens to be the last element in the list, then p->next->next does not exist.
The if-statement ensures that we do not attempt to assign an invalid address to p in line 5.

41

Singly Linked Lists in C (14/18)

Rewrite showElements() as a recursive function.

void printElements(NodeT *list) {
if (list != NULL) {

printf(“%6d”, list->data);
printElements(list->next);

}
}

42

Singly Linked Lists in C (15/18)

Insert a new element at the beginning:

NodeT *insertAtHead(NodeT *list, int d) {
NodeT *new = createNode(d);
new->next = list;
return new;

}

43

Singly Linked Lists in C (16/18)

Delete the first element:

NodeT *deleteHead(NodeT *list) {
assert(list != NULL);
NodeT *head = list;
list = list->next;
free(head);
return list;

}

What would happen if we didn’t free the memory pointed to by head?

44

Singly Linked Lists in C (17/18)

Delete a specific element (recursive version):

NodeT *deleteLL(NodeT *list, int d) {
if (list == NULL) {

return list;

} else if (list->data == d) {
return deleteHead(list);

} else {
list->next = deleteLL(list->next, d);
return list;

}
}

45

Singly Linked Lists in C (18/18)
Write a C-function to destroy an entire list.
Iterative version:

void freeLL(NodeT *list) {
NodeT *p;

p = list;
while (p != NULL) {

NodeT *temp = p->next;
free(p);
p = temp;

}
}
Why do we need the extra variable temp?

46

Stack ADT Implementation Using Linked List
(1/4)

Interface (in stack.h)
// provides an opaque view of ADT

typedef struct StackRep *stack;
// set up empty stack
stack newStack();
// remove unwanted stack
void dropStack(stack);
// check whether stack is empty
int StackIsEmpty(stack);
// insert an int on top of stack
void StackPush(stack, int);
// remove int from top of stack
int StackPop(stack);
ADT stack defined as a pointer to an unspecified struct

47

Stack ADT Implementation Using Linked List
(2/4)
#include
#include
#include “stack.h”

typedef struct node {
int data;
struct node *next;

} NodeT;

typedef struct StackRep {
int height;
NodeT *top;

} StackRep;

stack newStack() {
stack S = malloc(sizeof(StackRep));
S->height = 0;
S->top = NULL;
return S;

}

int StackIsEmpty(stack S) {
return (S->height == 0);

}

48

Stack ADT Implementation Using Linked List
(3/4)
void StackPush(stack S, int v) {

NodeT *new = malloc(sizeof(NodeT));

assert(new != NULL);

new->data = v;

new->next = S->top;

S->top = new;

S->height++;

}

void dropStack(stack S) {
NodeT *curr = S->top;
while (curr != NULL) {

NodeT *temp = curr->next;
free(curr);
curr = temp;

}
free(S);

}

49

Stack ADT Implementation Using Linked List
(4/4)
int StackPop(stack S) {

assert(S->height > 0);
NodeT *head = S->top;

S->top = S->top->next;
S->height–;

int d = head->data;
free(head);
return d;

}

50

Doubly Linked Lists (1/2)

Doubly-linked lists are a variation on “standard” linked lists where each node has a
pointer to the previous node as well as a pointer to the next node.

51

Doubly Linked Lists (1/2)

• The doubly-linked list also has a notion of a “current” node, and the current node
can move backwards and forwards along the list.

• The doubly-linked list does insertions either immediately before or immediately
after the current node.

• Unlike the singly linked list, deleting the last node does not need to traverse the
entire list.

52

Summary (1/3)

void *malloc(size_t nbytes)
• aim: allocate some memory for a data object
• attempt to allocate a block of memory of size nbytes in the heap
• if successful, returns a pointer to the start of the block
• if insufficient space in heap, returns NULL

Things to note:
• the location of the memory block within heap is random
• the initial contents of the memory block are random

53

Summary (2/3)

void free(void *ptr)
• releases a block of memory allocated by malloc()
• *ptr is the start of a dynamically allocated object
• if *ptr was not malloc()’d, chaos will ensue

Things to note:
• the contents of the memory block are not changed
• all pointers to the block still exist, but are not valid
• the memory may be re-used as soon as it is free()’d

54

Summary (3/3)

• Singly linked lists
• Doubly linked lists
• Suggested reading:
Moffat, Ch.10.1-10.2
 Sedgewick, Ch.3.3-3.5,4.4,4.6

55

COMP9024: Data Structures and Algorithms
Contents
Storage Classes in C
Automatic Variables
Register Variables
External Variables
Static Variables
Memory Layout of A C Program (1/4)
Memory Layout of A C Program (2/4)
Memory Layout of A C Program (3/4)
Memory Layout of A C Program (4/4)
Example
Dynamic Memory Allocation (1/3)
Dynamic Memory Allocation (2/3)
Dynamic Memory Allocation (3/3)
The malloc() Function (1/3)
The malloc() Function (2/3)
The malloc() Function (3/3)
Example
Example
More about malloc() (1/2)
More about malloc() (2/2)
Memory Management (1/5)
Memory Management (2/5)
Memory Management (3/5)
Memory Management (4/5)
Memory Management (5/5)
Memory Leaks
Singly Linked Lists in C (1/18)
Singly Linked Lists in C (2/18)
Singly Linked Lists in C (3/18)
Singly Linked Lists in C (4/18)
Singly Linked Lists in C (5/18)
Singly Linked Lists in C (6/18)
Singly Linked Lists in C (7/18)
Singly Linked Lists in C (8/18)
Singly Linked Lists in C (9/18)
Singly Linked Lists in C (10/18)
Singly Linked Lists in C (11/18)
Singly Linked Lists in C (12/18)
Singly Linked Lists in C (13/18)
Singly Linked Lists in C (14/18)
Singly Linked Lists in C (15/18)
Singly Linked Lists in C (16/18)
Singly Linked Lists in C (17/18)
Singly Linked Lists in C (18/18)
Stack ADT Implementation Using Linked List (1/4)
Stack ADT Implementation Using Linked List (2/4)
Stack ADT Implementation Using Linked List (3/4)
Stack ADT Implementation Using Linked List (4/4)
Doubly Linked Lists (1/2)
Doubly Linked Lists (1/2)
Summary (1/3)
Summary (2/3)
Summary (3/3)