C++学习记录13--链表的简单理解

　　内存的动态建立和撤销通过new delete运算符来实现，只有正确理解了在堆内申请空间使用、使用后释放申请的空间，才能更好的理解理解链表的建立。

　　 int *p=new int;
　　 delete p;

　　首先， new int是向堆空间申请了int型数据所需要的空间，然后用int型的指针指向它。使用完成后再用 delete释放掉申请的空间。

一、链表的创建

　　链表最终的形式是这样。如果按照这个图中所画的数据结构来创建，很自然的一个想法是用两个指针head，end分别指向链表开始和结束。用一个中间指针p不断的向堆空间申请结点空间，并将end->link=p;end=p;end->link=0;

datapoint *creat(int n)
{
    datapoint *head=NULL,*end,*p;
for(int i=0;i<n;i++)
    {
        p=new datapoint;
        p->data=rand()%100;
if(!head)
        {
            head=p;
            end=p;
            end->link=0;
        }
else
        {
            end->link=p;
            end=p;
            end->link=0;
        }
    }
return head;
}

　　同时，也可以注意到，end->link是一直等于0的，如果以此未开始，可以少用一个指针，即只用head和p（p用来指向向堆区申请的空间）。如下图所示:
　　

datapoint *creat(int n)
{
    datapoint *head=NULL;
for(int i=0;i<n;i++)
    {
        datapoint *p=new datapoint;
if(head==0)
        {
            head=p;
            head->data=rand()%100;
            head->link=0;
        }
else
        {
            p->link=head;
            head=p;
            head->data=rand()%100;
        }
    }
return head;
}

二、链表的输出

void print(datapoint *head)
{
while(head)
    {
        cout<<head->data<<'\t';
        head=head->link;
    }
    cout<<endl;
}

三、链表的删除（释放已申请的堆空间内存）

　　void del(datapoint *head)
{
    datapoint *p;
while(head)
    {
        p=head->link;    //或 p=head;
        delete head;       // head=head->link;
        head=p;            // delete p;
    }
}
//申请的堆内存空间是一直存在的，无非是选择用head还是p指针来释放。