6 Replies - 477 Views - Last Post: 02 September 2009 - 07:25 PM Rate Topic: -----

#1 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Linked List and order

Posted 01 September 2009 - 10:28 PM

Ok well i have to create a linked list, the particular difficulty that im finding is that i have to order the linked list, say here comes number 1 so it goes into the list, then here comes numbre 2 and goes into the list after numbre 1, there here comes 5 so it goes into the list after 2, now our list looks like this "1 2 5". Now here comes 4, so 4 has to go between 5 and 2, and our list should now look like this "1 2 4 5", but i just cant get it into code for some reason i cant even get the "1 2" or maybe is my display i dunno, a little help will be greatly apreaciated, here is my code.
#include <iostream>

using namespace std;

struct Node{
	int dato;
	Node *link;
};
Node *fin=NULL, *inicio=NULL;

void meter(int num){
	Node *t=NULL, *t2;
	t2=inicio;
	t=new Node;
	t->dato=num;
	t->link=NULL;
	if(inicio==NULL||num<inicio->dato){
		if(fin==NULL)
			fin=inicio=t;
		else{
			t->link=inicio;
			inicio=t;
		}
	}
	else{
		if(num>fin->dato){
			t->link=fin;
			fin=t;
		}
		else{
			while(t->dato<t2->dato){
				t2=t2->link;
			}
			t->link=t2->link;
			t2->link=t;
		}
	}
}
void mostrar(){
	Node *t;
	t=inicio;
	do{
		cout<<t->dato<<endl;
		t=t->link;
	}while(t!=NULL);
}
void del(){

}
int main(){
	int num;
	while(true){
		cout<<"Ingrese un numero 0 para salir ";
		cin>>num;
		if(num==0)
			break;
		meter(num);
	}
	mostrar();
	system("pause");
	return 0;
}


Thank You

Is This A Good Question/Topic? 0
  • +

Replies To: Linked List and order

#2 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Linked List and order

Posted 01 September 2009 - 11:40 PM

Ok fixed code but still need to figure out why it goes mad after several entries and the "sacar" fuction is not working perfectly either if i take out the first number it goes all crazy on me
#include <iostream>

using namespace std;

struct Node{
	int dato;
	Node *link;
};
Node *fin=NULL, *inicio=NULL;

void meter(int num){
	Node *t=NULL, *t2;
	
	t=new Node;
	t->dato=num;
	t->link=NULL;
	if(inicio==NULL||num<inicio->dato){
		if(fin==NULL)
			fin=inicio=t;
		else{
			t->link=inicio;
			inicio=t;
		}
	}
	else{
		if(num>fin->dato){
			fin->link=t;
			fin=t;
		}
		else{
			t2=inicio;
			while(t->dato<t2->dato){
				t2=t2->link;
			}
			t->link=t2->link;
			t2->link=t;

		}
	}
}
void mostrar(){
	Node *t;
	t=inicio;
	do{
		cout<<t->dato<<endl;
		t=t->link;
	}while(t!=NULL);
}
void sacar(int num){
	Node *tmp, *temp;
	tmp=inicio;
	if(num==tmp->dato){
		cout<<"Deleted number was "<<tmp->dato;
		inicio=tmp->link;
		delete tmp;
		return;
	}
	temp=tmp;
	while(tmp!=NULL){
		if(tmp->dato==num){
						cout<<"Deleted number was: "<<tmp->dato;
			temp->link=tmp->link;
			delete tmp;
			return;
		}
		temp=tmp;
		tmp=tmp->link;
	}
			cout<<"Numbre doesnt exist";
}
void del(){

}
int main(){
	int num, ans;
	char res;
	while(true){
		cout<<"Imput the numbers, 0 to exit ";
		cin>>num;
		if(num==0)
			break;
		meter(num);
	}
	mostrar();
	while(true){
		cout<<"\nDo you want to delete a numbre? y o n"<<endl;
		cout<<"Answer: ";
		cin>>res;
		if(res=='y'||res=='Y'){
			cout<<"Which numbre do you want to remove? "<<endl;
			cout<<"Answer: ";
			cin>>ans;
			sacar(ans);
			mostrar();
		}
		else
			break;
	}
	system("pause");
	return 0;
}


