专栏首页程序员周同学【数据结构】单链表的增删改查

【数据结构】单链表的增删改查

内容目录

单链表需要使用的函数指针操作小技巧计算单链表的长度创建单链表单链表插入数据单链表删除数据效率分析

单链表

1//本文所有的代码基于如下定义
2#include <stdio.h>
3#include <stdlib.h>
4typedef int DataType;//定义DataType类型
5typedef struct List{
6    DataType data;//结构体数据域
7    struct List *next;//结构体指针域
8}linkedList;//用typedef定义linkedList结构体List类型

上一篇文章中写的时候没有参照《数据结构》的课本,完全靠自己对单链的理解写的。所以在上一篇文章中还有一种单链表情况我没有提到。 上篇文章中所构建的链表是无头结点的链表,还有一种有头结点的链表;这里的有无并非真的指没有头结点,而是指头结点是否储存数据。有头结点的链表,在链表头部添加元素时,头指针的地址是不变的,而无头结点的链表向链表头部插入数据时,头指针的地址永远等于插入元素的地址。 本文的链表依旧以有存在头结点为例子

需要使用的函数

链表中结点所占据的空间都是在使用时才进行分配,也就是需要使用中自行进行申请,申请之后才能从内存空间中得到一块储存空间,这个操作叫做动态内存空间申请。当我们不再使用动态申请的空间时,必须将其释放。 首先,申请内存空间的函数有三个(三个函数均包含在头文件stdlib.h中):

  • void* malloc(unsigned size)
  • void* calloc(size_t numElements, size_t sizeOfElement)
  • void* realloc(void* ptr, unsigned newsize)

我们常用的内存分配函数是malloc,也是我觉得最方便的一个分配函数。 简单讲一下malloc函数如何分配内存空间,malloc函数的参数是unsigned size,无符号整型数据size,也就是告诉计算机你需要得的内存大小。这里需要用到一个函数sizeof()

函数原型sizeof(DataType),返回值是数据类型占据的内存空间(即内存地址)

返回时,计算机并不知道这块内存空间是用来干什么的,只知道要给你这块空间。所以这里我们必须进行强制类型转换将其转换成自己想要的数据指针。 例如申请linkedList类型的空间大小(linkedList*)malloc(sizeof(linkedList))

指针操作小技巧

因为在链表操作中经常使用到指针,所以呢,这里插入一个关于指针的小技巧: 比如下面代码中更改主函数中数据a的值:

 1void change(int *data){
 2    *data = 3;
 3}
 4int main() {
 5    int a = 5;
 6    printf("调用函数前:a = %d\n",a);
 7    change(&a);
 8    printf("调用函数后:a = %d\n",a);
 9    return 0;
10}

运行结果:

1调用函数前:a = 5
2调用函数后:a = 3

再比如改变两个指针的指向:

 1void change(int **point1,int **point2){
 2    int *change = *point1;
 3    *point1 = *point2;
 4    *point2 = change;
 5}
 6int main() {
 7    int a = 5 , b = 3;
 8    int *p1 = &a,*p2 = &b;
 9    printf("交换前p1指向 : %d , p2 指向: %d\n",*p1,*p2);
10    change(&p1,&p2);
11    printf("交换后p1指向 : %d , p2 指向: %d\n",*p1,*p2);
12    return 0;
13}

运行结果:

1交换前p1指向 : 5 , p2 指向: 3
2交换后p1指向 : 3 , p2 指向: 5

总结:

想通过无参函数改变某个主函数变量,必须传入该变量的地址,比如要改变的是第n层指针变量,则传入第(n+1)层指针【即用&取一次地址】;在函数中的改变时取第n层变量,也就是传入变量就一个*号。取该地址的值

计算单链表的长度

首先我们确定一个计算链表长度的函数length(linkedList* head),这里传入指针是因为head本来就是指针变量,而非需要修改,而传入指针。 该函数不做过多解释

 1//此处因为head本来就是指针,所以传入指针,而非要改变head的值
 2int linkedListLength(linkedList *head){
 3    int length = 0;//计数变量
 4    //循环检测有多少个结点
 5    while(head->next != NULL){
 6        length++;
 7        head = head->next;
 8    }
 9    //返回链表的长度
10    return length;
11}

创建单链表

书上也没写是如何创建单链表的,我就按照自己的方法来把这个封装成函数。 我是用尾插法创建链表,也就是创建链表时,每次插入的元素都是在最后一个。

 1//此处传入双重指针,是因为我们需要修改head的值,而head是一重指针
 2//在下方修改的时候仍然使用(*head)也就是一重指针
 3/**
 4 * @param head 头指针的地址
 5 * @param n 创建有n个结点的链表
 6 */
 7void creatLinkedList(linkedList **head,int n){
 8    linkedList *node,*tail;
 9    int data;
10    while(n--){
11        scanf("%d",&data);
12        node = (linkedList*)malloc(sizeof(linkedList));//动态分配内存
13        node->data = data;
14        node->next = NULL;
15        if ((*head)->next == NULL)
16            (*head)->next = node;
17        else
18            tail->next = node;
19        tail = node;
20    }
21}

单链表插入数据

因为书上有示例代码,我就按照书上的代码来画图解。 书上的函数定义:

