1 A 1inked list librarv This is a refresher lab. The tasks here are setting up s
ID: 3752787 • Letter: 1
Question
1 A 1inked list librarv This is a refresher lab. The tasks here are setting up some of the future topics, but are mostly things you have seen before only have the functions specified. You can have a main and other functions in your testcases, but your library should be able to be separated out from any test code. This will be important for fu- ture assignments where the test code will be pro- vided by us. I'm trying to make sure that everyone is on the same page by the time the course really starts picking up speed. And it will pick up speed. Oh boy, will it ever... 4 Grading This lab will not be graded, though we will tell you if you have done your work correctly or not. 2 The task at hand If you are solid on your /C++, you are prob- Write a library that will facilitate easy operations on linked lists. ably set and can coast for the first week. You need the following functions. struct list* list cons(int data_item, struct list* tail) struct list* list make cell(int data item struct list* tail) int list car(struct list* Ist) . int list_get_data-item(struct list" 1st) struct list" list-get-next-cell(struct list" lst) * struct list* list-cdr(struct list* 1st) int list get nth item(struct list* Ist, int in- dex) void list_set nth item(struct list Ist, int in- dex, int new value) . int list-length(struct list* 1st) Cons, car, and cdr are just aliases of list_make_cell, list get_data_item and list get_next cell. Once you have written this library use only list get nth_item and list set nth_item to per- form a bubble sort on a list of 5000 items. Thern do it on a list of 10000 items, 20000 items and so on, until it becomes too slow to bear 3 The list cells Each cell is composed out of two parts 1. The data item stored within the cell. 2. The pointer which leads to the next cell, if anv In this case we are stuck storing only integers. We will correct that some day Your library should consider NULL to be a list of length 0. Taking a car or cdr of NULL is a crash. To create the very first link in the list you should cons an integer onto a NULL tail. You should not provide a main function in the files that define your library. Your job is to Page 2Explanation / Answer
here is your library : ---------------->>>>>>>>
listFunc.h : ----------->>>>>>>>>
#ifndef LIST_FUNC
#define LIST_FUNC
struct list{
int data;
struct list *next;
};
struct list* list_make_cell(int data_item,struct list* tail){
struct list* nn = (struct list*)malloc(sizeof(struct list));
nn->data = data_item;
nn->next = NULL;
if(tail != NULL)
tail->next = nn;
else
tail = nn;
return nn;
}
int list_get_data_item(struct list* lst){
return lst->data;
}
struct list* list_get_next_cell(struct list* lst){
return lst->next;
}
int list_get_nth_item(struct list* lst,int index){
int n = list_length(lst);
int i;
if(index < 0 || index >= n){
return -1;
}
for(i=0;i<index;i++){
lst = list_get_next_cell(lst);
}
return lst->data;
}
void list_set_nth_items(struct list* lst,int index,int new_value){
int n = list_length(lst);
int i;
if(index < 0 || index >= n){
return;
}
for(i=0;i<index;i++){
lst = list_get_next_cell(lst);
}
lst->data = new_value;
}
int list_length(struct list* lst){
int i=0;
while(lst != NULL){
lst = list_get_next_cell(lst);
i++;
}
return i;
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.