LINKED LISTS For your linked lists, you must use the structs we have specified i
ID: 3600733 • Letter: L
Question
LINKED LISTS
For your linked lists, you must use the structs we have specified in ListyString.h without any
modifications. You must #include the header file from ListyString.c like so:
#include "ListyString.h"
The node struct you will use for your linked lists is defined in ListyString.h as follows:
typedef struct ListyNode
{
char data; // Each node holds a single character.
struct ListyNode *next; // Pointer to next node in linked list.
} ListyNode;
Additionally, there is a ListyString struct that you will use to store the head of each linked list string,
along with the length of that list:
typedef struct ListyString
{
struct ListyNode *head; // Pointer to head of string's linked list.
int length; // Length of this string / linked list.
} ListyString;
ListyString *createListyString(char *str);
Description: Convert str to a ListyString by first dynamically allocating a new ListyString
struct, and then converting str to a linked list string whose head node will be stored inside that
ListyString struct. Be sure to update the length member of your new ListyString, as well.
Special Considerations: str may contain any number of characters, and it may contain nonalphanumeric
characters. If str is NULL or an empty string (“”), simply return a new
ListyString whose head is initialized to NULL and whose length is initialized to zero.
Runtime Requirement: This should be an O(k) function, where k is the length of str.
Returns: A pointer to the new ListyString. Ideally, this function would return NULL if any calls
to malloc() failed, but I do not intend to test your code in an environment where malloc()
would fail, so you are not required to check whether malloc() returns NULL.
ListyString *destroyListyString(ListyString *listy);
Description: Free any dynamically allocated memory associated with the ListyString and
return NULL. Be sure to avoid segmentation faults in the event that listy or listy->head are
NULL.
Returns: NULL.
ListyString *cloneListyString(ListyString *listy);
Description: Using dynamic memory allocation, create and return a new copy of listy. Note
that you should create an entirely new copy of the linked list contained within listy. (That is,
you should not just set your new ListyString’s head pointer equal to listyhead.) The
exception here is that if listy->head is equal to NULL, you should indeed create a new
ListyStruct whose head member is initialized to NULL and whose length member is initialized
to zero. If listy is NULL, this function should simply return NULL.
Runtime Requirement: The runtime of this function should be no worse than O(n), where n is
the length of the ListyString.
Returns: A pointer to the new ListyString. If the listy pointer passed to this function is NULL,
simply return NULL.
void replaceChar(ListyString *listy, char key, char *str);
Description: This function takes a ListyString (listy) and replaces all instances of a certain
character (key) with the specified string (str). If str is NULL or the empty string (“”), this
function simply removes all instances of key from the linked list. If key does not occur
anywhere in the linked list, the list remains unchanged. If listy is NULL, or if listy->head is
NULL, simply return.
Important Note: Be sure to update the length member of the ListyString as appropriate.
Runtime Requirement: The runtime of this function should be no worse than O(n + km),
where n is the length of the ListyString, k is the number of times key occurs in the ListyString,
and m is the length of str.
Returns: Nothing. This is a void function.
Stuck on the functins, running into segmentation faults and output mismatches
Explanation / Answer
#include "ListyString.h"
ListyString *createListyString(char *str)
{
int i;
ListyString *pListyString;
ListyNode *pTempListyNode;
ListyNode *pLastListyNode;
pListyString = (ListyString *)malloc(sizeof(ListyString));
if (NULL == pListyString)
{
return NULL;
}
pListyString->length = 0;
pListyString->head = NULL;
if (NULL == str)
{
return pListyString;
}
pListyString->length = strlen(str);
i = 0;
pLastListyNode = NULL;
while (str[i] != '')
{
pTempListyNode = (ListyNode *)malloc(sizeof(ListyNode));
pTempListyNode->data = str[i];
pTempListyNode->next = NULL;
if (NULL == pListyString->head)
{
pLastListyNode = pListyString->head = pTempListyNode;
}
else
{
pLastListyNode->next = pTempListyNode;
pLastListyNode = pLastListyNode->next;
}
i++;
}
return pListyString;
}
ListyString *destroyListyString(ListyString *listy)
{
struct ListyNode* current;
struct ListyNode* next;
if (NULL == listy)
{
return NULL;
}
current = listy->head;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
free(listy);
return NULL;
}
ListyString *cloneListyString(ListyString *listy)
{
ListyNode *pTemp;
if (NULL == listy)
{
return NULL;
}
ListyString *pListyString;
ListyNode *pTempListyNode;
ListyNode *pLastListyNode;
pListyString = (ListyString *)malloc(sizeof(ListyString));
if (NULL == pListyString)
{
return NULL;
}
pListyString->length = listy->length;
pListyString->head = NULL;
pTemp = listy->head;
pLastListyNode = NULL;
while (pTemp != NULL)
{
pTempListyNode = (ListyNode *)malloc(sizeof(ListyNode));
pTempListyNode->data = pTemp->data;
pTempListyNode->next = NULL;
if (NULL == pListyString->head)
{
pLastListyNode = pListyString->head = pTempListyNode;
}
else
{
pLastListyNode->next = pTempListyNode;
pLastListyNode = pLastListyNode->next;
}
pTemp = pTemp->next;
}
return pListyString;
}
void replaceChar(ListyString *listy, char key, char *str)
{
int i = 0;
ListyNode *pPrevNode;
ListyNode *pCurrNode;
ListyNode *pTempNode;
ListyNode *pNewListyNode;
if (NULL == listy)
{
return;
}
pPrevNode = NULL;
pCurrNode = listy->head;
while (pCurrNode != NULL)
{
if (pCurrNode->data == key)
{
if (NULL == str || 0 == strlen(str))
{
//remove char from list.
pTempNode = pCurrNode;
if (NULL == pPrevNode)
{
pCurrNode = pCurrNode->next;
listy->head = pCurrNode;
}
else
{
pPrevNode->next = pCurrNode->next;
pCurrNode = pCurrNode->next;
}
free(pTempNode);
listy->length--;
}
else
{
pCurrNode->data = str[0];
i = 1;
while (str[i] != '')
{
pNewListyNode = (ListyNode *)malloc(sizeof(ListyNode));
pNewListyNode->data = str[i];
pNewListyNode->next = NULL;
pNewListyNode->next = pCurrNode->next;
pCurrNode->next = pNewListyNode;
pCurrNode = pCurrNode->next;
listy->length++;
i++;
}
pPrevNode = pCurrNode;
pCurrNode = pCurrNode->next;
}
}
else
{
pPrevNode = pCurrNode;
pCurrNode = pCurrNode->next;
}
}
}
int main()
{
ListyString *temp = createListyString("testz");
ListyString *temp1 = cloneListyString(temp);
destroyListyString(temp1);
replaceChar(temp, 't', "");
destroyListyString(temp);
return 0;
}
//Tested with above conditions in main.
//ListyString.h
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct ListyNode
{
char data; // Each node holds a single character.
struct ListyNode *next; // Pointer to next node in linked list.
} ListyNode;
typedef struct ListyString
{
struct ListyNode *head; // Pointer to head of string's linked list.
int length; // Length of this string / linked list.
} ListyString;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.