线性表之不带头结点的双向循环链表代码,C代码库,德仔网

代码语言

代码分类

【C】线性表之不带头结点的双向循环链表

作者:马德成 / 发布于2012/5/26/ 742

#include<iostream>
using namespace std;
template<typename T>struct node{
T data;
node<T> *prior,*next;
};
template <typename T> class nLink
{
private:
node<T> *head;
public:
nLink()
{
head=NULL;
}
~nLink()
{
clearLink();
}
void clearLink()
{
node<T> *p=head;
if(p!=NULL)
{
p->prior->next=NULL;
do{
p=p->next;
delete head;
head=p;
}
while (p!=NULL);
}
}
bool empty()
{
return head==NULL;
}
int linkLength()
{
node<T> *p=head;
int i=1;
while (p->next!=head)
{
i++;
p=p->next;
}
return i;
}
node<T> *getAddress(int i)
{
node <T> *p=head;
int j=1;
if(i<1 || head ==NULL)
return NULL;
else {
if(i==1)
return p;
do {
j++;
p=p->next;
}while(p!=head && j<i);
if(p==head)
{
return NULL;
}
else return p;
}
}
bool getElem(int i,T &e)
{
node<T> *p;
if(!getAddress(i))
return false;
else {
p=getAddress(i);
e=p->data;
return true;
}
}
bool Insert(int i,T e)
{
node<T> *s,*p=getAddress(i-1);
s=new node<T>;
s->data=e;
if(i==1)
{
if(head==NULL)
{
s->prior=s->next=s;
}
else {
s->next=head;
s->prior=head->prior;
s->next->prior=s;
s->next->prior=s;
}
head=s;
return true;
}
else {
if(p==NULL)
return false;
else {
s->next=p->next;
s->prior=p;
s->next->prior=s;
p->next=s;
return true;
}
}
}
bool deleteElem(int i,T &e)
{
node<T> *p=getAddress(i);
if(p==NULL)
return false;
e=p->data;
if(p->next==p)
{
head=NULL;
}
else {
p->prior->next=p->next;
p->next->prior=p->prior;
if(p==head)
head=p->next;
}
delete p;
return true;
}
void print()
{
node<T> *p=head;
if(p!=NULL)
do{
cout<<p->data<<" ";
p=p->next;
}while(p!=head);
cout<<endl;
}
template <class T>
friend ostream & operator <<(ostream &,nLink<T> &);
template <class T>
friend void MergeLink(nLink<T> &,nLink<T> &);
};
template <class T>
ostream & operator <<(ostream &out,nLink<T> &a)
{
node<T> *p=a.head;
if(p!=NULL)
{
do{
out<<p->data<<" ";
p=p->next;
}while(p!=a.head);
}
out<<endl;
return out;
}
template <class T>
void MergeLink(nLink<T> &a,nLink<T> &b)
{
node<T> *pa,*pb,*p,*t;
pa=a.head;
pb=b.head;
p=new node<T>;
t=p;
if(pa)
pa->prior->next=NULL;
if(pb)
pb->prior->next=NULL;
while(pa && pb)
{
if(pa->data<=pb->data)
{
p->next=pa;
pa->prior=p;
p=pa;
pa=pa->next;
}
else {
p->next=pb;
pb->prior=p;
p=pb;
pb=pb->next;
}
}
while (pa)
{
p->next=pa;
pa->prior=p;
p=pa;
pa=pa->next;
}
while (pb)
{
p->next=pb;
pb->prior=p;
p=pb;
pb=pb->next;
}
p->next=t->next;
t->next->prior=p;
a.head=p->next;
b.head=NULL;
}
int main()
{
nLink<int > La,Lb;
cout<<"La是否为空?"<<boolalpha<<La.empty ()<<endl;
for(int i=1;i<4;i++)
{
La.Insert(i,i);
}
cout<<La;
for(int i=1;i<4;i++)
{
Lb.Insert(i,i+1);
}
cout<<Lb;
MergeLink(La,Lb);
cout<<La;
cout<<Lb;
return 0;
}

试试其它关键字

　双向循环链表　

同语言下

可能有用的

马德成贡献的其它代码(4)