C++

Forum

 
Sorting a doubly linked list

aeck (21)
I am trying to do this assignment:
1. Read data for names and weights for 15 people from the console where there is a name on a line followed by a weight on the next line, like in names.txt.
2. Your program will build a list for the data maintained in ascending order based on both name and weight via a doubly linked list.
3. This dll will use one pointer to keep weights in sorted order, and use the other link to keep names on sorted order.
4. You need to build the list as you go maintaining this ordering, so at any time a print method was called it would print the related field in order. (This means nodes are added to the list in sorted order, elements are not added to the list followed by a sort called on the list.)

For example after 3 elements are added for (Name – Weight):
Michael – 275, Tom – 150, Abe – 200.

Output:
Names & weights sorted(ascending) by name. : Abe – 200, Michael – 275, Tom - 150
Names & weights sorted(ascending) by weight. : Tom – 150, Abe – 200, Michael - 275

So far I am only entering and sorting the weight. I need some guidance on how to
Read data for names and weights for 15 people from the console where there is a name on a line followed by a weight on the next line.


The sample input is as follows:
Audrey
127
Brian
152
Johnny
147

So far I have 

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
162
163
164
165
166
167
168
169
170
171
172
173
 


#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;

int c = 0;

struct node
{
	char name[20];
	int weight;

    node *next;
	node *prev;


}*head = NULL, *tail = NULL, *p = NULL, *r = NULL, *np = NULL;

 node *start_ptr = NULL;

void create(int x)
{
    np = new node;

    np->weight = x;
    np->next = NULL;
    np->prev = NULL;
    if (c == 0)
    {
        tail = np;
        head = np;
        p = head;
        p->next = NULL;
        p->prev = NULL;
        c++;
    }
    else
    {
        p = head;
        r = p;
    if (np->weight < p->weight)
    {
        np->next = p;
        p->prev = np;
        np->prev = NULL;
        head = np;
        p = head;
        do
        {
            p = p->next;
        }
        while (p->next != NULL);
        tail = p;
    }
    else if (np->weight > p->weight)
    {
        while (p != NULL && np->weight > p->weight)
        {
            r = p;
            p = p->next;
        if (p == NULL)
        {
            r->next = np;
            np->prev = r;
            np->next = NULL;
            tail = np;
            break;
        }
        else if (np->weight < p->weight)
        { 
            r->next = np;
            np->prev = r;
            np->next = p;
            p->prev = np;
            if (p->next != NULL)
            {
                do
                {
                    p = p->next;
                }
                while (p->next !=NULL);
            }
            tail = p;
            break;
         }
       }
     }
   }
}

//void traverse_tail()
//{
//    node *t = tail;
//    while (t != NULL)
//    {
//        cout<<t->weight<<"\t";
//        t = t->prev;
//    }
//    cout<<endl;
//}

void traverse_head()
{
    node *t = head;
    while (t != NULL)
    {
        cout<<t->weight<<"\t";
        t = t->next;
    }
    cout<<endl;
}


void print_node()
  {
    node *temp;
    temp = start_ptr;
    if(temp == NULL) cout << "Empty List!" << endl;
    while(temp != NULL)
      {
        if(temp == NULL) cout << "Empty List!" << endl;



		cout << "Names & weights sorted(ascending) by name. :\n";

		
        cout << "Name   : " << temp->name << endl;
        cout << "Weight : " << temp->weight << endl;


		cout << "Names & weights sorted(ascending) by weight. : \n";

        cout << endl;  
        temp = temp->next; 
      }           
  } 




int main()
{
    int i = 0, n, x, ch;
    cout<<"Enter the number of people: \n";
    cin>>n;

    while (i < n)
    {
        cout<<"\nEnter Weights: \n";
        cin>>x;
        create(x);
        i++;
    }


	//print_node();



	cout << "Output: \n";
   /* cout<<"\nTraversing Doubly Linked List head first\n";*/
    traverse_head();
    /*cout<<"\nTraversing Doubly Linked List tail first\n";
    traverse_tail();*/
    getch();

	system("pause");
	return 0;
}




kbw (9488)
So what's the problem?

