Duplicates in list
-
you're on the right track. but the key thing that's missing is that the list needs to be sorted before you can be guaranteed that duplicates will show up in p and p->next. duplicates, but p, p->next will never be the same: 1,4,3,5,3 this will work: 1,3,3,4,5
it's getting messy. How to sort a list??? (Doubly linked)
-
it's getting messy. How to sort a list??? (Doubly linked)
You do not need to actually sort the list, since that would mean you first compare a lot of them and move around some nodes, then remove some (the duplicates). That is too much effort for what is needed. What you need to do is compare a lot and remove, but never move. In pseudo-code (always solve an algorithmic problem in pseudo-code first):
foreach(Node n1) {
foreach (Node n2 before n1) {
if (n2.value==n1.value) {
remove(n1);
break;
}
}
}:) PS: and that could be done on a single-linked list as well, as both loops are enumerating from the start and never need to go backward.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
you're on the right track. but the key thing that's missing is that the list needs to be sorted before you can be guaranteed that duplicates will show up in p and p->next. duplicates, but p, p->next will never be the same: 1,4,3,5,3 this will work: 1,3,3,4,5
for(int i = 1; i < N; i++) for(int j = N - 1; j >= i; j--) if(p->key > p->next->key) { t = p->key; p->key = p->next->key; p->next->key = t; } Here is the sort but it doesn' t work
-
You do not need to actually sort the list, since that would mean you first compare a lot of them and move around some nodes, then remove some (the duplicates). That is too much effort for what is needed. What you need to do is compare a lot and remove, but never move. In pseudo-code (always solve an algorithmic problem in pseudo-code first):
foreach(Node n1) {
foreach (Node n2 before n1) {
if (n2.value==n1.value) {
remove(n1);
break;
}
}
}:) PS: and that could be done on a single-linked list as well, as both loops are enumerating from the start and never need to go backward.
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
i did not understand anything you said. And whats that code C++?
-
it's getting messy. How to sort a list??? (Doubly linked)
if you don't want to sort:
for each node, Cur
for each node, Temp
if Temp!=Cur
if Temp.value==Cur.value, duplicate
Temp=Temp.next
Cur=Cur.nextbasically, for each node, you compare its value to every other node. it's inefficient, but it will work. you can also sort your list when you add: 1. walk the list, find the first node with a value greater than the new value. this is 'Cur' 2. change the next pointer of Cur->prev to point to your new node. 3. set your new node's prev to Cur->prev. now you're all linked in the prev direction. 4. change the prev pointer of Cur to point to your new node. 5. set your new node's cur to point to Cur. now you're all linked in the next direction. that way, the list is always sorted, and you can just walk it, looking for duplicates.
-
if you don't want to sort:
for each node, Cur
for each node, Temp
if Temp!=Cur
if Temp.value==Cur.value, duplicate
Temp=Temp.next
Cur=Cur.nextbasically, for each node, you compare its value to every other node. it's inefficient, but it will work. you can also sort your list when you add: 1. walk the list, find the first node with a value greater than the new value. this is 'Cur' 2. change the next pointer of Cur->prev to point to your new node. 3. set your new node's prev to Cur->prev. now you're all linked in the prev direction. 4. change the prev pointer of Cur to point to your new node. 5. set your new node's cur to point to Cur. now you're all linked in the next direction. that way, the list is always sorted, and you can just walk it, looking for duplicates.
OK, I decided to sort the list, but can you tell me why is not working well?
-
for(int i = 1; i < N; i++) for(int j = N - 1; j >= i; j--) if(p->key > p->next->key) { t = p->key; p->key = p->next->key; p->next->key = t; } Here is the sort but it doesn' t work
first problem: you're never moving p
-
first problem: you're never moving p
how to move it? p++
-
how to move it? p++
p = p->next; p = p->prev; (forgot you're inserting at the beginning, not at the end of list) if (p==NULL) bail.
-
p = p->next; p = p->prev; (forgot you're inserting at the beginning, not at the end of list) if (p==NULL) bail.
OK, here is the full code that I' m working on. Can you tell me my mistakes exactly because I can' t understand where to put what. The UniqueList function is important, which now only shows the list and nothing more. The sort does not work...
#include "iostream"
using namespace std;
void Add(int n);
void UniqueList(int N);struct Elem
{
int key;
Elem *prev;
Elem *next;
} *start;int main()
{
int num;
int N = 0;start = NULL; while(cin >> num) { Add(num); N++; } cout << endl; UniqueList(N); return 0;}
void Add(int n)
{
Elem *p = start;
start = new Elem;start->key = n; start->next = p; start->prev = NULL; if(NULL != p) p->prev = start;}
void UniqueList(int N)
{
Elem *p = start;
int t;if(NULL != start) cout << "List:" << endl; else cout << "Empty list!"; for(int i = 1; i < N; i++) for(int j = N - 1; j >= i; j--) { if(p->key > p->next->key) { t = p->key; p->key = p->next->key; p->next->key = t; } } while(NULL != p) { cout << p->key << endl; p = p->next; }}
-
OK, here is the full code that I' m working on. Can you tell me my mistakes exactly because I can' t understand where to put what. The UniqueList function is important, which now only shows the list and nothing more. The sort does not work...
#include "iostream"
using namespace std;
void Add(int n);
void UniqueList(int N);struct Elem
{
int key;
Elem *prev;
Elem *next;
} *start;int main()
{
int num;
int N = 0;start = NULL; while(cin >> num) { Add(num); N++; } cout << endl; UniqueList(N); return 0;}
void Add(int n)
{
Elem *p = start;
start = new Elem;start->key = n; start->next = p; start->prev = NULL; if(NULL != p) p->prev = start;}
void UniqueList(int N)
{
Elem *p = start;
int t;if(NULL != start) cout << "List:" << endl; else cout << "Empty list!"; for(int i = 1; i < N; i++) for(int j = N - 1; j >= i; j--) { if(p->key > p->next->key) { t = p->key; p->key = p->next->key; p->next->key = t; } } while(NULL != p) { cout << p->key << endl; p = p->next; }}
Just the sort?
-
Just the sort?
maybe it's best to rethink this from the beginning. if your goal is to have a list with no duplicates, the easiest thing to do is to simply not add duplicates. so, every time, you go to add a new Elem, walk through your list and see if you already have an Elem with that key. if you do, don't add anything. to do that, you need a function that can walk through the list and look for an Elem with a given key:
bool haveKey(Elem *p, int k)
{
while (p!=NULL)
{
if (p->key=k) return true;
p = p->next;
}
return false;
}just call that at the top of your Add. if it returns false, don't add anything.
-
maybe it's best to rethink this from the beginning. if your goal is to have a list with no duplicates, the easiest thing to do is to simply not add duplicates. so, every time, you go to add a new Elem, walk through your list and see if you already have an Elem with that key. if you do, don't add anything. to do that, you need a function that can walk through the list and look for an Elem with a given key:
bool haveKey(Elem *p, int k)
{
while (p!=NULL)
{
if (p->key=k) return true;
p = p->next;
}
return false;
}just call that at the top of your Add. if it returns false, don't add anything.
No, the assignment is to add duplicates, but when show the list to show it without them. I think the sort thing will do the job but can' t do it properly.
modified on Monday, April 18, 2011 4:57 PM
-
No, the assignment is to add duplicates, but when show the list to show it without them. I think the sort thing will do the job but can' t do it properly.
modified on Monday, April 18, 2011 4:57 PM
ok, then i would recommend sorting the nodes on input. it is far more efficient than sorting the whole list, and it's actually fairly straightforward. (i outlined it above) unfortunately, i have to leave for the day. so.. good luck!
-
it's getting messy. How to sort a list??? (Doubly linked)
TCPMem wrote:
How to sort a list???
Insert the items in their "sorted" position within the list.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Some people are making such thorough preparation for rainy days that they aren't enjoying today's sunshine." - William Feather