📄 w1_1997.html

📁 Data Structure Ebook
💻 HTML
字号:
<html><head>
<title>Data Structures and Algorithms - Workshop 1</title>
</head>
<BODY BGCOLOR="#fffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<H2>Workshop 1 - 1997</H2>
<H3>Familiarisation</H3>
<OL>
<LI>Download and save into your directory from the download window:
<OL TYPE="a">
<LI><A HREF="collection.h" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/collection.h" TARGET="Download Window">collection.h</A>
<LI><A HREF="collection.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/collection.c" TARGET="Download Window">collection.c</A> and
<LI>the test program <A HREF="testcol.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/testcol.c" TARGET="Download Window">testcol.c</A>.
</OL>
<P>
<LI>Compile into an executable:
<P>
<CENTER><TT><FONT COLOR=green>gcc -o testcol testcol.c collection.c</FONT></TT>
</CENTER>
<P>
Note that you will need to use an 
<A HREF="ANSI_C.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ANSI_C.html">ANSI C compiler</A> as the
programs are written in ANSI C. 
On some Unix machines, <TT><FONT COLOR=green>cc</FONT></TT>
only accepts the older "K&R C".
<P>
<LI>Run the program and verify that it runs as expected.
Examine the test program listing to determine how it runs!
<P>
<LI>Now we want to find out how efficiently it runs:
<P>
<OL TYPE="i">
<LI>Modify the test program so that it inserts a large number, <i><B>n</B></i>, of
integers into the collection. <P>
You will need to determine <I><B>n</B></I> by experimentation:
it will need to be large enough so that each run measured in
the next section takes several seconds. A value of 10<SUP>5</SUP>
would probably be a good start!<P>
Make a small function to generate a set of unique integers -
the numbers from 1 to <I><B>n</B></I> will do fine for this exercise.<P>
By timing a run for suitably large <I><B>n</B></I>,
determine the average time to insert an integer into
the collection.
You will need to use the Unix functions<BR>
<UL>
<LI><A HREF="time.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/time.html" TARGET=timing>ftime</A> for the Suns<BR>
<LI><A HREF="clock.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/clock.html">clock</A> for the SG machines<BR>
</UL>
to time your programs.
Note that the two functions have a different idea of how
to tell you about the time.
Read the manual page carefully!
<BLOCKQUOTE>
You will need to time quite a few runs for this course,
so spend a little time to design a simple, efficient timing
routine!
</BLOCKQUOTE>
<LI>Determine the average time to search the collection for
a randomly generated integer -
again by finding the time to search for <I><B>n</B></I> 
randomly generated integers.
Use the random number generator, 
<A HREF="rand.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/rand.html"><TT><FONT COLOR=green>rand()</FONT></TT></A>,
to generate random integers.
<P>
<LI>Modify the program so that it prints out the
insertion and searching times for a range of values of
<I><B>n</B></I>.
Suitable values will produce run times between <EM>about</EM>1 and 20
seconds. About 10 values should enable you to determine the
characteristics of the time <i>vs</i> <I><B>n</B></I> curve.
</OL>
<P>
<LI>Now download a linked list version of the same program
<A HREF="collection_ll.c" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/source/collection_ll.c" TARGET="Download Window">collection_ll.c</A> and
use the same program to print out the 
time <i>vs</i> <I><B>n</B></I> values for this implementation.
(You may need to change the range of the values of <I><B>n</B></I>!)
</OL>

<P>
<A HREF="submit.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/submit.html">Submission Instructions</A>
</body>
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -