📄 tut2.html
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Tutorial Problems 2</TITLE>
<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types ">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>
<TR><TD><FONT FACE=helvetica SIZE=+2><B>Tutorial Problems: Part 2</B></FONT>
</TD></TR>
</TABLE>
<H3>Tutorial 2</H3>
<H3><LI>Asymptotic behaviour</H3>
<OL TYPE="a">
<H4><LI>Threshhold values</H4>
<P>
For what values of <B><I>n</I></B> is
<CENTER>
4 x 10<SUP>6</SUP> <B><I>n</I><SUP>2</SUP></B> > 10 x 2<SUP><B><I>n</I></B></SUP> ?
</CENTER>
<H4><LI> Algorithm comparison</H4>
<P>
Algorithm <B>A</B> requires 200 machine cycles for each iteration and
requires <B><I>n</I>log<I>n</I></B> iterations to solve a problem of size
<B><I>n</I></B>.
<P>
A simpler algorithm, <B>B</B>, requires 25 machine cycles for each iteration and
requires <B><I>n<SUP>2</SUP></I></B> iterations to solve a problem of size
<B><I>n</I></B>.
<P>
Under what conditions will you prefer algorithm <B>A</B> over algorithm <B>B</B>?
</OL>
<HR>
<H3>Tutorial 3</H3>
<LI><H3>Simple ADT Design</H3>
A <B><FONT COLOR="#fa0000">double-ended queue</FONT></B> or
<B><FONT COLOR="#fa0000">deque</FONT></B>
is one that has
<B>both</B> LIFO and FIFO behaviour,
<I>ie</I> you can add an item to the head or the tail of a list
and extract an item from the head or the tail.
<P>
Taking the following specification for the Collection class,
modify it to handle a <B>deque</B>.
Note:
<UL><LI>There are quite a few ways that a software engineer could do this:
see how many you can devise!
<LI>A software engineer would probably try to ensure that code using the
original specification continued to function correctly.
</UL>
<P>
Similarly, modify the implementation to handle a <B>deque</B>.
<PRE>/* Specification for Collection */
typedef struct t_Collection *Collection;
Collection ConsCollection( int max_items, int item_size );
/* Construct a new Collection
Pre-condition: max_items > 0
Post-condition: returns a pointer to an empty Collection
*/
void AddToCollection( Collection c, void *item );
/* Add an item to a Collection
Pre-condition: (c is a Collection created by a call to
ConsCollection) &&
(existing item count < max_items) &&
(item != NULL)
Post-condition: item has been added to c
*/
void DeleteFromCollection( Collection c, void *item );
/* Delete an item from a Collection
Pre-condition: (c is a Collection created by a call to
ConsCollection) &&
(existing item count >= 1) &&
(item != NULL)
Post-condition: item has been deleted from c
*/
void *FindInCollection( Collection c, void *key );
/* Find an item in a Collection
Pre-condition: c is a Collection created by a call to
ConsCollection
key != NULL
Post-condition: returns an item identified by key if one
exists, otherwise returns NULL
*/
<HR>
/* Linked list implementation of a collection */
#include <stdlib.h> /* calloc */
#include <stdio.h> /* NULL */
#include <assert.h> /* Needed for assertions */
#include "collection.h" /* import the specification */
extern void *ItemKey( void * );
struct t_node {
void *item;
struct t_node *next;
} node;
struct t_collection {
int size; /* Needed by FindInCollection */
struct t_node *node;
};
collection ConsCollection(int max_items, int item_size )
/* Construct a new collection
Pre-condition: (max_items > 0) && (item_size > 0)
Post-condition: returns a pointer to an empty
collection
*/
{
collection c;
/* Although redundant, this assertion should be
retained as it tests compliance with the formal
specification */
assert( max_items > 0 );
assert( item_size > 0 );
c = (collection)calloc( 1, sizeof(struct t_collection) );
c->node = (struct t_node *)0;
c->size = item_size;
return c;
}
void AddToCollection( collection c, void *item )
/* Add an item to a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) &&
(existing item count < max_items) &&
(item != NULL)
Post-condition: item has been added to c
*/
{
struct t_node *new;
assert( c != NULL );
assert( item != NULL );
/* Allocate space for a node for the new item */
new = (struct t_node *)malloc(sizeof(struct t_node));
/* Attach the item to the node */
new->item = item;
/* Make the existing list `hang' from this one */
new->next = c->node;
/* The new item is the new head of the list */
c->node = new;
assert( FindInCollection( c, ItemKey( item ) ) != NULL );
}
void DeleteFromCollection( collection c, void *item )
/* Delete an item from a collection
Pre-condition: (c is a collection created by a call to
ConsCollection) &&
(existing item count >= 1) &&
(item != NULL)
Post-condition: item has been deleted from c
*/
{
struct t_node *node, *prev;
assert( c != NULL );
/* The requirement that the collection has at least
one item is expressed a little differently */
assert( c->node != NULL );
assert( item != NULL);
/* Select node at head of list */
prev = node = c->node;
/* Loop until we've reached the end of the list */
while( node != NULL )
{
if ( item == node->item )
{
/* Found the item to be deleted,
re-link the list around it */
if( node == c->node )
/* We're deleting the head */
c->node = node->next;
else
prev->next = node->next;
/* Free the node */
free( node );
break;
}
prev = node;
node = node->next;
}
}
</PRE>
<HR>
</OL>
<P>
<TABLE WIDTH="100%" BGCOLOR="#00c0f0">
<TR><TD><H3>Key terms</H3></TD></TR></TABLE>
<DL>
<DT><FONT COLOR="#fa0000"><B>deque</B></FONT>
<DD>A <B>double-ended queue</B> - one to which items can be added at both the
head and the tail and one from which items can be extracted from the head or
the tail.
</DL>
<P>
<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Continue on to <A HREF="tut3.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Tutorials/tut3.html">Tutorials: Part 3</A></TD>
<TD>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
© <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -