CS代考 4CCE1PHC – cscodehelp代写
4CCE1PHC
1 Introduction
Data Structures & Dynamic Memory Allocation
October 25, 2021
This lab introduces you to programming with data structures and dynamic memory management which are powerful and fundamental concepts in C programming.
At the end of the lab, you should be able to: • Implement data structures in C.
• Implement dynamic memory allocation in C to enable objects to be sized at runtime.
Before starting work you should read through this document and complete the preparatory tasks detailed
in §2.
2 Preparation
Materials
Make sure you have everything you need to complete this lab.
Ensure that you have the following software installed on your computer: (i) a terminal program (e.g., xterm or similar on Linux/Mac OS, cygwin on Windows), (ii) a text editor (e.g., gedit or similar on Linux/Mac OS, notepad++ on Windows), (iii) the GNU compiler collection (i.e., gcc).
Self-study
Read §3 below and read up on any new material (in textbooks and/or online) that you need to, to accomplish the tasks. Remember to make notes of where you get any information, so that you can quickly go there again if something does not work as expected.
Answer the following questions:
1. Assuming z1, z2 and z3 are complex numbers (i.e., z1 = a1 + ib1, etc, where i = expressions for the following in terms of their real and imaginary parts
√
−1), write down
Addition Multiplication
Absolute value
z3 =z1 +z2=(a1 +a2)+(b1 +b2)i
z3 = z1z2= (a1 + b1i)(a2 + b2i) = a1a2 − b1b2 + (a1b2 + a2b1)i (2)
z3 = |z1|= a21 + b21
(1)
(3) (4)
Deparment of Engineering King’s College London
2. Describe the operation of the malloc function.
malloc is used to allocate space in memory, and returns a pointer to that space.
3. How can you give back memory that you have dynamically allocated?
free takes a pointer to a previously allocated space and frees the memory used.
Dr Matthew Howard 1 © 2020
4CCE1PHC
3 Laboratory Work
3.1 Complex Numbers
C allows you to create data structures which enable you to better reflect the behaviour of certain objects in the real world. In this exercise you will write a small library to work with complex numbers (i.e., numbers with real and imaginary components). Follow these steps:
1. Create a new header file complex.h and implementation file complex.c. Define a C struct data type to represent complex numbers. The struct should contain a fields for holding the number’s real and imaginary parts. A sample header file is below:
Dr Matthew Howard © 2020
2 Deparment of Engineering King’s College London
1 #ifndef _COMPLEX_H
2 #define _COMPLEX_H
3 #include
4
5 typedef struct { /*
6 float real; /*
7
8 float imag; /* 9
Define the struct type */ This float contains the real part of the number */
This float contains the imaginary part of the number. */
10
11 } Complex; 12
13 #endif
Listing 1: Sample implementation of complex.h.
4CCE1PHC
2. Implement functions complex_add() and complex_multiply() in the library. The functions should take two complex numbers as arguments and use an appropriate return value to pass the result to the calling function. A sample implementation of these functions is:
1 #include “complex.h” /* Include the header file we created. */ 2
3 /* Function to add two complex numbers x and y */
4 Complex complex_add(const Complex x, const Complex y)
5{ 6
7
8
Complex z;
z.real = x.real + y.real;
z.imag = x.imag + y.imag;
return z;
/* /*
/*
/*
Declare variable to hold the result. */
Add the real parts of x and y and store in the real part of z. */
Add the imaginary parts of x and y, and store in the imaginary part ofz*/
Return the complex number z. */
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
}
Complex complex_multiply(const Complex x, const Complex y) {
Complex z; /* Declare variable to hold the result. */
z.real = x.real*y.real – x.imag*y.imag;
/* Compute the real partofz…*/
z.imag = x.real*y.imag + y.real*x.imag;
return z; }
/* … and the imaginary part. */
Listing 2: Sample implementation of complex.c.
3. Implement a function complex_abs() in the library. The function should take a complex number as an argument and use an appropriate return value to pass the result to the calling function. The below is a sample implementation of the function:
1
2
3 4{ 5
6
7 8}
/* Function to compute the absolute value of * complex number x. */
float complex_abs(const Complex x)
/* Use the equation from the preparation to compute the absolute value, and return as a float. */
return
sqrt(pow(x.real ,2)+pow(x.imag ,2));
Listing 3: Sample implementation of complex_abs().
3
Dr Matthew Howard © 2020
Deparment of Engineering King’s College London
4CCE1PHC
4. Test your library by writing a main() program which uses the functions to compute (i) z3 = z1 + z2, (ii) z6 = z4z5, and (iii) |z3| where z1 = 3+2i, z2 = −4+2i, z4 = 6, and z5 = −i. A sample test program is in Listing 4.
3.2 Dynamic Vectors
When writing programs it is sometimes difficult to know the size of an object in advance of running the program. The only way to handle this robustly is to dynamically allocate the memory as the program runs. In this part of the lab, you will define a data type and libary to handle vectors of variable size.
1. Create a new header file la.h. Define a C struct data type for vectors in your new library. The struct should contain a fields for holding the vector’s elements and its size.
A sample header file is below:
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16
#ifndef _LA_H #define _LA_H
#include
typedef struct { /* Define a vector data type. */
float * v; int size;
} vector;
#endif
/* Define a pointer to an array of floats. */
/* Field to specify the size (i.e., number of elements) of the vector. */
Listing 5: Sample implementation of la.h.
Dr Matthew Howard © 2020
4
Deparment of Engineering King’s College London
4CCE1PHC
1 #include
2 #include “complex.h” /* Include our library
3 for complex numbers. */
4 #define SUCCESS 0
5
6 int 7{
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 }
Complex z1; /* Declare z1 and */ z1.real = 3; /* assign its */ z1.imag = 2; /* component parts. */ printf(“z1␣=␣%f␣+␣%fi
”,z1.real,z1.imag);
Complex z2; /* Declare z2 and */ z2.real = -4;/* assign its */ z2.imag = 2; /* component parts. */ printf(“z2␣=␣%f␣+␣%fi
”,z2.real,z2.imag);
/* Declare z3 and use our function * to compute its value. */
Complex z3 = complex_add(z1,z2); printf(“z3␣=␣%f␣+␣%fi
”,z3.real,z3.imag);
Complex z4; /* Declare z4 and */
main(void)
z4.real = 6;/* assign its
z4.imag = 0;/* component parts. */
Complex z5; /* Declare z5 and */
z5.real = 0;/* assign its
z5.imag =-1;/* component parts. */
/* Declare z6 and use our function * to compute its value. */
Complex z6 = complex_multiply(z4,z5); printf(“z6␣=␣%f␣+␣%fi
”,z6.real,z6.imag);
/* Use our function to compute * the absolute value of z3. */
printf(“|z3|␣=␣%f
”,complex_abs(z3)); return SUCCESS;
Listing 4: Sample implementation of test_complex.c.
*/
*/
Dr Matthew Howard 5 © 2020
Deparment of Engineering King’s College London
4CCE1PHC
2. Implement functions vector_alloc() and vector_free() in the la.h library to dynamically allo- cate a vector and to free up the memory when it is no longer required. The functions (i) vector_alloc() should take the size of the vector as an argument and return a pointer to the vector and (ii) vector_free() should take a pointer to a vector as an argument and return nothing. A sample implementation of these functions is:
/* Function to allocate a new vector * given the size it should be. */
1
2
3 4{ 5
6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22
/* Declare pointer to vector and allocate space. */
vector * p_vector = (vector*) malloc (sizeof (vector)); /* Allocate space for the array that contains
* the vector elements. */
p_vector->v = (float*)malloc(size*sizeof(float)); p_vector->size = size; /* Set the vector size. */ return p_vector; /* Return pointer to vector. */
vector * vector_alloc(int size)
}
/* Function to free up space taken by * a vector when it’s not needed
* anymore. */
void vector_free(vector * v) {
free(v->v); /* Free the array. */ free(v); /* Free the vector. */ return ;
}
1
2
3 4{ 5
6
7
8 9}
v->v[i]=x; /* As v is a pointer, we need to use the -> notation to access the
array and set to x. */
return ;
Listing 7: Sample implementation of vector_set().
Listing 6: Sample implementation of vector_alloc() and vector_free().
3. Write a function vector_set() that takes a pointer to a vector, an int i and a float x as arguments and sets the ith element of the vector to the value of x. A sample implementation of the function is:
/* Function to set ith element of the vector * to x. */
void vector_set(vector * v,const int i,float x)
Dr Matthew Howard © 2020
6
Deparment of Engineering King’s College London
4CCE1PHC
q2
q1
Figure 1: Two link robot arm model.
4. Write a function vector_printf() that takes a pointer to a vector as an argument and prints it to stdout. A sample implementation of the function is:
5.
5
6 7{ 8
9
int i;
for (i=0; i< v->size; i++) /* Iterate through
the elements. */
printf(“%f␣”,v->v[i]); /* Access the element and print it. */
}
printf(“
”); return ;
}
Listing 8: Sample implementation of vector_set().
Test your library by writing a main() program which calls uses the three functions to (i) create, (ii) as- sign, (iii) display, and (iv) destroy the following three vectors a = (1, 2, 3)⊤, b = (6, 5, 4, 3, 2, 1)⊤, c = (−0.36, 0.45)⊤. A sample test program is given in Listing 9.
10 11 12 13
(r1, r2)⊤
1 /* Function to print out the contents of a vector. */ 2 void vector_printf(vector * v)
3{
4
Optional Additional Work
4
4.1 Matrices
Extend your library to define a matrix data structure and implement functions matrix_alloc(), matrix_free() and matrix_printf() to create, destroy and print matrices. Test your library by (i) creating, (ii) assigning,
(iii) displaying, and (iv) destroying the following matrix
1 −2 3 A= 4 5.5 6 .
4.2 Solving Inverse Kinematics
A common problem in robotic manipulation is that of figuring out how to move the robot’s arm in order to bring its hand to a desired location (for example, when picking up an object or pressing a button). This is called the inverse kinematics problem.
In the version of the problem we consider here, the robot starts at a configuration with the joints in positions q = (q1, q2)⊤, and we want it to move so that the end-effector (i.e., hand) goes to the position r∗ =(x,y)⊤.
Dr Matthew Howard 7 Deparment of Engineering © 2020 King’s College London
4CCE1PHC
1 #include
2 #include “la.h”
3 #define SUCCESS 0
4
5
6 int 7{
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 }
main(void)
vector * a = vector_alloc(3); /* Create 3-dimensional
vector_set(a,0,1); /* … set its
vector_set(a,1,2);
vector_set(a,2,3);
printf(“a␣=␣”);
vector_printf(a); /* … print it … */ vector_free(a); /* … and destroy it. */
vector * b = vector_alloc (6);
/* Create 6-dimensional vector b… */
vector_set(b,0,6); vector_set(b,1,5); vector_set(b,2,4); vector_set(b,3,3); vector_set(b,4,2); vector_set(b,5,1); printf(“b␣=␣”); vector_printf(b); vector_free(b);
/* … and destroy it. */
vector * c = vector_alloc (2); /*
Create 2-dimensional vector c… */
destroy it. */
vector_set(c,0,-0.36); vector_set(c,1, 0.45); printf(“c␣=␣”); vector_printf(c); vector_free(c);
/* … and
vector a… */ elements … */
return SUCCESS;
Listing 9: Sample implementation of test_la.c.
Dr Matthew Howard 8 © 2020
Deparment of Engineering King’s College London
4CCE1PHC
One way to solve this problem is to take an iterative approach where, starting from the initial configuration, the required position of the joints is successively updated according to the rule
qt+1 = qt + αJ⊤t (r∗ − rt) (5) where α is a small scaling factor (e.g., α = 0.01), rt is the position of the hand and Jt is the Jacobian
matrix at iteration step t.
For the robot arm in Fig. 1, the hand position can be computed as
and the Jacobian is
−sinq1 +sin(q1 +q2) −sinq1 J= cosq +cos(q +q) cosq
r=(cosq1 +cos(q1 +q2), sinq1 +sin(q1 +q2))⊤ (6)
1121
Implement a program to use (5)-(7) to compute how the robot’s joint angles should be set to move its hand to position r∗ = (1,1)⊤ starting from the configuration q = (0,π/3)⊤. Use and extend your la.h library to peform the scalar-vector, vector-vector and vector-matrix operations needed. Check that the q that your program computes is correct by substitution into (6).
Dr Matthew Howard 9 Deparment of Engineering © 2020 King’s College London
. (7)
