#define LEN 100
#include <iostream>
using namespace std;
//单链表中结点的类型
template <class T>
struct LNode{
T data;//值域
LNode* next; //指针域
};
template <class T>
class LinkList{
LNode<T> *head;
public:
//不带形参构造函数
LinkList() {
head=new LNode<T>;
head->next=0;
}
//带二个形参构造函数 ,n是初始化元素个数
LinkList(int n) {
T a[LEN+1];
head=new LNode<T>;
LNode<T> *p=head,*q;
for(int i=1;i<=n;i++) {
q= new LNode<T>;
q->data =0;
p->next =q;
p=p->next;
}
p->next =0;
}
//复制构造函数
LinkList(LinkList& HL) {
head=new LNode<T>;
head->next=0;
LNode<T> *p2=HL.head->next ,*p1=head,*q;
while( p2) {
q= new LNode<T>;
q->data=p2->data ;
p1->next =q;
p1=q;
p2=p2->next ;
}
p1->next =0;
}
//析构函数
~LinkList(){//析构函数
LNode<T> *p=head->next ,*q;
while(p) {
q=p->next ;
delete(p);
p=q;
}
delete(head);
}
//清空单链表
void ClearList(){//清空单链表
LNode<T> *p=head->next ,*q;
while(p) {
q=p->next;
delete(p);
p=q;
}
head->next =0;
}
//求单链表长度
int ListSize(){//求单链表长度
LNode<T> *p=head->next ;
int i=0;
while(p) {
i++;
p=p->next ;
}
return i;
}
//检查单链表是否为空
bool ListEmpty() {return ListSize()==0;}
//返回单链表中指定序号的结点值
T& GetElem(int pos) {
LNode<T> *p=head->next ;
int i=1;
while(p){
if(i++==pos)return p->data ;
p=p->next ;
}
return head->data ;
}
//遍历单链表
void TraverseList(void f(T &)){//遍历单链表
LNode<T> *p=head->next ;
while(p) {
f(p->data );
p=p->next ;
}
}
//从单链表中查找元素
bool FindList(T &item){//从单链表中查找元素
LNode<T> *p=head->next ;
while(p) {
if(p->data==item)return 1;
p=p->next ;}
return 0;
}
//单链表la 和lb 的元素按值非递减排列,两个单链表
//合并后的链表也是一个有序的
void MergeList_L(LinkList &la,LinkList &lb) {
LNode<T> *pa=la.head->next ,*pb=lb.head->next ,*p=head;
while(pa&&pb) {
LNode<T> *q=new LNode<T>;
if(pa->data <pb->data ) {
q->data =pa->data;
pa=pa->next ;
p->next =q;
p=q;}
else {
q->data =pb->data;
pb=pb->next ;
p->next =q;
p=q;
}
}
while(pa) {
LNode<T> *q=new LNode<T>;
q->data =pa->data;
pa=pa->next ;
p->next =q;
p=q;
}
while(pb) {
LNode<T> *q=new LNode<T>;
q->data =pb->data;
pb=pb->next ;
p->next =q;
p=q;
}
p->next =0;
}
//向单链表插入元素 , mark=0 插在表首,否则插在表尾
void InsertList(T item,int mark=-1) {
LNode<T> *q= new LNode<T>;
q->data = item;
switch (mark){
case 0: {
q->next = head->next ;
head->next=q;
}
break;
case -1:{
LNode<T> *p=head;
while(p->next) p=p->next;
q->next =0;
p->next =q;
}
break;
default:{
if (mark<-1) return;
int k=mark-1;
LNode<T> *p=head;
while(k&&p->next) {p=p->next;k--;}
q->next=p->next;
p->next=q;
}
break;
}
}
//从单链表中删除元素 , mark为要删除的第几个元素
bool DeleteList(T& item,int mark=0) {
if(ListEmpty()||mark>ListSize())return 0;
LNode<T> *p=head,*q;
if(!mark) {while(p->next->next) p=p->next;item=p->next->data;p->next=0;return 1;}
for(int i=0;i<mark-1;i++)
p=p->next;
item=p->next->data;
q=p->next->next ;
delete(p->next );
p->next=q;
return 1;
}
};
//主函数
int main()
{
LinkList<int> list;
list.InsertList(190); //初始化假设的值
for(int i=0;i!=18;i++) list.InsertList(9); //InsertList是向链尾插入一个数
}
评论0