#include <iostream>
using namespace std;
struct Node {
struct Node *prev;
struct Node *next;
char data;
};
class DoubleLink {
public:
void dInsert(char ch);
void dInsert(char ch, char pos);
void dReverse();
void dOut();
DoubleLink() { head = NULL; };
private:
struct Node *head;
void exchangeNode(struct Node *p1, struct Node *p2);
};
void DoubleLink::dInsert(char ch)
{
struct Node *p = new Node;
p->data = ch;
if (head == NULL) {
head = p;
head->next = head->prev = p;
} else {
p->prev = head->prev;
p->next = head;
head->prev->next = p;
head->prev = p;
}
}
void DoubleLink::dInsert(char ch, char pos)
{
struct Node *p, *nodePos, *insertPos;
p = new Node;
p->data = ch;
if (head == NULL) {
head = p;
head->next = head->prev = p;
} else {
nodePos = head;
while (nodePos != NULL) {
if (nodePos->data == pos) {
insertPos = nodePos;
}
nodePos = nodePos->next;
if (nodePos == head)
break;
}
p->prev = insertPos->prev;
p->next = insertPos;
insertPos->prev->next = p;
insertPos->prev = p;
}
}
void DoubleLink::dReverse()
{
struct Node *front, *end;
front = head;
end = head->prev;
while (front != end && (front == head || front->prev != end)) {
exchangeNode(front, end);
front = front->next;
end = end->prev;
}
}
void DoubleLink::exchangeNode(struct Node *p1, struct Node *p2)
{
char tmp;
tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
}
void DoubleLink::dOut()
{
struct Node *p = head;
cout << "Output link: " << endl;
if (p != NULL) {
cout << p->data << " ";
for (p = p->next; p != head; p = p->next)
cout << p->data << " ";
cout << endl;
}
}
int main()
{
DoubleLink dLink;
cout << "Gen Double link" << endl;
dLink.dInsert('a');
dLink.dInsert('b');
dLink.dInsert('c');
dLink.dInsert('d');
dLink.dInsert('e');
dLink.dInsert('f');
dLink.dOut();
cout << "Reverse Double link" << endl;
dLink.dReverse();
dLink.dOut();
cout << "Insert g beyond a" << endl;
dLink.dInsert('g', 'a');
dLink.dOut();
return 0;
}
评论0