Sorting a Linked list help

Mar 11, 2011 at 4:36am
Hello
I need to sort a linked list at insertion, I just can't figure out how to do it. any guidance in the right direction would be appreciated


I have in pseudo code what I think it should start like, but when I do that it just seems wrong to me, and I cannot add any more if statements in or i get segmentation faults.

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
//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)
{
	
		// if current = NULL or  curent's -> last name is smaller than 
		// the one were imputting (lname) && / if current's last name == 
		//  the one were inputting (lname) compare first names the same way.
		//m_head = new Address(fname,lname,phnum,email, m_head);
}
	

void Addr_list::remove(string fname, string lname)
{
	//cout<<"remove function was called " << endl;
}
// iterate through all the Nodes in the list and print each Node
void Addr_list::print()
{
       Address *ptr = m_head; 
       cout << ptr->m_fname<<ptr -> m_lname<<": "<<ptr->m_phnum<<","<<ptr->m_email<<endl;
       ptr = ptr->m_next;
	
	
        // cout << "size is: " << size << endl;
      
}



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
//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 print();
       
    private:	
	  struct Address
          {
	       public:
		    Address (string fname, string lname, string phnum, string email, Address *next)
		    {m_fname=fname, m_lname=lname, m_phnum=phnum, m_email=email,m_next=next;}
		    string m_fname,m_lname,m_phnum,m_email;
		    Address *m_next;
		    
    };
    Address *m_head;
};

#endif 


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
//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);
		list -> print();
		
		}
		if (command == "remove")
		{
		//cout << "remove was called " <<endl;	
		list ->remove(fname,lname);	
		}
		else if (command != "insert"&& command != "remove")
		{
		cerr<< "Wrong"<<endl;
		}
	}

}




Mar 11, 2011 at 4:48am
First consider the case when head == NULL; i.e., the list is empty. That is pretty simple. Then consider how you can iterate over the list to compare names when inserting into a non-empty list.
Mar 11, 2011 at 4:57am
That's where I'm stuck, I cant seem to figure out how to traverse through this linked list of strings, I can do arrays easily.
Mar 11, 2011 at 6:04am
For lists, the basic sorting algorithms are as good as any and probably better.

You have two very simple ones: insertion sort and selection sort. Selection sort is probably the easier. First, lets see what selection sort is all about:

You partition the original sequence in two portions - sorted portion and unsorted portion. At the beginning everything is in the unsorted portion, in the end everything is in the sorted portion, at each step you move one element from the unsorted to the sorted portion.

The step is implemented like this: you find the element in the unsorted portion that has the least value and you swap it with the first element in the unsorted portion. Then you join the first element from the unsorted portion with the sorted portion, where it becomes the last element.

One issue - what does it mean "least" element. Depends. You can compare the first names, the last names, the first names and then last names if the first names were equal, etc.

Another issue - what does it mean to swap. With arrays it is simple. With node-based structures, like lists, you have two options. Relink the nodes so that their positions in the list are swapped, or swap all data inside the nodes as you would do in an array.

Third issue - usually you use indices when you sort arrays. What do you use here?

Well, first, when you use indices, you keep one index to the first element in the unsorted portion. When you join this element with the other already sorted elements, you move the index forward. With lists, you will keep pointer to the first node from the unsorted tail of the list. When you join this node to the already sorted nodes, you will move this pointer to the next node. However, this is in case that you swap the node values in the forementioned swap operation. If your node swap is to reposition the nodes in the list by unlinking and relinking them, which is arguably more effective in your case, since you have all this data, you have to keep pointer to the place where you keep the link (pointer to) the node. This would be the m_next field of the previous node or the address of the m_head field, if this is the first node.

Second, when you use indices, you keep one index that shows the position of the current least element when you seek the smallest from the unsorted portion. With nodes, you again keep pointer to the node instead. If the swap is implemented with relinking you have to keep pointer to the link (pointer to) the node, as in the previous paragraph. In order to do that, during the search you have to use pointers to pointers also.

So, basically, you have outer loop that tries to eat away the unsorted tail of the list, adding one node at time to the sorted front portion. (Adding here means simply moving forward.) Then you have inner loop that traverses the tail from beginning to end, looking for the node with the least/minimum value. Then you swap/relink the minimum node and the first node from the tail, and move the pointer of the outer loop forward, until the tail is empty.

Regards

P.S. You can implement insertion sort with lists similarly, but IMO selection sort is a tad bit simpler to comprehend.
Mar 11, 2011 at 7:14am
Hi ,
I have tried this way .. hope it work .
please cheack this .

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
struct Address
{
string m_fname ;
string m_lname ; 
string m_phnum ;
string  m_email ;
Address* next; 
}* m_head ; 

void Addr_list::insert(string fname, string lname,string phnum, string email)
{
	Address* m_temp ;
	if ( m_head == NULL ) 
	{
		strcpy ( m_head->m_name ,  fname ) ; 		
		strcpy ( m_head->m_lname ,  lname ) ; 		
		strcpy ( m_head->m_phname ,  phname ) ; 		
		strcpy ( m_head->m_email ,  email ) ; 		
		m_head->next = NULL; 
	}
	else
	{
		Address* m_temp * m_q  , * m_last ;
		m_temp = m_head ; 
		
		while ( m_temp = m_temp->next)
		{
			if( atoi(fname[0]) < atoi( m_temp->next->m_fname[0] ) ) 
			{
				continue;
			}
			else
			{
				strcpy ( m_q->m_name ,  fname ) ;
				strcpy ( m_q->m_lname ,  lname ) ;
				strcpy ( m_q->m_phname ,  phname ) ;
				strcpy ( m_q->m_email ,  email ) ;
				m_q->next = m_temp->next  ; 
				m_temp->next = m_q ; 
				break ;
			}
		};
		m_head = m_temp ; 
	
	}
	
}
Mar 11, 2011 at 7:24am
Wow thank you, that way seems so much easier than the way i was doing it!
could you do me a favor and explain exactly whats going on? i
Thank you so much

Edit:

When I try to compile it i get : addr_list.cpp:32: error: cannot convert ˜std::string tochar* for argument ˜1 to char* strcpy(char*, const char*)
Last edited on Mar 11, 2011 at 7:31am
Topic archived. No new replies allowed.