C++

Forum

 
C++ Linked List Sorting, Splitting, and Printing issue

Twigler (4)
Hi guys for my lab assignment this week I was assigned to learn about Linked Lists. The lab prompt is as follows:

Write a program that creates a forward linked list of at least 20 elements, where each element holds a random integer between 0 and 99. Print the list.

Write the function "returnMiddleList" to find the middle element of the linked list in one pass. Print the integer value of this element and the position of this element (starting at zero) in relation to the head (where the head = 0, the element pointed to by the head = 1, the element pointed to by the previous one = 2, etc).

Split the list in half at the middle element to create two entirely separate* linked lists of near equal size (+/- 1) and print the two lists. Modify the "returnMiddleList" function to accomplish this, returning the head of the second linked list and setting the link of the element pointing to that head to null. Then print the two sums of the integers stored in the elements of both lists.

Sort the two lists from least to greatest and print them out (printing at this step is optional depending on the sort approach taken). Then combine the two lists while sorting them again from least to greatest and print out the new list. (HINT: you can subdivide the lists further and sort them on a scale of one to two element lists before sorting and combining the first two unsorted lists. What is this sort called?)

I have got #1 and #2 working, but #3 and #4 is where the issue is beginning. When I split my link list into two lists and print the individual lists out, my first link list prints out 9 numbers when it should be printing out 10 (the 10th number somehow disappears?), but when I do the sum of the first list right after that, the number that has disappeared gets added in the sum! I do not know why it is disappearing, and this is one issue. Another issue is in the second list, a random "0" gets added to the list and one of the numbers is lost. My last issue is about #4 as the merge algorithm I have used does not seem to work (I am merging the list together while sorting them, but I am not using a recursion sort because we have not learned that yet). Any input and help would be greatly appreciated! Thanks!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

struct nodeType {
    int data;
    nodeType *link;
};

void populateList(nodeType *head) {
//  srand(time(NULL));
    nodeType *temp;
    nodeType *current = head;

    for (int i = 0; i < 20; i++) {
        temp = new nodeType;

        current->data = rand() % 100;

        current->link = temp;

        current = temp;
    }

    temp->link = NULL;
}

void print(nodeType *head) {
    int i = 1;

    while (head->link != NULL) {
        cout << "#" << i++ << ": " << head->data << endl;

        head = head->link;
    }
}

nodeType* returnMiddleList(nodeType *head) {
    nodeType *p1 = head, *p2 = head;
    int count = 0;
    int middle = 1;

    while (p1->link->link != NULL) {
        p1 = p1->link;

        count++;

        if (count % 2 == 0) {
            p2 = p2->link;
            middle++;
        }

    }

    cout << "Middle #" << middle << ": " << p2->data << endl;

    p1 = p2->link;
    p2->link = NULL;

    return p1;
}

void add(nodeType *head) {
    int sum = 0;

    while (head != NULL) {
        sum = sum + head->data;
        head = head->link;
    }

    cout << sum << endl;
}

void sort(nodeType *head) {
    nodeType *temp = head;

    while (temp != NULL) {
        nodeType *temp2 = temp;

        while (temp2 != NULL) {
            if (temp->data > temp2->data) {
                int temp3;

                temp3 = temp->data;
                temp->data = temp2->data;
                temp2->data = temp3;
            }

            temp2 = temp2->link;
        }

        temp = temp->link;
    }
}

nodeType* merge(nodeType* head1, nodeType* head2) {
    nodeType *head3 = new nodeType, *current1 = head1, *current2 = head2;

    while (current1 != NULL || current2 != NULL) {
        if (current1 == NULL) {
            while (current2 != NULL) {
                //logic
                current2 = current2->link; //dumps list 2
                head3->data = current2->data;
            }
            break;
        }
        if (current2 == NULL) {
            while (current1 != NULL) {
                //Logic
                current1 = current1->link; //dumps list 1
                head3->data = current1->data;
            }
            break;
        }

        if (current1->data < current2->data) {
            //logic
            current1 = current1->link; //increments list 1
            head3->data = current1->data;

        } else {
            //logic
            current2 = current2->link; //increments list 2
            head3->data = current2->data;

        }

    }

    return head3;
}

int main() {
    nodeType *head = new nodeType, *head2, *head3;

    populateList(head);

    print(head);
    cout << endl;

    head2 = returnMiddleList(head);

    cout << endl << "List #1 Sum: ";
    add(head);

    cout << endl << "List #2 Sum: ";
    add(head2);

    sort(head);
    cout << endl << "List #1 Sorted" << endl;
    print(head);

    sort(head2);
    cout << endl << "List #2 Sorted" << endl;
    print(head2);

    head3 = merge(head, head2);
    print(head3);
}
cire (8284)
Your print function doesn't print the last element in the list. It only prints nodes which have a link member that is not null. The last element of a list will not meet that requirement.

Once you fix that, you can see the initial list generated is a bit larger than intended and contains some junk data, and the sum of list 1 and list 2 may make more sense to you.
Last edited on
Twigler (4)
@cire But it prints out the last element of my list for the 2nd list which makes no sense!
cire (8284)
No it doesn't. Your second list has 11 elements, not 10.
cire (8284)
Change print to:

1
2
3
4
5
6
7
8
9
10
11
 
void print(nodeType* head) 
{
    nodeType* node = head;

    unsigned count = 0;
    while (node)
    {
        std::cout << '#' << ++count << ": " << node->data << '\n';
        node = node->link;
    }
}


And examine the output.
Twigler (4)
Wow, so why is the 21st element being generated when in my populateList() function it is only generating 20 nodes?
cire (8284)
populateList generates 20 nodes, but how many nodes does the list consist of when you call it?
Twigler (4)
@cire it has 21 for some reason and I do not know why
nichodiaz (2)
Try this, moving the [i++ to ++i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void populateList(nodeType *head) {
//  srand(time(NULL));
    nodeType *temp;
    nodeType *current = head;

    for (int i = 0; i < 20; ++i) {
        temp = new nodeType;

        current->data = rand() % 100;

        current->link = temp;

        current = temp;
    }
cire (8284)
nichodiaz wrote:
Try this, moving the [i++ to ++i]

That would have no effect at all.

Twigler wrote:
@cire it has 21 for some reason and I do not know why

Yes. There are the 20 inside populateList and the 1 in main on line 136 in the OP.
Topic archived. No new replies allowed.