云湍小站
数据结构_02：顺序表
云湍 Lv3
  2023-01-10 23:21:20   2023-02-07 22:43:11    2.7k 字  11 分钟  

数组和表的区别

在开启本教程学习之前，相信大家已经有了一定语言基础，对于数组，大家一定十分熟悉。我们在使用数组时，或多或少会遇到以下几个问题：

  1. 必须在一开始就声明数组的长度；
  2. 无法随时随用地对数组进行扩容，这就导致了一开始声明的数组的长度必须足够大；
  3. 可能会存在未使用的数组，这对内存是一种浪费。

而表，就是一种可以解决这些问题的数据结构。
关于数组和表，更多的区别需要可能会涉及一些更加深层的知识，这里不做赘述，欢迎自己探知。

顺序表

按照惯例，我们一般需要对顺序表进行一定的介绍：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
为了方便理解，我们可以简单地认为他是一种可以动态变化的连续存储的数组。

定义结构体

顺序表的实现有很多方式，其中，我们采取结构体的方式。
首先我们需要定义一个结构体：

1
2
3
4
5
6
struct list
{
  int* array;
  int capacity;
  int size;
};

在这段代码中，我们定义了一个叫list的结构体，它包含了三个成员，整型指针变量array，整型变量capacity和整型变量size。
和它们的名字一样，array表示顺序表所占的内存空间，capacity表示顺序表的理论最大容量，size表示顺序表中已经填满的容量，即实际长度。

初始化

当我们定义完结构体后，我们还没有真正创建一个顺序表，即便我们在main函数中创建了一个结构体变量，它也不能真正算得上一个顺序表。
一个顺序表的实现必须要对其进行初始化，为了便于多次使用，我们采取自定义一个初始化函数的方式实现。
在此之前，为了便于后续操作，我们可以使用typedef函数将结构体指针struct list*重命名为arraylist，即：

1
typedef struct list* arraylist;

此后涉及struct list*的内容我们一律用arraylist代替，请根据需求自行代换。
根据我们此前定义的结构体的三个成员内存array，容量capacity，长度size，我们可以设想到初始化需要进行的操作。
我们都知道计算机在存储数据时需要用到内存空间，所以我们在初始化时，需要使用malloc()函数申请一块内存空间，使用此函数前我们需要引入新的头文件<stdlib.h>，即：

1
#include<stdlib.h>

接着，我们需要用变量表示顺序表初始的最大容量和实际长度。
综上，初始化一个顺序表需要实现以下三个功能：

  1. 向计算机申请一块内存空间；
  2. 表示顺序表初始最大容量；
  3. 表示顺序表初始实际长度，即0；

实现这三个功能并不难，即：

1
2
3
4
5
6
void setuplist(arraylist list)
{
  list->capacity=1;//此处初始化顺序表容量为1，实际可更改
  list->array=malloc(sizeof(int)*list->capacity);
  list->size=0;
}

观察上述代码块，有几点值得我们注意：

  1. 在学习函数章节时，我们已经知道了函数传值和传地址的区别，此处由于我们需要对顺序表地址进行操作，故需要用到结构体指针；
  2. 表示结构体指针的成员需要用到->符号，或者也可以用(*指针名).成员名表示；
  3. sizeof()函数会根据括号内的数据类型换算成对应的内存大小；

当我们深入了解malloc()函数后，我们会知道有时malloc()函数也会申请内存失败，此时它会返回NULL，同时申请失败也就意味着初始化失败，我们可以采取一种方式来表示初始化的成功与否。
我们可以用布尔型返回true和false来表示初始化的结果，但是我们都知道true=1，false=0，又因为C语言中可能存在没有布尔型的情况，此处我们仅仅展示一个在部分C语言标准下存在的代码块，后续涉及判断内容我们一律采用int型，代码块即：

1
2
3
4
5
6
...
#include<stdbool.h>
...
_Bool test_1=true;
bool test_2=false;
...

