C语言手撕实战代码_单链表

简介: 本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。

C语言手撕实战代码_单链表

题目清单:
| 单链表习题|
|--|
| 1.使用头插法构建带头结点的单链表 |
| 2.使用尾插法构建带头结点的单链表|
| 3.在第i个数据结点前插入元素e |
|4.设计算法高效查找带头单链表倒数第m个位置(m个正整数)的结点并输出该结点值 |
| 5.已知指针La和Lb分别指向两个无头结点的单链表。编写函数完成从La中删除第j个元素开始的共len个元素,并将这len个元素插入到表Lb中第j个元素之前 |
| 6.设单链表表头指针为L,节点数据域为字符。设计时间复杂度最低的算法判断前n/2个字符是否与后n/2字符依次相同,例如:xyx和xyxy中前一半字符与后一半字符是否相同|
|7.La和Lb按值非递减,归并La和Lb,得到新的单链表Lc,使得Lc也按值非递减且不含重复元素,并占用原来的空间 |
|8.带头单链表中所有元素的数据值按递增顺序排列,删除链表中大于min且小于max的元素 |
|9.设计一个算法,判断La是否为Lb的子链,子链的定义为:La中的从前到后的所有节点的数据域都按照原有顺序出现在Lb上 |
| 10.两个单词有相同的后缀时可共享相同的后缀存储空间,例如“act”和“dicf”,如下图所示,设La和Lb分别指向两个单词所在单链表的头结点,链表结点结构(data,next),设计算法查找公共后缀的起始位置。如图中标注的阴影数据结点部分分为"act"和“dict”公共后缀的起始位置|

1.使用头插法构建带头结点的单链表

构建大体思路,
写一个函数构建单链表(链表引用头,int数组,数组长度)
也就是说通过先读入数组,然后再构建单链表

#include<stdio.h>
#include<stdlib.h>
typedef  int ElemType;
typedef struct LinkNode
{
   
   
    ElemType data;
    struct LinkNode* next;

}LinkNode,*LinkList;

void creat_linklist_byinserthead(LinkList &L,int enterArra[],int enterArraLength)
{
   
   
    //先定义头结点
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;

    //循环头插结点
    int index=0; //第一个数组下标
    while(index<enterArraLength)
    {
   
   
        LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
        p->data= enterArra[index++];
        p->next=L->next;
        L->next=p;
    }
}

void printLink(LinkList L)
{
   
   
    LinkList p=L->next;
    while (p) {
   
   
        printf("%d->",p->data);
        p=p->next;
    }
    printf("NULL\n");
}
int main()
{
   
   
    LinkList L=NULL;  //声明一个头指针
    int enterArra[100]={
   
   0};
    int enterlength=0;
    printf("请输入数组序列:\n");
    int enterData=999999;//读入结束标记是999999,当读入999999时,输入就结束,循环就结束
    while (scanf("%d",&enterData)&&999999>enterData) {
   
   
        enterArra[enterlength++]=enterData;
    }             //结束数组的读入
    creat_linklist_byinserthead(L, enterArra, enterlength);
    printLink(L);

    printf("\n");
    return 1;
}

image.png

2.使用尾插法构建带头结点的单链表

void creat_linklist_byinserttail(LinkList &L,int enterArra[],int enterArraLength)
{
   
   
    //先定义头结点
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;

    //循环尾插结点
    int index=0; //第一个数组下标
    LinkList tail=L;
    while(index<enterArraLength)
    {
   
   
        LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
        p->data= enterArra[index++];
        tail->next=p;
        tail=p;
    }
    tail->next=NULL;
}

3.在第i个数据结点前插入元素e

void insert_before_i(LinkList &L,int k,int e)  //在第k个元素前插入,移动k-1下就插入
{
   
   
    LinkNode *p=L;
    for(int i=0;i<k-1;i++)
    {
   
   
        p=p->next;
    }            // 找到插入点
    LinkNode *x=(LinkNode*)malloc(sizeof(LinkNode));
    x->data=e;
    x->next=p->next;
    p->next=x;
}

