deletion of duplicate

[usha]

hello,
i am very happy for the answers which u have given me.
Now i have a problem in deleting duplicate elements in a linked list after sorting.
I am giving u the sample code below.Please verify it out and replace the error

void sort(struct node *x)//x is the initial address
{
struct node *p,*q,*r;
int temp;
p = q = x;
r = p->link;
while(r!=NULL)
{
while(r!=NULL)
{
if(p->data >r->data)
{
temp = r->data;
r->data = p->data;
p->data = temp;
}
else
{
if(p->data == r->data)
{
while(q->link!=r)
q=q->link;

q->link = r->link;
}

q=x;
r = r->link;
}
p = p->link;
r = p->link;
}
}
}

here i am able to delete any repetitive element.But not the last repetitive element.
usha

[i3839]

I don't know how your program uses that list, nor if nodes are used directly anywhere else, but what you do now is a bit dangerous. This because you move data values around and keep the nodes in the same place. Because of this nodes and their data aren't coupled, so you can't use nodes as a reference to the data anywhere. So simple code like the following won't work:


struct node* new = malloc(sizeof(struct node));

new->data = x;
add_to_list(somelist, new); // sorted here with your sort function
add_to_list(anotherlist, new); // Oops, new->data may have changed


To avoid vague behaviour like this it's much better to move nodes around instead of their data. So change the 'link' values instead.

Also are you sure that the thing works? Those two while loops check for the same condition, so effectively it's just one while loop. If it really works you have invented the fastest sorting algorithm there is. ;-) So try it out on something like "5 3 1 9 2 4".

Just curious, but what sorting algorithm are you trying to implement? Good overview of sorting algorithms: http://en.wikipedia.org/wiki/Sorting_algorithm

It may be useful to make basic list functions like node_add(list, newnode), node_remove(list, node) and node_add_after(list, node, newnode) and use those to implement the rest.


(Why didn't you use code tags? Did you read the big text at the top of your new post? Do you have any suggestions on how we could make it more clear that people should use code tags when posting code? Because the huge text is ignored by a lot of people, not only you, so it doesn't seem to work that well.)

[usha]

I don't know how your program uses that list, nor if nodes are used directly anywhere else, but what you do now is a bit dangerous. This because you move data values around and keep the nodes in the same place. Because of this nodes and their data aren't coupled, so you can't use nodes as a reference to the data anywhere. So simple code like the following won't work:


struct node* new = malloc(sizeof(struct node));

new->data = x;
add_to_list(somelist, new); // sorted here with your sort function
add_to_list(anotherlist, new); // Oops, new->data may have changed


To avoid vague behaviour like this it's much better to move nodes around instead of their data. So change the 'link' values instead.

Also are you sure that the thing works? Those two while loops check for the same condition, so effectively it's just one while loop. If it really works you have invented the fastest sorting algorithm there is. ;-) So try it out on something like "5 3 1 9 2 4".

Just curious, but what sorting algorithm are you trying to implement? Good overview of sorting algorithms: http://en.wikipedia.org/wiki/Sorting_algorithm

It may be useful to make basic list functions like node_add(list, newnode), node_remove(list, node) and node_add_after(list, node, newnode) and use those to implement the rest.


(Why didn't you use code tags? Did you read the big text at the top of your new post? Do you have any suggestions on how we could make it more clear that people should use code tags when posting code? Because the huge text is ignored by a lot of people, not only you, so it doesn't seem to work that well.)




hi
Thanks for ur reply.I dont know whether u understood my problem or not.I am telling u here once again.I have written a program to sort the elements in a linked list. and while sorting i want to delete the elements which r being repeted.
Here i am able to delete the elements any where in the program except the last element.

like for example,if i give the elements,"8,4,8,6",the out put is "4,6,8".But if the last element is the biggest element to be deleted,like"8,4,6,8"then its not showing the output.

thank u
usha

[RobSeace]

And, I don't think you understood i3839's answer... He's telling you that the
code you posted above simply doesn't work at all... And, he's quite right... I
don't know how you think that code will perform any sorting, but it's not going to
work properly... The fact that you can't find duplicates is just a side-issue, really;
the main problem is that your sorting code is completely wrong...

[usha]

And, I don't think you understood i3839's answer... He's telling you that the
code you posted above simply doesn't work at all... And, he's quite right... I
don't know how you think that code will perform any sorting, but it's not going to
work properly... The fact that you can't find duplicates is just a side-issue, really;
the main problem is that your sorting code is completely wrong...


Hi,
U said that my code doesnt work at all.Keeping aside the issue of finding duplicates,my code is working properly.
It is able to sort out the elements in a very proper way.

[RobSeace]

Um, I'm sorry, but no it's not... Unless you're using some code different from
what is posted above... Because, that code up there won't sort anything properly,
unless it happens to already be mostly sorted... What it is doing is walking two
adjoining nodes through the list, and swapping them if necessary... But, that's all
that it does, in one single run-through... That's not going to cut it, I'm afraid... Try
something simple like sorting 4, 3, 2, 1; your code sure looks to MY in-brain C
compiler like it will yield 3, 2, 1, 4, which is very wrong...

[i3839]

I think the code you posted is different from the code you tested. Because if I give your code 8 4 8 6 it returns 4 8 6. And if I give it 5 3 1 9 2 4 it returns 3 1 5 2 4 9. Even a simple 3 2 1 gives 2 1 3 as output.

Code used to test your function:


#include <stdio.h>
#include <stdlib.h>

struct node {
struct node* link;
int data;
};

/* your function unaltered */
void sort(struct node *x){ ... }


int main(int argc, char* argv[])
{
int i;
struct node* n;
struct node list[argc];

if (argc < 3){
printf("Usage: %s <num1> <num2> [num3] ...\n", argv[0]);
return 1;
}
/* build the list */
for (i = 1; i < argc; ++i){
list[i - 1].data = atoi(argv[i]);
list[i - 1].link = &list[i];
}
list[argc - 2].link = NULL;

/* sort it with your function */
sort(list);

n = list;

while (n){
printf("%i ", n->data);
n = n->link;
}
printf("\n");
return 0;
}

[usha]

hi
what u have told is correct.I have verified my code once again.Only the mistake is i have kept extra braces which made u confused. Now removing them i am able to sort the elements. There is no problem with sorting. But only with deleting of duplicate elements . So pls give me a code for the function delete which have to check if there r any duplice elements,and deletes the duplicates.
Thanking u,
Usha

void sort(struct node *x)//x is the initial address
{
struct node *p,*q,*r;
int temp;
p = q = x;
r = p->link;
while(r!=NULL)
{
while(r!=NULL)
{
if(p->data >r->data)
{
temp = r->data;
r->data = p->data;
p->data = temp;
}
else
if(p->data == r->data)
{
while(q->link!=r)
q=q->link;

q->link = r->link;
}

q=x;
r = r->link;
}
p = p->link;
r = p->link;

}} :lol: