当前位置:   article > 正文

数据结构——单向链表

数据结构——单向链表

目录

前言

一、单向链表

二、单向链表基本操作

1、链表单创建

2.节点插入

(1)尾部插入

 (2)任意位置插入

3、单向链表节点删除

4、链表打印

5、释放链表

6、链表逆序

 ......

三、链表测试

总结



前言

        链表(Linked List)是一种常见的数据结构,它属于线性表的一种链式存储结构,其逻辑上相邻的元素在物理存储位置并不相邻。它由一系列节点(Node)组成,每个节点包含数据部分和指向列表中下一个节点(或者上一个节点)的指针(链接)。链表中的节点通过指针相互连接,从而形成一个序列。链表可以分为几种不同的类型,但最常见的是单向链表和双向链表。


一、单向链表

        在单向链表中,每个节点包含两个部分:

        1、数据部分:存储节点的数据,数据类型可以是整型、浮点型、字符型或自定义的数据结构(如结构体)等。

        2、指针部分(也称为链接或“next”指针):指向链表中下一个节点的指针。链表的最后一个节点的指针部分通常设置为NULL,表示链表的结束。

         链表就如同一群人手拉着手站在一起,最开始的一个人要拉着一根杆,防止链子丢失了。每个人都带着属于自己的数据(如姓名、性别、年龄等),但他们都手拉着手,随意找到上一个人,便可以自然而然的知到下一个人,他们的手就是next指针。

         链表特性:

         1、动态数据结构:链表的节点可以动态地分配和释放,因此链表是一种动态数据结构。链表的大小可以在运行时动态地增加或减少,不需要像数组那样在创建时指定大小。

        2、非连续存储:链表中的节点可以存储在内存中的任何位置,不像数组那样要求所有元素连续存储。但每个节点都需要额外的内存来存储指针,这增加了链表的内存开销。

        3、灵活:通过指针,可以很容易地在链表中的任何位置插入或删除节点,而不需要移动其他节点,通常只需要修改节点的指针,因此效率较高,尤其是在链表中间或末尾进行这些操作时。。

        4、访问方式:单链表不支持快速随机访问,因为从链表的头节点到任意节点的访问都需要从头开始遍历。

        5、常见运用:在实际应用中,链表常用于实现栈、队列等数据结构,或者在需要频繁插入和删除操作而不太需要随机访问的场景中。

二、单向链表基本操作

1、单向链表创建

        首先声明链表节点。

  1. typedef int data_t;
  2. typedef struct node {
  3. data_t data;
  4. struct node * next;
  5. }listnode, * linklist;

         然后进行链表创建,一般只需要创建一个头节点即可,因为在刚创建时,没有数据要放在链表上,即没有新节点插入。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. linklist list_create() //创建链表,即头节点
  4. {
  5. linklist H;
  6. H = (linklist)malloc(sizeof(listnode));//给节点动态分配内存
  7. if (H == NULL)//判断是否申请内存成功
  8. {
  9. printf("malloc failed\n");
  10. return H;
  11. }
  12. //如果成功了,则进行赋初值
  13. H->data = 0; //一般存放节点个数
  14. H->next = NULL;//刚开始时没有节点插入链表,所以该头节点即是尾节点
  15. return H; //返回头节点指针
  16. }
  17. int main(void)
  18. {
  19. linklist H;
  20. H = list_create();//外部调用函数进行创建
  21. if (H == NULL)
  22. return -1;
  23. return 0;
  24. }

2.节点插入

