Lab 14: Linked List(s)

/*

LAB 14:  Linked Lists

In this lab you will expand upon the code listed below to create a program that can insert a char at any point in a linked list.

There are two lists being used in the code, although this only matters for the extra credit.

This particular function would be easier to do with an array, but you are NOT allowed to alter the node class nor can you use any kind of array.

Pretend your computer is somehow allergic to arrays.  You don't want to make your computer sneeze and/or turn into a dinosaur, do you? I don't.

Specifically, you are to finish the code for the "insertAtIndex" function.  You don't need to alter any other part of the code to get 2 points.

Originally both lists are empty, so there are 0 elements in each list, and it would be appropriate to insert at position 0. 

After a list has an element, we could insert at position 0 (which would be before the element) or position 1 (which would be after the element).

An attempt to insert at a position greater than the length of a list should result in the element being added to the end of the list, with a warning message.

Extra Credit:

Finish the function that inserts another list into the first given list at the indexPosition.

[struct node * combineTheLists( struct node * listH, struct node * otherListH, int indexPosition)]

How to give input:

Example input: 0 0 D

The first value determines the list command:

0 = adding to list one

1 = adding to list two

2 = inserting list two into list one (char doesn't matter)

3 = inserting list one into list two (char doesn't matter)

The second value determines the index position

The third value is the character to be stored in the new struct node.

The following commands:

0 0 D

<Stuff is printed out>

0 0 C

<stuff is printed out>

would result in this:

List One:

Pos_0, Value_C

Pos_1, Value_D

if we then inputted 0 1 E the result would be:

List One:

Pos_0, Value_C

Pos_1, Value_E

Pos_2, Value_D

if we then inputted 1 0 A and 1 0 B the result would be:

List One:

Pos_0, Value_C

Pos_1, Value_E

Pos_2, Value_D

List Two:

Pos_0, Value_B

Pos_1, Value_A

if we did the extra credit, and then inputting 2 1 X after the above commands would result in:

List One:

Pos_0, Value_C

Pos_1, Value_B

Pos_2, Value_A

Pos_3, Value_E

Pos_4, Value_D

List Two:

Pos_0, Value_B

Pos_1, Value_A

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <iostream>

struct node * insertAtIndex( struct node * pHead, char valueToInsert, int indexPosition);

void printTheList(struct node * pHead);

struct node * combineTheLists( struct node * listH, struct node * otherListH, int indexPosition);

void deleteList(struct node * pHead);

struct node

{

    char theChar;

    struct node * pNext;

}node;

int main()

{

    //this code uses TWO linked lists.

    struct node * pHeadOne = NULL;

    struct node * pHeadTwo = NULL;

    int listNum;

    int indexPos;

    char inputC;

   

    char notDone = 'Y';  

    do

    {

        //Read in input

       

        printf("Please enter the list command(0,1,2, or 3), an index position, a space, and a char. (0 0 D): ");

        std::cin >> listNum >> indexPos >> inputC;

 

        //insert value into the linked list

        if(listNum == 0)

        {

            pHeadOne = insertAtIndex(pHeadOne, inputC, indexPos); //adds to the first list

        }

        if(listNum == 1)

        {

            pHeadTwo = insertAtIndex(pHeadTwo, inputC, indexPos); //adds to the second list

        }

        if(listNum == 2)

        {

            pHeadOne = combineTheLists(pHeadOne, pHeadTwo, indexPos); // insets list two into list one.

        }

        if(listNum == 3)

        {

            pHeadTwo = combineTheLists(pHeadTwo, pHeadOne, indexPos); // inserts list one into list two.

        }      

        if(listNum < 0 || listNum > 3)

        {

            printf("\n Would you like to try again? Y/N: ");

            scanf(" %c", &notDone);

            notDone = toupper(notDone);

        }

        else

        {

            std::cout << "List one:" << std::endl;

            printTheList(pHeadOne);

       

            std::cout << std::endl << "List two:" << std::endl;

            printTheList(pHeadTwo); 

            std::cout << std::endl;     

        }

    }while(notDone == 'Y');

   

    deleteList(pHeadOne); //Cleanup

    deleteList(pHeadTwo);

    return 0;

}

//Print statements like this can be used for error checking - so try to have print statements that are not tied up with other functions!

//I.E., try to avoid functions that both print AND do some other process at the same time.

void printTheList(struct node * pHead)

{

    struct node * pTemp = pHead;

    int pos = 0;

    while(pTemp != NULL)

    {

        std::cout << "Pos_" << pos <<", Value_" << pTemp->theChar << std::endl;

        pTemp = pTemp->pNext;

        ++pos;

    }

}

//Write code

struct node * insertAtIndex( struct node * pHead, char valueToInsert, int indexPosition)

{

    struct node * pNew = new struct node;

   

    if(pHead == NULL || indexPosition == 0)

    {

        //Add code here.

        return pNew;

    }

    struct node * pTemp = NULL;

   

    //add code here.  Hint: This section should not change pHead.

   

    return pHead;

}

//Write code to insert otherList into list at the correct index position.

// listH and otherListH are the pHeads of their respective lists.

struct node * combineTheLists( struct node * listH, struct node * otherListH, int indexPosition)

{

    struct node * pTemp = NULL;

   

    if(otherListH == NULL)

    {

        return listH;

    }

    if(listH == NULL || indexPosition == 0)

    {

        //Add code here. Hint: This section should will change listH.

        return listH;

    }

   

    //add code here.  Hint: This section should not change listH.

    return listH;

   

}

void deleteList(struct node * pHead)

{

    struct node * pTemp = pHead;

    while(pTemp != NULL)

    {

        pHead = pTemp->pNext;

        delete(pTemp);

        pTemp = pHead;

    }

}

/*

POINTS:

1 Point: Have a program that can correctly add the first given char to a list (it just needs to work once).

2 Points: Have a working program that can insert chars into the list at any given index. An attempt to insert at a position greater than the length of the list should result in the element being added to the end of the list, with a warning message.

3 Points(Extra Credit):  Alter the program so that it is capable of inserting lists into other lists, as noted above.

   

NOTES:

Submission:

*/