image.png

4.设计算法高效查找带头单链表倒数第m个位置(m个正整数)的结点并输出该结点值

void getdata(LinkList L,int m)
{
   
   
    LinkNode *cur=L->next;
    LinkNode *pre=L->next;

    while (m--) {
   
   
        cur=cur->next;
    }

    while(cur!=NULL)
    {
   
   
        pre=pre->next;
        cur=cur->next;
    }
    printf("元素是%d\n",pre->data);
}

5.已知指针La和Lb分别指向两个无头结点的单链表。编写函数完成从La中删除第j个元素开始的共len个元素,并将这len个元素插入到表Lb中第j个元素之前

分析:
本题中值得积累的点,在于人为加入头结点,来进行头结点的让控制链表的操作更简单。
至于这道题就是按步骤来就行

主函数

//定义两个现成的单链表La和Lb
    int a[8]={
   
   1,2,3,4,5,6,7,8};
    int b[8]={
   
   9,10,11,12,13,14,15,16};
    LinkList La=NULL;
    LinkList Lb=NULL;
    creat_linklist_byinserttail(La, a, 8);
    creat_linklist_byinserttail(Lb, b, 8);
    printLink(La);
    printLink(Lb);
    operator_linklist(4, 3, La, Lb);
    printLink(La);
    printLink(Lb);

自定义函数

void operator_linklist(int j,int len,LinkList &La,LinkList &Lb)
{
   
   
    //首先是从给La和Lb加上头结点
    LinkNode* headLa=(LinkNode*)malloc(sizeof(LinkNode));
    LinkNode* headLb=(LinkNode*)malloc(sizeof(LinkNode));
    headLa->next=La;
    headLb->next=Lb;

    int count=j; //
    LinkNode* p1=headLa;
    //找到La第j个元素指向位置
    while (count--) {
   
   
        p1=p1->next;
    }    //循环结束后此时的p1指向第j个元素的前一个元素
    count=len;
    LinkNode* p2=p1;
    while(count--)
    {
   
   
        p2=p2->next;
    }             // p2指向删除链上的最后一个元素
    printf("第%d个元素的前一个元素是%d\n",j,p1->data);
    printf("删除链的最后一个元素是%d\n",p2->data);

    LinkNode* p3=p1;  p1=p1->next; //p1指向删除链的第一个元素,p2指向删除链的最后一个元素,p3指向删除链的前一个元素
    p3->next=p2->next;  //完成La的断链
    p2->next=NULL;

    //记录L的第j个元素的前一个元素,和第j个元素
      count=j-1;
    LinkNode* p4=Lb;
    while (count--) {
   
   
        p4=p4->next;
    }    //循环结束后此时的p4指向第j个元素的前一个元素
    LinkNode* p5=p4->next;  //p5记录指向j个元素
    p4->next=p1;
    p2->next=p5;
    free(headLa);
    free(headLb);

}

image.png

6.设单链表表头指针为L,节点数据域为字符。设计时间复杂度最低的算法判断前n/2个字符是否与后n/2字符依次相同,例如:xyx和xyxy中前一半字符与后一半字符是否相同

思路:
利用快慢指针找到中间结点,然后依次从前往后对比就完了

7.La和Lb按值非递减,归并La和Lb,得到新的单链表Lc,使得Lc也按值非递减且不含重复元素,并占用原来的空间

思路:
La和Lb从头开始遍历,用尾插法建立单链表,然后利用尾插法建立单链表Lc,若元素和Lc表尾元素不同,加入Lc,相同就下一个。

void no_repeat_insert(LinkList &tailLc, LinkNode *&pnode)
{
   
   
    // 判断元素是否重复, 使用尾插法插入
    if (tailLc == NULL || tailLc->data != pnode->data)
    {
   
   
        tailLc->next = pnode;
        tailLc = tailLc->next;  // 尾插法,一直指向表尾
    }
    pnode = pnode->next;  // 后移
}