1//在第i个结点出插入数据data
2void insertLinkedList(linkedList *head,int i,DataType data);

假设在第3个元素处插入数据C 记住A结点之前还存在一个头结点head

插入数据第一步

插入数据第二步

插入数据第三步

插入数据第四步 通过这四步,数据就成功插入了链表。 特别注意:第三步和第四步不能写反,否则会发生错误。可以自己画图试试。 代码演示:

 1//不知道大家能不能理解为什么这里不是双指针。
 2//这个函数实际上我们并不需要改变头指针的值,而是相当于创建链表时添加数据过程
 3void insertLinkedList(linkedList *head,int i,DataType data){
 4    linkedList*node = head,*tail;
 5    int j = -1;
 6    //循环判断i是否合理,若合理,则跳出循环后node指向第i-1个结点,且j == i+1
 7    while (node->next != NULL && j<i-1){
 8        node = node->next;
 9        j++;
10    }
11    if (j!=i-1){
12        printf("插入位置有误!");
13        return;
14    }
15    //上述步骤的第3,4步
16    tail= (linkedList *) malloc(sizeof(linkedList));
17    tail->data = data;
18    tail->next = node->next;
19    node->next =tail;
20}

单链表删除数据

单链表删除数据其实在一定程度上说是比较简单的(如果你完全掌握插入数据了)。 假设我们有一条单链表ABCDE,我们要删除结点C。

删除结点第一步

删除结点第二步

删除结点第三步 free(void*p)函数用于释放动态申请的内存空间。将指针放入括号就好了~ 代码演示:

 1//删除第i个元素,被删除的值由data带回,无需返回值
 2//主体思路和插入元素类似
 3void deleteLinkedList(linkedList*head,int i,DataType* data){
 4    linkedList *p = head,*s;
 5    int j = -1;
 6    while(p->next !=NULL && p->next->next !=NULL && j<i-1){
 7        p = p->next;
 8        j++;
 9    }
10    if (j != i-1){
11        printf("删除位置错误!");
12        return;
13    }
14    s = p->next;
15    *data = s->data;
16    p->next = p->next->next;
17    free(s);
18}

单向链表的改查操作这里不做讲解 链表还有一个清空操作:循环使用free依次释放每个结点的内存空间。

1void destroy(linkedList**head){
2    linkedList*p=head,*q;
3    while(p != NULL){
4        q = p;
5        p = p -> next;
6        free(q);
7    }
8    *head = NULL;
9}

效率分析

单链表的插入和删除效率均不需要移动元素,平均时间复杂度是相同的:O(n)。 单链表求结点个数和撤销单链表两个操作均需要遍历完整个链表,所以时间复杂度为:O(n)。 其他操作均与数据元素个数n无关,所以时间复杂度为:O(1)

这篇推文写的途中遇到了几个坑,,所以才这么迟才完成。增添操作时一定要注意是否存在头结点。 觉得有用的话就点个‘在看’吧~

本文分享自微信公众号 - 程序员周同学(jay-ztx)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • go语言学习-位运算

    Go语言的大多数位运算符与C语言都比较类似,除了取反在C语言中是~x,而在Go语言中 是^x

    solate
  • 程序员C语言快速上手——高级篇(九)

    这在实际操作中非常麻烦,我们需要一种新的数据类型,将这些信息存放在一起,而不是这样分散的去表示和操作。数组显然是无法满足这个需求的,因为数组只能存放相同的数据类...

    arcticfox
  • 系统补白:流畅的python(1)

    初学者学Python,不但入门容易,而且将来深入下去,可以编写那些非常非常复杂的程序。

    一粒小麦
  • 程序员迁移模式

    上图中红颜色标记了目前最常见的“终端节点”(所谓终端节点是人们在这里停下来因为他们找不到更好的东西)。终端节点是:Rust,Java,Go,Python 3,J...

    歪脖贰点零
  • 四个大点,搞懂 Redis 到底快在哪里?

    Redis是一种基于键值对(Key-Value)的NoSQL数据库,Redis的Value可以由String,hash,list,set,zset,Bitmap...

    芋道源码
  • Centreon v19.04远程执行代码漏洞

    Centreon是一个免费的开源基础设施监控软件,Centreon允许系统管理员从集中式Web应用程序监控其基础设施,Centreon已成为欧洲企业监控...

    洛米唯熊
  • 聊一聊C语言变量的含义

    假如我花了200元买了一块4G内存条,然后我定义了一个int a ;就意味着从这4G的内存上要拿走4个字节,又定义了一个int b;那么b同样也要从4G的内存条...

    算法与编程之美
  • 聊一聊少儿编程

    1984年,邓小平的一句话开启了中国计算机的新篇章“计算机普及要从娃娃抓起”。而且在2017年浙江省就明确表明,Python将纳入浙江省的的高考。如果说这离我们...

    算法与编程之美
  • 【数据结构】线性表的顺序表示

    1.写在前面1.C语言关键词---typedef3.线性表的特点4.线性表的顺序表示5.线性表的顺序表示(顺序表)结构

    程序员周同学
  • ES6——异步操作

    ES2017 标准引入了 async 函数,使得异步操作变得更加方便。 async 函数是什么?一句话,它就是 Generator 函数的语法糖。 前文有一...

    羊羽shine

扫码关注云+社区

领取腾讯云代金券