1、线性表链式存储结构及基本操作算法实现
(1)单链表存储结构类的定义：
#include <iostream>
using namespace std;
template <class T>
class LinList
{ private:
ListNode <T> *head; //头指针
int size; //当前的数据元素个数
ListNode <T> *Index(int i); //定位
public:
LinList(void); //构造函数
LinList(T a[],int i)
~LinList(void); //析构函数
int Size(void) const; //取当前数据元素
void Insert(const T& e,int i); //插入
T Delete(int i，T& e); //删除
T GetData(int i); //取数据元素
void GetAll(); //取得所有数据
int countnum(); //元素个数
bool isnull(); //判断列表是否为空
void deleteall(); //删除所有节点
};
（2）初始化带头结点空单链表构造函数实现
template <class T>
LinList <T>::LinList() //构造函数
{
head=new ListNode <T>(); //头指针指向头结点
size=; //size的初值为0
}
（３）利用数组初始化带头结点的单链表构造函数实现
template <class T>
LinList <T>::LinList(T a[],int i)
{
head=new ListNode<T>();
size=;
if(int j=;j<i;j++)
{
ListNode<T>*p;
p=new ListNode<T>(a[i],head->next);
head->next=p;
size++;
}
}
（４）在带头结点单链表的第i个位置前插入元素e算法
template <class T>
void LinList<T>::Insert(const T& e,int i); //插入
{
if(i<||i>size-)
{
cout<<"参数i越界出错！"<<endl;
exit();
}
ListNode <T> *p=Index(i-); //p为指向第i-1个结点的指针
//构造新结点q的data域值为item,next域值为p->next
ListNode <T> *q=new ListNode <T> (e,p->next);
p->next=q; //新结点插入第i个结点前
size++; //元素个数加1 }
（５）在带头结点单链表中删除第i个元素算法
template <class T>
T LinList<T>::Delete(int I,T& e); //删除
{
if(size==)
{
cout<<"链表已空无可删"<<endl; }
if(i<||i>size-)
{
cout<<"参数i越界出错！"<<endl;
exit();
}
ListNode <T> *s,*p=Index(i-); //p为指向第i-1个结点指针
s=p->next; //s指向第i个结点
p->next=p->next->next; //第i个结点脱链
T x=s->data;
e=x;
delete s; //释放第i个结点空间
size--; //结点个数减1
return e; //返回第i个结点的data域值
}
（６）遍历单链表元素算法
template <class T>
void LinList<T>::GetAll()
{
for(int i=;i<=size-;i++)
{
cout<<GetData(i)<<" ";
}
cout<<endl;
}
（７）求单链表表长算法。
template <class T>
int LinList<T>::Size(void) const
{
return size;
}
（８）判单链表表空算法
template <class T>
bool LinList<T>::isnull()
{
if(size==)
{
cout<<"为空"<<endl;
return ;
}
else
{
cout<<"非空"<<endl;
return ;
}
}
(９）获得单链表中第i个结点的值算法
template <class T>
T LinList<T>::GetData(int i)
{
if(i<||i>size-)
{
cout<<"参数i越界出错！"<<endl;
exit();
}
ListNode<T>*p=Index(i)
return p->data;
}
主函数调用
#include <iostream>
#include"LinList.h"
using namespace std;
int main()
{
LinList<int>li1335;
int s[]={,,,,,,,,,};
int e;
for(int i=;i<;i++)
li1335.Insert(s[i],i);
li1335.Delete(,e);
li1335.GetAll();
li1335.isnull();
li1335.deleteall();
li1335.isnull();
return ;
}
===========================================================
2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。
（１）利用数组初始化带头结点的单循环链表构造函数实现
template <class T>
CircleList::CircleList(T a[],int n) //创建方式大同小异，唯一的区别就是创建的最后将尾结点指向头结点
{
if(n<)
cout << "你输入的长度不正确 " << endl;
else
{
length = n;
ListNode<T>*p,*q; //定义头尾节点
p = head;
for(int i=;i<n;i++)
{
q = new ListNode<T>();
q->data=a[i];
q->next = head;
p->next = q;
p = q;
}
}
}
（２）在带头结点单循环链表的第i个位置前插入元素e算法
template <class T>
void CircleList::insertNode(int n,T data)
{
Node *q,*p = new Node();
p->data = data;
q = head;
for(int i = ;i<n;i++)
q = q->next;
p->next = q->next;
q->next = p;
length++;
}
（３）在带头结点单循环链表中删除第i个元素算法
template <class T>
void CircleList<T>::deleteNode(int i) //删除i位置的结点
{
if(i<||i>length)
{
cout<<"参数i越界错误\n";
exit();
}
else
{
ListNode<T> *p,*q;
p = head;
for(int j=;j<i;j++)
p=p->next;
q = p->next;
p->next = q->next;
delete q;
q = NULL;
length--;
}
}
３、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。
template<class T>
void sort1(int c,int d,T a[],T b[],LinList<T>li)
{
int amin=,bmin=;
for(int i=;i<c+d;i++)
{
if(amin==c)
{
for(int j=bmin;j<d;j++,i++)
li.Insert(b[j],i);
break;
}
if(bmin==d)
{
for(int j=amin;j<c;j++,i++)
li.Insert(a[j],i);
break;
}
if(a[amin]>b[bmin])
{
li.Insert(b[bmin],i);
bmin++;
}
else if(a[amin]<b[bmin])
{
li.Insert(a[amin],i);
amin++;
}
else
{
li.Insert(a[amin],i);
amin++;
bmin++;
} }
li.GetAll();
}