/*header.h*/

#pragma once
#include
using namespace std;
template
struct LinkNode //节点类定义
{
T data; //数据域
LinkNode *next; //链指针域
LinkNode(LinkNode *ptr = NULL){this->next = ptr;} //初始化指针域的构造函数
LinkNode(const T& item, LinkNode *ptr = NULL)//初始化数据成员和指针成员和指针的构造函数
{
this->data = item;
this->next = ptr;
}
};

template
class List //用头结点的数据域表示链表元素数量
{
protected:
LinkNode *first;
public:
List(){first = new LinkNode;first->data = 0;}//无参数构造
List(const T& x)
{
this->first = new LinkNode;
//first->data = 1;
this->inputHead(x);
}//含有参数的构造函数
List(List& L);//拷贝构造
~List(){makeEmpty();}//析构函数
void makeEmpty();//将链表置空的函数
int Length()const{return this->first->data;}//计算链表长度的函数
LinkNode* getHead()const{return this->first;}//返回附加头结点地址
LinkNode* getRear()const;//返回尾部指针
void inputHead(T head);//头插
void inputRear(T rear);//尾插
void output();//将链表打印出来
bool IsEmpty()const{return !this->first->data;}
void Sort();//排序
bool Insert(int i, T& x);//在第i个位置插入x
bool Remove(int i, T& x);//删除第i个元素，将第i个元素的data赋值给x
T *getData(int i);//返回第i个元素的data地址
void setData(int i, T& x);//将第i个元素的data值更改为x
LinkNode *Search(T x);//查找链表中第一个含有data为x的元素，返回x节点指针
LinkNode *Locate(int i);//返回第i个元素的指针
List& operator=(List& L);//符号重载，赋值

};
template
List& List::operator=(List& L)
{
if(!L.IsEmpty())
{
LinkNode *srcptr = L.first, *desptr = this->first;
while(srcptr->next != NULL)
{
desptr->data = srcptr->data;
desptr->next = new LinkNode;
srcptr = srcptr->next;
desptr = desptr->next;
}
desptr->data = srcptr->data;
}
　　　　return *this;
}
template
LinkNode* List::Locate(int i)//找第i个元素，找到返回地址，找不到返回头结点地址
{
if(i>0 && ifirst->data)
{
int j = 0;
LinkNode *tmp = this->first;
while(j!=i)
{
tmp = tmp->next;
++j;
}
return tmp;
}
return this->first;
}
template
LinkNode* List::Search(T x)
{
if(!this->IsEmpty())
{
LinkNode *tmp = this->first->next;
while(tmp->data!=x && tmp->next!=NULL)
{
tmp = tmp->next;
}
if(tmp->data==x)
return tmp;
}
return this->first;
}
template
void List::setData(int i, T& x)
{
if(i>0 && i<=this->first->data)
{
int j = 0;
LinkNode *tmp = this->first;
while(j!=i)
{
tmp = tmp->next;
++j;
}
tmp->data = x;
}
}
template
T* List::getData(int i)
{
if(i>0 && i<=this->first->data)
{
LinkNode *tmp = this->first;
int j = 0;
while(j!=i)
{
tmp = tmp->next;
++j;
}
return &tmp->data;
}
}
template
bool List::Remove(int i, T& x)
{
if(i>0 && i<=this->first->data)
{
LinkNode *tmp = this->first, *p;
if(i!=1)
{
int j = 0;
while(j!=i-1)
{
tmp = tmp->next;
++j;
}
p = tmp->next;
tmp->next = p->next;
x = p->data;
delete p;
}
else
{
p = tmp->next;
x = p->data;
tmp->next = p->next;
delete p;
}
--this->first->data;
return true;
}
return false;
}
template
bool List::Insert(int i, T& x)
{
if(i>0 && ifirst->data+2)
{
if(i == this->first->data+1)
{
this->inputRear(x);
return true;
}
else if(i == 1)
{
this->inputHead(x);
return true;
}
int j = i-1;
LinkNode *tmp = new LinkNode, *p = this->first;
tmp->data = x;
while(j)
{
p = p->next;
--j;
}
tmp->next = p->next;
p->next = tmp;
++this->first->data;
return true;
}
else
return false;

}
template
void List::Sort()//排序有两类方法，一种是改变指针指向的，一种是仅为元素data排序，而不改变指针指向
{
if(this->first->data > 1)
{
int i = this->first->data, j;
LinkNode *p = this->first, *q;
while(i)
{
p = p->next;
q = p->next;
j = i - 1;
while(j)
{
if(p->data > q->data)
{
p->data = p->data + q->data;
q->data = p->data - q->data;
p->data = p->data - q->data;
q = q->next;
}
--j;
}
--i;
}
}
}
template
void List::inputHead(T head)
{
LinkNode *tmp = new LinkNode;
if(tmp == NULL)
{
cerr<<"内存分配错误！\n"<<endl;
exit(-1);
}

if(this->first->next != NULL)  
{  
    tmp->next = this->first->next;  
    this->first->next = tmp;  
}  
else  
{  
    this->first->next = tmp;  
    tmp->next = NULL;  
}  
tmp->data = head;  
++this->first->data;

}
template
void List::inputRear(T rear)
{
LinkNode *tmp = new LinkNode;
if(tmp == NULL)
{
cerr<<"内存分配错误！\n"<<endl;
exit(-1);
}

LinkNode<T> \*p = this->getRear();  
p->next = tmp;  
tmp->data = rear;  
++this->first->data;

}
template
void List::output()
{
LinkNode *p = this->first->next;
while(p!=NULL)
{
cout<data<<"—>";
p = p->next;
}
cout<<"over"<
List::List(List& L)
{
T value;
LinkNode *srcptr = L.getHead();
LinkNode *desptr = this->first = new LinkNode;
this->first->data = srcptr->data;
while(srcptr->next != NULL)
{
value = srcptr->next->data;
desptr->next = new LinkNode(value);
desptr = desptr->next;
srcptr = srcptr->next;
}
desptr->next = NULL;
}
template
void List::makeEmpty()
{
LinkNode *p, *q = this->first->next;
this->first->data = 0;
while(q != NULL)
{
p = q;
q = q->next;
delete p;
}
}
template
LinkNode* List::getRear()const
{
LinkNode *p = this->first;
while(p->next!=NULL)
p = p->next;
return p;

}
/*
template
int List::Length()const
{
LinkNode *p = this->first->next;
int count = 0;
while(p != NULL)
{
++count;
p = p->next;
}

};*/

一个含有头结点的单链表，链表头节点的数据与保存链表长度。

顺序表适合随机读，链表适合随机写，随机删除。

/*main.cpp*/

#include"header.h"
int main()
{
const int o = 10;
List L(0),M;
for(int i=100; i<=110; ++i)
L.inputHead(i);

//for(int i=0; i<=10; ++i)  
//  L.inputRear(i);  
L.output();  
int i = 2111;  
L.Insert(1, i);  
L.output();  
L.Sort();  
L.output();  
L.Remove(1, i);  
cout<<i<<endl;  
L.output();  
cout<<\*L.getData(1)<<endl;i = 1;  
L.setData(12, i);  
L.output();  
cout<<L.Search(100)<<endl;  
M = L;  
M.output();  
return 0;  

}

　运行结果如下