当前位置:   article > 正文

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

数据结构顺序表

前言

        本篇为数据结构系列的第一篇文章,数据结构是一种有效地存储和管理数据的方法,在应对实际问题时的重要性不亚于算法。本系列为我在学习数据结构后对于数据结构的理解,使用的语言为C。这里提几点建议,数据结构最重要的是思想,先有思路再进行代码还原能提高学习效率,在学习时,建议多画图辅助理解,图形能更直观地表达出数据结构。


1 顺序表的基本思路

       顺序表,又称线性表,是一种基础的线性数据结构。其基本思路是在一段连续的内存空间上存储数据。

1.1 静态版顺序表

       顺序表的基本思路是将数据存储在一段连续的内存空间上,这与C语言数据类型中的数组非常相似,因此我们可以通过数组来实现一个顺序表。

       当然,当我们创建一个数组作为顺序表后,需要存储的数据量可能会小于数组的大小,这时数组中就有部分未使用的空间。因此,在顺序表中最好有一个变量来管理顺序表有效空间的大小。如下为一个简单的静态顺序表结构。

  1. struct SeqList
  2. {
  3. int a[100]; //容量大小为100个整型的顺序表
  4. int size;
  5. };

       在这样一个顺序表结构中,结构成员a即顺序表主体,用于存储数据。而变量size则负责管理有效空间,其初始值应该为0,表明初始有效空间为0,即顺序表中的数据量为0。

       由于数组大小直接给定,因此这个顺序表的容量已经确定,无法改变,我们把这种无法改变容量的顺序表称为静态顺序表。

       下图为静态顺序表的图解(矩形中的数字代表存储在表中的整型数据)。

1.2 动态版顺序表 

       与静态顺序表相反,动态顺序表的容量大小可以通过动态内存分配来管理。与静态版相比,动态版顺序表使用起来更加灵活,能更好地适应实际情况,提高内存空间的利用率(大部分数据结构基本都使用动态内存管理)。如下为一个简单的动态顺序表结构。

  1. struct SeqList
  2. {
  3. int* a;
  4. int size;
  5. int capacity;
  6. };

       与静态顺序表相比,动态顺序表结构中的主体a变成了指针类型。其实很好理解,学了数组后我们知道,数组本质上也是通过数组初始位置的指针来管理数组,这里用指针替换主要是方便进行动态内存管理。另外,多出了一个变量capacity,用来管理顺序表的容量,当容量不够大时,可使用realloc函数进行扩容。

       下图为动态顺序表的图解。

 

2 顺序表的实现

2.1 接口

       对于比较复杂的项目,我们采用接口,即在一个头文件中包含所有该项目所需要的标识符声明,以便完工后使用,在数据结构中也如此。

       在写接口前,我们需要先分析该项目所需具备的功能,并分模块实现。

       接下来我们来分析顺序表所需的功能。首先,当我们创建一个顺序表时,需要对顺序表进行初始化,包括为顺序表动态开辟初始空间,设置初始容量,设置初始有效容量为0等。相对的,既然进行了动态内存开辟,那么在空间使用完毕后就要释放空间。其次,就是实现顺序表作为数据结构的基本功能,数据的增删查改。

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #define SeqListAdd 2
  6. typedef int SLDataType;
  7. typedef struct SeqList
  8. {
  9. SLDataType* a;
  10. int size;
  11. int capacity;
  12. }SeqList;
  13. // 对数据的管理:增删查改
  14. void SeqListInit(SeqList* ps);
  15. void SeqListDestroy(SeqList* ps);
  16. void SeqListPrint(SeqList* ps);
  17. void SeqListPushBack(SeqLis
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号