当前位置:   article > 正文

数据结构——顺序表和链表_顺序链表

顺序链表

目录

一、线性表

二、顺序表

1、顺序表的定义

2、初始化

3、销毁

4、增删查改以及扩容

三、链表

1、链表的定义

2、创建

3、销毁

4、增删查改


一、线性表

        线性表的定义是n个相同类型的数据元素的有限序列,在初学C语言时,我们使用的字符串就可以看成一种线性表,线性表在逻辑上是一条直线,但在物理结构上可能并不是连在一起的。常见的线性表有顺序表、链表、栈、队列等,本章将围绕顺序表和链表讲解。

二、顺序表

1、顺序表的定义

        顺序表一般指用一块连续的内存空间,依次存放数据。

         由于顺序表要的空间是连续的,所以我们一般用数组的方式来存储数据,我们现在有以下两种结构。

静态开辟:

  1. #define Size 10//数据个数为10个
  2. typedef int SLDteType;//数据类型为int 以后更好改
  3. typedef struct SeqList
  4. {
  5. SLDateType a[Size];
  6. size_t size;
  7. }SeqList;

动态开辟:

  1. typedef int SLDateType;//数据类型为int
  2. typedef struct SeqList
  3. {
  4. SLDateType* a;//指向之后动态开辟空间的指针
  5. size_t size;//当前数据个数
  6. size_t capacity; //容量大小
  7. }SeqList;

        静态顺序表的缺点是开辟空间后不能修改大小,可能导致开小了不够用或者是开大了浪费空间,在实际使用中也一般以动态顺序表为主。因此,下面我们将事件动态顺序表。

2、初始化

  1. void SeqListInit(SeqList* ps)
  2. {
  3. assert(ps != NULL);//防止对空指针的解引用
  4. ps->a = NULL;
  5. ps->capacity = 0;//我们默认容量为0,把默认容量放到判断是否需要扩容里
  6. ps->size = 0;
  7. }

3、销毁

        结构体是我们自己在栈上创建的,所以不用用free释放,而结构体中a所指向的空间则是动态开辟的,在销毁表时应该free并且把其他成员置为0。

  1. void SeqListDestroy(SeqList* ps)
  2. {
  3. assert(ps != NULL);//防止对空指针的解引用
  4. free(ps->a);
  5. ps->a = NULL;//避免野指针
  6. ps->capacity = 0;
  7. ps->size = 0;
  8. }

4、增删查改以及扩容

扩容:在添加数据时,难免遇到空间不够的情况,针对此情况,我们先写一个函数,在增加数据时,先判断是否需要扩容,然后再插入数据。

  1. void SeqListChange(SeqList* ps)
  2. {
  3. if (ps->size == ps->capacity)
  4. {
  5. ps->capacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;//如果容量大小为零,则改为2,否者改成原来大小的两倍
  6. SLDateType* newa = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity);
  7. if (newa == NULL)
  8. {
  9. perror("realloc:");
  10. exit(-1);
  11. }
  12. ps->a = newa;
  13. }
  14. }

增:在添加数据时,由于数据是连续存放的。除了在最后一个位置插入数据,在其他的位置插入数据都要把数据往后挪一个位置。

  1. void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
  2. {
  3. assert(ps);//防止对空指针解引用
  4. assert(pos >= 0);//防止在数组前插入数据导致越界
  5. assert(pos <= ps->size);//保证pos下标的合法性
  6. SeqListChange(ps);//判断是否需要扩容
  7. int i = ps->size;
  8. while (i > pos)//挪动数据
  9. {
  10. ps->a[i] = ps->a[i - 1];
  11. i--;
  12. }
  13. ps->a[i] = x;
  14. ps->size++;
  15. }

有了在任意位置插入数据的函数,头插和尾插也可以很方便的实现了。

  1. void SeqListPushFront(SeqList* ps, SLDateType x)//头插
  2. {
  3. assert(ps);
  4. SeqListInsert(ps, 0, x);
  5. }
  6. void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
  7. {
  8. assert(ps);
  9. SeqListInsert(ps, ps->size, x);
  10. }

删:在删除数据时,我们要重点关注size是否为0,当size为0时则代表表已经被删空了,不能再删了。

  1. //删除任意位置的值
  2. void SeqListErase(SeqList* ps, size_t pos)
  3. {
  4. assert(ps);
  5. assert(pos < ps->size);//pos的值要在0到size-1之间
  6. assert(pos >= 0);
  7. int i = pos;
  8. while (i < ps->size - 1)//如果不是删除最后一个值的话,往前挪动位置
  9. {
  10. ps->a[i] = ps->a[i + 1];
  11. i++;
  12. }
  13. ps->size--;
  14. }
  15. //头删
  16. void SeqListPopFront(SeqList* ps)
  17. {
  18. assert(ps);
  19. SeqListErase(ps, 0);
  20. }
  21. //尾删
  22. void SeqListPopBack(SeqList* ps)/
  23. {
  24. assert(ps);
  25. SeqListErase(ps, ps->size-1);
  26. }

查:这个就非常简单了,挨个遍历,找到了就返回下标

  1. int SeqListFind(SeqList* ps, SLDateType x, int begin)
  2. {
  3. assert(ps);//防止空指针解引用
  4. int i = begin;//从begin下标的位置开始找
  5. while (i < ps->size)
  6. {
  7. if (ps->a[i] == x)
  8. {
  9. return i;
  10. }
  11. }
  12. return -1;
  13. }