(1)尾部插入

        将链表创建完成后,就可以向链表插入数据了,其中最简单的插入方式为,尾部插入。基本步骤为:

        1、创建新的节点,用以存放将插入的数据;

        2、找到当前链表的尾部,即next指针指向NULL的节点;

        3、将新创建的节点放在尾部,原来尾部节点的next指针指向自己,自己的next指针指向NULL即可。

  1. int list_tailinsert(linklist H, data_t data) //传入待插入的链表地址和待插入的数据
  2. {
  3. linklist p;//定义临时指针变量
  4. linklist q;
  5. if (H == NULL) //检验传入的链表是否有效
  6. {
  7. printf("H is NULL\n");
  8. return -1;
  9. }
  10. //创建新节点并检查有效性,存放待插入数据
  11. if ((p = (linklist)malloc(sizeof(listnode))) == NULL)
  12. {
  13. printf("malloc failed\n");
  14. return -1;
  15. }
  16. p->data = data;
  17. p->next = NULL;
  18. q = H;
  19. while (q->next != NULL) //遍历链表找尾部
  20. {
  21. q = q->next;
  22. }
  23. q->next = p;//插入链表,尾部的next指针指向新节点
  24. H->data++;//插入数据后,数据个数加一
  25. return 0;
  26. }

 (2)任意位置插入

        在这里,我们用-1表示链表的头节点位置,存放数据的第一个节点用0表示,后面的位置依次即可,可以自定义。其插入基本步骤:

        1、对插入位置的有效性进行判断;

        2、查找待插入位置的前一个节点,如下查找某一位置的节点的操作;

  1. //寻找链表上某一位置的节点的地址,返回该节点地址
  2. linklist list_getpos(linklist H, int pos) //传入链表指针和待寻找节点的位置
  3. {
  4. linklist p;
  5. int i;
  6. if (H == NULL)
  7. {
  8. printf("H is NULL\n");
  9. return NULL;
  10. }
  11. if (pos == -1) return H;//如果是-1,则返回链表头节点,因为用0表示第一个节点的位置
  12. p = H;
  13. i = -1;
  14. while (i < pos) //遍历寻找
  15. {
  16. p = p->next;
  17. if (p == NULL) //没有到达指定位置,链表已经结尾了,位置错误,返回NULL
  18. {
  19. printf("pos is invalid\n");
  20. return NULL;
  21. }
  22. i++;
  23. }
  24. return p;
  25. }

        3、创建新节点,存放待插入数据;

        4、重新连接节点,即插入新节点,先将上一个节点的next指针内容赋给新节点的next指针,再将新节点的地址赋给上一个节点的next指针(切勿将顺序搞反)。

  1. //任意位置插入,传入链表地址,待插入数据,待插入位置
  2. int list_insert(linklist H, data_t data, int pos)
  3. {
  4. linklist p;
  5. linklist new;
  6. if (H == NULL)
  7. {
  8. printf("H is NULL\n");
  9. return -1;
  10. }
  11. p = list_getpos(H, pos-1);//找到待插入位置的上一个节点P
  12. if (p == NULL) return -1;//没有找到则返回
  13. if ((new = (linklist)malloc(sizeof(listnode))) == NULL)//创建待插入的新节点
  14. {
  15. printf("malloc failed\n");
  16. return -1;
  17. }
  18. new->data = data;//存放数据
  19. new->next = NULL;
  20. //插入链表,注意先后次序,以免节点丢失
  21. new->next = p->next;
  22. p->next = new;
  23. H->data++;//插入数据后,数据个数加一
  24. return 0;
  25. }

3、单向链表节点删除

        删除节点也可以像插入一样,可进行尾部删除和任意位置删除的操作,尾部删除可对照插入进行,不再赘述。下面进行任意位置节点的删除操作,其基本步骤为:

        1、查找待删除节点的上一个节点;

        2、将待删除的next指针赋给上一个节点的next指针,这样便可以从链表上去掉待删除节点;

        3、然后将删除的节点释放掉内存即可。

  1. int list_delete(linklist H, int pos)
  2. {
  3. linklist p;
  4. linklist deletenode;
  5. if (H == NULL) return -1;
  6. p = list_getpos(H, pos-1);//寻找待删除节点的上一个节点
  7. if (p == NULL) return -1;//没有找到则返回
  8. if (p->next == NULL) //如果要删除的节点不存在,则返回
  9. {
  10. printf("delete pos is invalid\n");
  11. return -1;
  12. }
  13. deletenode = p->next;//找到要删除的节点
  14. //将待删除的next指针赋给上一个节点的next指针
  15. p->next = deletenode->next;//也可以用p->next = p->next->next;
  16. //printf("free:%d\n", deletenode->data);
  17. //释放删除节点的内存
  18. free(deletenode);
  19. deletenode = NULL;
  20. H->data--;//删除节点后,数据个数减一
  21. return 0;
  22. }

