Sorting linked list first by last name then by firrst name

tkauffman2 (37)
Hello, I Have a function sort in my program (below) that takes in linked lists and inserts them sorted. I have the function working 100% by last name but when Itry to do it by first name IF the last names are the same I get seg fault when I'm trying to insert a new head node.

edit!! Also, When I enter if both names are the same, I want it to spit out the way I inserted it but it prints it out backwards
Thank you.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void Addr_list::insert(string fname,string lname, string phnum, string email)
{
    Address *new_address = new Address(fname,lname,phnum,email);
    if (m_head == NULL || lname < m_head->m_lname || lname == m_head->m_lname)
    {
	new_address->m_next = m_head;  //if statements for the similar names.
	m_head = new_address;
	return;
    }
    Address *curr = m_head;
    Address *prev;
    while (curr != NULL && lname >curr->m_lname || lname ==curr->m_lname)
    {
	prev = curr;
	curr = curr->m_next;
    }
        new_address->m_next = curr;
	prev->m_next = new_address;
	
 }


any psuedo code, tips would be appreciated thanks!!
Last edited on
tkauffman2 (37)
please anyone?
closed account (zwA4jE8b)
I mean, because in your if statement you care comparing last names, not first names.

You should make 2 different functions, one for last name sorting and one for first name sorting.
Last edited on
tkauffman2 (37)
I have the name sorting working, i meant in that code it is printing out backwards, I want it when The first and last names are the same to print it out the way I inserted it.
closed account (zwA4jE8b)
Well the code above doesn't print at all so I do not know what your traversal function looks like.

If the nodes are sorted correctly then a traversal should go just fine. Post your output code.
tkauffman2 (37)
okay, I ran into probems with first name, so I took it out, but here is my entire program..
input:
input <fname> <lname> <phnum> <email>
print (prints the list)
lookupfirst <fname> (displays all parts of list wit the first name you entered)
lookuplast <lname> same as above
remove <fname> <lname> (removes from that node wont delete head node after the list is sorted, error)
header:
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
 
//addr_list.h
//Kauffman,Tyler
//tkauffman

#ifndef ADDR_LIST_H
#define ADDR_LIST_H

class Addr_list
{
    public:
        Addr_list();
        ~Addr_list();
	void insert(string fname,string lname,string phnum, string email);
        void remove(string fname,string lname);
	void lookupfirst(string fname);
	void lookuplast(string lname);
        void print();
       
    private:	
	  struct Address
          {
	       public:
		    Address (string fname, string lname, string phnum, string email)
		    {m_fname=fname, m_lname=lname, m_phnum=phnum, m_email=email;}
		    string m_fname,m_lname,m_phnum,m_email;
		    Address *m_next;
		    
    };
    Address *m_head;
};

#endif


main:
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
 
//abook.cpp
//Kauffman,Tyler
//tkauffman

#include <iostream>
#include <string>
#include<algorithm>

using namespace std;
#include "addr_list.h"
int main()
{
    string insert = "insert";
    int i;
    string command;
    string fname,lname,phnum,email;
	Addr_list *list = new Addr_list;	
	
        while (cin>>command)
        {
		if(command == "insert")
		{
		cin >> fname>>lname>>phnum>>email;
		list -> insert (fname,lname,phnum,email);
	
		}
		
		if (command == "remove")
		{
		cin>>fname>>lname;
		list ->remove(fname,lname);	
		}
		if(command == "print")
		{
		list ->print();	
		}
		if(command == "lookupfirst")
		{
		cin >> fname;
		list ->lookupfirst(fname);
		}
		if (command == "lookuplast")
		{
		cin >>lname;
		list ->lookuplast(lname);
		}	
		else if (command != "insert" && command != "remove"&& command != "lookupfirst" && command != "print")
		{
		cerr<< "Wrong"<<endl;
		}
	}

}


program part:
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
 
//addr_list.cpp
//Kauffman,Tyler
//tkauffman

#include <iostream>
using namespace std;
#include "addr_list.h"

