3
\$\begingroup\$

Here is a simple program which takes string from user input and creates linked list from it. Each element of list represents a single character from string. Words in inputted string can be delimited by one or more tabs or spaces. The main goal is to modify list by deleting words that have different first letters then the first word in string also all duplicate delimiters and delimiters on the beggining and end of the string should be removed too.

#include <iostream>
#include <string>

using namespace std;

//Structure for List element
typedef struct Node {
    char data; //Character in string
    Node* next; //Next node in list
    Node(char data, Node* next) : 
        data(data), next(next)
    {}
} Node;

//Class for linked list
class LinkedList
{
public:
    Node* head; //Head of list

    LinkedList() : head(nullptr) 
    {}
    ~LinkedList() 
    {
        Node* tmp;
        for (; head; head = tmp)
        {
            tmp = head->next;
            delete head;
        }
    }
    //Append element to list
    void Append(char item)
    {
        if (head == nullptr)
        {
            head = new Node(item, nullptr);
        }
        else
        {
            Node* last = head;
            while (last->next)
            {
                last = last->next;
            }
            last->next = new Node(item, nullptr);
        }

    }
};

LinkedList* CreateList(char *inputString);
void ModifyList(LinkedList* listToModify);
void DisplayList(LinkedList* listToDisplay);
Node* GetFirstNode(LinkedList* linkedList);
Node* SkipNodesWithDelimiters(Node* currentNode);
Node* SkipNodesWithChars(Node* currentNode);
void FilterListByFirstCharInWord(LinkedList* linkedList, char charToFilter);
Node* DeleteWordNodes(Node* firstCharNode, Node* lastActualNode);
void RevomeDuplicateDelimiters(LinkedList* sourceList);


int main(int argc, char* argv[])
{
    //Input buffer
    char inputString[300];

    cout << "Please enter your string:" << endl;
    cin.getline(inputString, sizeof(inputString));

    LinkedList* linkedList;

    if (inputString[0] != '\0')
    {
        linkedList = CreateList(inputString);
        cout << "Source list:" << endl;
        DisplayList(linkedList);
        ModifyList(linkedList);
        cout << "Modified list:" << endl;
        DisplayList(linkedList);
        delete linkedList;
    }


    return 0;
}

LinkedList* CreateList(char *inputString) 
{
    LinkedList* linkedList = new LinkedList;

    for (int i = 0; inputString[i] != '\0'; i++)
    {
        linkedList->Append(inputString[i]);
    }

    return linkedList;
}

void ModifyList(LinkedList* listToModify)
{
    RevomeDuplicateDelimiters(listToModify);
    Node* firstNode = GetFirstNode(listToModify);
    FilterListByFirstCharInWord(listToModify, firstNode->data);
}

Node* GetFirstNode(LinkedList* linkedList)
{
    Node* currentNode = linkedList->head;
    while (currentNode->next)
    {
        if (currentNode->data != ' ' || currentNode->data != '\t')
            return currentNode;

        currentNode = currentNode->next;
    }
}

void FilterListByFirstCharInWord(LinkedList* linkedList, char charToFilter)
{
    Node* currentNode = linkedList->head;
    Node* lastNodeInWord = SkipNodesWithChars(currentNode);

    if (lastNodeInWord->next != NULL)
    {
        while (currentNode != NULL)
        {
            Node* nextWordFirstNode = SkipNodesWithDelimiters(lastNodeInWord);

            if (nextWordFirstNode->data != charToFilter)
            {
                currentNode = DeleteWordNodes(nextWordFirstNode, lastNodeInWord->next);
            }
            else
            {
                currentNode = SkipNodesWithChars(nextWordFirstNode);
                lastNodeInWord = currentNode;
            }

            if (!currentNode || !currentNode->next)
                break;
        }
    }
}

Node* SkipNodesWithDelimiters(Node* currentNode)
{
    Node* nextNode;
    while (currentNode->next)
    {
        nextNode = currentNode->next;
        if (nextNode->data == '\t' || nextNode->data == ' ')
        {
            currentNode = nextNode;
        }
        else
        {
            break;
        }
    }

    return nextNode;
}

