Transcript 슬라이드 제목 없음

Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Chapter #4:
LISTS
Fundamentals of
Data Structures in C
Horowitz, Sahni and Anderson-Freed
Computer Science Press
Revised by H. Choo, September 2000.
Networking Laboratory Chap. 4-1
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Pointers
arrays
- sequential representation
- some operations are very time-consuming
due to data movement
solution? pointers: often called links
- size of data must be predefined
- static storage allocation and
deallocation
pointers
- for any type T, there is a corresponding
type called pointer-to-T in C
- actual value of pointer type: an address
of the memory
Networking Laboratory Chap. 4-2
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Pointers
pointer operators in C
- the address operator: &
- the dereference(or indirection)operator: *
dynamically allocated storage
- C provides a mechanism, called a heap, for
allocating storage at run-time
int i,*pi;
float f,*pf;
pi = (int *) malloc(sizeof(int));
pf = (float *) malloc(sizeof(float));
*pi = 1024; *pf = 3.14;
printf(“an integer=%d,a float=%f\n”,*pi,*pf);
free(pi); free(pf);
Networking Laboratory Chap. 4-3
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Singly Linked Lists
- compose of data part and link part
- link part contains address of the next
element in a list
- non-sequential representations
- size of the list is not predefined
- dynamic storage allocation and
deallocation
ptr
bat
cat
sat
vat
NULL
Networking Laboratory Chap. 4-4
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Singly Linked Lists
to insert the word mat between cat and sat
ptr
bat
cat
sat
vat
NULL
mat
1) get a currently unused node (paddr)
2) set paddr’s data to mat
3) set paddr’s link to point to the
address found in the link of the node cat
4) set the link of the node cat to point
to paddr
Networking Laboratory Chap. 4-5
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists
ptr
to delete mat from the list
bat
cat
mat
sat
vat
NULL
1) find the element that immediately
precedes mat, which is cat
2) set its link to point to mat’s
link
- no data movement in insert and
delete operation
Networking Laboratory Chap. 4-6
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists

Ex 4.1 [list of words ending in at]
define a node structure for the list
- data field: character array
- link field: pointer to the next node
- self-referential structure
typedef struct list_node *list_ptr;
typedef struct list_node {
char data[4];
list_ptr link;
};
list_ptr ptr = NULL;
Networking Laboratory Chap. 4-7
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists
create a new node for our list
then place the word bat into our list
ptr=(list_ptr)malloc(sizeof(list_node));
strcpy(ptr->data,”bat”);
ptr->link=NULL;
address of
first node
ptr->data
b
a
t
ptr->link
\0
NULL
ptr
Networking Laboratory Chap. 4-8
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists

Ex 4.2 [two-node linked list]
create a linked list of integers
typedef struct list_node *list_ptr;
typedef struct list_node {
int data;
list_ptr link;
};
list_ptr ptr = NULL;
ptr
10
20
NULL
Networking Laboratory Chap. 4-9
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists
list_ptr create2() {
list_ptr first, second;
first =
(list_ptr)malloc(sizeof(list_node));
second =
(list_ptr)malloc(sizeof(list_node));
second->link=NULL;
second->data=20;
first->data=10;
first->link=second;
return first;
}
Networking Laboratory Chap. 4-10
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Singly Linked Lists

Ex 4.3 [list insertion]
ptr
10
20
node
NULL
50
temp
determine if we have used all
available memory: IS_FULL
#define IS_FULL(ptr) (!(ptr))
Function call: insert(&ptr, node);
Networking Laboratory Chap. 4-11
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists
void insert (list_ptr *pptr,list_ptr node) {
list_ptr temp;
temp=(list_ptr)malloc(sizeof(list_node));
if(IS_FULL(temp)) {
fprintf(stderr,”The momory is full\n”);
exit(1);
}
temp->data=50;
if (*pptr) {
temp->link = node->link;
node->link = temp;
}
else {
temp->link = NULL; *pptr = temp;
}
}
Networking Laboratory Chap. 4-12
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists

