数据结构 | 顺序表专题

数据结构 | 顺序表专题

课前准备

1. 目标

• C语言语法基础到数据结构与算法，前面已经掌握并具备了扎实的C语言基础，为什么要学习数据结构课程？⸺ 通讯录项目

2. 需要的储备知识

• 简单了解，通讯录具备增加、删除、修改、查找联系⼈等操作。要想实现通讯录项目有两个技术关键:
• C语言语法基础
• 数据结构之顺序表/链表

3. 数据结构相关概念

• 1、什么是数据结构？

数据结构是由“数据”和“结构”两词组合而来。

• 什么是数据？
  常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页肉眼可以看到的信息（文字、图片、视频等等），这些都是数据.

• 什么是结构？
  当我们想要使用大量使用同一类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。
  想要找到草原上名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来。

• 概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

1）能够存储数据（如顺序表、链表等结构）
2）存储的数据能够⽅便查找

---

2、为什么需要数据结构？

• 如图中所示，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
• 通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。

最基础的数据结构：数组

【思考】有了数组，为什么还要学习其他的数据结构？
假定数组有10个空间，已经使用了5个，向数组中插⼊数据步骤：

• 求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这里是否要判断数组是否满了，满了还能继续插⼊吗）…
  假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现

开始顺序表

1、顺序表的概念及结构

1.1 线性表的概念

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
• 案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合如何理解逻辑结构和物理结构？

2、顺序表分类

• 顺序表和数组的区别

  • 顺序表的底层结构是数组,所以顺序表在逻辑结构上是线性的,在物理结构上也是线性的
  • 数组分为定长数组和动态数组

• 顺序表分类

  • 静态顺序表
  • 动态顺序表

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

• 静态顺序表

• 静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

• 动态顺序表

3、动态顺序表的实现

在我们实现顺序表的时候，首先定义出结构体，还有数据类型的定义

头文件：SeqList.h

• 其中size是记录多少个有效数据，为什么要定义这个capacity呢？因为是动态的顺序表，今天100的空间，明天200的空间，所以就是capacity空间有多大，空间容量~~

• 我们可以看到我们当前的顺序表只能存储的是整形的数据，假如我把顺序表实现好了，我给其他人使用的时候，那我这里是整形，那能不能是char类型，double型…，我这里为什么一定要定义int类型？

• 那么我们这里就要使用typedef来定义类型~~

• 那我们也给这个结构体也重命名一个名字~~

#pragma once
//头文件
#include<stdio.h>//数据类型的定义
typedef int SLDataType;//结构体的定义
typedef struct SeqList
{int* a;int size;int capacity;
}SL;

初始化顺序表

函数的声明:SeqList.h

//顺序表的打印
void SeqListPrint(SeqList* ps1);

函数的实现:SeqList.c

//初始化顺序表
void SeqListInit(SeqList* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}

打印顺序表

函数的声明:SeqList.h

void SeqListPrint(SeqList* ps);

函数的实现:SeqList.c
assert函数断言传过来的指针是否为空，若为空就直接结束程序 。

