Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP9024 23T3

Dr. Aditya Joshi

Week  3  Problem  Set
Dynamic Data Structure

1.(Memory)

Given the following definition:

int data[12] ={6， 5， 3， 2， 7， 4， 9， 1， 8};

and  assuming  that  &data[0]==  Ox10000,what  are  the  values  of  the  following  expressions?

data[3]

data[data[2]]

data+3

*data+3

*(data+3)

*(data+*(data+4))

2.(Pointers)

Consider the following piece of code:

typedef struct { int studentID; int age; char gender; float WAM; } PersonT; PersonT perl; PersonT per2; PersonT *ptr; ptr =&perl; perl.studentID = 3141592; ptr->gender ='M'; ptr =&per2; ptr->studentID = 2718281; ptr->gender ='F'; per1.age = 25; per2.age = 24; ptr =&perl; per2.WAM = 86.0; ptr->WAM = 72.625;

What are the values of the fields in the per1 and per2 record after execution of the above statements?

3.(Memory management)

a.Consider the following function:

/* Makes an array of 10 integers and returns a pointer to it */ #define SIZE 10 int *makeArrayOfInts () { int arr [SIZE] ; int i; for (i=0; i arr[i] = i; } return arr; }

Explain what is wrong with this function. Rewrite the function so that it correctly achieves the intended result using malloc().

b. Consider the following program:

#include #include #include void func(int *a) { a = malloc (sizeof (int) ) ; assert(a !- NULL) ; } int main (void) { int *p; func(p) ; *p=6; printf ("8d\n",*p) ; free(p) ; return 0; }

Explain what is wrong with this program.

4.(Dynamic    arrays)

Write  a  C-program  that

。 takes 1 command line argument, a positive integer n

。 creates    a    dynamic    array    ofn    unsigned    long    long    int numbers (8 bytes, only positive numbers)

。 uses the array to compute the n'th Fibonacci number.

For example,./fib 60 should result in 1548008755920.

Hint: The placeholder %llu (instead of %d) can be used to print an unsigned long long int. Recall that the Fibonacci  numbers  are  defined  as  Fib(1)=  1,  Fib(2)=  1  and  Fib(n)=  Fib(n-1)+Fib(n-2)  for  n≥3.

An  example  of the  program  executing  could  be

prompt$   ./ fib

1548008755920

If  the  commad  line  argument  is  missing,  then  the  output  to  stderr  should  be

prompt$ ./fib
Usage: . / fib number

prompt$ 9024 dryrun fib

5.(Common memory errors)

Memory errors are common in C programs, and can be difficult to reproduce and debug. You're given a file memerrors.c that contains 8 functions, f1 through f8, each of which contains a common memory error.

You're also given a file memerrors.txt that  contains a description for each of the  8  memory errors:

buffer overflow memory leak unchecked malloc double free dangling pointer uninitial ised read invalid free no memory allocated

a.The given program uses the functions strlen()  and  strcpy()  from  the  standard  C  library  string.h. Check the meaning of these functions by running the man (for: manual) command on a CSE machine

prompt$ man strlen

prompt$ man strcpy

b. Re-arrange the descriptions in memerrors.txt to match the error in each function. For example, thedescription matching f1 should appear on the first line, and the description matching f8 should appear on the last line. You should not modify the text at all, just the order in which each line of text appears, and the re-arranged file should only contain 8 lines of text.

c. Correct each of the 8 functions in memerrors.c. Fixing the code will require adding, modifying, moving, or removing one line of code from each of the functions. Once corrected, the code should compile without warnings, run without error, and not leak any memory.

Here's an example of compiling and running the corrected code:

prompt$ gce -Wall -Werror -std=c11 -00 -g -o memerrors memerrors.c

prompt$ ./memerrors

f1

f2

f3

f4

f5

f6

f7

f8

Here's an example of testing it for memory leaks:

6.(Dynamic linked lists)

Write a C-program called llbuild.c that builds a linked list of integers from user input. Your program should use the following functions:

。NodeT *makeNode(int d), NodeT *insertLL(NodeT *list, int d) and void freeLL(NodeT *list): taken from the

。 void showLL(Node T list): taken from the lecture but needs modification.

。 NodeT *appendLL(NodeT *list, int d): returns a pointer to the linked list obtained by appending a new element with data d at the end of list. Needs to be implemented.

The program:

。 starts with an empty linked list called all(say), initialised to NULL

。 prompts the user with the message "Enter a number:" to input an integer

if the number is even, i.e. divisible by 2, the number is added as a new linked list node at the beginning of all

if the number is odd, i.e. divisible by 2, the number is added as a new linked list node at the beginning of all

。 asks for more user input and repeats the cycle

。the cycle is terminated when the user enters any imput that cannot be interpreted as a number

。on termination, the program generates the message "Done. List is " followed by the contents of the linked list in the format shown below.

A sample interaction is:

prompt$. /llbuild

Enter         a         number: 12

Enter         a         number: 34

Enter         a         number: 65

Enter    a    number: quit

Done     List  is  34->12->65

Note that any non-numeric data finishes' the interaction. If the user provides no data, then no list should be output:

prompts		./llbuild
Enter Done.	a	number:	#

We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find a program named llbuild.c in the current directory. You can use dryrun as follows:

prompt$ 9024 dryrun llbuild

Note: Please ensure that your output follows exactly the format shown above.

7.(Advanced linked list processing)

Extend the C-program from the previous exercise to divide the linked list in two separate lists: The first list should contain every other number starting with the 2nd element in the original list, the second list should contain all the other numbers(i.e., the 1st, 3rd,.). If the original list has an odd number of elements, then the second list will contain one

more element than the first.

Note that:

your algorithm should be in-place'(so you are not permitted to create new list elements when you "divide" the list, nor use some other data structure such as an array).

An example of the program executing could be

prompt$ ./11divide Enter a number: 4 Enter a number: 421 Enter a number: 456732 Enter a number: 321 Enter a number: 86 Enter a number: 89342 Enter a number: 9 Enter a number: # Done. List is 89342->86->456732->4->421->321->9 . Even-numbered elements are: 86->4->321 odd-numbered elements are: 89342->456732->421- >9

To test your program you can execute the dryrun program that corresponds to this exercise. It expects to find a program named lldivide.c in the current directory. You can use dryrun as follows:

prompt$ 9024 dryrun lldivide

Note: Please ensure that your output follows exactly the format shown above.

8.Challenge Exercise

Write a C-program that takes 1 command line argument and prints all its prefixes in decreasing order of length.

。You are not permitted to use any library functions other than printf ().

。You are not permitted to use any array other than argv [].

An example of the program executing could be

prompt$. /prefixes Programming Programming Programmin Programmi Programm Program Progra Progr Prog Pro Pr P

Assessment

Submit your solutions to Exercise 5 using the following give command:

prompts$  give  cs9024  week3 memerrors. txt memerrors . C

· Make sure you spell the filenames correctly. You can submit multiple times. Only your last submission will be considered.

· Make sure to always submit all files you intend to submit for this problem set when you overwrite a previous submission.

· The deadline for submission is Tuesday, 3 October 5:00:00pm.

· Auto-marking will be run by the lecturer several days after the submission deadline.

Each submitted file is worth 1 mark. Total marks = 2. Auto-marking will be run by the lecturer several days after the submission deadline.

Hints:

● Programs will not be manually marked.
● It is important that you follow exactly the syntax shown above, otherwise auto-marking will result in 0 marks.
● Ensure that your program compiles on a CSE machine with the command line options as shown above. A program that does not compile will receive 0 marks.

Plagiarism

Group submissions will not be allowed. Your programs must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise (including submissions for similar assessments in previous years, if applicable) and serious penalties will be applied, including an entry on UNSW's plagiarism register.

· Do not copy ideas or code from others

· Do not use a publicly accessible repository or allow anyone to see your code

Please refer to the on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:

· Plagiarism and Academic Integrity

· UNSW Plagiarism Policy Statement

· UNSW Plagiarism Procedure

Reproducing, publishing, posting, distributing or translating this page is an infringement of copyright and will be referred to UNSW Conduct and Integrity for action.