Ex 4.4 [list deletion]
- ptr: point to the start of list
- node: point to the node to be deleted
- trail: point to the node that precedes node to
be deleted
delete(&ptr,NULL,ptr);
delete(&ptr,ptr,ptr->link);
ptr node
10
trail = NULL
50
ptr
20
NULL
50
(a) before deletion
ptr trail
10
(a) before deletion
NULL
(b) after deletion
node
50
20
ptr
20
NULL
10
20
NULL
(b) after deletion
Networking Laboratory Chap. 4-13
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Singly Linked Lists
void delete(list_ptr *pptr, list_ptr trail,
list_ptr node) {
if (trail) trail->link = node->link;
else *pptr = (*pptr)->link;
free(node);
}
delete(&ptr,NULL,ptr); delete(&ptr,ptr,ptr->link);

Ex 4.5 [printing out a list]
void print_list(list_ptr ptr) {
printf(“The list contains: “);
for(; ptr; ptr = ptr->link)
printf(“%4d”, ptr->data);
printf(“\n”);
}
Networking Laboratory Chap. 4-14
Data Structures in C
top
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
element link
······
front
(a) linked stack
NULL
rear
element link
······
NULL
(b) linked queue
#define MAX_STACKS 10 /* n=MAX_STACKS=10 */
typedef struct {
int key; /* other fields here */
} element;
typedef struct stack *stack_ptr;
typedef struct stack {
element item; stack_ptr link;
};
stack_ptr top[MAX_STACKS];
Networking Laboratory Chap. 4-15
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
top[0]
element link
key
top[MAX_STACKS-1]
······
NULL
······
NULL
·
·
·
initial condition for n stacks
top[i] = NULL, 0  i < MAX_STACKS
boundary conditions
top[i]==NULL iff the ith stack is empty
IS_FULL(temp) iff the memory is full
Networking Laboratory Chap. 4-16
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
add to a linked stack
void push(stack_ptr *ptop, element item) {
stack_ptr temp =
(stack_ptr)malloc(sizeof (stack));
if(IS_FULL(temp)) {
fprintf(stderr,”The memory is full\n”);
exit(1);
}
temp->item=item;
temp->link=*ptop;
*ptop = temp;
}
#define IS_FULL(ptr) (!(ptr))
add(&top[stack_no], item);
Networking Laboratory Chap. 4-17
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
delete from a linked stack
element pop(stack_ptr *ptop) {
stack_ptr temp = *ptop;
element item;
if(IS_EMPTY(temp)) {
fprintf(stderr,”The stack is empty\n”);
exit(1);
}
item=temp->item;
*ptop=temp->link;
free(temp);
return item;
}
#define IS_EMPTY(ptr) (!(ptr))
item=delete(&top[stack_no]);
Networking Laboratory Chap. 4-18
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
front
rear
element link
······
NULL
(b) linked queue
#define MAX_QUEUES 10 /* m=MAX_QUEUES=10 */
typedef struct queue *queue_ptr;
typedef struct queue {
element item;
queue_ptr link;
};
queue_ptr front[MAX_QUEUES],rear[MAX_QUEUES];
Networking Laboratory Chap. 4-19
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Dynamically Linked
Stacks And Queues
front[0]
rear[0]
element link
key
front[MAX_QUEUES-1]
······
·
·
·
NULL
rear[MAX_QUEUES-1]
······
NULL
initial conditon for n queues
front[i]=NULL, 0  i < MAX_QUEUES
boundary conditions
front[i]==NULL iff the ith queue is empty
IS_FULL(temp) iff the memory is full
Networking Laboratory Chap. 4-20
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
add to the rear of a linked queue
void addq(queue_ptr *pfront,
queue_ptr *prear, element item) {
queue_ptr temp =
(queue_ptr)malloc(sizeof(queue));
if(IS_FULL(temp)) {
fprintf(stderr,”The memory is full\n”);
exit(1);
}
temp->item=item;
temp->link=NULL;
if (*pfront)
(*prear)->link=temp;
else
*pfront = temp;
*prear = temp;
}
addq(&front,&rear,item);
Networking Laboratory Chap. 4-21
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Dynamically Linked
Stacks And Queues
delete from the front of a linked queue
element deleteq(queue_ptr *pfront) {
queue_ptr temp=*pfront;
element item;
if (IS_EMPTY(*pfront)) {
fprintf(stderr,”The queue is empty\n”);
exit(1);
}
item=temp->item;
*pfront=temp->link;
free(temp);
return item;
}
item=deleteq(&front);
comparison: array vs. linked list
Networking Laboratory Chap. 4-22
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials

