ListNode.h
#pragma once
#include<iostream>
using namespace std;
#include<stdlib.h>
template<class T>class LinkList;//为了实现友元,前向定义
template<class T>
class ListNode
{
friend class LinkList<T>;
private:
T data;
ListNode<T>* next;
public:
ListNode(ListNode<T>* ptrnext = NULL)
{
next = ptrnext;
}
ListNode(const T& item, ListNode<T>* ptrnext = NULL)
{
data = item;
next = ptrnext;
}
~ListNode() {}
};
LinkList.h
#pragma once
#include"ListNode.h"
template <class T>
class LinkList
{
private:
ListNode<T>* head;
int size;
public:
LinkList();//构造
~LinkList();//析构
ListNode<T>* Index(int i);//定位
T Delete(int i);//删除
T GetData(int i);//取数据元素
void PrintList();
void OrderInsert(T x);//有序插入
int GetSize()const;//取长度
};
//构造
template<class T>
LinkList<T>::LinkList()
{
head = new ListNode<T>();
size = 0;
}
//析构
template<class T>
LinkList<T>::~LinkList()
{
ListNode<T>* p, * q;
p = head;
while (p != NULL)
{
q = p;
p = p->next;
delete p;
}
size = 0;
head = NULL;
}
//取长度
template<class T>
int LinkList<T>::GetSize()const
{
return size;
}
//定位
template<class T>
ListNode<T>* LinkList<T>::Index(int i)
{
if (i<-1 || i>GetSize() - 1)
{
cout << "i越界" << endl;
exit(0);//退出
}
if (i == -1)
{
return head;
}
else
{
ListNode<T>* p = head->next;
int k = 0;
while (p != NULL && k < i)
{
p = p->next;
k++;
}
return p;
}
}
//取数据元素
template<class T>
T LinkList<T>::GetData(int i)
{
if (i<0 || i>GetSize() - 1)
{
cout << "i越界" << endl;
exit(0);//退出
}
else
{
ListNode<T>* p = Index(i);
return p->data;
}
}
//输出
template<class T>
void LinkList<T>::PrintList()
{
for (int i = 0; i < GetSize(); i++)
{
cout << GetData(i) << " ";
}
cout << endl;
}
//有序插入
template<class T>
void LinkList<T>::OrderInsert(T x)
{
ListNode<T>* curr, * pre;
curr = head->next;
pre = head;
while (curr != NULL && curr->data <= x)
{
pre = curr;
curr = curr->next;
}
ListNode<T>* p = new ListNode<T>(x, pre->next);
pre->next = p;
size++;
}
#include"LinkList.h"
//合并
template<class T>
void Merge(LinkList<T>L1, LinkList<T>L2)
{
T temp;
for (int i = 0; i < L2.GetSize(); i++)
{
temp = L2.GetData(i);
L1.OrderInsert(temp);
}
}
int main()
{
LinkList<int>list1, list2;
int x;
cout << "创建链表1;" << endl;
cout << "输入元素:";
cin >> x;
while (x != 0)
{
list1.OrderInsert(x);
cout << "输入元素:";
cin >> x;
}
cout << "输出链表1:";
list1.PrintList();
cout << "创建链表2;" << endl;
cout << "输入元素:";
cin >> x;
while (x != 0)
{
list2.OrderInsert(x);
cout << "输入元素:";
cin >> x;
}
cout << "输出链表2:";
list2.PrintList();
Merge(list1, list2);
cout << "合并后的链表:";
list1.PrintList();
return 0;
}