lab2

Valgrind: There is another requirement that applies to all labs starting lab 2. You will be heavily penalized if your program contains memory errors.  Memory errors include (among other things) failure to call free() on the memory you obtained through malloc(), accessing past array bounds, dereferencing uninitialized pointers, etc. You can use a debugging tool called "valgrind" to check your program:

    valgrind --leak-check=yes ./your_executable

It will tell you if your program has any memory error.  See "The Valgrind Quick Start Guide" at http://valgrind.org/docs/manual/quick-start.html for more info. You must include the output of the valgrind run for EACH PART in your README.txt.  In addition, TAs will run valgrind on your program when grading. You can include the valgrind output in your README.txt as follows.  If you’re in your part1 directory, for example, issue the following command:

    valgrind --leak-check=yes ./your_executable >> ../README.txt 2>&1

The command will append the valgrind output at the end of your README.txt.  Make sure you put ">>", not ">".  If you type ">", it will overwrite your README.txt. calloc() / memset() / bzero()

Do not use calloc(), memset(), or bzero() in this assignment. This policy also applies to all future assignments unless their use is explicitly allowed in the prompt or required to prepare a data structure prior to calling a library function.

Those functions are used to explicitly zero-out the content of an array. While this practice could be viewed as defensive programming in general, we do not want to use it in this class because it often hides memory errors instead of solving them. In this class, every byte must be allocated and initialized with purpose!

Part 1: Sorting an integer array

--------------------------------

Write a program that dynamically allocates integer arrays on the heap using malloc(). While it is possible to allocate arrays with variable lengths on the stack, arrays with variable lengths are usually allocated on the heap.  There is a limit on the stack size, and trying to allocate a large array may overflow the stack and crash your program. The size of the array (the number of integers, not the byte size) should be read from the user using scanf(). You may assume that the user will input a positive integer (i.e., don’t do error checking).  The elements of the array should be filled using random() function.  After filling the array with random numbers, your program should then make a copy of the array, and sort the new array in ascending order: that is, the first entry of the array should contain the smallest integer in the array, while the last entry should contain the largest integer in the array.  Then make a second copy of the original array, and sort it in descending order. Finally your program should print out all three arrays.

All three arrays should be separately allocated using malloc() library function. Don’t forget to call free() to deallocate the arrays. You will notice that random() function always returns the same sequence of integers.  It’s just a pseudo-random number generator that simulates randomness. You can "seed" the random number generator by calling srandom() function once in the beginning of your program.  Calling it with the return value of time(NULL) will ensure a different sequence of random numbers everytime the program is run. You should do that.

For sorting, you have two options. You can include an implementation of any sorting algorithm in your code. You are allowed to copy any sorting function from the Internet or textbooks. If you do, please cite the source in the comment. Or you can use qsort() function provided by the standard C library (just like they provide printf()).  Using the qsort() library function is simpler, but requires that you know how to use pointers to functions, which we have not covered yet.  Section 5.11 of K&R2 describes pointers to functions. Unfortunately, the section uses a sorting function named "qsort" to illustrate pointers to functions, but it takes a different set of parameters than the real qsort() of standard library.  The standard library version of qsort() is described on page 253, K&R2, or in the man page (type "man 3 qsort").

从第二次实验开始，所有实验都要求程序不能包含内存错误，否则将受到严重扣分。内存错误包括未释放通过动态内存分配获得的内存、越界访问数组、解引用未初始化的指针等。可以使用调试工具 Valgrind 检查程序是否存在内存错误。每个部分的 README.txt 文件中必须包含 Valgrind 的运行输出，助教在评分时也会使用 Valgrind 检查程序。注意在保存输出到 README.txt 文件时，使用追加模式，以避免覆盖已有内容。

在本次及后续作业中，除非明确允许，否则禁止使用用于清零数组内容的函数，如 calloc()、memset() 或 bzero()，因为这些函数可能掩盖内存错误。

第一部分：排序整数数组。编写一个程序，使用动态内存分配在堆上创建整数数组。由于栈的大小有限，通常在堆上分配可变长度数组，以避免栈溢出。数组的大小应通过用户输入读取，假设用户输入的是正整数。用伪随机数填充数组，然后复制数组并按升序排序。再复制一次原始数组，并按降序排序。最后，程序应输出所有三个数组。

所有三个数组都应分别分配，并在程序结束时释放内存。注意伪随机数生成器每次返回相同的数列，因此在程序开始时应对随机数生成器进行“播种”，以确保每次运行程序时生成不同的随机数序列。

对于排序，可以选择自行实现排序算法，或使用标准库中的排序函数。自行实现排序算法时，可以参考网络或教材中的实现，并在代码中注明来源。如果选择使用库函数，需要了解函数指针的用法。