void SeqListPrint(SeqList* ps)
{assert(ps);for (size_t i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

内存容量的检查

函数的声明:SeqList.h

void SeqListCheckCapacity(SeqList* ps);

函数的实现:SeqList.c

因为创建的顺序表示个动态存储的顺序表那么就得满足当容量不足的时候，能够进行扩容，而不是一开始在定义结构体的时候就将顺序表的容量写死。
这里采用的是检查容量的方式来实现顺序表的动态存储，（size）是已经存入的数据个数，（capacity）是可以存储数据的个数，当存入和容量相等即空间满了的时候，这里采用realloc函数对顺序表进行扩容。因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍。
这里使用了动态内存开辟realloc如果不懂这个动态内存开辟可以看看详解动态内存管理这篇文章

void SeqListCheckCapacity(SeqList* ps1)
{assert(ps1);if (ps1->size == ps1->capacity){size_t newcapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;int* tmp = realloc(ps1->a, sizeof(DataType) * newcapacity);if (tmp == NULL){printf("%s\n", strerror(errno));exit(-1);}else{ps1->a = tmp;}ps1->capacity = newcapacity;}
}

顺序表的尾插

函数的声明:SeqList.h

void SeqListPushBack(SeqList* ps, DataType x);

函数的实现:SeqList.c
这里调用一个函数进行,在顺序表的指定位置插入数据

void SeqListPushBack(SeqList* ps1, DataType x)
{assert(ps1);SeqListInsert(ps1, ps1->size, x);
}

顺序表的尾删

函数的声明:SeqList.h

void SeqListPopBack(SeqList* ps);

无需过多操作直接将size–就可以了，因为size是存入数据的个数，size–也就是将最后一个元素去掉。

函数的实现:SeqList.c

void SeqListPopBack(SeqList* ps)
{assert(ps);SeqListErase(ps, ps->size--);
}

顺序表的头插

函数的声明:SeqList.h

void SeqListPushFront(SeqList* ps, DataType x);

函数的实现:SeqList.c

void SeqListPushFront(SeqList* ps, DataType x)
{assert(ps);SeqListInsert(ps, 0, x);
}

先检查顺序表的空间是否充足用来插入一个新的数据。因为是头插就得将第一个的位置腾出来，那就要将顺序表中每一个元素向后移动一个位置，这里采用从后往前挪动的方法即将最后一个数据向后挪动一个，再将到倒数第二个数据向后挪动一个，依次向前，因为如果从前往后挪例如将第一个挪到第二个的时候会将第二个数据覆盖，从而修改了顺序表原有的数据。

顺序表的头删

函数的声明:SeqList.h

void SeqListPopFront(SeqList* ps);

函数的实现:SeqList.c

//顺序表的头删
void SeqListPopFront(SeqList* ps)
{assert(ps);SeqListErase(ps, 0);
}

先检查顺序表的空间是否充足用来插入一个新的数据。因为是删除掉第一个数据，就需要用到覆盖。思路是将整个顺序表即从第二个开始整体向前挪动一个单位，这里采用的是从二个数据开始向前挪一个，再将第三个向前挪一个，依次下去这样第一个数据就会被覆盖掉，如果采用从后往前依次挪动的话，会造成顺序表中的数据被覆盖从而内容被修改。

在顺序表的指定位置插入数据

函数的声明:SeqList.h

void SeqListInsert(SeqList* ps, size_t pos, DataType x);

函数的实现:SeqList.c

//在顺序表pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, DataType x)
{assert(ps);assert(pos <= ps->size);SeqListCheckCapacity(ps);size_t end = ps->size;while (end > pos){ps->a[end] = ps->a[end - 1];end--;}ps->a[pos] = x;ps->size++;
}

对要插入的pos位置断言，如果要插入的位置不符合规范就直接结束程序。检查顺序表的空间是否充足用来插入一个新的数据。因为是在指定位置插入数据，这里才去从后向前挪的方式，因为是要将pos的位置腾出来，思路和头插一样，就不再赘述。

这个就要注意这个循环体了:

如果要是在pos == 0的地方插入数据的话就相当于头插。end只需要走到第二个数据的位置（即end到1的时候就结束了）这样就可以实现将pos位置之后的位置向后挪一个单位的操作。

因为通常标准数组的下标都是用无符号整形表示的，pos的类型为无符号的,如果采用这种方法：

果要是在pos == 0的地方插入数据的话就相当于头插。这里的end会走到下标为0的位置，此时end再自减就为-1，因为end的类型为sizez_t（无符号整形）就会将-1的补码按照无符号整形解读成一个很大的数即（4294967295）那么循环永不停止，就是死循环。

如果将end的类型设置为int有符号整形即（int end = ps1->size - 1;）那当end为0时再次自减一次还会发生和上面一样的问题，因为这里发生了算数转换，当int类型的数据和size_t类型的数据进行比较时，int类型的数据要转换成size_t类型的数据这时-1又被转成很大的数即（4294967295）。循环不会停止。

上述代码为第一种解决方案，第二种解决方案就是将pos的数据类型进行强制类型转换即(int)pos，这样循环才能够停下来。

在顺序表的指定位置删除数据

函数的声明:SeqList.h

void SeqListErase(SeqList* ps, size_t pos);

函数的实现:SeqList.c

void SeqListErase(SeqList* ps, size_t pos)
{assert(ps);assert(pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

这里将pos位置的数据删除，就是将pos之后的所有数据向前挪动一个单位将pos位置的数据覆盖掉。这里采取从前向后挪动的方式与头删类似，在此不再赘述，这里要注意数组越界的问题。

顺序表的查找

函数的声明:SeqList.h

int SeqListFind(SeqList* ps, DataType x);

函数的实现:SeqList.c

int SeqListFind(SeqList* ps, DataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->a[i])return i;}return -1;
}

x为想要查找的数据，如果查找到了返回这个值的下标，如果找不到返回-1。

顺序表的修改

函数的声明:SeqList.h

void SeqListModify(SeqList* ps, size_t pos, DataType x);

函数的实现:SeqList.c

void SeqListModify(SeqList* ps, size_t pos, DataType x)
{assert(ps);assert(pos < ps->size);ps->a[pos] = x;
}

将指定pos位置的数据修改成x。

顺序表的销毁

函数的声明:SeqList.h

void SeqListDestroy(SeqList* ps);

函数的实现:SeqList.c

void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

将顺序表连续的空间的首地址指向空，有效数据个数和容量均置为0。

数组越界的检查

如果上述代码中没有assert断言的话，会出现越界访问的问题。编译器对越界的检查是抽查，即有的越界会被查出来，有的越界就有可能查不出来，所以我们要在写程序的时候尽量避免越界的可能。

一般数组在越界的时候是不会当时就检测出越界，像静态的数组例如：int arr[10] 这种数组越界的检查会在函数结束的时候检查，例如：像malloc 开辟的动态数组，会在free释放空间的时候检查数组是否越界。如果是在free的时候报错了，就要检查是否是数组越界的情况。