void combineSortedLink(LinkList &Lc, LinkList &La, LinkList &Lb)
{
   
   
    LinkNode *pcurLa = La;
    LinkNode *pcurLb = Lb;
    LinkNode *tailLc = Lc;

    // 只有在两个链表都不为空的情况下,才能进行比较合并
    while (pcurLa != NULL && pcurLb != NULL)
    {
   
   
        if (pcurLa->data <= pcurLb->data)
        {
   
   
            no_repeat_insert(tailLc, pcurLa);
        }
        else
        {
   
   
            no_repeat_insert(tailLc, pcurLb);
        }
    }

    // 如果La有剩余,继续插入
    while (pcurLa != NULL)
    {
   
   
        no_repeat_insert(tailLc, pcurLa);
    }

    // 如果Lb有剩余,继续插入
    while (pcurLb != NULL)
    {
   
   
        no_repeat_insert(tailLc, pcurLb);
    }

    // 最后将链表末尾置空,确保链表的完整性
    tailLc->next = NULL;
}

本题积累,
1.用函数的过程中,别忘了&,指针变量也要&,才能进行实际操作。
2.pcurLb != NULL和!pcurLb作为while循环的条件,意义不同
pcurLb != NULL是说它不是空指针
!pcurLb意思是只要pcurLb是空的就进行循环,完全是相反的语句。

8.带头单链表中所有元素的数据值按递增顺序排列,删除链表中大于min且小于max的元素

设计数据:
1.全部小于min或全部大于max,返回原先链表
2.有大于min小于max的部分,删除后返回

void delete_min_max(LinkList &head,int min,int max)
{
   
   
    LinkNode*cur=head->next;
    LinkNode*pre=head;
    while(cur!=NULL)
    {
   
   
        if(cur->data>min&&cur->data<max)
        {
   
   
            pre->next=cur->next;
            cur=cur->next;
        }else
        {
   
   
            cur=cur->next;
            pre=pre->next;
        }
    }
}

9.设计一个算法,判断La是否为Lb的子链,子链的定义为:La中的从前到后的所有节点的数据域都按照原有顺序出现在Lb上

思路核心:
遍历Lb,每当Lb的第一个结点与La的第一个结点相同时,比较随后的结点是否相同,若不相同则返回Lb的下一个结点,知道Lb结点遍历完,以此类推。

设计数据:
La是Lb子链的情况:
{1,2,3};
{1,2,1,2,2,1,2,3};
La不是Lb子链的情况:

int isSubLinkList(LinkList La, LinkList Lb)
{
   
   
    LinkNode *pb = Lb;
    LinkNode *pa;

    while (pb != NULL)
    {
   
   
        printf("循环开始时pb指向:%d\n",pb->data);

        // 每次新的匹配尝试时,重置 pa 到 La 的头部
        pa = La;
        LinkNode *falg = pb;  // 记录当前的起始位置
        printf("记录当前的起始位置flag:%d\n",falg->data);

        // 进入匹配过程
        while (pa != NULL && pb != NULL && pa->data == pb->data)
        {
   
   
            pa = pa->next;
            pb = pb->next;
        }

        if (pa == NULL)  // 如果 La 的所有节点都匹配完毕
        {
   
   
            printf("匹配成功\n");
            return 1;  // 匹配成功
        }

        // 如果匹配失败,重置 pb 到 falg 的下一个节点,继续检查
        pb = falg->next;
    }

    return 0;  // 匹配失败
}

注意以上代码是不带头结点的单链表,我要提醒自己了,敲代码的时候忘了我定义的单链表是带头结点的了,然后一直调试失败。我要提醒我自己了。

10.两个单词有相同的后缀时可共享相同的后缀存储空间,例如“act”和“dicf”,如下图所示,设La和Lb分别指向两个单词所在单链表的头结点,链表结点结构(data,next),设计算法查找公共后缀的起始位置。如图中标注的阴影数据结点部分分为"act"和“dict”公共后缀的起始位置