4、链表打印

        我们需要查看链表时,就需要遍历打印出来,如下操作。

  1. int list_show(linklist H) //链表打印显示
  2. {
  3. linklist p;
  4. if (H == NULL)
  5. {
  6. printf("H is NULL\n");
  7. return -1;
  8. }
  9. p = H;
  10. while (p->next != NULL)//遍历打印
  11. {
  12. printf("%d ", p->next->data);
  13. p = p->next;
  14. }
  15. puts("");
  16. return 0;
  17. }

5、释放链表

        当链表使用完成之后,需要释放其占用的内存。

  1. int list_free(linklist H)
  2. {
  3. linklist p;
  4. if (H == NULL) return 0;//没有头节点(即链表),则不用释放
  5. p = H;
  6. //printf("free:");
  7. //头节点依次往后移动,然后将前面的删掉
  8. while (H != NULL)
  9. {
  10. p = H;
  11. //printf("%d ", p->data);
  12. free(p);
  13. H = H->next;
  14. }
  15. puts("");
  16. return 0;
  17. }

6、链表逆序

        链表反序主要有以下步骤:

        1、对当前链表的节点数进行判断(头节点不算),如果没有节点或者只有一个节点,则不需要逆序;

        2、将待逆序的链表的第二个及以后的部分分离,这样,待逆序链表只有头节点和第一个节点了,然后依次取出分离部分的头节点在待逆序链表的头部进行插入,便实现了逆序操作。

  1. int list_reverse(linklist H)
  2. {
  3. linklist p;
  4. linklist q;
  5. if (H == NULL)
  6. {
  7. printf("H is NULL\n");
  8. return -1;
  9. }
  10. //如果是空链表,或者是只有一个节点,则没有逆序的必要,返回
  11. if (H->next == NULL || H->next->next == NULL) return 0;
  12. //开始时将链表分为两段
  13. p = H->next->next;//p第二个节点及之后的节点
  14. H->next->next = NULL;//H只有第一个节点
  15. while (p != NULL)
  16. {
  17. q = p;
  18. p = p->next;//p继续往后移
  19. q->next = H->next;//在H链表的头部进行插入
  20. H->next = q;
  21. }
  22. return 0;
  23. }

 ......

三、链表测试

        通过以上链表的基本操作,已基本可以使用链表了,如下简单测试:

  1. int main(void)
  2. {
  3. linklist H;
  4. int value;
  5. H = list_create();//创建链表
  6. if (H == NULL)
  7. return -1;
  8. printf("input:");
  9. while (1)
  10. {
  11. scanf("%d", &value);//输入要插入的值
  12. if (value < 0)//输入负数退出尾部插入的操作
  13. break;
  14. list_tailinsert(H, value);//在链表尾部进行插入
  15. printf("input:");
  16. }
  17. list_show(H);//打印显示当前链表内容
  18. list_insert(H, 100, 1);//在1位置处插入数据为100的节点,位置从0开始算
  19. list_show(H);
  20. list_delete(H, 2);//删除位置2所在的节点
  21. list_show(H);
  22. printf("H=%p\n", H);//打印链表头节点地址
  23. H = list_free(H);//释放链表
  24. printf("H=%p\n", H);
  25. return 0;
  26. }

总结

        链表作为一种灵活且高效的数据结构,在计算机科学的各个领域都有着广泛的应用,更多操作需要自己灵活展现。

有误之处望指正!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/945091
推荐阅读
相关标签
  

闽ICP备14008679号