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

程序员周同学

发布于 2019-07-27 19:55:07

1.6K0

发布于 2019-07-27 19:55:07

文章被收录于专栏：程序员周同学程序员周同学

内容目录

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

单链表

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}