1.链表的概念

链表是由若干个结点组成，是一种线性表。结点一般由数据域与指针域，数据域存放数据，指针域存放指向下一结点的地址，从而形成一个链式结构。链表有带头节点head的，也有没有带头节点head的，头节点的数据域不存放数据，而指针域指向下一结点（该结点称为第一个结点），链表的最后一个结点的指针域指向NULL，即空地址，表示链表的结尾。

struct node{
      int data;
      node* next;
}

每次使用新结点时需临时分配内存空间给新结点，可以使用C语言的malloc或者C++的new。

malloc用法：

node* p=(node*)malloc(sizeof(node));

sizeof的作用就是返回一个对象或者类型所占的内存字节数，sizeof(node)就是返回node类型所占的内存字节数，malloc的作用分配内存空间，malloc(sizeof(node))就是向内存申请一块大小为sizeof(node)的空间，并且返回指向这块空间的指针，但该指针类型是void，返回类型是 void 类型，void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针，所以在malloc前面加上（node ）进行强制转换，转换成node型指针，赋值给node*型的变量p。

new的用法：

node* p=new node；（只需要new+类型名即可分配一块该类型的内存空间）

在使用完malloc，必须用free释放空间，new相对应就是delete。
free用法：free（p）；
delete用法：delete（p）；

2. 链表的基本操作

2.1 链表的创建

//创建链表
struct node* create()
{
    struct node *p,*pre,*phead;
    int len,i=1,j;
    phead=(struct node*)malloc(sizeof(struct node));
    phead->next=NULL;
    pre=phead;
    
    printf("设定链表长度为:");
    scanf("%d",&len);
    while(i<len)
    {
        
        printf("第%d个结点的数据是:",i);
        scanf("%d",&j);
        p=(struct node*)malloc(sizeof(struct node));
        if(NULL==p)
        {
            printf("分配失败");
            exit(-1);
        }
        p->data=j;
        p->next=NULL;
        pre->next=p;
        
        pre=p;
        
        i++;
    }
    return phead;
}

2.2 打印

void print(struct node* phead)
{
    struct node* p;
         p=phead;
    while(p->next!=NULL)//在这一步曾经用p->data!=NULL来做条件，导致输出异常，我认为的是因为到最后一个结点有数据，但没有下一节点，会造成溢出 
    {
        p=p->next;
        printf("%d",p->data);
    }
}

2.3 查找

void search(struct node* phead)
{
    struct node* p=phead;
    int count=0,flag=0,a;
    printf("请输入要查找的元素是：");
    scanf("%d",&a);
    while(p->next!=NULL)
    {
        p=p->next;
        count++;
        if(p->data==a)
        {
            printf("%d在第%d个结点\n",a,count);
            flag=1;
        }
    }
    if(flag==0)
    {
        printf("没有这个元素");
    }
}

2.4 删除

如果要删除p，就是pre->next=p->next；free(p);

void Delete(struct node* phead)
{
    struct node* p,*pre;
    int a;
    p=phead->next;
    pre=phead;
    printf("请输入要删除的元素是：");
    scanf("%d",&a);
    while(p!=NULL)
    {
        if(p->data==a)
        {
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
}

2.5 插入

插入的重点是先 pnew->next=p;
后pre->next=pnew;

void insert(struct node* phead)
{
    struct node* pnew;
    int a,c;
    pnew=(struct node*)malloc(sizeof(struct node));
    struct node* pre=phead,*p=phead->next;
    printf("新插入结点的数据是：");
    scanf("%d",&a);
    printf("在哪个元素的位置插入：");
    scanf("%d",&c); 
    while(p!=NULL)
    {
        if(c==p->data)
        {
            pnew->next=p;
            pre->next=pnew;
            pnew->data=a;
            break; 
    
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
}

链表