第一关：干掉链表这个小喽啰

偏执的太偏执、 2023-02-10 05:30 10阅读 0赞

# 第一关：干掉链表这个小喽啰 #

### 文章目录 ###

*  第一关：干掉链表这个小喽啰
 *   *  前备知识：
     *  具体代码实现
     *   *  单链表
         *  循环链表
         *  双向循环链表
     *  相关习题：

## 前备知识： ##

链表作为线性数据结构的一种，提它之前必须得讲下：**顺序表**（也就是一个个结点的地址是连续的存储在一起的），这样可能比较抽象：其实也就是C语言学的**数组**（这其中就包括了：普通数组和结构体数组）  
而链表有什么区别呢？  
链表相对于数组而言，引入了指针，这样就实现了：即使相邻的结点在计算机内存的地址不连续，但是可以通过指针实现两个结点的连接（这好像不是我要讲的，哈哈哈）

## 具体代码实现 ##

### 单链表 ###

*  单链表分类：  
    1.带头结点的单链表  
    ![在这里插入图片描述][20200520212308809.png_pic]
    
    2.不带头结点的单链表  
    也就是上图中的a1直接做链表头部

带头结点的单链表在链表相关操作时，要比不带头结点的单链表要好，所以一般建单链表都选择带头结点  
为什么呢要好呢？  
主要区别在于第一个结点的操作，以插入为例：如果没有头结点的话，第一个结点就是当前链表的头；而有头结点的话，第一个结点的插入也就和其他结点插入相同，这样就不需要特判了（如果还不懂，建议画一下图哦）  
综上：我们尽量选择带头结点的链表

*  链表插入两种方法  
    1.头插法  
    2.尾插法  
    书上有非常详细的代码，如果还是不是很懂的话，推荐下面博客：  
    [头插法和尾插法图文并茂][Link 1]

插入操作解决了后，其他操作也就相对来说比较简单了，可以看看下面代码，这是我大一写的，如果不懂的话，欢迎在下面留言，当然也可以加我QQ私聊哦（哈哈）

**带头结点的尾插法单链表相关操作：**

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    using namespace std;
    typedef struct node
    {
        
        int data;
        struct node *next;
    } LNode,*LinkList;
    LinkList L;
    LNode *head=(LNode *)malloc(sizeof(LNode));
    LNode *creat_L()
    {
        
        L=head;
        LNode *r=head;
        printf("请输入数字用以创建链表，输入0结束\n");
        int num;
        scanf("%d",&num);
        while(num!=0)
        {
        
            LNode *p=(LNode*)malloc(sizeof(LNode));
            p->data=num;
            r->next=p;
            r=p;
            scanf("%d",&num);
        }
        r->next=NULL;
        return L;
    }
    void show_L(LinkList L)
    {
        
        if(L->next==NULL)
        {
        
            printf("Link is empty");
        }
        else
        {
        
            LNode *p=L->next;
            printf("%d",p->data);
            while(p->next!=NULL)
            {
        
                p=p->next;
                printf(" %d",p->data);
            }
            printf("\n");
        }
    }
    LNode *get_L(LinkList L,int location)
    {
        
        LNode *p=L;
        int i=0;
        while(p->next!=NULL&&i<location)
        {
        
            p=p->next;
            i++;
        }
        if(i==location)
            return p;
        else
            return NULL;
    }
    int delete_L(LinkList L,int location)
    {
        
        LNode *p,*s;
        p=get_L(L,location-1);
        if(p==NULL||p->next==NULL)
            return 0;
        else
        {
        
            s=p->next;
            p->next=s->next;
            free(s);
            return 1;
        }
    }
    int insert_L(LinkList L,int location,int num)
    {
        
        LNode *p,*s;
        p=get_L(L,location-1);
        if(p==NULL)
            return 0;
        else
        {
        
            s=(LNode *)malloc(sizeof(LNode));
            s->data=num;
            s->next=p->next;
            p->next=s;
            return 1;
        }
    }
    int main()
    {
        
        L=creat_L();
        char str[20];
        printf("请输入相关指令，包括：insert，show，delete，get\n");
        while(~scanf("%s",str))
        {
        
            if(strcmp(str,"insert")==0)
            {
        
                printf("请输入你所要插入的地址及数值\n");
                int location;
                int num;
                scanf("%d%d",&location,&num);
                int flag=insert_L(L,location,num);
                if(flag==1)
                {
        
                    printf("insert OK\n");
                    printf("插入成功，插入后的链表为：\n");
                    show_L(L);
                }
                else
                    printf("insert fail\n");
            }
            if(strcmp(str,"show")==0)
            {
        
                printf("链表为：\n");
                show_L(L);
            }
            if(strcmp(str,"delete")==0)
            {
        
                printf("请输入需要删除的位置:\n");
                int location;
                scanf("%d",&location);
                int flag=delete_L(L,location);
                if(flag==1)
                {
        
                    printf("delete OK\n");
                    show_L(L);
                }
                else
                    printf("delete fail\n");
            }
            if(strcmp(str,"get")==0)
            {
        
                printf("请输入你想要得到数值的位置:\n");
                int location;
                scanf("%d",&location);
                LNode *p=get_L(L,location);
                if(p==NULL)
                {
        
                    printf("get fail\n");
                }
                else
                {
        
                    printf("获取成功,其数值为：\n");
                    printf("%d\n",p->data);
                }
            }
        }
        return 0;
    }

**建议少用拼音命名法…，这样太没技术含量了，计算机相关英语还是挺少的，我这种四级飘过的都不觉得难，你们就更不用说了**

### 循环链表 ###

### 双向循环链表 ###

这两个实现起来都还是有点困难的，考虑大家难以接受，我就自己没有写代码了，但是担心大佬们吃不饱，准备了下面博客：  
[带头结点的双向链表的基本操作][Link 2]

## 相关习题： ##

前面那些操作都可以说比较抽象的，到具体问题下，该怎么思考和求解呢？

1.  [**HNUCM-OJ 1225：链表的基本操作**][HNUCM-OJ 1225]
2.  [**HNUCM-OJ 1227：双向循环链表**][HNUCM-OJ 1227]
3.  [**拼题A：带头结点的链式表操作集 (20分)**][A_ _20]

其实做个第一题也就差不多了

关于第一题的答案，之前有写过一篇博客，大家感兴趣也可以看看：  
[单链表基本操作整合][Link 3]

链表这一关到这，也就基本上算闯关成功了，至于是否能拿MVP就看大家了

[20200520212308809.png_pic]: https://img-blog.csdnimg.cn/20200520212308809.png#_pic
[Link 1]: https://blog.csdn.net/zhengnianli/article/details/79320230
[Link 2]: https://blog.csdn.net/zgege/article/details/79830567?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-2
[HNUCM-OJ 1225]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1225
[HNUCM-OJ 1227]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1227
[A_ _20]: https://pintia.cn/problem-sets/15/problems/729
[Link 3]: https://blog.csdn.net/boliu147258/article/details/88927466