CS计算机代考程序代写 Microsoft PowerPoint - 12_LinkedLists.pptx

Microsoft PowerPoint – 12_LinkedLists.pptx

CS 2211
Systems Programming

Part Eleven:
Linked Lists

Linked List

Node object

Nodes in Singly Linked Lists

• Nodes for our linked lists will be objects
dynamically created or deleted in the HEAP

• Each Node object in a singly linked list will
contain two member variables:

Node* nextItem value

Linked List

Node objects

Data objects can be simple data (int, double, etc) or
complex data (arrays, structures or unions ) or
pointers to data outside each individual nodes

typedef struct fraction {
int wP;
int fP;

} fract;

MEMORY MAPPING – STRUCTURE

397 – 398 – 399 –
1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1
400 – 401 – 402 –
0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1
403 – 404 – 405 –
0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0
406 – 407 – 408 –
1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0
409 – 410 – 411 –
0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1
412 – 413 – 414 –
1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1
415 – 416 – 417 –
1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0
418 – 419 – 420 –
0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0
421 – 422 – 423 –
1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first *pNew;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403
first.fP 404 – 407
first.link 408 – 411
pNew 412 – 415

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pNew;

first.wp = 7;
first.fP = 3;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411
pNew 412 – 415

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411
pNew 412 – 415 10100
{DM} 10100 – 10111

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pNew;

first.wp = 7;
first.fP = 3;

pNew = (fract*)malloc(sizeof (fract));

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pNew;

first.wp = 7;
first.fP = 3;

pNew = (fract*)malloc(sizeof (fract));

pNew->wP = 56;
pNew->fP = 92;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411
pNew 412 – 415 10100
pNew->wP 10100 – 10103 56
pNew->fP 10104 – 10107 92
{DM} 10108 – 10111

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pNew;

first.wp = 7;
first.fP = 3;

pNew = (fract*)malloc(sizeof (fract));

pNew->wP = 56;
pNew->fP = 92;

first.link =
pNew;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411 10100
pNew 412 – 415 10100
pNew->wP 10100 – 10103 56
pNew->fP 10104 – 10107 92
{DM} 10108 – 10111

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411 10100
pNew 412 – 415 10100
pNew->x 10100 – 10103 56
pNew->y 10104 – 10107 92
{DM} 10108 – 10111

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pNew;

first.wp = 7;
first.fP = 3;

pNew = (fract*)malloc(sizeof (fract));

pNew->wP = 56;
pNew->fP = 92;

first.link = pNew;
printf( “\nwP: %d, fP: %d\n” , first.link->wP , first.link->fP ) ;

MEMORY MAPPING – STRUCTURE

POINTERS and STRUCTURES and LINKS
– a pointer variable can also be used

to DYNAMICALLY allocate memory.

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411 10100
pNew 412 – 415 10100
pNew->wP 10100 – 10103 56
pNew->fP 10104 – 10107 92
{DM} 10108 – 10111

…
pNew = (fract*)malloc(sizeof (fract));

pNew->wP = 56;
pNew->fP = 92;

first.link = pNew;
printf( “\nwP: %d, fP: %d\n” , first.link->wP , first.link->fP ) ;

7
3

56
92

[ 400 ]

[ 10100 ]

[ 10100 ]
link

link

MEMORY MAPPING – STRUCTURE

better use of pointer variables in a link

Address
Label

Label Address Value

first.wP 400 – 403 7
first.fP 404 – 407 3
first.link 408 – 411 10100
pNew 412 – 415 10100
pNew->x 10100 – 10103 56
pNew->y 10104 – 10107 92
{DM} 10108 – 10111

typedef struct fraction {
int wP;
int fP;
struct fraction* link;
} fract;

fract first, *pTop, *pNew;

first.wp = 7;
first.fP = 3;

pTop = &first;

pNew = (fract*)malloc(sizeof (fract));

pNew->wP = 56;
pNew->fP = 92;

pTop->link = pNew;
printf( “\nwP: %d, fP: %d\n”, pTop->link->wP , pTop->link->fP ) ;

Linked Lists in C

END OF PART 1

Related Posts