representing polynomials as singly linked lists
em-1
A(x) = am-1x
e0
+ ··· + a0x
typedef struct poly_node *poly_ptr;
typedef struct poly_node {
int coef; int expon; poly_ptr link;
};
poly_ptr a,b,d;
poly_node
14
a = 3x
a
3
14
2
8
b = 8x
14
-3
10
expon
link
8
+ 2x + 1
1
14
b
8
coef
0
NULL
10
+ 10x
6
NULL
- 3x
10
6
Networking Laboratory Chap. 4-23
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
adding polynomials
3
14
2
8
1
0
NULL
-3
10
10
6
NULL
a
8
14
b
11
14 NULL
d rear
(a) a->expon == b->expon
Networking Laboratory Chap. 4-24
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
3
14
2
8
1
0
NULL
10
6
NULL
a
8
14
-3
10
b
11
14
d
-3
10 NULL
rear
(b) a->expon < b->expon
Networking Laboratory Chap. 4-25
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
3
14
2
8
1
0
NULL
10
6
NULL
a
8
14
-3
10
b
11
14
-3
10
d
2
8
NULL
rear
(c) a->expon > b->expon
Networking Laboratory Chap. 4-26
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
3
14
2
8
1
0
NULL
a
8
14
-3
10
10
6
NULL
b
11
14
-3
10
2
8
d
10
6
NULL
rear
(d) a->expon < b->expon
Networking Laboratory Chap. 4-27
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
3
14
2
8
1
0
NULL
a
8
14
-3
10
10
6
NULL
b
11
14
-3
10
6
1
0
2
8
d
10
NULL
rear
(e) b == NULL;
Networking Laboratory Chap. 4-28
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
poly_ptr padd(poly_ptr a,poly_ptr b) {
poly_ptr front,rear,temp;
int sum;
rear=(poly_ptr)malloc(sizeof(poly_node));
if(IS_FULL(rear)) {
fprintf(stderr,”The memory is full\n”);
exit(1);}
front = rear;
while(a && b)
switch(COMPARE(a->expon,b->expon)) {
case -1: /* a->expon < b->expon */
attach(b->coef,b->expon,&rear);
b = b->link;
break;
case 0: /* a->expon = b->expon */
sum = a->coef + b->coef;
if(sum) attach(sum,a->expon,&rear);
a = a->link; b = b->link; break;
case 1: /* a->expon > b->expon */
attach(a->coef,a->expon,&rear);
a = a->link;
}
Networking Laboratory Chap. 4-29
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
poly_ptr padd(poly_ptr a,poly_ptr b) {
·
·
·
(continued from the previous slide)
for(; a; a=a->link)
attach(a->coef,a->expon,&rear);
for(; b; b=b->link)
attach(b->coef,b->expon,&rear);
rear->link = NULL;
temp=front; front=front->link; free(temp);
return front;
}
Networking Laboratory Chap. 4-30
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
function attach() to create a new node
and append it to the end of d
void attach(float coe, int exp, poly_ptr *pptr)
{
poly_ptr temp;
temp=(poly_ptr)malloc(sizeof(poly_node));
if(IS_FULL(temp)) {
fprintf(stderr,”The memory is full\n”);
exit(1);
}
temp->coef = coe;
temp->expon = exp;
(*pptr)->link = temp;
*pptr=temp;
}
Networking Laboratory Chap. 4-31
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
analysis of padd where
m, n : number of terms in each
polynomial
- coefficient additions:
O(min{m, n})
- exponent comparisons:
O(m + n)
- creation of new nodes for d
O(m + n)
time complexity:
O(m + n)
Networking Laboratory Chap. 4-32
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
erasing polynomials
void erase(poly_ptr *pptr) {
poly_ptr temp;
while (*pptr) {
temp = *pptr;
*pptr = (*pptr)->link;
free(temp);
}
}
useful to reclaim the nodes that are
being used to represent partial
result such as temp(x)
Networking Laboratory Chap. 4-33
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Polynomials
allocating/deallocating nodes
how to preserve free node
- initially link together
into a list in a storage
- avail: variable of type
points to the first node
nodes
in a storage pool?
all free nodes
pool
poly_ptr that
in list of free
storage pool
1
2
avail
n
······
NULL
initial available space list
Networking Laboratory Chap. 4-34
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
Allocating nodes
poly_ptr get_node(void) {
poly_ptr node;
if (avail) {
node = avail; avail = avail->link;
}
else {
node =
(poly_ptr)malloc(sizeof(poly_node));
if (IS_FULL(node)) {
fprintf(stderr,”The memory is full\n”);
exit(1);
}
}
return node;
}
Networking Laboratory Chap. 4-35
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
Deallocating nodes
void ret_node(poly_ptr ptr) {
ptr->link = avail;
avail = ptr;
}
Networking Laboratory Chap. 4-36
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
void erase(poly_ptr *pptr) {
poly_ptr temp;
while (*pptr) {
temp = *pptr;
*pptr = (*pptr)->link;
ret_node(temp);
}
}
- traverse to the last node in the list:
O(n) where n: number of terms
- how to erase polynomial efficiently?
how to return n used nodes to storage
pool?
Networking Laboratory Chap. 4-37
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
representing polynomials as
circularly linked list
to free all the nodes of a
polynomials more efficiently
- modify list structure
the link of the last node points to
the first node in the list
- called circular list ( chain)
ptr
Networking Laboratory Chap. 4-38
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
maintain our own list (as a chain)
of nodes that has been freed
- obtain effective erase algorithm
void cerase(poly_ptr *pptr) {
if (*pptr) {
temp = (*pptr)->link;
(*pptr)->link = avail;
avail
= temp;
*pptr = NULL;
}
}
independent of the number of nodes
in a list: O(1)
Networking Laboratory Chap. 4-39
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Polynomials
circular list with head nodes
- handle zero polynomials in the same
way as nonzero polynomials
ptr
-
-
(empty list)
head node
ptr
-
-
head node
Networking Laboratory Chap. 4-40
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
Inverting (or reversing) a chain
“in place” by using three pointers
- lead, middle, trail
typedef struct list_node *list_ptr;
typedef struct list_node {
char data; list_ptr link; };
list_ptr invert(list_ptr lead) {
list_ptr middle, trail;
middle = NULL;
while (lead) {
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail;
}
return middle;
}
time: O(length of the list)
Networking Laboratory Chap. 4-41
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
middle
lead
NULL
NULL
trail
middle lead
NULL
trail
middle
NULL
lead
Networking Laboratory Chap. 4-42
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
NULL
trail
NULL
middle
lead
NULL
trail
NULL
middle
lead
NULL
NULL
trail
middle
lead
Networking Laboratory Chap. 4-43
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
concatenates two chains
- produce a new list that contains ptr1
followed by ptr2
list_ptr concat(list_ptr ptr1,list_ptr ptr2) {
list_ptr temp;
if (IS_EMPTY(ptr1)) return ptr2;
else {
if (!IS_EMPTY(ptr2)) {
for (temp=ptr1; temp->link; temp=temp>link)
;
temp->link = ptr2;
}
return ptr1;
}
}
Networking Laboratory Chap. 4-44
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
finding the length of a list(chain)
int length(list_ptr ptr) {
int count = 0;
while (ptr) {
count++;
ptr = ptr->link;
}
return count;
}
insert a new node at the front or at the
rear of the chain
ptr
x1
x2
x3 NULL
- front-insert: O(1),
- rear-insert: O(n)
Networking Laboratory Chap. 4-45
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for Chains
Insert a new node at the front of a
list(chain)
void insert_front(list_ptr *pptr, list_ptr node) {
if (IS_EMPTY(*pptr)) {
*pptr = node;
node->link = NULL;
}
else {
node->link = *pptr;
*pptr = node;
}
}
Networking Laboratory Chap. 4-46
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for
Circularly Linked Lists
(singly) circular linked lists
ptr
x1
x2
x3
insert a new node at the front or
at the rear
- move down the entire length of ptr
to insert at both front and rear:
insert-front : O(n)
insert-rear : O(n)
Networking Laboratory Chap. 4-47
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for
Circularly Linked Lists
improve this better:
make ptr points to the last node
x1
x2
x3
ptr
insert a new node at the front or at
the rear
front-insert : O(1)
rear-insert : O(1)
Networking Laboratory Chap. 4-48
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for
Circularly Linked Lists
Insert a new node at the front of a
circular list
void insert_front(list_ptr *pptr, list_ptr
node) {
if (IS_EMPTY(*pptr)) {
*pptr = node;
node->link = node;
}
else {
node->link = (*pptr)->link;
(*pptr)->link = node;
*pptr = node; /* for rear-insert */
}
}
Networking Laboratory Chap. 4-49
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Operations for
Circularly Linked Lists
finding the length of a circular list
int length(list_ptr ptr) {
list_ptr temp;
int count = 0;
if (ptr) {
temp = ptr;
do {
count++;
temp = temp->link;
} while (temp != ptr);
}
return count;
}
Networking Laboratory Chap. 4-50
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
problems of singly linked lists
- move to only one way direction
- hard to find the previous node
- hard to delete the arbitrary node
doubly linked circular lists
- doubly lists + circular lists
- allow two links
- two way direction
Networking Laboratory Chap. 4-51
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
typedef struct node *node_ptr;
typedef struct node {
node_ptr llink;
element item;
node_ptr rlink;
};
suppose that ptr points to any node
in a doubly linked list
ptr = ptr->llink->rlink = ptr->rlink->llink
Networking Laboratory Chap. 4-52
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
introduce dummy node, called, head
- to represent empty list
- make easy to implement operations
- contains no information in item
field
ptr
empty doubly linked circular list
with head node
Networking Laboratory Chap. 4-53
Copyright(c) 2000, Sungkyunkwan University
Data Structures in C
Doubly linked lists
llink
item
rlink
head node
doubly linked circular list with
head node
Networking Laboratory Chap. 4-54
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
insertion into a doubly linked
circular list
void dinsert(node_ptr node,node_ptr newnode)
{
/* insert newnode to the right of node */
newnode->llink = node;
newnode->rlink = node->rlink;
node->rlink->llink = newnode;
node->rlink = newnode;
}
time: O(1)
Networking Laboratory Chap. 4-55
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
node
node
newnode
insertion into an empty doubly
linked circular list
Networking Laboratory Chap. 4-56
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
deletion from a doubly linked
circular list
void ddelete(node_ptr node,node_ptr deleted)
{
/* delete from the doubly linked list */
if (node == deleted)
printf(“Deletion of head node ”
“not permitted.\n”);
else {
deleted->llink->rlink = deleted->rlink;
deleted->rlink->llink = deleted->llink;
free(deleted);
}
}
time complexity : O(1)
Networking Laboratory Chap. 4-57
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
node
node
deleted
deletion in a doubly linked list
with a single node
Networking Laboratory Chap. 4-58
Data Structures in C
Copyright(c) 2000, Sungkyunkwan University
Doubly linked lists
doubly linked circular list
- don’t have to traverse a list :
O(1)
- insert(delete) front/middle/rear
is all the same
Networking Laboratory Chap. 4-59