当前位置：首页 > news >正文

wordpress小程序插件百度seo排名360

news 2025/8/22 2:59:47

wordpress小程序插件,百度seo排名360,国家企业信用公示信息年报官网,网站建设开发合作协议目录 1.顺序表简介什么是顺序表顺序表的分类 2.顺序表的实现 SeqList.h中接口总览具体实现顺序表的定义顺序表的初始化顺序表的销毁打印顺序表编辑检查顺序表的容量尾插尾删编辑头插头删查找在pos位置插入元素删除pos位置的值 …

1.顺序表简介

什么是顺序表

顺序表的分类

2.顺序表的实现

SeqList.h中接口总览

具体实现

顺序表的定义

顺序表的初始化

顺序表的销毁

打印顺序表

编辑

检查顺序表的容量

尾插

尾删

编辑

头插

头删

查找

在pos位置插入元素

删除pos位置的值

编辑

修改

3.完整代码附录

SeqList.h

SeqList.c

1.顺序表简介

什么是顺序表

顺序表是一种用物理地址连续的存储单元依次存储数据元素的线性结构。

等等，物理地址连续的存储单元…… 这不就是我们在C语言中学习过的数组吗？是的，我们可以这样理解，顺序表的底层物理结构就是数组。需要注意的是，顺序表的底层物理结构是数组，并不是说顺序表就是数组。顺序表要求依次存储，也就是存储数据元素的时候，从第一个位置紧挨着存储，对顺序表进行增、删、改、查操作之后的顺序表也必须满足这一特性。

顺序表的分类

顺序表一般可以分为静态顺序表和动态顺序表。静态顺序表使用定长数组存储元素，动态顺序表使用动态开辟的数组存储元素。

静态顺序表示意图：

动态顺序表示意图：

静态顺序表只适用于存储空间大小明确的场景。如果静态顺序表的大小N定大了，就会造成空间的浪费，如果N定小了就会造成空间不够用。在实际应用中，我们很少能够确切的知道需要处理的数据元素的大小，所以，静态顺序表在实际应用中并不实用，现实中基本都是使用动态顺序表，根据需要动态的分配空间。

2.顺序表的实现

基于上述原因，我们实现动态顺序表。我们需要创建两个文件，分别是SeqList.h和SeqList.c，SeqList.h中用来存放接口的声明，SeqList.c中存放接口的定义。（文章末尾附完整代码）

SeqList.h中接口总览

实现顺序表，主要实现顺序表的增删改查，需要实现以下接口。

具体实现

顺序表的定义

我们定义的顺序表的底层物理空间为动态开辟的，用变量a指向这块空间，用变量size记录存储的有效数据的个数，用变量capacity表示容量空间的大小，当size == capacity的时候就需要进行扩容操作了。

顺序表的初始化

对于初始化操作，我们主要初始化struct SeqList结构体变量中的成员即可。

对于最开始的容量可以根据实际需求动态设置即可；
size初始化为0，因为还没有向顺序表中添加元素。
capacity的初始值和动态申请的空间大小一致。

注意：

我们初始化顺序表的时候，指向顺序表的指针不能为空，我们使用assert()函数暴力的检查，如果ps指针为空，程序就会崩溃。使用assert()函数的时候，需要包含头文件assert.h。
我们还需要注意动态内存分配失败的情况，如果初始化的时候，动态分配内存失败，那么后面的程序都没有执行的必要了，我们使用exit()函数终止整个程序。使用exit()函数的时候，需要包含头文件stdlib.h。

后面的所有操作都需要判断指向顺序表的指针是否为空的情况（该指针不能为空！！！）

顺序表的销毁

销毁顺序表时，主要销毁的是struct SeqList结构体变量中的成员

对于变量a，需要将变量a指向的空间释放，也就是把使用权归还给操作系统；并将a置为空，避免出现野指针。
变量size和变量capacity置为0即可。

打印顺序表

直接循环打印即可。

检查顺序表的容量

当size == capacity的时候，说明顺序表的所有空间都用来存储有效元素了，当再次往顺序表中插入元素的时候，就没有空间了，需要扩容，我们选择2倍扩容。

扩容的时候，我们选择realloc函数。该函数会自动的帮我们申请一块空间，同时将原数组中的内容拷贝至新数组中，并且释放旧的数组空间，返回新空间的起始地址。

几个注意点：

