CS240 Final Exam Review
Return the solutions to the following programs written by hand before
the final exam. We will post the solutions the day before the final
exam so you can compare your solutions. We strongly encourage you to
solve this review before looking at the solutions.
1. Write the following functions for a single linked list data
structure:
SLList.h
typedef struct SLListEntry {
char * name;
char * value;
struct SLListEntry * next;
} SLListEntry;
typedef struct SLList {
SLListEntry * head;
} SLList;
SLList.cpp
#include "SLList.h"
// Create a single-linked list
SLList * sllist_create() {
}
// Insert an element in the linked list. If name already exists
substitute value. Otherwise insert entry. Return 0 if name is not there.
int sllist_insert(SLLIST *sllist, char * name, char * value) {
}
// Remove entry in single linked list.
int sllist_remove(SLLIST *sllist, char * name) {
}
// Return last entry in pname, pvalue. Return 0 if list is empty or 1
otherwise.
int sllist_last(SLLIST *sllist, char ** pname, char **pvalue) {
}
// Print linked list in the format:
// 0: name=name0 value=value0
// 1: name=name1 value=cvalue1
...
void sllist_print(SLLIST sllist) {
}
// Reverse the list. Use the existing list and nodes. Do not allocate a
new SLLIST nor use an array.
void sllist_reverse(SLLIST * sllist) {
}
2. Implement the following functions for a resizable array.
RArray.h
typedef struct RArrayEntry {
char * value;
} RArrayEntry;
typedef struct RArray {
int nElements; // Number of elements in the array that are
in use
int maxElements; // Maximum number of elements in the array
RArrayEntry * array;
} RArray;
RArray.cpp
#include "RArray.h"
//Create a new resizable array. Make maxElements=10, that is the
initial max size of the array before resizing.
RArray * rarray_create( ) {
}
// Append a new value at the end of the resizable array
void rarray_append(RArray *rarray, char * value) {
}
// Insert a value in the middle of the array at index ith. Move the
elements beyond ith one position up if necessary
// and enlarge the array if necessary. Return 0 if ith is out of range
or 1 otherwise.
int rarray_insert_at(RArray * rarray, int ith, char * value) {
}
// Remove an element in the middle of the array at index ith. Return 0
if ith is out of range or 1 otherwise.
// Move the elements beyond ith one position down.
int rarray_remove_at(RArray * rarray, int ith) {
}
// Free the memory needed by the resizable array
void rarray_free(RArray * rarray) {
}
3. Sorting array using comparison function passed as parameter.
Write a sorting function that can sort any array that is passed as
argument using a comparison function passed as parameter.
// Comparison function. Returns 1 if a > b, -1 if a<b, 0 if a == b
typedef int (*COMP_FUNC)(void * a, void *b);
void sort_array(void * array, int num_elements, int element_size,
COMP_FUNC comp_func) {
}
int compInt(void* a, void * b) {
// Write int comparison function
}
int compStr(void* a, void * b) {
// Write string comparison function
}
int main(){
int a[] = {7,8,1,4,3,2}
int n=sizeof(a)/sizeof(int);
sort_array(array, n, sizeof(int),
compInt);
int i=0;
for(i=0;i<n;i++){
printf(%d \n, a[i]);
}
char strings[] = {pear, banana,
apple, strawberry}
n = sizeof(strings)/sizeof(char*);
sort_array(strings, n,
sizeof(char*), compStr);
for(i=0; i<n; i++) {
printf(%s\n, strings[i]);
}
}
4. Write the function int
countOnes(unsigned int value) that counts the number of 1s in
the parameter value.
Iportant: DO NOT USE "/", or '%", instead use bit operations such as
&, |, >>, << etc.
int countOnes(unsigned int
value) {
}
5. Write the following string operations using pointers. IMPORTANT:
DO NOT USE the array[i]
operator nor the equivalent *(array+i)
expression. Instead use pointers and pointer operations like *p,
p++, p = q, q < p etc.
int strlen(char * str) {
}
char * strcpy(char * dest, char * src) {
}
char * strcat(char * dest, char * src) {
}
char * strstr(char * hay, char * needle) {
}