详解链表的创建，插入，删除，遍历

电玩女神 2022-05-28 07:10 228阅读 0赞

开始前废话几句，前几天做C语言笔记时，写到链表这块，懒得写链表的基本操作了，只浏览了一下概念，拖了好几天，今天打算把它完成,期间遇到了一个困惑，在这里再一次对马博老师表示感谢！

//为了方便理解，链表的节点的结构体写简单点：
    typedef struct DATE
    {
        int num;
        struct DATE *next;
    }date;//用date代替typedef struct DATE

## 一·链表的创建： ##

**1.头插法：新节点每次都插在头节点后面**  
先上图，懒得用工具画了，自己手画的，凑合着看：

![这里写图片描述][SouthEast]

date *  create()//头插法创建单链表 
    {
        date *phead, *pnew;//phead头节点，pnew新申请的节点
        int x;
        phead=(date*)malloc(sizeof(date));//申请头节点 
        phead->next=NULL;
        scanf("%d",&x);
        while(x!=0) 
        {   
            pnew=(date*)malloc(sizeof(date));//申请新节点 
            pnew->num=x;
            scanf("%d",&x);     
            pnew->next=phead->next ;//①
            phead->next=pnew;//②
        }
        //free(pnew);
        return phead;   
     }

**2.尾插法：新节点每次接在最后**  
![这里写图片描述][SouthEast 1]

date *  create()//尾插法创建单链表 
    {
        date *phead, *pnew,*pend;//phead指向头节点，pnew指向新申请的节点,pend指向尾节点 
        int x;
        phead=(date*)malloc(sizeof(date));//申请头节点 
        phead->next=NULL;
        pend=phead; 
        scanf("%d",&x);
        while(x!=0) 
        {   
            pnew=(date*)malloc(sizeof(date));//申请新节点 
            pnew->num=x;    
            pnew->next=NULL;//①
            pend->next=pnew;//②
            pend=pnew;  //③
                scanf("%d",&x); 
        }
        //free(pnew);
        return phead;   
     }

## 二·链表的插入： ##

**1.插入为第一个节点：**

void insert( date *phead)//将节点插入为头节点 
    {
        date *p=phead, *pnew;//phead头节点，pnew新申请的节点
        pnew=(date*)malloc(sizeof(date));//申请节点 
        scanf("%d",&pnew->num);     
        pnew->next=p->next ;
        p->next=pnew;
     }

**2.节点插入在某节点（num为xx的）后面**

void insert( date *phead,int num)//将节点插入在某节点（num为xx的）后面
    {
        date *p=phead->next, *pnew;//phead头节点，pnew新申请的节点
        pnew=(date*)malloc(sizeof(date));//申请节点 
        scanf("%d",&pnew->num);
        while(p!=NULL&&p->num!=num)
        {
            p=p->next ;
        }   
        pnew->next=p->next ;
        p->next=pnew;
     }

**3.将节点插入在链表最后面**

void insert( date *phead)//将节点插入在链表最后面
    {
        date *p=phead->next, *pnew;//phead头节点，pnew新申请的节点
        pnew=(date*)malloc(sizeof(date));//申请节点 
        scanf("%d",&pnew->num);
        while(p->next!=NULL)
        {
            p=p->next ;
        }   
        pnew->next=p->next;
        p->next=pnew;
     }

## 四·链表的删除： ##

**1.链表的删除**  
![这里写图片描述][SouthEast 2]

void Delete(date *phead,int num) // num为要删除的节点的num 
     {
        date *p=phead->next;//p指向要删除节点的前一个节点
        q=(date*)malloc(sizeof(date));//申请头节点 
        while(p!=NULL&&p->next->num!=num)
        {
            p=p->next ;
        }   
        p->next=p->next->next ;//①
     }

## 五·链表的遍历： ##

**1.链表的遍历**

void print(date* phead)//遍历单链表 
     {
        date *p;
         p=phead->next ;
         while(p!=NULL) 
         {
            printf("%d ",p->num);
            p=p->next;  
         }
            printf("\n");
     }

## 六·附完整代码： ##

以下代码上机测试正确，