三、链表

1、链表的定义

        链表在物理上不是连续的,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表可以分成单/双向、带/不带头、循/非循环,三种情况排列组合可以有8种情况,但是最常见的还是下面两种情况。

本章我们只实现单链表

2、创建

  1. typedef int SLTDateType;
  2. typedef struct SListNode
  3. {
  4. SLTDateType data;//存储数据
  5. struct SListNode* next;//下一个节点的地址
  6. }SListNode;
  7. //创建一个结点
  8. SListNode* BuySListNode(SLTDateType* data)
  9. {
  10. SListNode* create = (SListNode*)malloc(sizeof(SListNode));
  11. if (!create)
  12. {
  13. perror("creat malloc file:");
  14. }
  15. create->data = data;//存放数据
  16. create->next = NULL;//将指针置为空避免野指针
  17. return create;//返回该节点的地址
  18. }

3、销毁

        在销毁时需要注意,要先保存下一个节点的地址,否者的话cur就是野指针了,会找不到下一个节点造成对非动态内存的释放和内存泄露。

  1. void SListDestroy(SListNode** plist)
  2. {
  3. SListNode* cur = *plist;
  4. while (*plist)
  5. {
  6. cur = cur->next;//要先保存下一个的地址
  7. free(*plist);
  8. *plist = cur;
  9. }
  10. }

4、增删查改

增:由于单链表只能找到下一个地址,所以一般是在下标的下一个位置添加。而且当要头插时,由于要改变指针,所以有时要参数为二级指针。

  1. // 单链表的头插
  2. void SListPushFront(SListNode** pplist, SLTDateType x)
  3. {
  4. SListNode* begin = BuySListNode(x);
  5. begin->next = *pplist;
  6. *pplist = begin;
  7. }
  8. // 单链表尾插
  9. void SListPushBack(SListNode** pplist, SLTDateType x)
  10. {
  11. SListNode* cur = *pplist;
  12. SListNode* newSLT = BuySListNode(x);
  13. if (*pplist==NULL)//当表为空时,要创建一个节点并返回该节点地址
  14. {
  15. *pplist = newSLT;
  16. }
  17. else
  18. {
  19. while (cur->next)
  20. {
  21. cur = cur->next;
  22. }
  23. cur->next = newSLT;
  24. }
  25. }
  26. // 单链表在pos位置之后插入x
  27. void SListInsertAfter(SListNode* pos, SLTDateType x)
  28. {
  29. assert(pos);
  30. SListNode* newnode = BuySListNode(x);
  31. newnode->next = pos->next;
  32. pos->next = newnode;
  33. }

删:由于在删除的过程中,当把最后一个节点删掉时,要把指针置为空避免野指针,形参的改变不会影响实参,所以我们可以用二级指针。

  1. // 单链表的尾删
  2. void SListPopBack(SListNode** pplist)
  3. {
  4. assert(*pplist);
  5. SListNode* cur = *pplist;
  6. SListNode* next = cur->next;
  7. if (next == NULL)
  8. {
  9. free(cur);
  10. *pplist = NULL;
  11. }
  12. else
  13. {
  14. while (next->next != NULL)
  15. {
  16. cur = next;
  17. next = next->next;
  18. }
  19. free(next);
  20. cur->next = NULL;
  21. }
  22. }
  23. // 单链表头删
  24. void SListPopFront(SListNode** pplist)
  25. {
  26. assert((*pplist));
  27. SListNode* next = (*pplist)->next;
  28. free((*pplist));
  29. if (next == NULL)
  30. {
  31. *pplist = NULL;
  32. }
  33. else
  34. {
  35. *pplist = next;
  36. }
  37. }
  38. //单链表删除pos位置的值
  39. void SListErase(SListNode** phead, SListNode* pos)
  40. {
  41. assert(pos);
  42. assert(phead);
  43. if (*phead == pos)
  44. {
  45. SListNode* next = (*phead)->next;
  46. free(*phead);
  47. *phead = next;
  48. }
  49. else
  50. {
  51. SListNode* cur = *phead;
  52. while (cur->next != pos)
  53. {
  54. cur = cur->next;
  55. }
  56. cur->next = cur->next->next;
  57. free(pos);
  58. }
  59. }

查:

  1. // 单链表查找
  2. SListNode* SListFind(SListNode* plist, SLTDateType x)
  3. {
  4. SListNode* cur = plist;
  5. while (cur != NULL)
  6. {
  7. if (cur->data == x)
  8. {
  9. return cur;
  10. }
  11. else
  12. {
  13. cur = cur->next;
  14. }
  15. }
  16. return cur;
  17. }

        关于顺序表和链表的实现就到这里,现在介绍以下它们的不同点

  • 在内存上,顺序表一定是连续的,而链表不是
  • 在读写上,顺序表易于读取,因为顺序表支持随机读写链表不支持,但是链表在插入删除数据时非常方便,而顺序表在插入删除数据时要挪动后面的数据,效率不高
  • 顺序表在存储数据时要判断要不要扩容,而链表不需要,链表没有最大容量这个概念

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/769674
推荐阅读
相关标签
  

闽ICP备14008679号