顺序表(SequenceList)数据结构的基本操作实现详解

数据结构的基本操作实现详解"/>

顺序表(SequenceList)数据结构的基本操作实现详解

目录

• 一、前言
• 二、整体设计框架
• 三、函数实现
• • 1. SeqListInit
  • 2. SeqListDestory
  • 3. SeqListCheckCapacity
  • 4. SeqListPushBack(尾插)
  • 5. SeqListPopBack(尾删)
  • 6. SeqListPushFront(头插)
  • 7. SeqListPopFront(头删)
  • 8. SeqlistFind
  • 9. SeqListInsert(任意位置插入)
  • 9. SeqListErase(任意位置删除)
  • 10. SeqListAt
  • 11. SeqListSize
• 四、完整代码
• • 1. test.c 测试代码
  • 2. sequenceList.h 头文件
  • 3. sequenceList.c 函数实现

一、前言

数据结构非常之多，后续小编会逐个更新，简单的存储数据一般有顺序表，链表（单链表和双链表），串等

创建完数据结构后不仅要存储数据，以后还需要查找数据，如果高效的进行查找也需要搜索树，哈希表等这样的结构来实现

有很多人有这样一个疑问：是先学数据结构还是先学算法？
其实数据结构和算法是不分家的，数据结构中包含一些算法，有些算法的解决又离不开数据结构，比如实现Dijkstra最短路径问题是基于Graph的数据结构实现的

二、整体设计框架

实现顺序表，我们可以分为三个文件，这样可读性更高，如果所有函数都在一个文件里会显得臃肿，其次不便于调试，之前实现 扫雷游戏也是按照图中框架来设计

1. test.c专门用于函数调用、调试
2. sequenceList.h 只用于函数声明
3. sequenceList.c 用于函数实现

三、函数实现

首先我们看一下头文件，顺序表有哪些函数需要实现以及结构的设计。

//typedef char SeqDataType;typedef int SeqDataType;typedef struct SeqList{SeqDataType* data;int size;   //当前数组有效数据个数int capacity;   //总容量大小，不够则进行扩容
}SLT;void SeqListInit(SLT* list);

这里的重新定义了一个SeqDataType方便后续类型的修改，可能是int，可能是char，也可能是float类型的数据

然后接着定义了一个SeqList结构，里面的第一个成员用于数据存储，第二个size和下面的capacity不要搞混淆了，前者是表示当前有多少个有效数据个数，后者是容器说明一共能存储多少数据，如果不够则进行扩容

顺序表一般都采用动态的，因为你不知道用户需要用多少空间

1. SeqListInit

我们在 sequenceList.c 中对SeqListInit函数进行初始化

void SeqListInit(SLT* list){assert(list);list->data = NULL;list->size = 0;list->capacity = 0;
}

这里我们的函数中都需要进行一下断言，防止用这个函数的人不小心传了一个NULL进来，反之不判断deubg需要花很多时间
ps: 记得#include <assert.h>

2. SeqListDestory

用完之后记得free开辟的动态空间，并把data置空

void SeqListDestroy(SLT* s){if(s->data){free(s->data);s->data = NULL;}s->capacity = 0;s->size = 0;
}

3. SeqListCheckCapacity

我们在进行push操作之前需要确认一下容量是否为空，如果为则默认分配4个空间大小，如果不为空在原来容量基础上扩容二倍。

为什么是二倍不是三倍四倍？
这是防止开多了空间浪费，后续讲解的链表可以很好的解决这个问题

//检查容量是已满
void SeqListCheckCapacity(SLT* s){assert(s);size_t sz = s->capacity == 0 ? 4: (s->capacity)*2;if(s->size == s->capacity){SeqDataType* newSize = (SeqDataType*)realloc(s->data, sizeof(SeqDataType)*sz);if(newSize!=NULL){s->data = newSize;}else{printf("Failed to realloc \n");}}
}

4. SeqListPushBack(尾插)

此函数就直接调用SeqListCheckCapacity来检测容量大小

//尾插
void SeqListPushBack(SLT* s ,SQDataType x){assert(s);SeqListCheckCapacity(s);s->arr[s->size] = x;s->size++; 
}

5. SeqListPopBack(尾删)

注意⚠️ ：这里我们要判断一下size的大小，如果size已经为0了，那么必须提醒用户，如果不加这一句判断，删过头编译器是不会报错的，后续就不便于debug咯

void SeqListPopBack(SLT* s){assert(s);assert(s->size>0);s->size--;
}

6. SeqListPushFront(头插)

这里的头插需要注意数据向后挪的顺序，顺序是从最后一个数据开始向后挪动，从前开始向后挪会导致数据被覆盖

void SeqListPushFront(SLT* s, SeqDataType x){