/**************************************************************** 作者：贺远 功能：链表的基本操作 时间：2018.3.30 ****************************************************************/ 
    #include<stdio.h>
    #include <stdlib.h> 
    typedef struct DATE
    {
        int num;
        struct DATE *next;
    }date;
    /*date * create()//头插法创建单链表 { date *phead, *pnew;//phead头节点，pnew新申请的节点 int x; phead=(date*)malloc(sizeof(date));//申请头节点 phead->next=NULL; scanf("%d",&x); while(x!=0) { pnew=(date*)malloc(sizeof(date));//申请新节点 pnew->num=x; scanf("%d",&x); pnew->next=phead->next ; phead->next=pnew; } //free(pnew); return phead; } */
    date *  create()//尾插法创建单链表 
    {
        date *phead, *pnew,*pend;//phead指向头节点，pnew指向新申请的节点,pend指向尾节点 
        int x;
        phead=(date*)malloc(sizeof(date));//申请头节点 
        phead->next=NULL;
        pend=phead; 
        scanf("%d",&x);
        while(x!=0) 
        {   
            pnew=(date*)malloc(sizeof(date));//申请新节点 
            pnew->num=x;    
            pnew->next=NULL;
            pend->next=pnew;
            pend=pnew;  
                scanf("%d",&x); 
        }
        //free(pnew);此处不要能free
        //print(phead);
        return phead;   
        /* date * create()//尾插法创建单链表 { date *phead=NULL, *pnew,*pend;//phead指向头节点，pnew指向新申请的节点,pend指向尾节点 int x; pnew=(date*)malloc(sizeof(date));//申请头节点 phead=(date*)malloc(sizeof(date));//申请头节点 pend=phead; scanf("%d",&x); while(x!=0) { pnew->num=x; pnew->next=NULL; pend->next=pnew; pend=pnew; pnew=(date*)malloc(sizeof(date));//申请新节点 scanf("%d",&x); } free(pnew);//此处可以free return phead; } */
     }
    /*void insert( date *phead)//将节点插入为头节点 { date *p=phead, *pnew;//phead头节点，pnew新申请的节点 pnew=(date*)malloc(sizeof(date));//申请节点 scanf("%d",&pnew->num); pnew->next=p->next ; p->next=pnew; } */ 
     /*void insert( date *phead,int num)//将节点插入在某节点（num为xx的）后面 { date *p=phead->next, *pnew;//phead头节点，pnew新申请的节点 pnew=(date*)malloc(sizeof(date));//申请节点 scanf("%d",&pnew->num); while(p!=NULL&&p->num!=num) { p=p->next ; } pnew->next=p->next ; p->next=pnew; }*/
     void insert( date *phead)//将节点插入在链表最后面
    {
        date *p=phead->next, *pnew;//phead头节点，pnew新申请的节点
        pnew=(date*)malloc(sizeof(date));//申请节点 
        scanf("%d",&pnew->num);
        while(p->next!=NULL)
        {
            p=p->next ;
        }   
        pnew->next=p->next;
        p->next=pnew;
     }
    
     void print(date* phead)//遍历单链表 
     {
        date *p;
         p=phead->next ;
         while(p!=NULL) 
         {
            printf("%d ",p->num);
            p=p->next;  
         }
            printf("\n");
     }
     void Delete(date *phead,int num) // num为要删除的节点的num 
     {
        date *p=phead->next;//p指向要删除节点的前一个节点
        q=(date*)malloc(sizeof(date));//申请头节点 
        while(p!=NULL&&p->next->num!=num)
        {
            p=p->next ;
        }   
        p->next=p->next->next ;
     }
    int main(void)
    {
         date *phead; 
         phead=create();//创建单链表 
         print(phead);//遍历单链表 
         insert(phead);
         print(phead);//遍历单链表 
         Delete(phead,7);
         print(phead);//遍历单链表 
    }

[SouthEast]: /images/20220528/517e715c179e456e91d16dca8cc7e3aa.png
[SouthEast 1]: /images/20220528/4b4105750e0f4bf3aa14e316dec94184.png
[SouthEast 2]: /images/20220528/91f08cec152e47dd98716a1f4239f13a.png