As far as I can see:
1. You're not reading names, just weights. You need to fix this.

2. You can save yourself a lot of work if you give node a constructor that initialises members. It's the right thing to do and you'll be surprised at how it simplifies your code.

3. You need a function that inserts each new node into the right list.
aeck (21)
Would you be willing to give an example of: giving a node a constructor
that initialises members?
MikeyBoy (5631)
Your textbook should already have examples of this.
kbw (9488)
The constructor initialises the struct (or class). Correspondingly, the destructor cleans up. In your case, there's nothing to clean up, so we don't need one.

Never use strcpy unless you're sure about the size of the source string. The catch with strncpy is that it doesn't null terminate the string if the buffer is full, that's why we need to write the terminating null just to be sure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct node
{
	node(const char* n, int w) :
		weight(w),
		next(nullptr),
		prev(nullptr)
	{
		strncpy(name, n, sizeof(name));
		name[sizeof(name) - 1] = 0;
	}

	char name[20];
	int weight;

	node *next;
	node *prev;
};


Ok, so what does this do for create? First, we need to add the string parameter. I just noticed all those global variables; that's bad. Anyway, we're just talking about constructors, so I won't get into all that. Nor will I look at the logic.
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
 
void create(const char* name, int weight)
{
	node* np = new node(name, weight);

	if (c == 0)
	{
		tail = np;
		head = np;
		p = head;
		c++;
	}
	else
	{
		p = head;
		r = p;
		if (np->weight < p->weight)
		{
			np->next = p;
			p->prev = np;
			head = np;
			p = head;
			do
			{
				p = p->next;
			}
			while (p->next != NULL);
			tail = p;
		}
		else if (np->weight > p->weight)
		{
			while (p != NULL && np->weight > p->weight)
			{
				r = p;
				p = p->next;
				if (p == NULL)
				{
					r->next = np;
					np->prev = r;
					tail = np;
					break;
				}
				else if (np->weight < p->weight)
				{ 
					r->next = np;
					np->prev = r;
					np->next = p;
					p->prev = np;
					if (p->next != NULL)
					{
						do
						{
							p = p->next;
						}
						while (p->next !=NULL);
					}
					tail = p;
					break;
				}
			}
		}
	}
}


Notice how all those assignments of prev/next to NULL are gone.
Last edited on
dhayden (5798)
I think you are all missing something important here. When the assignment says a "doubly linked list" it does NOT mean a list with prev and next pointers:
This [doubly linked list] will use one pointer to keep weights in sorted order, and use the other link to keep names on sorted order.

In other words, this is like two lists, one sorted by name and one sorted by weight, but you're supposed to have two pointers within each node.

Here are the classes and the insert() method. Pay particular attention to the use of Node **pp, which names the inserting into a list much easier than most textbooks and teachers seem to teach.

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
 
class Node {
public:
    Node(const string &p_name, unsigned p_weight) :
	name(p_name),
	weight(p_weight),
	nextByWeight(NULL),
	nextByName(NULL)
    {}

    void print(ostream &os) const;

    string name;
    unsigned weight;

    Node *nextByName;		// next node sorted by name
    Node *nextByWeight;		// next node sorted by weight
};

class List {
public:
    List() :
	nameHead(NULL),
	weightHead(NULL)
    {}
    ~List();
    void insert(const string &name, unsigned weight);
    void printByName(ostream &os) const;
    void printByWeight(ostream &os) const;
private:
    Node *nameHead;
    Node *weightHead;
};

void List::insert(const string &name, unsigned weight)
{
    Node *node = new Node(name, weight);

    Node **pp, *p;

    // Insert into name list
    for (pp = &nameHead; p = *pp; pp = &(p->nextByName)) {
	if (p->name >= name) {
	    break;
	}
    }
    node->nextByName = p;
    *pp = node;

    // Insert into weight list
    for (pp = &weightHead; p = *pp; pp = &(p->nextByWeight)) {
	if (p->weight >= weight) {
	    break;
	}
    }
    node->nextByWeight = p;
    *pp = node;
}


Topic archived. No new replies allowed.