浅谈数据结构顺序表的实现（超详细，附代码）_顺序表的定义和操作实现流程图

这篇博客我们来谈数据结构顺序表的实现操作。谈数据结构的顺序表，我们要从线性表开始说起。
注：本顺序表的实现基于
编译器：VS2015
语言： C/C++
头文件：2个
源文件：1个

一、线性表介绍

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。
常见的线性表：顺序表、链表、栈、队列、字符串…

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

二、顺序表基本介绍

2.1 概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
1

2.2 分类

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组存储。
1
2
3

2.3 分类示例

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
   
SLDataType array[N]; // 定长数组
 size_t size; // 有效数据的个数
}SeqList;
1
2
3
4
5
6
7
8
9

// 顺序表的动态存储
typedef struct SeqList
{
   
SLDataType* array; // 指向动态开辟的数组
size_t size ; // 有效数据个数
size_t capicity ; // 容量空间的大小
}SeqList;
1
2
3
4
5
6
7
8

2.4 应用范围

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，
1
2

三、顺序表的实现

本顺序表的代码共包含三个文件。

3.1 Common.h

此头文件主要是添加了一些系统头文件，如校验文件、bool文件等等，宏的定义，还有一个交换函数。

#ifndef _COMMON_H
#define _COMMON_H

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define ElemType int  //便于类型的修改

//交换函数
void Swap(ElemType *a, ElemType *b)
{
   
	ElemType tmp = *a;
	*a = *b;
	*b = tmp;
}

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 seqlist.h

这个头文件 主要包含了顺序表结构的定义、顺序表操作的声明以及定义、顺序表初始容量的定义（便于修改）。

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

#include "Common.h"
#pragma warning(disable:4996)

#define SEQLIST_DEFAULT_SIZE 8

//定义顺序表结构
typedef struct SeqList
{
   
	ElemType* base;
	size_t capacity;
	size_t size;
}SeqList;

void SeqListInit(SeqList *plist);                         //初始化
void SeqListPushBack(SeqList *plist, ElemType x);         //尾插
void SeqListShow(SeqList *plist);                         //显示
void SeqListPushFront(SeqList *plist, ElemType x);        //头插
void SeqListDestroy(SeqList *plist);                      //摧毁                     
void SeqListPopBack(SeqList *plist);                      //尾删
void SeqListClear(SeqList *plist);                        //清理
bool SeqListInsertByPos(SeqList *plist, int pos, ElemType x);   //按位置插入
void SeqListSort(SeqList *plist);                         //排序
size_t SeqListLength(SeqList *plist);                     //统计长度
void SeqListPopFront(SeqList *plist);                     //头删
bool SeqListInsertByVal(SeqList *plist, ElemType x);      //按值插入
size_t SeqListCapacity(SeqList *plist);                   //顺序表容量
void SeqListEraseByPos(SeqList *plist, int pos);          //按位置清除
int SeqListFind(SeqList *plist, ElemType key);            //查找
void SeqListEraseByVal(SeqList *plist, ElemType key);     //按值清除
void SeqListReverse(SeqList *plist);                      //转置
/

bool _Inc(SeqList *plist, size_t new_capacity)
{
   
	assert(plist != NULL && new_capacity > plist->capacity);
	ElemType *new_base = (ElemType*)realloc(plist->base, sizeof(ElemType)*new_capacity)
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