Node* SkipNodesWithChars(Node* currentNode)
{   
    while (currentNode->next)
    {
        Node* nextNode = currentNode->next;
        if (nextNode->data != '\t' && nextNode->data != ' ')
        {
            currentNode = nextNode;
        }
        else
        {
            break;
        }
    }

    return currentNode;
}

Node* DeleteWordNodes(Node* firstCharNode, Node* lastActualNode)
{
    int deletedNodesCount = 0;
    Node* currentNode = firstCharNode;

    while (currentNode != NULL)
    {
        if (currentNode->data == '\t' || currentNode->data == ' ')
        {
            lastActualNode->next = currentNode->next;
            delete currentNode;

            currentNode = lastActualNode;
            break;
        }

        lastActualNode->next = currentNode->next;
        delete currentNode;
        deletedNodesCount++;

        currentNode = lastActualNode->next;
    }

    return currentNode;
}

void RevomeDuplicateDelimiters(LinkedList* sourceList)
{
    Node* currentNode = sourceList->head;
    Node* previousNode;
    Node* nextNode;

    //Trim delimeters in begging and end
    while (sourceList->head != NULL & (sourceList->head->data == ' ' || sourceList->head->data == '\t'))
    {
        sourceList->head = currentNode->next;
        delete currentNode;

        currentNode = sourceList->head;
    }

    while (currentNode != NULL)
    {
        if (currentNode->next != NULL)
        {

            if ((currentNode->data == ' ' || currentNode->data == '\t') &&
                (currentNode->next->data == '\t' || currentNode->next->data == ' '))
            {
                if (currentNode->data == '\t')
                    currentNode->data = ' ';

                nextNode = currentNode->next;
                currentNode->next = nextNode->next;
                delete nextNode;
                continue;
            }
        }
        else
        {
            if (currentNode->data == ' ' || currentNode->data == '\t')
            {
                delete currentNode;
                previousNode->next = nullptr;
                break;
            }
        }
        previousNode = currentNode;
        currentNode = currentNode->next;
    }
}

void DisplayList(LinkedList* listToDisplay)
{
    Node* currentNode = listToDisplay->head;

    cout << endl;

    while (currentNode != NULL)
    {
        cout << "List element: " << currentNode->data << "\n";
        currentNode = currentNode->next;
    }

    cout << endl;
}
\$\endgroup\$
1
\$\begingroup\$

This might be a good attempt for a beginner. I stopped reading after main(). There are just too many things that are wrong, for C++ programmer. I feel strong influence of higher level languages, but C++ drifts somewhere in between, making arguable tradeoffs. "Choosing right tool for the right job" is even more encouraged in C++, because it has so many ways to do one thing.

Here are some things that are wrong in my opinion:

  • Half baked LinkedList class. It has public members (spoiling encapsulation) and has only one Append() method. Other operations are free functions. That doesn't make sense. Also, I've never seen the naming convention used in C++ code. I believe it is more natural to C#.

  • #include <string> included, but never used. char[] used to read the string instead, which actually makes program less robust. It is possible to read into std::string, deal with delimiter, create std::istringstream from the read std::string and read the words from that.

  • Linked list for chars. In bigger programs that would be somehow endurable, but it incures around 800% overhead in memory, e.g. it increases the size of the Node by 9 times ... The Node could be private and preserve encapsulation if the class would provide good interface. It is possible to save memory by using a container which stores elements in a contiguous memory, which would incur small constant memory overhead compared to linear complexity memory overhead with big constant.

  • Passing most of objects by pointers, and yet no checks whether it is nullptr. References solve that problem.

There are other problems that are not so severe as listed above. I recommend picking up a good book about C++ programming (starting point) and slowly starting learning from complete scratch. Using standard library should be considered as well, because trying to write code for imaginary purpose rarely ends up well.

\$\endgroup\$
  • \$\begingroup\$ I mainly write C# so you are right about naming conventions. I've tried to solve this task while relying on C# experience. Thanks a lot for advises! \$\endgroup\$ – Anton Mar 13 '17 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.