Just a bit of help would be nice

This post has been edited by poncho4all: 01 September 2009 - 11:40 PM

Was This Post Helpful? 0
  • +
  • -

#3 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Linked List and order

Posted 02 September 2009 - 06:10 AM

Have you stepped through this in the debugger? That's where I'd start.
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Re: Linked List and order

Posted 02 September 2009 - 07:00 AM

I don't know why you have a head and a tail. I don't know why it's global, but that's bad. Also, your naming conventions are messing with me. ;)

For no globals or tail, consider this:
#include <iostream>

using namespace std;

struct Node{
	int dato;
	Node *link;
};

void meter(Node **inicio, int num){
	Node *t=new Node;
	t->dato=num;
	
	if(*inicio==NULL || num < (*inicio)->dato) {
		t->link=*inicio;
		*inicio = t;
	} else {
		Node *t2 = *inicio;
		while(t2->link!=NULL && num > t2->link->dato){
			t2=t2->link;
		}
		t->link=t2->link;
		t2->link=t;
	}
}

void mostrar(Node *t){
	while (t!=NULL) {
		cout<<t->dato<<endl;
		t=t->link;
	}
}

int main(){
	Node *inicio = NULL;
	
	meter(&inicio, 3);
	meter(&inicio, 1);
	meter(&inicio, 5);
	meter(&inicio, 4);
	meter(&inicio, 2);
	
	mostrar(inicio);
	
	// note, should be freed
	return 0;
}



Even better, wrap the thing in a class; it's OOP, after all.

This post has been edited by baavgai: 02 September 2009 - 07:01 AM

Was This Post Helpful? 1
  • +
  • -

#5 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Linked List and order

Posted 02 September 2009 - 03:30 PM

Sry about the naming but my teacher knows only spanish, and he wont let me use classes since we haven't seen that subject yet.
With the "note, should be freed" did you meant node?
and wich one should be freed? the "inicio"?
If you meant the inicio as in should be freed of taking all the data out of it, it is done with the function "sacar". The only thing is that it doesnt take out every single one just the one that the user asks to take of.
So for what i have seen so far in your program my problem was i had to many condition and "inicio" as global right?

Also i wanted to thank you for the help.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Re: Linked List and order

Posted 02 September 2009 - 05:58 PM

View Postponcho4all, on 2 Sep, 2009 - 04:30 PM, said:

With the "note, should be freed" did you meant node?


"Note" perhaps doesn't translate well. Essentially meaning, take notice, pay attention, etc.

A linked list should delete all it's nodes before the program ends. In practice, this is not strictly required if you're exiting. However if you wished to free the list in the middle of program execution, you'll need it.

Here's where you show the list:
void mostrar(Node *t){
	while (t!=NULL) {
		cout<<t->dato<<endl;
		t=t->link;
	}
}



Here's where you kill it. Note, a pointer pointer so you can null out the head.
// matar?
void deleteList(Node **inicio){
	Node *p = *inicio;
	while (p!=NULL) {
		Node *t = p;
		p=p->link;
		delete t;
	}
	// delete doesn't actually remove the value from the pointer
	// just frees the memory
	// null out your pointers if some var still points them
	*inicio=NULL; 
}



I don't want to give away "sacar", but it's a lot like the ordered insert. You move through the list, looking at the next node while keeping the prior. When you find the one you want to kill, you point the prior next at the next next and kill the middle node you just orphaned.


View Postponcho4all, on 2 Sep, 2009 - 04:30 PM, said:

So for what i have seen so far in your program my problem was i had to many condition and "inicio" as global right?


Quite. Globals are just generally bad form; your instructor should yell at you for using them. There are times when you will track both the head and the tail of a linked list. However, if you don't have to, don't.

Keeping things simple is surprisingly hard. Once you get the basics, programing is more an organizational challenge than anything else.
Was This Post Helpful? 0
  • +
  • -

#7 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Linked List and order

Posted 02 September 2009 - 07:25 PM

Thank much sir xD
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1