线性表之不带头结点的单链表代码,C代码库,德仔网

代码语言
代码分类
【C】线性表之不带头结点的单链表
作者:马德成 / 发布于2012/5/26/ 774
线性表之不带头结点的单链表
#include<iostream>
using namespace std;
template<typename T>struct node{
T data;
node<T> *next;
};
template <typename T>class NLink{
private:
node<T> *head;
public:
NLink()
{
head=NULL;
}
~NLink()
{
clearLink();
}
void clearLink()
{
node<T> *p=head;
while(head!=NULL)
{
head=head->next;
delete p;
p=head;
}
}
bool empty()
{
return head==NULL;
}
int linkLength()
{
node<T> *p=head;
int i=0;
while(p!=NULL)
{
i++;
p=p->next;
}
return i;
}
bool getElem(int i,T &e)
{
if(i<0)
return false;
node<T> *p=head;
int j=0;
while(j<i-1 && p!=NULL)
{
j++;
p=p->next;
}
if(j>i-1 || p==NULL)
return false;
e=p->data;
return true;
}
bool insertLink(int i,T e)
{
if(i<1) 
return false;
node<T> *s,*p=head;
int j=1;
s=new node<T>;
s->data=e;
if(i==1)
{
s->next=p;
head=s;
}
else {
while(p!=NULL && j<i-1)
{
j++;
p=p->next;
}
if(p==NULL)
{
return false;
}
else {
s->next=p->next;
p->next=s;
}
}
return true;
}
bool deleteLink(int i,T &e)
{
node<T> *p=head;
if(p==NULL)
return false;
else {
if(i<1 || i>linkLength())
return false;
else {
if(i==1)
{
head=head->next;
delete p;
}
else {
node<T> *q=p->next;
int j=0;
while(q->next!=NULL && j<i-1)
{
j++;
p=q;
q=q->next;
}
if(q==NULL)
return false;
p->next =q->next;
delete q;
return true;
}
}
}
}
void print()
{
node<T> *p=head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
template<class T>
friendostream & operator <<(ostream &,NLink<T> &); 
template <class T>
friend void MergeList(NLink<T>&,NLink<T>&);
template <class T>
friend void MergeList(NLink<T>&,NLink<T>&,NLink<T>&);
};
template<class T>
ostream & operator <<(ostream &out,NLink<T> &a)
{
node<T> *p=a.head;
while (p!=NULL)
{
out<<p->data<<" ";
p=p->next;
}
out<<endl;
return out;
}
template <class T>
void MergeList(NLink<T>&a,NLink<T>&b)
{
node<T> *p,*pa=a.head,*pb=b.head;
p=new node<T>;
while (pa && pb)
{
if(pa->data<=pb->data)
{
p->next=pa;
p=pa;
pa=pa->next;
}
else {
p->next=pb;
p=pb;
pb=pb->next;
}
}
while(pa)
{
p->next=pa;
p=pa;
pa=pa->next;
}
while(pb)
{
p->next=pb;
p=pb;
pb=pb->next;
}
b.head=NULL;
}
template <class T>
void MergeList(NLink<T>&a,NLink<T>&b,NLink<T>&c)
{
node<T> *pa,*pb,*p;
int i=1,j=1,k=0;
T ai,bj;
pa=a.head;
pb=b.head;
while (pa && pb)
{
a.getElem(i,ai);
b.getElem(j,bj);
if(ai<=bj)
{
c.insertLink(++k,ai);
i++;
pa=pa->next;
}
else {
c.insertLink(++k,bj);
j++;
pb=pb->next;
}
}
while (pa)
{
a.getElem(i++,ai);
c.insertLink(++k,ai);
pa=pa->next;
}
while(pb)
{
b.getElem(j++,bj);
c.insertLink(++k,bj);
pb=pb->next;
}
}
int main()
{
NLink<int> La,Lb,Lc;
int e;
for(int i=1;i<4;i++)
{
La.insertLink(i,i);
}
cout<<La;
for(int i=1;i<4;i++)
{
Lb.insertLink(i,i*2);
}
cout<<Lb;
//MergeList(La,Lb);
MergeList(La,Lb,Lc);
cout<<La;
cout<<Lb;
cout<<Lc;
return 0;
}
试试其它关键字
同语言下
可能有用的
马德成贡献的其它代码(4)