【初阶数据结构篇】顺序表的实现（赋源码）

本篇代码位置

代码位置

顺序表和链表

1.线性表

​ 线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的 数据结构，常见的线性表：顺序表、链表、栈、队列、字符串······

​ 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性 表在物理上存储时，通常以数组和链式结构的形式存储。

---

2.顺序表

2.1 概念与结构

​ 概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

顺序表和数组的区别？

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。可以这么理解，我们使用数组来存储数据，并提供了增删查改数据的接口(函数)，这样组织和存储数据的结构我们将它称为顺序表。

2.2分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

• 缺陷：显而易见的，空间一定，给少了不够用，给多了太浪费

2.2.2 动态顺序表

概念：不存储数组，而是存储一个指向一块动态开辟的内存空间的指针

• 优点：按需开辟，可增容

  故我们一般都使用动态顺序表

---

2.3 动态顺序表的实现

2.3.1动态顺序表的初始化和销毁及打印

创建顺序表，并将其中的指针置为NULL，容量和有效数据个数置为0，销毁大致相同，不过如果arr指针非空，不要忘了释放动态申请的空间

SeqList.h(其中方法会一一讲到)

• 定义顺序表结构
• 将存储数据类型重命名(方便之后替换->例如我们要求顺序表内存储char类型数据，只用改一行代码即可)
• 所写的函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

#pragma once
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>

typedef int sldatatype;
typedef struct Seqlist
{
	sldatatype* arr;
	sldatatype size;
	sldatatype capacity;
} sl;
void slinit(sl*);//初始化
void sldestroy(sl*);//销毁

void slprint(sl*);//打印
void checkcapacity(sl*);//判断空间是否足够
void slpushback(sl*, sldatatype);//尾插
void slpushfront(sl*, sldatatype);//头插

void slpopfront(sl*);//头删
void slpopback(sl*);//尾删

//在指定位置插入和删除数据
void slinsert(sl*, sldatatype, int);
void slfrase(sl*, int);


//查找指定数据
 int slfind(sl*, sldatatype);
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

test.c

• 用来测试我们写的函数(函数的调用)
• 这一部分就是自己写的时候用的测试用例，随便什么都行

最好是写一个方法测试一次，不然找错误的时候会很痛苦