对于增加判断申请内存失败与否的初始化函数，即：

1
2
3
4
5
6
7
8
9
int setuplist(arraylist list)
{
  list->capacity=1;
  list->array=malloc(sizeof(int)*list->capacity);
  if(list->array==NULL)
    return 0;
  list->size=0;
  return 1;
}

至此，我们已经实现了顺序表的初始化功能。

扩容

当我们初始化一个顺序表后，有时我们会面临最大容量不足的情况，当然我们一开始初始化的可以很容易的保证最大容量足够第一次使用，可是当我们后续使用时，有时要对其进行扩容。
在C语言中本身提供了realloc()函数重新申请一块内存，和malloc()一样，它也是包含于<stdlib.h>头文件中的，扩容的操作极其简单，即：

1
2
3
4
5
6
7
8
9
10
int extendlist(arraylist list)
{
  int newcapacity=list->capacity*2;//内存扩展两倍
  int* newarray=realloc(list->array, sizeof(int)*newcapacity);
  if(newarray==NULL)
    return 0;
  list->array=newarray;
  list->capacity=newcapacity;
  return 1;
}

插入

一个顺序表被创建出来后，其中并没有元素，这时我们可以对其进行插入。和插入数组一样，我们顺序表的插入也需要三个要素：

  1. 被插入的顺序表；
  2. 插入的数字；
  3. 插入的位置。

基于此，我们很容易就可以设计出一个插入顺序表的函数，在我们正式开始进行写代码前，我们可以很容易的预见一些插入过程中可能会发生的问题：

  1. 插入的位置在可插入的位置之外；
  2. 顺序表容积已满，需要扩容；
  3. 如何选择插入的方法。

关于第一个问题，我们一般认为顺序表从的位置从1开始，那么当我们插入的位置小于1或很大时，这个插入是不可取的；关于第二个问题，我们只需要在插入过程中引入if判断是否需要扩容即可；关于第三个问题，我们可以很容易想到，我们只需要将顺序表的元素从尾部开始依次向后移动一位直到空出需要插入的位置，再将需要插入的元素插入需要插入的位置即可。
综上，我们可以很容易写出代码，即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int insertlist(arraylist list, int element, int index)
{
  if(index<1||index>list->size+1)
    return 0;
  if(list->size==list->capacity)
  {
    if(!extendlist(arraylist list))
      return 0;
  }
  int i;
  for(i=list->size; i>index-1; i--)
    list->array[i]=list->array[i-1];
  list->array[index-1]=element;
  list->size++;
  return 1;
}

删除

当我们学会了插入后，再学习删除是非常简单的，我们只需要根据位置信息，就可以将顺序表中的某个元素删除，值得注意是，输入的位置信息也需要在合法的范围内，代码即：

1
2
3
4
5
6
7
8
9
10
int deletelist(arraylist list, int index)
{
  if(index<1||index>list->size)
    return 0;
  int i;
  for(i=index-1; i<list->size; i++)
    list->array[i]=list->array[i+1];
  list->size--;
  return 1;
}

查找长度

查找长度相当简单，我们只需要向主程序返回size值即可，即：

1
2
3
4
int sizelist(array list)
{
  return list->size;
}

查找元素

查找元素也同样简单，我们可以选择多种查找方式，这里我们采用简单的遍历查找，即：

1
2
3
4
5
6
7
8
int findlist(arraylist list, int element)
{
  int i;
  for(i=0; i<list->size; i++)
    if(list->array[i]==element)
      return i+1;//数组从0开始，顺序表从1开始，故i+1
  return 0;
}

查找索引

查找索引即查找某个位置上对应元素的值，有了上述模块的经验，我们很容易设计出一个功能齐全的函数，即：

1
2
3
4
5
6
int* getlist(arraylist list, int index)
{
  if(index<1||index>list->size)
    return NULL;
  return &list->array[index-1];//注意数组索引和顺序表索引的区别
}

