Introduction需要提交的文件为：IntList.c和timing.txt插入过程：首先遍历现有的链表，判断是否是已经排过序（小的在前，大的在后）如果是，则继续插入接下来判断是否是空链表，如果是，则插入第一个节点，并记录为新的首尾节点如果不是空链表，则判断要插入的数是否比最后一个大，如果大，则直接插入到链表尾，并记录新的尾节点如果不比最后一个大，则需要从第一个节点开始依次比较，如果遇到一个大于等于要插入的数的节点，则表示插入位置在该节点之前一个，这里需要判断是否是首节点，如果是的话需要更新链表的首节点关于运行时间数字越多，速度越慢在插入到头和尾的过程中不需要完全遍历整个链表，而是直接插入到对应的位置，所以插入速度要比乱序的要快在直接插入的情况下（正序，或者倒叙，对应直接插入到链表尾和链表头）由于根据题意，每次插入前需要判断链表是否有序，所以需要遍历一次链表已有元素，所以比直接用sort来排序要慢Requirement2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise1/8COMP2521 17s2Week 02 Lab ExerciseLinked Lists, PerformanceData Structures and AlgorithmsObjectivesto re­acquaint you with C progamming and ADTsto manipulate a linked­list data structureto learn about the COMP2521 programming styleto learn (or remind yourself) about Makefilesto learn about shell scripts to automate repetitive tasksto do some simple performance analysisAdminMarks 5=outstanding, 4=very good, 3=adequate, 2=sub­standard, 1=hopelessDemo in the Week02 Lab or in the Week03 LabSubmit give cs2521 lab02 IntList.c timing.txt or via WebCMSDeadline must be submitted by 11:59pm Sunday 06 AugustNote: you need to do something truly outstanding, above and beyond the “call of duty” to get 5 marks. Doing the exercise just asspecified will generally get you 4­4.5 marks.BackgroundAt the end of COMP1511, you dealt with linked lists. Over the break, you haven’t forgotten linked lists(have you?), but a bit of revision never hurts, especially when many of the data structures we’ll deal withlater are based on linked lists. So … on with this simple linked list exercise …Setting UpTo keep your files manageable, it’s worth doing each lab exercise in a separate directory (folder). I’dsuggest creating a subdirectory in your home directory called “cs2521”, and then creating a subdirectoryunder that called “labs”, and then subdirectories “week02”, “week03”, etc. Let’s assume that the directoryyou finally set up for this lab is Week02LabDir.Change into your Week02LabDir directory and run the following command:$ unzip /home/cs2521/web/17s2/labs/week02/lab.zipIf you’re working at home, download lab.zip by right­clicking on the above link and then run the abovecommand on your local machine.In the example interactions, we assume that you are in a Linux shell window, and the shell isgiving you a $ prompt. All the text that you type is in bold font and all the text that the shelltypes at you is in normal font.If you’ve done the above correctly, you should now find the following files in the directory:Makefile a set of dependencies used to control compilationIntList.h interface definition for the IntList ADTIntList.c implementation for the IntList ADTuseIntList.c main program for testing the IntList ADTrandList.c main program for generating random sequences of numbers2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise2/8timing.txt template for your results file; you need to add more rowsBefore you start using these programs, it’s worth looking at the code. Are there any constructs that youdon’t understand? Try to work them out with your lab partner, or ask your tutor.Once you’ve understood the programs, the next thing to do is to run the command:$ makeIt’s worth taking a look at the Makefile to see if you can work out what it’s doing. Don’t worry if youdon’t understand it all; we’ll be taking a longer look at make in later labs. Note: you will need to run maketo recompile the system each time you make changes to the source code file and are ready to test theprogram again.The make command will produce messages about compiling with gcc and will eventually leave twoexecutable files in your directory (along with some .o files).uselThis is the executable for the useIntList.c program. It reads a list of integers from standardinput, then attempts to make a sorted (ascending order) copy of the list, and then prints both theoriginal and the sorted lists. It doesn’t work at the moment because the function to produce thesorted list is incomplete.randlThis is the executable for the randList.c program. It writes, on its standard output, a list ofrandom numbers in the range 1..999999. It takes one command­line argument to indicate howmany numbers it should write, and another optional argument to give a seed for the randomnumber generator. Note that it does not attempt to eliminate any duplicate values produced; if yougenerate a large enough number of values, duplicates are inevitable.You can run the usel command by typing the command name, followed by return. It will then patientlywait for you to type some numbers, and will store them in a list, display the list, then call the function thatis supposed to sort the list, and then display the “sorted” list. Of course, this doesn’t currently work,because the list sorting function is incomplete. You can, however, fake it by typing the numbers in inorder, e.g.$ ./usel -v1 2 3 4Here you type control-D to finish your inputOriginal:1234Sorted:1234When usel eventually works properly, this is the kind of output you’ll expect to see … except that youwon’t be giving it sorted lists as input. To see the existing behaviour on an unsorted list, type a fewnumbers not sorted in ascending order, e.g.$ ./usel -v1 3 2Once again, you type control-D to finish your inputOriginal:132Sorted2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise3/8132usel: useIntList.c:20: main: Assertion IntListIsSorted(myOtherList) failed.AbortedIf you omit the -v command­line parameter, the the usel program only displays the final sorted list(which is not yet sorted, of course).$ ./usel1 3 2Once again, you type control-D to finish your input132usel: useIntList.c:20: main: AssertionIntListIsSorted(myOtherList)’ failed.AbortedNow it’s time to play with the list generator. If you execute the command:$ /.randl 10it should display a list of 10 random numbers. If you run it again, you’ll get a different list of randomnumbers. Enjoy generating small lists of random numbers until you are bored.If you then execute the command:$ ./randl 10 | ./uselthe randl command will generate 10 random numbers and give them to the usel command which willprint the list of numbers twice (separated by the word Sorted ) and then fail the assertion as above.If you’re not familiar with Unix/Linux conventions, the | is a “pipe” that connects twocommands, e.g. C 1 |C 2 . The standard output ( stdout ) of the command C 1 will be directlyconnected to the standard input ( stdin ) of the command C 2 , so that whatever C 1 writes,C 2 reads.You can adjust the number of numbers that randl generates via the command­line argument, e.g.$ ./randl 100 | lesswill produce 100 random numbers. If you want to change the range of numbers produced (e.g. to onlymake numbers in the range 1..10) edit the randList.c code and add extra command­line argumentsto set the range.If you supply only one command­line argument, randl will generate a completely random (well, pseudo­random) sequence each time you run it. If you want to generate a large sequence of pseudo­randomnumbers, and be able to generate the same sequence consistently, you can use the second command­line argument to specify a seed for the random number generator. If you give the same seed each timeyou run randl , you’ll get the same sequence each time. To see the difference between using and notusing the second command­line argument, try the following commands:$ ./randl 10$ ./randl 10$ ./randl 10$ ./randl 10 13$ ./randl 10 13$ ./randl 10 132017/8/3 COMP2521 17s2 - Week 02 Lab Exercise4/8The first three commands will generate different sequences. The second three commands all generatethe same sequence.While ./randl is useful for producing large amounts of data, you don’t need to use ./randl toproduce input to ./usel . An alternative is to use the echo command and enter the numbers yourself,e.g.$ echo 5 4 3 2 1 | ./uselAnother alternative, which will be more useful for testing, is to use the seq command, in combination withthe sort command, e.g.$ seq 10# gives 1 2 3 4 5 6 7 8 9 10$ seq 10 | sort -n# gives 1 2 3 4 5 6 7 8 9 10$ seq 10 | sort -nr# gives 10 9 8 7 6 5 4 3 2 1$ seq 10 | sort -R# gives 1..10 in a random orderThe -nr argument to the sort command tells it to treat the input as numbers and sort them in reverseorder. The -R argument to the sort command tells it to put the input in random order. You can find moredetails about sort via the command man sort .One thing to remember is that sort orders items lexically, not numerically, by default. The followingpipeline may not produce what you expect. Try it.$ seq 10 | sortTask 1The IntListInsertInorder() function is incomplete. In fact, it’s just a stub function that invokesthe IntListInsert() function, which inserts the number, but not in order. You should re­write theIntListInsertInorder() function so that it takes an IntList and an integer and inserts thevalue into the appropriate place in the list, so that the list always remains sorted (in ascending order). Thefunction should fail if the original list (before insertion) is not sorted. Don’t forget to handle the cases of (a)empty list, (b) smallest value, (c) largest value, (d) second­smallest value, (e) second­largest value, (f)value somewhere in the middle. Why were these kinds of values chosen? Discuss with your partner andpropose test cases that test these and any other cases that you can think of.Make a directory called tests , and place files containing your test cases in that directory with one testcase in eachC代写 Week 02 Lab Exercise帮做php编程作业、php实验作业代做 file. A useful name strategy is to call the test files 01 , 02 , etc. You could create test files invarious ways, e.g.$ mkdir tests$ seq 10 | sort -R > tests/01$ seq 10 | sort -nr > tests/02$ randl 10 11 > tests/03etc. etc. etc.In order to check that your program is producing the correct results, you could compare it to the output ofa known correct sorting program. The diff command can help here (see man diff for details). Forexample, you could put each test case in a file, then run both your usel program and the built­in sortcommand, save the results of each output in a file, and then compare the files using diff . If yourprogram is correct, there should be no difference. The following shows an example of how to do this:$ sort -n tests/01.expected # generate correct result$ ./usel tests/01.observed # generate your result$ diff tests/01.expected tests/01.observed # if correct, no output2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise5/8If you produce a decent number of tests (10­20), as you should, then testing them one by one using theabove is a bit tedious. You could simplify carrying out the testing by writing a small shell script. like:#!/bin/shfor t in 01 02 03 04 05 … and the rest of your test filesdoecho === Test $t ===sort -n tests/$t.expected./usel tests/$t.observeddiff tests/$t.expected tests/$t.observeddonerm tests/.expected tests/.observedIf you put the above in a file called e.g. run_tests , and then run the command:$ sh run_teststhe script. will run all your test cases and any that fail will either produce an assertion message or showyou the difference between your output and the expected output.You will have some confidence that your IntListInsertInorder() function is working properlywhen, for all test cases, the assertions in useIntList.c no longer fail.Task 2Once IntListInsertInorder() is working correctly, modify useIntList.c so that it behavesas a sorting program: it reads a list of numbers from its standard input, and writes a sorted version of thenumbers to its standard output. This is a simple change to the existing program, and can beaccomplished by commenting a couple of lines.Recompile and check that the new version of usel behaves correctly. Once you’re satisfied, run sometests to compare the time taken by usel with the time taken by the Unix sort command for the sametask.The first thing to do is to check that both commands are producing the same result (otherwise, it’s notuseful to compare them). Try the following commands:$ ./randl 1000 > nums$ ./usel out1$ sort -n out2$ diff out1 out2If the diff command gives no output, then the files have no difference (i.e. the observed output is hesame as the expected output). If you try the above a number of times with different sets of numbers eachtime and get the same result, then you can be more confident that both commands are producing thesame result. (However, you cannot be absolutely certain that they will always produce the same result forany input. Why not?)Note that you need to use the -n option to sort because the default sorting order is lexcial, not numeric.If you don’t use -n , then e.g. 111 is treated as being less than 12. (See man sort for details.)The next thing to do is to devise a set of test cases and collect some timing data. There is a commandcalled time that will produce the timing data for you. Use it as follows:$ ./randl 100000 > nums$ time ./usel out1$ time sort -n out2As before, check that both commands are producing the same result. This time, however, you will alsosee output that contains some timing information (note that the output format may vary depending on2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise6/8which shell you’re using):user time time spent executing the code of the commandsystem time time spent executing system operations, such as input/outputelapsed/real time wall­clock time between when the command starts and finishesThe elapsed/real time is affected by the load on the machine, and so is not reliable. The system timeshould be similar for both commands (same amount of input/output). The value that’s most useful is theuser time , which represents the time that the program spent doing computation. Note that the time willvary if you run the same command multiple times. This is because the timing uses sampling and maysample the program at different points during the different executions. Collect results from a number ofexecutions on the same output and take an average.You will need to use large numbers of values (large argument to randl ) to observe any appreciabledifference. Of course, if you use very large numbers of values, the nums file may become too large tostore in your directory. In this case, you could store nums under the /tmp directory:$ ./randl 10000 > /tmp/nums$ time ./usel /tmp/out1$ time sort -n /tmp/out2$ diff /tmp/out1 /tmp/out2It would also be worth taking your /tmp/nums file and modifying it to check the timings for sorted andreverse sorted inputs:$ sort -n /tmp/nums > alreadySortedWithDuplicates$ sort -nr /tmp/nums > reverseSortedWithDuplicatesAs well as lists produced by randl , it would be worth trying lists produced using the seq / sortcombinations mentioned above. These will be different to the lists produced by randl in that they won’thave any duplicate values. For example, you could generate data files like:$ seq 10000 > alreadySortedNoDuplicates$ seq 10000 | sort -nr > reverseSortedNoDuplicates$ seq 10000 | sort -R > randomOrderNoDuplicatesand use these in place of /tmp/nums to generate more timing data.Once the data files get big enough, and once you’ve checked that both programs are producing the sameoutput for a wide selection of cases, you can avoid generating and comparing large output files byrunning the timing commands as follows:$ time ./usel /dev/null$ time sort -n /dev/nullThe above commands do all of the computation that we want to measure, but send their very large outputto the Unix/Linux “data sink” ( /dev/null ), so it never takes up space on the file system.If you do write results to files, don’t forget to remove them after you’ve finished the lab.You should take note of the timing output and build a collection of test results for different sizes/types ofinput and determine roughly the point at which it becomes impractical to use usel as a sort program(rather than using the Unix sort command).You’ll find that the timing data for relatively small lists (e.g. up to 10000) doesn’t show much differencebetween usel and sort , and shows time pretty close to zero. Try using list sizes such as 5000, 10000,20000, 50000, 100000, and as high as you dare to go after that. Also, try varying the kinds of input thatyou supply. Consider the cases for the order of the input: random, already sorted, reverse sorted. Also,consider the proportion of duplicate values in the input, e.g. all distinct values, some duplicates. Note that./randl will most likely include duplicates as soon as you specify a relatively large list size.2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise7/8Put your results and some brief comments explaining the results, in a file called timing.txt . The fileshould contain a table of results, with major rows dealing with a particular size of data, and sub­rowsdealing with the order of the input. You should have three columns: one to indicate how many runs ofeach program were used to compute the average time­cost, one to give the average time­cost for useland the other to give the average time­cost for sort . The table should look something like the following:InputSizeInitialOrderHasDuplicatesNumberof runsAvg Timefor uselAvg Timefor sort5000 random no N T 1 sec T 2 sec5000 sorted no N T 1 sec T 2 sec5000 reverse no N T 1 sec T 2 sec5000 random yes N T 1 sec T 2 sec5000 sorted yes N T 1 sec T 2 sec5000 reverse yes N T 1 sec T 2 sec10000 random no N T 1 sec T 2 sec10000 sorted no N T 1 sec T 2 sec10000 reverse no N T 1 sec T 2 sec10000 random yes N T 1 sec T 2 sec10000 sorted yes N T 1 sec T 2 sec10000 reverse yes N T 1 sec T 2 secetc. etc.Note that, given the variation in timing output, it’s not worth considering more than two significant figuresin your averages.You should also write a short paragraph to explain any patterns that you notice in the timing results. Don’tjust re­state the timing result in words; try to explain why they happened.If you’re looking for a challenge, and know how to write scripts, write e.g. a Linux shell script. to automatethe testing for you, and maybe even produce the timing file for you.Another interesting challenge would be to plot graphs using the R system, available as the Linuxcommand R (a single upper­case letter). I’d suggest plotting a separate graph for each type (random,ascedning, descending) for a range of values (e.g. 5000, 10000, 20000, 50000, … as far as you can bebothered, given how long larger data files take to sort). Alternatively, produce your timing.txt as atab­separated file and load it into a spreadsheet, from where you could also produce graphs.If you’re feeling brave, try to find out how large input sort can deal with. However, you should try suchtesting on a machine where you are the sole user. Also, you shouldn’t try to store the data files; usecommands like:$ seq SomeVeryLargeNumber | time sort -n > /dev/null$ seq SomeVeryLargeNumber | sort -nr | time sort -n > /dev/null$ seq SomeVeryLargeNumber | sort -R | time sort -n > /dev/nullSubmission2017/8/3 COMP2521 17s2 - Week 02 Lab Exercise8/8You need to submit two files: IntList.c and timing.txt . You can submit these via the commandline using give or you can submit them from within WebCMS. After submitting them (either in this labclass or the next) show your tutor, who’ll give you feedback on your coding style, your timing results, andaward a mark.Have fun, jas转自：http://ass.3daixie.com/2019030627560478.html