链表的基本操作及链表的有序合并

#include <stdlib.h>
#include <iostream>
using namespace std;


template <class Type>
struct Node {
Type data;
Node * next;
};


template <class Type>
class Link
{
private :
Node<Type> * head;
public:
Link();
~Link();
void InsertNode(Type data);
void InsetNodeAt(int position , Type data);
Node<Type> * GetAt(int position);
void DeleteNodeAt(int position);
void DeleteHead();
void InverseLink();
void MergeLink( Node<Type> * );
Node<Type> * GetHead();
void InsertMerge(Node<Type> *, Node<Type> *);
void InsertNode(Node<Type> * );
void PrintLink();


void Display_everyone(Node<Type> * );
};


template<class Type>
inline Link<Type>::Link()
{
head = NULL;
}


template<class Type>
inline Link<Type>::~Link()
{
while ( head )
{
Node<Type> * temp = head;
head = head->next;
delete temp;
}
}


template<class Type>
inline void Link<Type>::InsertNode(Type data )
{
Node<Type> * tempNode = new Node<Type>;
tempNode->data = data;
tempNode->next = head;
head = tempNode;
}


template<class Type>
inline void Link<Type>::InsetNodeAt(int position, Type data)
{
Node<Type> * preTempNode = GetAt(position);
if (preTempNode == NULL )
{
cout << "链表为空或输入位置越界！" << endl;
return;
}
Node<Type> * tempNode = new Node<Type>;
tempNode->data = data;
tempNode->next = preTempNode->next;
preTempNode->next = tempNode;
}


template<class Type>
inline Node<Type>* Link<Type>::GetAt(int position)
{
int count = 0;
Node<Type> * tempNode = head;
while (tempNode)
{
if ( count == position )
{
return tempNode;
}
tempNode = tempNode->next;
count++;
}
return NULL;
}


template<class Type>
inline void Link<Type>::DeleteNodeAt(int position)
{
if ( position == 0 )
{
DeleteHead();
return;
}
Node<Type> * preTemp = GetAt(position - 1);
Node<Type> * temp = GetAt(position);
if ( preTemp == NULL || temp == NULL )
{
cout << "输入位置越界！" << endl;
return;
}
preTemp->next = temp->next;
delete temp;
}


template<class Type>
inline void Link<Type>::DeleteHead()
{
Node<Type> * temp = head;
head = head->next;
delete temp;
}


template<class Type>
inline void Link<Type>::InverseLink()
{
Node<Type> * current = head;
Node<Type> * next = NULL;
Node<Type> * result = NULL;
while ( current )
{
next = current->next;
current->next = result;
result = current;
current = next;
}
head = result;
}


template<class Type>
inline void Link<Type>::MergeLink(Node<Type> * p_head)
{
Node <Type> * newHead = NULL;
while ( p_head && head )
{
if ( head->data >= p_head->data )
{
Node<Type> * temptr = head ;
head = head->next;
temptr->next = newHead;
newHead = temptr;
cout << "上："; Display_everyone(newHead);
cout << "head=" ;Display_everyone(head);
cout << "p_head=";Display_everyone(p_head);
cout << endl; 

}
else
{
Node<Type> * temptr = p_head;
p_head = p_head->next;
temptr->next = newHead;
newHead = temptr;
cout << "下："; Display_everyone(newHead);
cout << "head=" ;Display_everyone(head);
cout << "p_head=";Display_everyone(p_head);
cout << endl; 
}
}
cout << "输出局部新链表：：";
Display_everyone(newHead); cout << endl;
while (head)
{
Node<Type> * temptr = head;
head = head->next;
temptr->next = newHead;
newHead = temptr;
}
while (p_head )
{
Node<Type> * temptr = p_head;
p_head = p_head->next;
temptr->next = newHead;
newHead = temptr;
}
cout << "再次验证新链表：：";
Display_everyone(newHead); cout << endl;
head = newHead;
}


template<class Type>
inline void Link<Type>::InsertNode(Node<Type>* p_node )
{
Node<Type> * ptr = head;
while ( head )
{
if ( ptr->data >= p_node->data )
{
p_node->next = ptr->next;
ptr->next = p_node;
return;
}
ptr = ptr->next;
}
}


template<class Type>
inline Node<Type> * Link<Type>::GetHead()
{
return head;
}


template<class Type>
inline void Link<Type>::PrintLink()
{
if ( head == NULL )
{
cout << "链表为空！" << endl;
return;
}
Node<Type> * tempPtr = head;
while ( tempPtr )
{
cout << tempPtr->data << " ";
tempPtr = tempPtr->next;
}
cout << endl;
}


template<class Type>
inline void Link<Type>::Display_everyone(Node<Type>* head )
{
if( !head )
{
cout << "空！"<< endl ;
return ;
}
Node<Type> * ptr = head;
while ( ptr )
{
cout << ptr->data << " ";
ptr = ptr->next;
}
cout << endl;
}


const int N = 10;
int BEGIN = 1;


void BuildLink(Link<int> * );


int main()
{
cout << "建立链表：\n";
Link<int> myLink;
BuildLink(&myLink);
myLink.PrintLink();


/*cout << "插入节点：";
myLink.InsetNodeAt(2, 999);
myLink.PrintLink();


cout << "删除结点：";
myLink.DeleteNodeAt(3);
myLink.PrintLink();


cout << "倒置结点：";
myLink.InverseLink();
myLink.PrintLink();*/


//cout << "合并链表：" << endl ;
Link<int> mergeLink;
BuildLink(&mergeLink);
mergeLink.PrintLink();


myLink.MergeLink( mergeLink.GetHead() );


cout << "合并后的新链表：";
myLink.PrintLink();
cout << "合并后的新链表：";
myLink.PrintLink();
cout << "合并后的新链表：";
myLink.PrintLink();
cout << "合并后的新链表：";
myLink.PrintLink();
cout << "--->建立的新表：";
mergeLink.PrintLink();
system("pause");
//exit(0);
    return 0;
}


void BuildLink(Link<int> * myLink)
{
for ( int i = BEGIN ++ ; i <= N; i+= 2 )
{
myLink->InsertNode(i);
}

}

参考一下这个也很好：http://www.geeksforgeeks.org/archives/3622

英语四级水平应该够了