C++

Forum

 
About swap two pointers.

gongzhen (32)
Hello Guys. I am writing a data structure about Linked-List. I want to sort my linked list from small to large. Now I got problem about my sorting function. I passed two pointers in the swap function but it does not sort like I thought. Actually it never sort my linked-list.
Any good ideas?
My Node's structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class Node
{
public:
    Node();
    Node(int data);
    ~Node();

    void setData(int data);
    int getData();

    void setNext(Node* next);
    Node* getNext()const;///const can help complier to tell different function overloaded.
    Node*& getNext();

    void setPrevious(Node* previous);
    Node* getPrevious()const ;
    Node*& getPrevious();

private:
    int m_data;
    Node* m_next;
    Node* m_previous;
};

List Structure
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
 
using namespace std;
class List
{
    public:
    List();
    ~List();
    unsigned int getNode();

    void pushFront(int data);
    void pushBack(int data);

    void popFront();
    void popBack();

    void insert(int data);
    void remove(int data, bool type);

    bool find(int data);
    bool findRecursive (int data);
    bool findRecursive(int data, Node* ptr);

    friend ostream& operator<<(ostream& outStream, const List& object);

    void clear();
    void clearRecursive(Node*& ptr);

    int getData();
    void sort();
    void swap(Node *&ptr1, Node *&ptr2);
    void print();

    private:
    unsigned int m_nodeCount;
    Node* m_head;
    Node* m_tail;

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
void List::sort()
{
    if(m_head!=NULL)
    {
        Node* ptr=m_head;
        int min = ptr ->getData();
        for(int i=0; i<m_nodeCount, ptr->getNext()!=NULL; i++, ptr = ptr->getNext())
        {
            if(min>=ptr->getNext()->getData())
            {
                swap(ptr, ptr->getNext());
            }
        }
    }
}
void List::swap(Node *&ptr1, Node *&ptr2)
{
    Node *tmp;
    tmp = ptr1;
    ptr1 = ptr2;
    ptr2 = tmp;
}

Please help me about the swap function. thanks
Last edited on
writetonsharma (1461)

would it be better if you only swap values and not pointer's? for pointer's you may have to update the next and prev pointer's also.


for the sorting you can use this and see if this works for you:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
void List::sort() //insertion sort
{
	if(m_head->getNext() != NULL)		//should have at least two nodes
    {
		Node *ahead = m_head->getNext();

		for(int i = 0; i < m_nodeCount - 1; i++, ahead = ahead->getNext())
		{
			Node *behind = ahead->getPrevious();

			while((*ahead > *behind) && behind != m_head)
			{
				behind = behind->getPrevious();
			}

			if(*behind > *ahead)
			{
				swap(&behind, &ahead);
			}
		}
    }
}


you will have to overload > operator..

1
2
3
4
5
6
7
 
void List::swapValues(Node **ptr1, Node **ptr2)
{
  
	int temp = (*ptr1)->getData();
	(*ptr1)->setData((*ptr2)->getData());
	(*ptr2)->setData(temp);
}
Topic archived. No new replies allowed.