Addr_list::Addr_list()
{
    m_head = NULL;
}
Addr_list::~Addr_list()
{
    Address *ptr = m_head;
   
    while (ptr != NULL)
    {
        Address *temp;
    
        temp = ptr;
        ptr = ptr->m_next;
        delete temp;
    }
}
    
 void Addr_list::insert(string fname,string lname, string phnum, string email)
{
    Address *new_address = new Address(fname,lname,phnum,email);
    if (m_head == NULL || lname < m_head->m_lname )
    {
	new_address->m_next = m_head;  //if statements for the similar names.
	m_head = new_address;
	return;
    }
    Address *curr = m_head;
    Address *prev;
    while (curr != NULL && lname >curr->m_lname)
    {
	prev = curr;
	curr = curr->m_next;
    }
        new_address->m_next = curr;
	prev->m_next = new_address;
	
 } 
		
 void Addr_list::lookupfirst(string fname)
 {
	 int count = 0;
         cout << "Matches for first name: " << fname<< endl;
	 Address *ptr = m_head; 
         for (Address *cur = m_head; cur != NULL; cur = cur->m_next)
	 {
	        if (fname == cur->m_fname)
		{
		++count;
		cout <<cur->m_fname<<" "<<cur->m_lname<<": " << cur->m_phnum
		<< " "<<cur->m_email<<endl;
		}
	 }
	string temp;
	 if( count != 1 )
	{	
	temp = " matches";	
	}
	else if ( count = 1)
	{
	temp = " match";	
	}
	 cout << count <<temp<<" found."<<endl;
 }
 
 void Addr_list::lookuplast(string lname)
 {
	 int count =0;
	 cout << "Matches for last name: " << lname<< endl;
	  Address *ptr = m_head; 
         for (Address *cur = m_head; cur != NULL; cur = cur->m_next)
	 {
		 ++count;
	        if (lname == cur->m_lname)
		{
		cout <<cur->m_fname<<" "<<cur->m_lname<<": " << cur->m_phnum
		<< " "<<cur->m_email<<endl;
		}
	 }
	 string temp;
	 if( count != 1 )
	{	
	temp = " matches";	
	}
	else if ( count = 1)
	{
	temp = " match";	
	}
	 cout << count <<temp<<" found."<<endl;
  }
  void Addr_list::remove(string fname, string lname)
{
	
	Address *cur, *prev;
	cur = m_head;
	prev = cur ->m_next;
	while(prev->m_lname != lname && prev->m_fname != fname)
	    {
	    cur = cur ->m_next;
	    prev=prev ->m_next;
	    }
	if(m_head ->m_lname == lname &&m_head->m_fname ==fname)
	    {
	    prev = cur;
	    m_head = m_head ->m_next;
	    delete prev;
	    }
	else
	    {
	    cur ->m_next = cur->m_next->m_next;
	    delete prev;
	    }
	    prev = NULL;
	    cur = NULL;
}

void Addr_list::print()
{
     for (Address *cur = m_head; cur != NULL; cur = cur->m_next)
	{
	cout <<cur->m_fname<<" "<<cur->m_lname<<": " << cur->m_phnum
		<< ", "<<cur->m_email<<endl;	
	}
      
}



closed account (zwA4jE8b)
I have looked at it but without rewriting the structure I don't know how to fix it. I am used to working with a grounded linked list (a fixed head and tail node). Here is my class, hope it helps.


This first one is the base class

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
174
175
176
177
178
179
180
181
182
183
184
 
//Michael Ervin - Linked list Class
//
//insertfirst & insertlast perform the same operation
//in an ordered linked list.

#ifndef H_linkedlist
#define H_linkedlist

#include <iostream>

//place all needed fields in here and modify code accordingly
//id is used as unique identifier throughout - do not change
template <class dType>
struct nodeType
{
	dType id;
	nodeType<dType> *link;
};

template <class dType>
class linkedlistiterator
{
	nodeType<dType>* c;
public:
	linkedlistiterator();
	linkedlistiterator(nodeType<dType>* ptr);
	dType operator*();
	linkedlistiterator<dType> operator++();
	bool operator==(const linkedlistiterator<dType>& right) const;
	bool operator!=(const linkedlistiterator<dType>& right) const;
};

template <class dType>
linkedlistiterator<dType>::linkedlistiterator()
{
	c == NULL;
}

template <class dType>
linkedlistiterator<dType>::linkedlistiterator(nodeType<dType>* ptr)
{
	current = ptr;
}

template <class dType>
dType linkedlistiterator<dType>::operator*()
{
	return c->id;
}

template <class dType>
linkedlistiterator<dType> linkedlistiterator<dType>::operator++()
{
	c = c->link;
	return *this;
}

template <class dType>
bool linkedlistiterator<dType>::operator==(const linkedlistiterator<dType>& right) const
{
	return (c == right.c);
}

template <class dType>
bool linkedlistiterator<dType>::operator!=(const linkedlistiterator<dType>& right) const
{
	return (c != right.c);
}

template <class dType>
class linkedlist
{
public:
	linkedlist();
	bool isEmpty() const;
	int length() const;
	void print() const;
	void printnode(nodeType<dType> *toprint, int pos) const;
	virtual void insertfirst(nodeType<dType> *newnode) = 0;
	virtual void insertlast(nodeType<dType> *newnode) = 0;
	virtual void deleteNode(dType todel) = 0;
	virtual void seqsearch(dType id) const = 0;
	void destroyList();
	~linkedlist();
	void copyList(const linkedlist<dType>& otherlist);
protected:
	nodeType<dType> *head;
	nodeType<dType> *tail;
	int count;
};