检查realloc函数执行是否失败，如果失败，终止整个程序。
返回的新空间的起始地址需要赋值给变量a，因为我们始终认为struct SeqList结构体变量中的成员a才是指向数组空间的。
最后不要忘记放大变量capacity的值。

尾插

当进行插入操作的时候，我们需要判断顺序表的容量有没有满，如果满了就扩容，这一步可以复用我们前面实现的SLCheckCapacity()函数。

size表示有效元素的个数，作为下标的话就是有效元素的下一个位置。
不要忘记将size++。

进行任何插入操作时，我们都需要先检查容量是否足够。通过复用SLCheckCapacity()函数即可。

可以看出顺序表尾插的时间复杂度是O(1)。

尾删

进行尾部删除元素的时候，我们可以直接让size--即可，因为size表示存储的有效元素的个数，当size--之后，最后一个元素就不是有效元素了，可以被覆盖。当然，你也可以将最后一个有效元素修改为指定值之后再进行size--操作，但这并没有什么意义。

进行删除操作的时候，需要确保数组中存有有效元素。我们同样可以使用assert()函数进行暴力的检查。

可以看出顺序表尾删的时间复杂度也是O(1)。

我们可以得出结论：顺序表在尾部进行插入和删除的效率非常高，时间复杂度都是O(1)，因此，顺序表适合进行尾插尾删操作。

注意：后面所有的删除操作都需要确保数组中存有有效元素。

头插

进行头部插入时，也就是在数组的最开始位置插入元素，我们需要将所有的有效元素向后移动一个位置，然后再插入元素。

可以看出顺序表头插的时间复杂度是O(N)，如果频繁大量的进行头插操作，效率将非常低下。

头删

进行头删操作时，只需要将除了第一个有效元素后面的元素都往前移动一个位置，然后进行size--操作即可。

可以看出顺序表头删的时间复杂度也是O(N)，如果频繁大量的进行头删操作，效率将非常低下。

我们可以得出结论：顺序表在头部进行插入和删除的时间复杂度都是O(N)，因此，顺序表不适合进行大量的头插、头删操作。

查找

在顺序表中查找元素的时候，只需要遍历顺序表即可，找到了就返回下标，没找到返回-1。-1不是合法的下标，当返回-1的时候，就表明查找的元素不存在。

在pos位置插入元素

在pos位置插入元素，只需要将pos位置以及pos位置之后的元素都向后移动一个位置，然后将pos位置的值覆盖即可。插入元素之后不要忘记将size++。

pos的取值必须合法，在插入数据的时候，pos可以是最后一个有效元素的下一个位置。

删除pos位置的值

删除pos位置的值只需要将pos之后的有效元素都向前挪动一个位置，然后将size--即可。

删除pos位置的值的时候也需要注意pos的取值，此时，pos的取值不能是有效元素的下一个位置。

修改

进行修改操作时，我们只需要将指定位置的值修改即可。

值得一提的是，直接使用赋值语句就能修改，为什么还需要封装成函数呢？

因为我们封装的函数有严格的边界检查。
直接赋值使用的 [ ] 并没有严格的边界检查，[ ] 的下标检查是一种抽查机制，不能保证准确的发现越界问题。

3.完整代码附录

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 定义动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;   // 指向动态开辟的数组空间int size;        // 存储有效数据个数int capacity;    // 空间大小
}SL;// 初始化
void SLInit(SL* ps);
// 销毁
void SLDestroy(SL* ps);
// 打印
void SLPrint(SL* ps);
// 容量检查
void SLCheckCapacity(SL* ps);// 头插
void SLPushBack(SL* ps, SLDataType x);
// 头删
void SLPopBack(SL* ps);
// 尾插
void SLPushFront(SL* ps, SLDataType x);
// 尾删
void SLPopFront(SL* ps);// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x);// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);// 删除pos位置的值
void SLErase(SL* ps, int pos);// 修改pos位置的元素
void SLModify(SL* ps, int pos, SLDataType x);

SeqList.c

#include"SeqList.h"// 初始化 
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps->a == NULL){perror("malloc failed");exit(-1);}ps->size = 0;ps->capacity = 4;
}// 销毁 
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}// 打印 
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}// 容量检查 
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity *= 2;}
}// 尾插 
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}// 尾删 
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->size--;
}// 头插 
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);// 挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}// 头删 
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}// 查找 
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}// 删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}// 修改 
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}