Hi guys!
I am wondering how can one perform a sorted merge between the calling object list and the the passed in list?
Here is what I have got so far :
Code:
1.
#include<iostream>
2.
3.
using namespace std;
4.
5.
#define NULL 0
6.
7.
template <typename T>
8.
class DoublyLinkedList;
9.
10.
template <typename T>
11.
class Node
12.
{
13.
friend class DoublyLinkedList<T>;
14.
public:
15.
Node()
16.
{next = this; prev = this;}
17.
Node(const T& data, Node<T> *next = NULL, Node<T> *prev = NULL)
18.
{this ->data = data; this ->next = next;
19.
this ->prev = prev;}
20.
private:
21.
T data;
22.
Node<T> *next;
23.
Node<T> *prev;
24.
};
25.
26.
template <typename T>
27.
class DoublyLinkedList
28.
{
29.
public:
30.
DoublyLinkedList();
31.
DoublyLinkedList(T arr[], T arrSize);
32.
~DoublyLinkedList();
33.
Node<T> *insert(Node<T> *insertionPoint, const T& data);
34.
void addSortedList(const DoublyLinkedList<T>& list2);
35.
void display();
36.
private:
37.
Node<T> *header;
38.
int size; // number of data nodes in list
39.
};
40.
41.
template<typename T>
42.
DoublyLinkedList<T>::DoublyLinkedList()
43.
{
44.
header = new Node<T>();
45.
size = 0;
46.
}
47.
48.
template<typename T>
49.
DoublyLinkedList<T>::DoublyLinkedList(T arr[], T arrSize)
50.
{
51.
header = new Node<T>();
52.
size = arrSize;
53.
for (int i = 0; i < size; i++)
54.
{
55.
insert(header->prev, arr[i]);
56.
}
57.
}
58.
59.
template<typename T>
60.
DoublyLinkedList<T>::~DoublyLinkedList()
61.
{
62.
while (header->next != header)
63.
{
64.
Node<T>* next = header ->next;
65.
header = next;
66.
}
67.
delete header;
68.
}
69.
70.
template<typename T>
71.
Node<T> *DoublyLinkedList<T>::insert(Node<T> *insertionPoint, const T& data)
72.
{
73.
Node<T> *prevNodePtr;
74.
Node<T> *newNodePtr;
75.
prevNodePtr = insertionPoint ->prev;
76.
newNodePtr = new Node<T>(data, insertionPoint, prevNodePtr);
77.
size++;
78.
insertionPoint ->prev = prevNodePtr->next = newNodePtr;
79.
return newNodePtr;
80.
}
81.
82.
template<typename T>
83.
void DoublyLinkedList<T>::addSortedList(const DoublyLinkedList<T> &list2)
84.
{
85.
DoublyLinkedList<T> current = list2;
86.
DoublyLinkedList<T> *next;
87.
while(header->next != header)
88.
{
89.
if (current.header->next < list2.header-> next)
90.
{
91.
header->next = current.header;
92.
current.header = current.header ->next;
93.
}
94.
else
95.
{
96.
header->next = list2.header;
97.
//list2.header = list2.header ->next;
98.
}
99.
100.
}
101.
}
102.
103.
template<typename T>
104.
void DoublyLinkedList<T>::display()
105.
{
106.
if(header->next == header)
107.
{
108.
cout<<"the list is empty"<<endl;
109.
}
110.
else
111.
{
112.
Node<T> *next = header ->next;
113.
header = next;
114.
cout<<header;
115.
}
116.
}
my driver :
Code:
1.
#include "DoublyLinkedList.h"
2.
3.
int main()
4.
{
5.
int arrA[] = {30,90,95};
6.
int arrB[] = {10,20,40,95, 100};
7.
int arrASize = sizeof(arrA)/sizeof(int);
8.
int arrBSize = sizeof(arrB)/sizeof(int);
9.
10.
DoublyLinkedList<int> listA(arrA, arrASize);
11.
DoublyLinkedList<int> listB(arrB, arrBSize);
12.
DoublyLinkedList<int> listC;
13.
14.
listC.display();
15.
listA.display();
16.
listA.addSortedList(listB);
17.
listA.display();
18.
listB.display();
19.
return 0;
20.
}
This should print
Empty linked list
30 90 95
10 20 30 40 90 95 100
30 90 95
I need help in addSortedList function, I think.
Thank you,
02-Dec-2009, 20:01
Problems with the Navy (Officers) by crystalattice
Similar Threads
