onelink.h

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>
#include "OnelinkNode.h"                   //单链表的结点类

class Onelink                              //单链表类
{
  public:
    OnelinkNode *head;                     //单链表的头指针
    
    Onelink(int n=0);                      //构造函数，以n个自然数建立单链表
    ~Onelink();                            //析构函数
    bool isEmpty()const                    //判断单链表是否为空
    {
        return head==NULL;
    }
    bool isFull()const                     //判断单链表是否已满(总是不满的)
    {
        return false;
    }
    int length()const;                     //返回单链表的长度 
    OnelinkNode* index(int i)const;        //定位，返回指向第i个结点的指针
    int get(int i)const;                   //返回第i个数据元素值
    bool set(int i,int k);                 //设置第i个数据元素值为k
    OnelinkNode* insert(OnelinkNode* p,int k);
                                           //k值插入作为p结点的后继结点
    bool remove(OnelinkNode *p);           //删除p结点的后继结点
    void output(OnelinkNode *p)const;      //输出以p为头指针的单链表 
    void output()const;                    //输出以head为头指针的单链表 
};

Onelink::Onelink(int n)                    //构造函数，以n个自然数建立单链表
{
    head=NULL;                             //n=0时，构造空链表
    if(n>0)                                //构造非空链表    
    {
        int i=1;
        OnelinkNode *rear,*q;
        head=new OnelinkNode(i++);
        rear=head;
        while(i<=n)              
        {
            q=new OnelinkNode(i++);
            rear->next=q;                  //q结点链入rear结点之后
            rear=q;                        //rear指向新的链尾结点
        }
    }
}

Onelink::~Onelink()                        //析构函数
{
    OnelinkNode *p=head,*q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;                         //到达p的后继结点
        delete q;                          //释放q结点所占用的存储单元
    }
    head=NULL;                             //单链表为空
}

int Onelink::length()const                 //返回单链表的长度
{
    int i=0;
    OnelinkNode *p=head;                   //即this->head;
    while(p!=NULL)
    {
        i++;
        p=p->next;
    }
    return i;
}

OnelinkNode* Onelink::index(int i)const    //定位
{                //当0<i<=length()时，返回指向第i个结点的指针；否则返回NULL
    if(i<=0) return NULL;
    int j=0;
    OnelinkNode *p=head;
    while(p!=NULL && j<i)
    {
        j++;
        p=p->next;
    }
    return p;
}

int Onelink::get(int i)const               //返回第i个数据元素值
{
    OnelinkNode *p=index(i);               //定位，p指向第i个结点
    if(p!=NULL)
        return  p->data;
    else 
        return -32768;
}

bool Onelink::set(int i,int k)             //设置第i个数据元素值为k
{
    OnelinkNode *p=index(i);               //定位，p指向第i个结点
    if(p!=NULL)
    {
        p->data=k;
        return true;                       //操作成功
    }
    else
        return false;                      //操作失败
}

OnelinkNode* Onelink::insert(OnelinkNode *p,int k)
{                                          //k值插入作为p结点的后继结点
    OnelinkNode *q=new OnelinkNode(k);     //创建k值结点q
    if(p==NULL)
        p=q;                               //空表插入
    else                                   //表中、表尾插入
    {
        q->next=p->next;                   //q的后继结点应是p的原后继结点
        p->next=q;                         //q作为p的后继结点
    }
    return p;
}

bool Onelink::remove(OnelinkNode *p)       //删除p结点的后继结点
{
    if(p!=NULL)
    {
        OnelinkNode *q=p->next;            //q结点为p结点的后继结点
        if(q!=NULL)
        {
            p->next=p->next->next;         //或者p->next=q->next;
            delete q;
            return true;
        }
    }
    return false;
}

void Onelink::output(OnelinkNode *p)const  //输出以p为头指针的单链表 
{
    while(p!=NULL)
    {
        cout<<p->data<<"  ";
        p=p->next;
    }
    cout<<"\n";
}

void Onelink::output()const                //输出以head为头指针的单链表 
{
    cout<<"Onelink:  ";
    output(head);
}

void output2(Onelink h1)                   //时间复杂度是O(n*n)
{
    for(int i=1;i<=h1.length();i++)        //length()的时间复杂度是O(n)
        cout<<h1.get(i)<<"  ";             //get(i)的时间复杂度是O(n)
    cout<<"\n";
}