c++链表（详解版）

在自学C++的时候，看到好多人都在提链表，于是就自学了一下，看了很多别人的文章，加入了一些自己的理解，做了一下总结，因为是初学可能会有些问题，希望大家能指正

怎么理解链表 看有个人写的很好，就是说你现在有一个小纸条，上面写着一个抽屉的地址，那个抽屉里有一些你需要的东西，和一个新的写着地址的小纸条，这个小纸条又指向了一个新的抽屉，大体可以这么理解

程序所包含的头文件

#include
#include

using namespace std;

当然如果要做随机顺序的链表的话 最好也包含ctime这个库

第一部分—构建抽屉 既然把装有东西和写有地址的小纸条比作抽屉那么我们不妨先写出抽屉的结构体`

typedef struct listpoint
{
    int data;
    listpoint *next;
}listpoint;

这就是一个最简单的结构体 int data,是一个数字，是我们存在抽屉里的东西 而listpoint *next是一个指向和这个抽屉结构一样的新的抽屉的指针；

我们可以在抽屉里放指向下一个抽屉的指针，自然也就可以在抽屉里放指向上一个抽屉的指针

typedef struct listpoint
{
    int data;
    listpoint *next;
    listpoint *last;
}listpoint;

我们在抽屉里不仅仅可以放一个数，我们可以往里面放一个收纳盒，例如，在下面的结构体中包含了另一个结构体

typedef struct data
{
    int number;
    string name;
    string sex;
}data;

typedef struct listpoint
{
    data *information;
    listpoint *next;
    listpoint *last;
}listpoint;

那个叫做information的小收纳盒里，装着一个人的学号，姓名，性别等信息 /

第二部分—创建一个链表

创建一个基础链表

listpoint *create_normal_list(int n)     /*链表每一个节点都是指向  listpoint结构的指针，所以返回值是listpoint *,n是指创建的链表的节点数目*/
{
    listpoint *head,*normal,*end;/*创建头节点，其他节点，和尾节点*/
    head=(listpoint*)malloc(sizeof(listpoint));
    head->information=(data*)malloc(sizeof(data));
    /*分配内存*/
    end=head;/*最开始最后一个节点就是头节点，注意因为通过指针可以直接对地址上的东西进行操作，此时end和head指向同一个地址，对end所指向地址进行操作，等同于对head地址所做的操作*/
    for(int i=0;iinformation=(data*)malloc(sizeof(data));
        /*给新节点分配内存*/
        coutnormal->information->number;
        coutnormal->information->name;
        coutnormal->information->sex;
        coutlast=NULL;/*链表最开始的节点没有上一个节点*/
    return head;
}

创建环状链表 操作和之前一样，只不过最后一个节点的下一个指向头节点

listpoint *create_loop_list(int n)
{
    listpoint *head,*normal,*end;
    head=(listpoint*)malloc(sizeof(listpoint));
    head->information=(data*)malloc(sizeof(data));
    end=head;
    for(int i=0;iinformation=(data*)malloc(sizeof(data));
        coutnormal->information->number;
        coutnormal->information->name;
        coutnormal->information->sex;
        coutlast=end;
    return head;
}

创建随机枝杈链表

**这一部分可以最后再看 **

每一个节点都有一个分支指向随机一个节点，这时候我们就要引入ctime库用来使用srand((int)(time(NULL)));以生成随机数，这里还用到了后面的一个函数 listpoint *search_point(listpoint *list,int n);是用来搜索节点的

#include
#include
#include

using namespace std;

typedef struct data
{
    int number;
    string name;
    string sex;
}data;

typedef struct listpoint
{
    data *information;
    listpoint *next;
    listpoint *last;
    listpoint *branch;
 }listpoint;

listpoint *create_random_branch_list(int n)
{
    listpoint *search_point(listpoint *list,int n);
    listpoint *head;
    head=create_normal_list(n);
    listpoint *p,*bp;
    p=head;
    srand((int)(time(NULL)));
    int randnum;
    while((p=p->next)!=NULL)
    {
        randnum=rand()%n+1;
        bp=search_point(head,randnum);
        p->branch=bp;
    }
    return head;
}

生成随机排序链表 同可以最后再看 先生成正常顺序链表，再从最后n个节点中随机选择一个，将其剔除并插入到第一个节点的位置，然后再从最后n-1个节点中随机选择一个，剔除后插入第二个节点位置，以此类推

listpoint *create_random_sort_list(int n)
{
    listpoint *head;
    head=create_normal_list(n);
    listpoint *p1,*p2;
    int n1=0;
    int n2=n;
    srand((int)(time(NULL)));
    int randnum;
    while(n2!=1)
    { 
        p1=head;
        p2=head;
        randnum=rand()%n2+1+n1;
        for(int i=0;inext;}
        for(int i=0;inext;}
        if(randnum==n)
        {
            p2->last->next=NULL;
        }
        else
        {
            p2->next->last=p2->last;
            p2->last->next=p2->next;
        }
        p1->next->last=p2;
        p2->next=p1->next;
        p1->next=p2;
        p2->last=p1;
        n1+=1;
        n2-=1;
    
    }
    return head;
}

/ 第三部分—修改链表

修改数据，因为我们通过指针可以直接修改地址储存的信息，所以函数并不需要返回值

void change_point(listpoint *list,int n,data *ifmation)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    p->information=ifmation;
}

删除节点

void delete_point(listpoint *list,int n)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    p->last->next=p->next;
    p->next->last=p->last;
    free(p);
}

插入节点

void insert_point(listpoint *list,int n,data *ifmation)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    listpoint *insertpoint;
    insertpoint=(listpoint*)malloc(sizeof(listpoint));
    insertpoint->information=ifmation;
    insertpoint->next=p->next;
    p->next->last=insertpoint;
    p->next=insertpoint;
    insertpoint->last=p;
}

搜寻节点

listpoint *search_point(listpoint *list,int n)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    return p;
}

/ 第四部分—输出数据 输出单个节点数据

void output_point(listpoint *point)
{
    coutnext=p1->next;
        p1->next=p2;
        p2->last=p1;
        n1+=1;
        n2-=1;
    
    }
    return head;
}
/********************************************************/
void change_point(listpoint *list,int n,data *ifmation)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    p->information=ifmation;
}
void delete_point(listpoint *list,int n)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    p->last->next=p->next;
    p->next->last=p->last;
    free(p);
}
void insert_point(listpoint *list,int n,data *ifmation)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    listpoint *insertpoint;
    insertpoint=(listpoint*)malloc(sizeof(listpoint));
    insertpoint->information=ifmation;
    insertpoint->next=p->next;
    p->next->last=insertpoint;
    p->next=insertpoint;
    insertpoint->last=p;
}
listpoint *search_point(listpoint *list,int n)
{
    listpoint *p;
    p=list;
    for(int i=0;inext;
    }
    return p;
}
void output_point(listpoint *point)
{
    cout