Linked list sorting Desperate!

[tkauffman2]

Hello, I really need help, ive been doign this ONE fucntion all day and I have gotten no where, the assignment is due TOMORROW!

I have a linked list, and what i want to do is sort it at insertion:

here is my insert function:
It is wrong, I know, but I'm not getting anything accomplished on it and its really frustrating, Thank you :)

void Addr_list::insert(string fname,string lname, string phnum, string email)
{
	Address *m_temp;
	Address *cur = m_head;
	if (cur == NULL || cur->m_lname < lname ) 
	{			                   
	m_head = new Address(fname,lname,phnum,email,m_head);
	//cur->m_next = NULL;
	}
	else
	{
			Address *m_temp, *m_q, *m_last;
			
			while (m_temp = m_temp -> m_next)
			{
				if (lname < m_temp->m_next->m_lname)
				{	
					continue;
				}
				else
				{
				m_q->m_next = m_temp ->m_next;
				m_temp->m_next = m_q;
				break;
				}
	
	
	
		
			};
			m_head = m_temp;
			



	}

}

[aiby]

void Addr_list::insert(string fname,string lname, string phnum, string email)
{
	Address *m_temp;
	
	if ((m_temp = head)) == NULL) {
           m_temp = m_head = new Address(fname,lname,phnum,email,m_head);
           m_temp->next = NULL
                  }
	else
	{
			Address *m_q;
			
			while (m_temp)
			{
				if (lname > m_temp->m_next->m_lname)
				{	
					break;
				}
                                                                        m_temp = m_temp -> m_next;
                       }			
                                m_q = new Address(fname,lname,phnum,email,m_head);; //get memmory before use it
				m_q->m_next = m_temp ->m_next;
				m_temp->m_next = m_q;
				break;
	}

}

[tkauffman2]

I tried that code and I get seg fault

[jsmith]

On your original post, line 15 -- m_temp is dereferenced but it is uninitialized.

[filipe]

I was writing the proper function when I noticed this: new Address(fname,lname,phnum,email,m_head);
I take it Address is your class for nodes. Why are you passing the list's head to every node you create? In a singly linked list, a node only needs to know which node comes after it. I'll just write the function for a type Address that doesn't take any nodes as constructor arguments:

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) {
        m_head = new_address;
        m_head->next = NULL;
        return;
    }
    Address *curr = m_head;
    Address *prev;
    while(curr != NULL && lname > curr->m_lname) {
        prev = curr;
        curr = curr->next;
    }
    prev->next = new_address;
    new_address->next = curr;
}

Be warned that I didn't test this. Also notice that prev isn't really necessary, but it makes things more readable.

[tkauffman2]

Alright, Filipe I tried your code in mine, IT prints out the first node for every node i enter, except if i enter b b b b in before a a a a i will get a seg fault
sample input :
insert a a a a
insert b b b b
insert c c c c
print

sample output :
a a: a, a
a a: a, a
a a; a, a

sample input:
insert b b b b
insert a a a a
print

sample output:
segmentation fault

Here is my complete code.

 //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)
		    {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 

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

}

//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)
    {
	m_head = new_address;
	m_head->m_next = NULL;
	return;
    }
    Address *curr = m_head;
    Address *prev;
    while (curr != NULL && lname >curr->m_lname)
    {
	prev = curr;
	curr = curr->m_next;
    }
	prev->m_next = new_address;
	new_address->m_next = curr;

}


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;
      
} 

[tkauffman2]

I narrowed it down further still;
The seg fault only happens when m_head needs be be replaced. I will keep trying


Edit once more; I figure that it is because I dont have the condition what if m_head is bigger than m_head->m_next->m_lname..
duh!! ill keep u guys posted!!

[filipe]

True. I forgot to cater for the case when the head is the value to be replaced (which means you can't dereference prev because it's dangling). I think you can take it from there.

[tkauffman2]

NVM! it was in the first if statement duh again, brains are definitely fried!!
You helped me so much Thank you.

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