/*
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", ¬Done);
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:
Keep in mind that this is a team effort so you should agree with your partner on what you are going to do before you start typing. The partner who is typing is the "driver" and the partner watching is the "navigator." Be sure to switch roles every 10 to 15 minutes, to foster a deep understanding of the code for both partners. The navigator should be watching for syntax errors and verifying the correctness of the code you're writing.
It will speed things up for you if you keep a window open for editing and have a separate window open for compiling and running your program. Remember that windows are resizeable!
You should work with a partner for a grade. Only one submission per group is necessary, but be sure to include your name if you work alone, or both people's names if you worked with a partner.
You should submit the lab to the Blackboard at the end of the lab session, by 50 minutes after the hour.
*/