image.png

本题的本质就是力扣上的相交链表

本题思想:
求出La,Lb的长度,然后找到较长的那个,两个链表做差,得到链表差,然后让较长的链表先移动差值个单位,然后两个链表就等长了。就可以一直后移找公共的后缀。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   
   
   if(headA == NULL || headB == NULL) return NULL;  // 如果任一链表为空,返回 NULL

    struct ListNode * pa=headA;
    struct ListNode * pb=headB;
    int length_la=0;
    int length_lb=0;
    int chazhi=0;
    while(pa->next!=NULL)
    {
   
   
        length_la++;
        pa=pa->next;
    }
     while(pb->next!=NULL)
    {
   
   
        length_lb++;
        pb=pb->next;
    }
    printf("%d\n",length_lb);
    pa=headA;
    pb=headB;
    if(length_la>=length_lb)
    {
   
   
        chazhi=length_la-length_lb;
        while(chazhi--)
        {
   
   
            pa=pa->next;
        }
    }else
    {
   
   
        chazhi=length_lb-length_la;
        printf("%d\n",chazhi);
         while(chazhi--)
        {
   
   
            pb=pb->next;
        }
    }

   while(pa!=NULL&&pb!=NULL)
   {
   
   
        printf("pa指向%d\n",pa->val);
        printf("pb指向%d\n",pb->val);
        if(pa==pb)
        {
   
   
            return pa;
        }
        pa=pa->next;
        pb=pb->next;
   }

   return NULL;
}

本题注意点是最后比较的时候,是pa\==pb不是pa->next==pb->next
image.png

相关文章
|
9天前
|
安全 C语言
在C语言中,正确使用运算符能提升代码的可读性和效率
在C语言中,运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
21 4
|
24天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树(BST)的基本操作,包括构建、查找、删除等核心功能。通过多个具体示例,如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等,帮助读者深入理解二叉排序树的工作原理与应用技巧。此外,还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST,以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现,便于学习与实践。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
Java Android开发 C语言
03_Android NDK中C语言调用Java代码,javah的使用,javap的使用以及生成签名,Android.mk的编写,C代码的编写
 1  案例场景,通过C语言回调Java的代码,案例的最终界面: 2  案例的代码结构如下: 3 编写DataProvider的代码: package com.example.ndkcallback;   public class DataProvider {     //C调用java空方法     public void helloFromJav
1436 0
|
23天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数,`gets`用于从标准输入读取字符串直至换行符,并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外,文章还详细讲解了`str`系列字符串操作函数,包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符,每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容,提供了丰富的示例帮助理解。通过对本文的学习,读者可以全面掌握C语言中的位运算和文件处理技术。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第七章 函数和预编译命令
本章介绍C语言中的函数定义与使用,以及预编译命令。主要内容包括函数的定义格式、调用方式和示例分析。C程序结构分为`main()`单框架或多子函数框架。函数不能嵌套定义但可互相调用。变量具有类型、作用范围和存储类别三种属性,其中作用范围分为局部和全局。预编译命令包括文件包含和宏定义,宏定义分为无参和带参两种形式。此外,还介绍了变量的存储类别及其特点。通过实例详细解析了函数调用过程及宏定义的应用。
|
1月前
|
Linux C语言
C语言 多进程编程(三)信号处理方式和自定义处理函数
本文详细介绍了Linux系统中进程间通信的关键机制——信号。首先解释了信号作为一种异步通知机制的特点及其主要来源,接着列举了常见的信号类型及其定义。文章进一步探讨了信号的处理流程和Linux中处理信号的方式,包括忽略信号、捕捉信号以及执行默认操作。此外,通过具体示例演示了如何创建子进程并通过信号进行控制。最后,讲解了如何通过`signal`函数自定义信号处理函数,并提供了完整的示例代码,展示了父子进程之间通过信号进行通信的过程。