单向链表c语言

一、链表概述

1.构成链表的最小单元

构成链表的最小单元为结构体，在链表中被称为节点。结构体中放有一个（单向链表）或两个指针（双向链表），以及若干数据X。

该指针用来指向下一个节点所在的位置，以此达成将每个节点串联起来的效果。

示意图：

代码如下：

struct node{
   
	int x;
	node *next;
}//单向链表的节点
struct node{
   
    int x;
    node *prev;
    node *next;
}//双向链表的节点

2.与数组的异同对比

相同点：

1.都可以存放一些数据

不同点：

1.存放元素的数量：数组存放的元素个数有限，而链表可以任意的添加或删除。

2.所占用的空间大小：在存放元素数量相同的情况下，链表所占用的空间一般大于数组。

3.操作的复杂程度：对于大部分人来说，对链表的理解要难于对数组的理解，同时构造一个链表所需要花费的精力也要大于构造一个数组。

3.存在的意义

链表与数组都有存放数据的功能，但数组所能存放的元素数量是有限的，因此在一些情景的使用下具有局限性。

如当需要在数组末尾再次添加数据时，若超过数组范围，便会发生数组越界，此时要想再加入新的元素，便要重新创建一个数组。这样的行为往往需要消耗大量的时间与空间。为了避免此类事件的发生，于是便应该使用链表代替数组进行对于数据的存储。

4.对于链表的操作

链表的操作有增删查改四项，后文将会详细说明。

二、单向链表

1.单向链表的创建与插入

概述

链表的插入大致需要进行两步操作，第一步是让上一处的指针指向待插入的这一处，此时待插入的节点已经与前半部分的链表产生了连接。接下来便需要将后半部分与前半部分断开并将后半部分与待插入的节点进行连接。由此可知第二步应该将待插入节点中的指针指向上一处指针原本所指向的位置。

尾插法

1.需要遍历此前所有节点的方式（需要的时间成本更高）：

p1=(struct node *)malloc(sizeof(struct node));
        //p2=(struct node *)malloc(sizeof(struct node));
        p1->data=a;
        p1->next=NULL;//读入节点中的数值
        p2=head;//遍历链表找到最后一个节点
        if(p2){
   //如果头节点不为空，便依次向后遍历
            while(p2->next){
   
                p2=p2->next;//将下一个地址给p2
            }
            p2->next=p1;//找到最后一个节点让它的next指向新读入的节点
        }else{
   
            head=p1;//若头节点为空，便让它直接指向刚读入的第一个节点
        }
        }

2.不需要遍历此前所有节点的方式：

void weicha(int a)//尾插法创建链表
{
   
    struct node *p1,*p2;//p1为先前一个指针跟随输入的值移动，p2为后一个指针随着p1的移动而移动
    p1=(struct node *)malloc(sizeof(struct node));
        p1->data=a;
        p1->next=NULL;
        if(head==NULL){
   
            head=p1;//若为第一个节点就让头指针直接指向节点；
        }else{
   
            p2->next=p1;//若不是第一个节点，就让上一个节点的next指向新的节点
        }
        p2=p1;//用p2将新一个节点的位置储存下来
}

头插法

图示过程：（图中的p应该为t1，作图时打错了）

void toucha(int a) 
{
    struct node *t1;
    t1=(struct node *)malloc(sizeof(struct node));
    t1->data=a;//读入节点中的数值
    if(head==NULL){
   
    	t1->next=NULL;
    }else{
   
    	t1->next=head;
    }
    head=t1;
}

1.处包含了头指针为空与头指针不为空两种情况

当头指针不为空时：先将头指针原本指向的节点的位置交给新建节点的中的next，再将新建节点的位置交给头指针。

当头指针为空时：此时头指针为空，该节点作为链表中的最后一个节点应该指向空。而此head也恰好指向空，可直接让next指向head。

综上所述，可将两种情况合并处理。

合并后：

 void toucha(int a)
{
   
    struct node *t1;
    t1=(struct node *)malloc(sizeof(struct node));
    t1->data=a;
    t1->next=head;
    head=t1;
}

任意位置的插入

（虚线为需要改动的位置）

void renyicha(int b,int c){
   //b为要插入的数字，c为要插入的位置
    struct node *q1,*q2;
    q1=(struct node *)malloc(sizeof(struct node));//动态申请q1以遍历链表来查找所要插入的位置
    q1->data=b;
    q1->next=NULL;//构建新的节点
    if(c==1){
   //当所要插入的位置为第一个位置时
        q1->next=head;//使新节点的next指向原本头指针所指向的节点
        head=q1;//使头指针指向新插入节点的位置
        return;
    }
    q2=head;
    int i;
    for(i=0;i<c-2;i++){
   //注意，若要在n处插入数字，则需要找到第n-1个位置
        q2=q2->next;
    }
    q1->next=q2->next;//使新节点的next指向插入位置处原有的节点的位置
    q2->next=q1;//将上一个节点的next指向新插入的节点
}

2.单向链表的清空与删除

概述

链表的删除主要包括三步，第一步为找到待删除的节点，第二步为修复链表，第三步为释放待删除节点所占用的空间。

清空链表

void qingkong()
{
   //清空链表
    struct node *s1 ,*s2;
    s1=head;//指针1从头遍历链表
    while(s1){
   //当指针s1所指非空时向后遍历
        s2=s1->next;//使用指针s2暂时保存s1所指向的待释放节点的下一个节点
        free(s1);//释放指针s1所指向的空间
        s1=s2;//将s2暂时保存的下一个节点的位置还给s1为下一个节点的释放做准备
    }
    head=NULL;//待所有节点释放完成之后令头指针指向空
}

注意：不可使p1=p1->next，这样当p1被释放之后便会发生错误。

删除任意位置的一个节点

图示：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9JrmYuSC-1672845724045)(/home/wlx/图片/博客用图/绘图7.png)]

void shanchu(int d)//d为要删除的位置
{
   
    int i;
    struct node *h1,*h2;
    h1=head;
    if(d==1){
   //当插入的位置为1时
        head=h1->next;//直接令头指针指向待删除节点后一节点的位置
        free(h1);//释放掉待删除节点
    }else{
   
        for(i=0;i<d-2;i++){
   //遍历找到待删除节点的前一个节点
            h1=h1->next;
        }
        h2=h1->next;//将待删除节点的位置交给指针h2储存
        h1->next=h2->next;//将前一个节点的指针指向待删除节点的后一个节点的位置处。同头插法，这里将待删除节点后为空的情况包含。
        free(h2);//释放掉待删除节点
    }
}

3.单向链表的反转

循环反转

void fanzhuan1()//循环反转链表
{
   
    struct node *current/*代表当前所指节点*/,*prev/*代表当前所指的前一个节点*/,*next/*当前所指的下一个节点*/;
    current=head;
    prev=NULL;
    while(current){
   
        next=current->next;
        current->next=prev;
        prev=current;//将当前节点的位置交给上一个指针
        current=next;//将下一个节点位置交给当前节点
    }
    head=prev;
}

递归反转

通过中间递归的方式进入到最后一个节点，再利用递归的特性由后向前遍历

void fanzhuan2(struct node *p)//递归反转一个链表
{
   
    if(p->==NULL){
   //当最后一个节点的时候使头指针指向该节点
        head=p;
        return;
    }
    fanzhuan2(p->next);//通过递归进入到最后一个节点
    struct node *q=p->next;//将下一个节点的位置交给q暂时储存
    q->next=p;//让下一个节点的next指向当前节点
    p-next=NULL;//该节点后的位置指向空,当此次调用结束后，p被释放，不会对链表中的指向产生影响
}