打印

打印顺序表索引元素的函数也同样简单，即：

1
2
3
4
5
6
7
void printlist(arraylist list)
{
  int i;
  for(i=0; i<list->size; i++)
    printf("%d ",list->array[i]);
  printf("\n");
}

销毁

当我们使用完顺序表后，有时候需要销毁它释放内存，此时我们可以用free()函数来进行操作，free()函数必须与malloc()函数配套使用，即：

1
2
3
4
5
6
7
8
9
10
int destorylist(arraylist list)
{
  if(list->array==NULL)
    return 0;
  free(list->array);
  list->array=NULL;
  list-capacity=0;
  list->size=0;
  return 1;
}

总结

顺序表作为数据结构的第一节，并不算难，我们关键是要从中领会思想，学习一些函数的用法，为接下来链表的学习打好基础。

附代码

全代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<stdlib.h>

struct list
{
  int* array;
  int capacity;
  int size;
};

typedef struct list* arraylist;

int setuplist(arraylist list)
{
  list->capacity=1;
  list->array=malloc(sizeof(int)*list->capacity);
  if(list->array==NULL)
    return 0;
  list->size=0;
  return 1;
}

int extendlist(arraylist list)
{
  int newcapacity=list->capacity*2;//内存扩展两倍
  int* newarray=realloc(list->array, sizeof(int)*newcapacity);
  if(newarray==NULL)
    return 0;
  list->array=newarray;
  list->capacity=newcapacity;
  return 1;
}

int insertlist(arraylist list, int element, int index){
  if(index<1||index>list->size+1)
    return 0;
  if(list->size==list->capacity)
  {
    if(!extendlist(arraylist list))
      return 0;
  }
  int i;
  for(i=list->size;i>index-1;--i)
    list->array[i]=list->array[i-1];
  list->array[index-1]=element;
  list->size++;
  return 1;
}

int deletelist(arraylist list, int index){
  if(index<1||index>list->size)
    return 0;
  int i;
  for(i=index-1; i<list->size; i++)
    list->array[i]=list->array[i+1];
  list->size--;
  return 0;
}

int sizelist(arraylist list)
{
  return list->size;
}

int findlist(arraylist list, int element)
{
  int i;
  for(i=0; i<list->size; i++)
    if(list->array[i]==element)
      return i+1;
  return 0;
}

int* getlist(arraylist list, int index)
{
  if(index<1||index>list->size)
    return NULL;
  return &list->array[index-1];
}

void printlist(arraylist list)
{
  int i;
  for(i=0; i<list->size; i++)
    printf("%d ",list->array[i]);
  printf("\n");
}

int destorylist(arraylist list)
{
  if(list->array==NULL)
    return 0;
  free(list->array);
  list->array=NULL;
  list-capacity=0;
  list->size=0;
  return 1;
}

int main()
{
...
}

返回目录

你可以点击此处返回或查看目录。

数据结构_02：顺序表
2023/01/10/数据结构-02：顺序表/
作者
云湍
发布于
2023-01-10 23:21
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 数组和表的区别
  2. 顺序表
    1. 定义结构体
    2. 初始化
    3. 扩容
    4. 插入
    5. 删除
    6. 查找长度
    7. 查找元素
    8. 查找索引
    9. 打印
    10. 销毁
  3. 总结
    1. 附代码
  4. 返回目录
© 2020 - 2024    云湍
由 Hexo 驱动 & 主题 Keep
总字数 23.8k 访客数 访问量
  1. 数组和表的区别
  2. 顺序表
    1. 定义结构体
    2. 初始化
    3. 扩容
    4. 插入
    5. 删除
    6. 查找长度
    7. 查找元素
    8. 查找索引
    9. 打印
    10. 销毁
  3. 总结
    1. 附代码
  4. 返回目录