当前位置:   article > 正文

【数据结构】超详细之单向链表(C语言实现)_c单向链表

c单向链表

文章目录


前言

今天我要介绍单向链表,单向链表与之前我们学的顺序表作用相同,但与顺序表相比,单向链表使用起来更加灵活,效率更高,是一种非常常见且实用的数据结构.


一、单向链表是什么?

1.顾名思义,单向表是用单向结构去实现功能

2.表有很多种,但常用的是单向

3.单向表的存储数据方式是一块一块独立的空间,与顺序表是有区别的

4.单向表比顺序表更适合实现增删改查的功能

5.单向链表是一种存储结构上非连续、非顺序的存储结构

二、单向链表实现步骤

1.打印链表数据以及实现链表头插

  1. .h文件
  2. #pragma once
  3. #include<stdio.h>
  4. #include<assert.h>
  5. #include<stdlib.h>
  6. typedef int Typen;//类型自定义名字,使数据灵活改变
  7. typedef struct ChainedList
  8. {
  9. Typen data;//存放的数据
  10. struct ChainedList* next;//用于存放下一个空间的地址
  11. }CList;
  12. //打印数据
  13. void ChainedListprint(CList* phead);
  14. //头插
  15. void ChainedListPushFront(CList** pphead, Typen x);

  1. .c文件
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include"ChainedList.h"
  4. //打印数据
  5. void ChainedListprint(CList* phead)
  6. {
  7. CList* ps = phead;
  8. while (ps != NULL)
  9. {
  10. printf("%d->", ps->data);
  11. ps = ps->next;
  12. }
  13. printf("NULL\n");
  14. }
  15. //动态申请一个结点
  16. CList* CListBuy(Typen x)
  17. {
  18. CList* p = (CList*)malloc(sizeof(CList));
  19. p->data = x;
  20. p->next = NULL;
  21. return p;
  22. }
  23. //头插
  24. //这里需要注意,传参必须使用双指针
  25. //因为当我们要改变头指针指向的地址时,我们需要用地址的指针
  26. void ChainedListPushFront(CList** pphead, Typen x)
  27. {
  28. assert(pphead);
  29. CList* ps = CListBuy(x);
  30. ps->next = *pphead;
  31. *pphead = ps;
  32. }

  1. .c(执行文件)
  2. CList* p = NULL;
  3. ChainedListPushFront(&p, 1);
  4. ChainedListPushFront(&p, 2);
  5. ChainedListPushFront(&p, 3);
  6. ChainedListprint(p);
  7. return 0;


2.实现链表尾插

  1. .h文件
  2. //尾插
  3. void ChainedListPushBack(CList** pphead, Typen x);
  1. .c文件
  2. //动态申请一个结点
  3. CList* CListBuy(Typen x)
  4. {
  5. CList* p = (CList*)malloc(sizeof(CList));
  6. if (p == NULL)
  7. {
  8. perror("malloc:");
  9. return NULL;
  10. }
  11. p->data = x;
  12. p->next = NULL;
  13. return p;
  14. }
  15. //尾插
  16. //形参1需要使用双指针,因为可能出现要改变头指针地址的情况
  17. void ChainedListPushBack(CList** pphead, Typen x)
  18. {
  19. assert(pphead);
  20. CList* ps = CListBuy(x);
  21. // 1、空链表
  22. // 2、非空链表
  23. if (*pphead == NULL)
  24. {
  25. *pphead = ps;
  26. }
  27. else
  28. {
  29. CList* n = *pphead;
  30. while (n->next != NULL)
  31. {
  32. n = n->next;
  33. }
  34. n->next = ps;
  35. }
  36. }


 3.实现链表头删尾删

  1. .h文件
  2. //头删
  3. void ChainedListPopFront(CList** pphead);
  4. //尾删
  5. void ChainedListPopBack(CList** pphead);
  1. .c文件
  2. //头删
  3. void ChainedListPopFront(CList** pphead)
  4. {
  5. assert(*pphead);
  6. CList* ps = *pphead;
  7. *pphead = ps->next;
  8. free(ps);
  9. ps = NULL;
  10. }
  11. //尾删
  12. void ChainedListPopBack(CList** pphead)
  13. {
  14. assert(*pphead);
  15. CList* ps = *pphead;
  16. //两种情况:
  17. // 1.一个结点
  18. // 2.多个结点
  19. if (ps->next == NULL)
  20. {
  21. *pphead = ps;
  22. free(ps);
  23. }
  24. else
  25. {
  26. //找到最后一个结点,next为NULL
  27. while (ps->next->next != NULL)
  28. {
  29. ps = ps->next;
  30. }
  31. free(ps->next);
  32. ps->next = NULL;
  33. }
  34. }

 


 4.实现链表查找

  1. .h文件
  2. //单链表查找
  3. CList* ChainedListFind(CList* phead, Typen x);
  1. .c文件
  2. //单链表查找
  3. CList* ChainedListFind(CList* phead, Typen x)
  4. {
  5. CList* ps = phead;
  6. while (ps)
  7. {
  8. if (ps->data == x)
  9. {
  10. return ps;
  11. }
  12. ps = ps->next;
  13. }
  14. return NULL;
  15. }


5.实现链表在pos之前/之后插入

  1. .h文件
  2. // 在pos之前插入
  3. void ChainedListInsert(CList** pphead, CList* pos, Typen x);
  4. // 在pos之后插入
  5. void ChainedListInsertAfter(CList* pos, Typen x);
  1. .c文件
  2. // 在pos之前插入
  3. void ChainedListInsert(CList** pphead, CList* pos, Typen x)
  4. {
  5. assert(pphead);
  6. assert(pos);
  7. //一个节点时的情况
  8. CList* ps = *pphead;
  9. if (*pphead == pos)
  10. {
  11. ChainedListPushFront(pphead, x);
  12. }
  13. else
  14. {
  15. //多节点时的情况
  16. while (ps->next != pos)
  17. {
  18. ps = ps->next;
  19. }
  20. CList* p = CListBuy(x);
  21. p->next = ps->next;
  22. ps->next = p;
  23. }
  24. }
  25. // 在pos之后插入
  26. void ChainedListInsertAfter(CList* pos, Typen x)
  27. {
  28. assert(pos);
  29. CList* ps = CListBuy(x);
  30. ps->next = pos->next;
  31. pos->next = ps;
  32. }

6.实现链表删除pos位置的值

  1. .h文件
  2. // 删除pos位置的值
  3. void ChainedListErase(CList** pphead, CList* pos);
  1. .c文件
  2. // 删除pos位置的值
  3. void ChainedListErase(CList** pphead, CList* pos)
  4. {
  5. assert(pphead);
  6. assert(pos);
  7. //一个结点时
  8. if (*pphead == pos)
  9. {
  10. ChainedListPopFront(pphead);
  11. }
  12. //多节点时
  13. else
  14. {
  15. CList* ps = *pphead;
  16. while (ps->next != pos)
  17. {
  18. ps = ps->next;
  19. }
  20. ps->next = pos->next;
  21. free(pos);
  22. }
  23. }

7.实现链表删除pos之后位置的值

  1. .h文件
  2. // 删除pos位置后面的值
  3. void ChainedListEraseAfter(CList* pos);
  1. .c文件
  2. // 删除pos位置后面的值
  3. void ChainedListEraseAfter(CList* pos)
  4. {
  5. assert(pos);
  6. assert(pos->next);
  7. pos->next = pos->next->next;
  8. free(pos->next);
  9. }

总结

以上就是今天要讲的内容,希望能帮助到大家,多多支持,非常感谢!

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号