//Change ID field to match min and max dType
template <class dType>
linkedlist<dType>::linkedlist()
{
	head = new nodeType<dType>;
	tail = new nodeType<dType>;

	tail->id = 9999.0;
	tail->link = NULL;

	head->id = -1.0;
	head->link = tail;

	count = 0;
}

template <class dType>
bool linkedlist<dType>::isEmpty() const
{
	return (head->link == tail);
}

template <class dType>
int linkedlist<dType>::length() const
{
	return count;
}

//If fields have been added to nodeType, they must also be added here
template <class dType>
void linkedlist<dType>::print() const
{
	nodeType<dType> *current;
	current = head->link;
	if (!isEmpty())
	{
		while (current != tail)
		{
			cout << current->id << " " << endl;
			current = current->link;
		}
	}
	else
		cout << "The list is empty...";
	cout << endl;
}

//If fields have been added to nodeType, they must also be added here
template <class dType>
void linkedlist<dType>::printnode(nodeType<dType> *toprint, int pos) const
{
	cout << "Found node at position " << pos << endl;
	cout << "ID = " << toprint->id << endl;
	cout << endl;
}

template <class dType>
void linkedlist<dType>::destroyList()
{
	nodeType<dType> *temp;
	while (head->link != tail)
	{
		temp = head->link;
		head->link = temp->link;
		delete temp;
	}
	count = 0;
}

template <class dType>
linkedlist<dType>::~linkedlist()
{
	destroyList();
}

//If fields have been added to nodeType, they must also be added here in order to copy correctly.
template <class dType>
void linkedlist<dType>::copyList(const linkedlist<dType>& otherlist)
{
	nodeType<dType> *current, *newnode;

	current = otherlist.head->link;

	while (current != otherlist.tail)
	{
		newnode = new nodeType<dType>;
		newnode->id = current->id;
		newnode->link = NULL;
		insertlast(newnode);
		current = current->link;
	}
}
#endif






This one is the derived class

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
 
//Michael Ervin - Ordered Linked list Class

#ifndef H_orderedlinkedlist
#define H_orderedlinkedlist

#include <iostream>
#include "linkedlist.h"

template <class dType>
class orderedlinkedlist:public linkedlist<dType>
{
public:
	void insert(nodeType<dType> *newnode);
	void insertfirst(nodeType<dType> *newnode);
	void insertlast(nodeType<dType> *newnode);
	void deleteNode(dType todel);
	void seqsearch(dType id) const;
};

template <class dType>
void orderedlinkedlist<dType>::insertfirst(nodeType<dType> *newnode)
{
	insert(newnode);
}

template <class dType>
void orderedlinkedlist<dType>::insertlast(nodeType<dType> *newnode)
{
	insert(newnode);
}

template <class dType>
void orderedlinkedlist<dType>::insert(nodeType<dType> *newnode)
{
	nodeType<dType> *current, *trail;
		trail = head;
		current = head->link;
		while (current != tail && current->id < newnode->id)
		{
			trail = current;
			current = current->link;
		}
		newnode->link = current;
		trail->link = newnode;
		count++;
}

template <class dType>
void orderedlinkedlist<dType>::deleteNode(dType todel)
{
	nodeType<dType> *current, *trail;

	if(!isEmpty())
	{
		trail = head;
		current = head->link;
		while (current != tail && current->id < todel)
		{
				trail = current;
				current = current->link;
		}
		if (current->id == todel)
		{
			trail->link = current->link;
			delete current;
			count--;
		}
		else
			cout << "The node to delete is not in the list!" << endl;
	}
	else
		cout << "The list is empty!" << endl;
}

template <class dType>
void orderedlinkedlist<dType>::seqsearch(dType id) const
{
	nodeType<dType> *current;
	bool found = false;
	int pos = 1;

	current = head->link;
	while (current != tail && !found)
	{
		if (current->id == id)
			found = true;
		else
		{
			current = current->link;
			pos++;
		}
	}
	if (found)
		printnode(current, pos);
	else
		cout << "Node not in list..." << endl;
}
#endif
closed account (D80DSL3A)
One problem I see is with line 30:
if (m_head == NULL || lname < m_head->m_lname )
If head IS NULL then dereferencing it will not be good (as you do on same line as testing for NULL).

You want something more like...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
if( head == NULL )// then list is empty
{
      head = new Address;
      head->next = NULL;
}
else// OK to dereference head
{
      if( lname < m_head->m_lname )
      {
            Address* pA = new Address(...);
            pA->next = head;
            head = pA;
            return;
      }
       // rest of function to search further into list
}
filipe (1165)
If head IS NULL then dereferencing it will not be good (as you do on same line as testing for NULL).

No, short circuit evaluation will prevent that from happening. If it's null then the expression a || b is true anyway, so the unnecessary check is skipped. If it were written as

if (lname < m_head->m_lname || m_head == NULL)

then it would cause a crash when a null pointer was passed.
closed account (D80DSL3A)
Thanks filipe! I didn't know it worked like that.
Topic archived. No new replies allowed.