目录
前言
顺序表是非常基础的数据结构，想必大家已经在日常学习过程中与它有所接触，比如对一个数组进行增删查改等操作，如果我们把数组和一个记录数据个数的变量放在同一个结构体中，再将增删查改分别封装成函数，提供其接口，这样一个简单的静态顺序表就完成啦。是不是感觉这个过程有一丢丢的熟悉？这不就是通讯录、成绩管理系统等小项目的实现方式吗？对的，所以说学会了顺序表，那么完成一个像通讯录、成绩管理系统……这样的小项目也就变的非常简单啦。
一、概念
线性表采用顺序存储的方式存储就称之为顺序表，顺序存储是指用一段物理地址连续的存储单元依次存储相邻数据元素的线性结构（这是顺序表的一大优势，这让它可以做到随机存取）。
顺序表在计算机内存中是以数组的形式保存，在数组上完成数据的增删查改，可以将顺序表简单理解为数组。
二、结构
顺序表一般可以分为：静态顺序表、动态顺序表。
·静态顺序表：使用定长数组存储元素:
//静态顺序表结构体的两个关键元素：存储数据的数组、记录数据个数的变量
#define N 100//使用宏定义便于修改静态顺序表的容量（define 后面没有";"）
typedef int SLDataType;//重定义要存储的数据的数据类型，可以根据我们的需要来修改要存储数据的数据类型（typedef 后面有";"）
typedef struct SeqList
{
SLDataType arr[N];
int size;//记录数据个数
}SL;
静态顺序表的缺点非常明显：当定义的容量N太小，不够用，N太大，又浪费空间。那我们不禁思考：我们可不可以先开辟一个较小的空间，当容量不足时，容量自动扩大一点呢？
结合我们所学过的动态内存分配，我们考虑使用一个动态开辟的数组来解决这一问题，将原来结构体的静态数组改变为动态开辟的数组，加上一个变量专门记录容量，这就形成了一个动态顺序表的结构体。
·动态顺序表：使用动态开辟的数组存储
//动态顺序表结构体的三个关键元素：存储数据的数组的指针、记录数据个数的变量、记录容量的变量
typedef int SLDataType;//重定义要存储的数据的数据类型，可以根据我们的需要来修改要存储数据的数据类型
typedef struct SeqList
{
SLDataType* arr;//指向动态数组的指针（存储空间的基地址）
int size;//记录数据个数
int capacity;//记录容量
}SL;回顾：动态内存分配：
1.要引入头文件stdio.h。
2.常用函数有malloc,relloc,free。
三、动态顺序表接口实现
数据结构要在内存中管理数据，做到增删查改等操作，这就要依靠我们提供的接口，才能达到这一目的，对于各种数据结构，我们要实现的接口一般有初始化（Init）、销毁（Destory）、增、删、查、改、打印（Pint）、判断是否为空（Empty），当然了由于一些数据结构自身的特性，我们有可能还要实现其它接口，也可能不需要实现以上某些接口。
以下是顺序表常用的接口（命名参考C++的STL）：
1.初始化函数（SLInit）
要特别注意的是：
a. 要改变实参的内容，我们必须传入实参的地址，这就是我们所说的传址调用。
在初始化过程中，我们要借助形参，把实参（动态顺序表结构体）的内容修改，故我们要形参定义为结构体指针，传入实参的地址，即动态顺序表结构体的地址。
传值调用和传址调用的对比：
b. 传入实参的地址，带来了另外的问题，要知道在建立结构体指针后，其地址一定不为NULL，用户如果不小心或恶意传入空指针，就会造成空指针异常，导致程序崩溃。使用这个时候我们还要检查传入的动态顺序表结构体的地址是否为空。我们可以温柔一点用 if(ps == NULL) {……}来检查，但我更推荐使用assert语句进行暴力的断言处理，这样就可以在发生不符合assert语句里的条件的错误时，根据返回的信息快速定位错误的位置， 但要注意assert只在debug模式下生效。
我们尝试一下，向初始化函数传入一个空指针
根据提示，我们能快速定位问题发生在SeqList.c文件的第五行
void* SLInit(SL* ps)//初始化函数
{
assert(ps != NULL);//防止恶意传递空指针
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
2.销毁函数（SLDestory）
主要是为了释放动态开辟的数组空间。
实现这个接口的注意事项主要有：
1.因为要改变动态顺序表结构体的内容，依旧要传入动态顺序表结构体的地址。
2.防御性检查，防止恶意传入空指针。
3.判断动态开辟的数组空间是否为空，不为空要用free函数释放空间。
4.让arr指向NULL，防止野指针问题。
5.使变量size（记录数据个数的变量）和capacity（记录容量大小的变量）归0 。
扩展：C/C++没有像Java那样的垃圾回收，动态开辟的空间不主动释放，在程序退出异常的情况下会成为僵尸，一直占用用户的内存，这就是通常所说的内存泄漏问题。
让我们看看开辟空间后不释放的后果：
动态开辟1G空间，不释放：
程序运行前：
程序运行后：
试想一下，如果是聊天软件、游戏这类需要长时间运行的程序，不断的内存泄漏到最后的程序崩溃是多么严重的事故，现在你理解使用free函数主动释放动态开辟的内存空间的重要性了吧。
void SLDestory(SL* ps)//销毁函数
{
assert(ps != NULL);//防止恶意传递空指针
if (ps->arr)
{
free(ps->arr);//释放空间
ps->arr = NULL;//置空防止野指针
ps->capacity = ps->size = 0;
}
}3.打印函数（SLPint）
循环遍历一遍结构体中存放数据的数组，将其一一打印。传值调用和传址调用都行，因为不需要改变动态顺序表结构体的内容。
void SLPint1(SL ps)//打印函数1(传值)
{
for (int i = 0; i < ps.size; i++)
{
printf("%d ", ps.arr[i]);
}
printf(" capacity:%d\n", ps.capacity);
putchar(10);//换行
}
void SLPint2(SL* ps)//打印函数2(传址)
{
assert(ps != NULL);//防止恶意传递空指针
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf(" capacity:%d\n", ps->capacity);
putchar(10);
}4.检查函数（SLCheckCapacity）
用于检查容量是否已满，满了就给数组扩容。
实现这个接口的注意事项主要有：
1.扩容时可能会改变数组的存储空间和容量大小，故要传入动态顺序表结构体的指针。
2.扩容使用的是relloc函数，当内存空间不足时，扩容会失败需要检查。
3.防御性检查。
void SLCheckCapacity(SL* ps)//检查函数（检查容量是否已满）
{
assert(ps != NULL);//防御恶意传递空指针
if (ps->size == ps->capacity)//检查容量空间
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//确定新容量大小（考虑容量为0的情况）
SLDataType* tmp = realloc(ps->arr, newcapacity * sizeof(SLDataType));//使用realloc函数开辟扩容后的新空间
//当容量满时用realloc函数扩容有可能失败
if (tmp == NULL)//如果扩容失败
{
printf("realloc fail!\n");
exit(-1);//退出程序
}
ps->arr = tmp;//将新空间赋给数组
ps->capacity = newcapacity;//更新容量大小
//使用realloc函数完全有可能原地扩容，故这里没有使用free释放原空间。
}
}5.尾插（SLPushBack）
在顺序表结构体中数组的尾部（即下标为size的位置）插入元素，要修改顺序表结构体的内容，依旧要传入指针。
实现这个接口的注意事项主要有：
1.防御性检查。
2.插入要检查容量是否已满，满了要扩容。（顺序表的插入都要进行检查）
3.插入完成后有效数据个数（size）加一。
void* SLPushBack(SL* ps, SLDataType x)//尾插
{
assert(ps != NULL);//防御恶意传递空指针
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;//插入完成后有效数据个数加一
}6.头插（SLPushFrant）
在顺序表结构体中数组的头部（即下标为0的位置）插入元素，要修改顺序表结构体的内容，依旧要传入指针。
实现这个接口的步骤：
1.防御性检查。
2.检查容量是否已满，满了要扩容。
3.从最后一个数据开始到第一个数据，每个数据都往后挪动一位。
4.头插：在下标为0的位置插入元素。
5.插入完成后有效数据(size)个数加一。
为什么头插要从最后一个数据开始向后挪动数据？
如果我们从第一个数据开始向后挪，会覆盖下一个数据，造成数据丢失：
如果我们从最后一个数据开始挪动，则能顺利空出第一个位置：
void* SLPushFrant(SL* ps, SLDataType x)//头插
{
assert(ps != NULL);//防御恶意传递空指针
SLCheckCapacity(ps);
int end = ps->size - 1;//确定最后一个数据
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];//从最后一个数据开始，向后移动一位。
end--;
}
ps->arr[0] = x;
ps->size++;
}
7.尾删（SLPopBack）
删除顺序表结构体中数组的尾部（即size位置）元素，我们直接让记录有效数据的个数的size减一就可以了。
void* SLPopBack(SL* ps)//尾删
{
assert(ps != NULL);//防御恶意传递空指针
//暴力检查
assert(ps->size > 0);//条件为假，报警告。
//温柔检查
/*if (ps->size <= 0)
{
printf("有效数据个数为0，无法删除！\n");
return;
}*/
ps->size--;//删除完成后有效数据个数减一
}8.头删（SLPopFrant）
要删除顺序表结构体中数组的头部（即下标为0的位置）的数据，要修改顺序表结构体的内容，依旧要传入指针。
实现这个接口的步骤：
1.防御性检查。
2.检查数组中是否还有数据（检查有效数据个数是否为0），没有数据不支持删除操作。
3.从第二个数据开始到最后一个数据，每个数据都往前挪动一位。
4.有效数据个数（size）减一。
为什么
头删要从第个二数据开始向前挪动数据？
如果我们从最后一个数据开始向前挪，会覆盖前数据，造成数据丢失：
如果我们从第二个数据开始挪动，则能做到只覆盖第一个位置：
void* SLPopFrant(SL* ps)//头删
{
assert(ps != NULL);//防御恶意传递空指针
//检查有效数据个数是否为0
assert(ps->size > 0);
int begin = 1;
while (begin < ps->size)
{
ps->arr[begin - 1] = ps->arr[begin];
++begin;
}
ps->size--;//删除后，有效数据个数要减少1
}在面试过程中，你可能会遇到这样的要求：请在10分钟内完成一个顺序表。
这不是HR（面试官）在为难你，学习以下接口后，你会发现你也可以做到10分钟内完成一个顺序表，甚至更快。
9.在指定位置插入数据（SLInsert）
在顺序表结构体中数组的pos位置数据插入数据，要修改顺序表结构体的内容，依旧要传入指针。
实现这个接口的步骤：
1.防御性检查。
2.检查数据的插入位置是否合理（0 <= pos <= size）。
3.检查容量是否已满，满了要扩容。（顺序表的插入都要进行检查）
4.从最后一个数据开始，向后挪动一位，直到挪完pos位置上的数据（顺序表的插入除尾插外，都要从最后一个数据开始，向后挪动一位）
5.有效数据个数（size）加一。
void* SLInsert(SL* ps, int pos, int x)//在指定位置插入数据。
{
assert(ps != NULL);//行防御性检查
assert(pos >= 0 && pos <= ps->size);//检查数据的插入位置是否合理(注意到pos == 0时为头插，pos == size时为尾插)
SLCheckCapacity(ps);
int end = ps->size - 1;//顺序表插入只要是非尾插，就要从最后一个数据开始，向后挪动一位
while (end >= pos)//挪动数据，直到挪完pos位置上的数据
{
ps->arr[end + 1] = ps->arr[end];
--end;
}
ps->arr[pos] = x;
//插入完数据后，有效数据个数size一定要加1
ps->size++;
}
10.在指定位置删除数据（SLErase）
要删除顺序表结构体中数组的pos位置的数据，要修改顺序表结构体的内容，依旧要传入指针。
实现这个接口的步骤：
1.防御性检查。
2.检查要删除的数据的位置是否合理（0 <= pos < size），要注意由于数组下标从0开始，所以size位置上没有数据，不能删除。
3.从pos+1位置开始，向前挪动一位，直到挪完最后一个位置（size-1）上的数据。（我们也可以从pos位置开始，用下一个数据覆盖，直到size-2位置的数据被覆盖。）
4.有效数据个数（size）减一。
void* SLErase(SL* ps, int pos)//删除指定位置的数据。
{
assert(ps != NULL);//防御性检查
assert(pos >= 0 && pos < ps->size);//检查pos的范围（和插入时的pos的范围不同）
//从pos位置开始
/*int begin = pos;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin + 1];
++begin;
}*/
//从pos+1位置开始
int begin = pos + 1;
while (begin < ps->size)
{
ps->arr[begin - 1] = ps->arr[begin];
++begin;
}
--ps->size;
}
回到刚才的问题：如何10分钟内完成一个顺序表？靠的就是以上两个接口来简化头插、尾插、头删、尾删。
尾插简化
void* SLPushBack(SL* ps, SLDataType x)//尾插 { SLInsert(ps, ps->size, x);//指定在尾部（ps下标处）插入 }头插简化
void* SLPushFrant(SL* ps, SLDataType x)//头插 { SLInsert(ps, 0, x);//指定在头部（0下标处）插入 }尾删简化
void* SLPopBack(SL* ps)//尾删 { SLErase(ps, ps->size - 1);//指定在尾部（ps下标处）删除 }头删简化
void* SLPopFrant(SL* ps)//头删 { SLErase(ps, 0);//指定在头部（0下标处）删除 }怎样是不是非常简单，完成一个顺序表的速度是不是瞬间就上去了？
11.查找函数（SLFind）
作用是找到指定数字的下标，找不到就返回-1。
循环遍历一遍数组，找到后返回指定数字的下标，找不到就返回-1 。
int SLFind(SL* ps, int x)//查找函数（找到指定数字的下标）
{
assert(ps != NULL);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;//找到后返回该数字的下标
}
return -1;//找不到返回-1
}12.修改函数（SLModify）
作用是修改数组中指定下标的数据。
直接对数组pos位置上的数据进行修改，注意要修改顺序表结构体的内容，依旧要传入指针。
void* SLModify(SL* ps, int pos, int x)//修改函数
{
assert(ps != NULL);
assert(0 <= pos && pos < ps->size);
ps->arr[pos] = x;
}四、顺序表的优点与缺点
·优点：
其一，顺序表采用顺序存储的方式存储数据，存储单元物理地址连续 ，这让它可以做到随机存取 ，这是很棒的一个优点，其他数据结构大多都无法做到这一点，所以尽管顺序表是如此的基础，但它仍有着它自己的独特作用。·缺点：
其一，对于静态顺序表来说，由于C语言中，数组一旦被声明，其长度即该结构占用的存储空间是固定的，申请的空间过大，造成空间的浪费同时也为维护该结构造成困难，申请过小，在程序运行过程中，有可能会造成结构空间不足，导致程序故障；
其二，动态顺序表虽然解决了静态顺序表无法增容的问题，但是还不够完美，要知道增容需要申请新空间，拷贝数据，释放旧空间，这都会消耗的计算机性能；
其三，动态顺序表的增容一般是呈1.5/2倍的增长，还是会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们如果只再继续插入了1个数据，那么就浪费了99个数据空间；
其四，在中间/头部插入，删除数据时，通常会导致大量数据的移动，时间复杂度为O(N)。
·思考：有没有一种数据结构能克服以上缺点呢？这就要提到我们接下来要讲解的链表了：数据结构详解(其二) 单链表
·顺序表的经典OJ题和常见面试题：数据结构OJ(其一) 顺序表
如果你还有其他想要学习的数据结构不妨在这里找找看：数据结构详解（序）
五、源码+详细注释（C语言实现）
1.SeqList.h
#pragma once//防止同一个文件被包含多次。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100//便于修改静态顺序表的容量（define 后面没有";"）
typedef int SLDataType;//便于修改数据类型（typedef 后面有";"）
//1.静态顺序表结构体
//typedef struct SeqList
//{
// SLDataType arr[N];
// int size;
//}SL;
//2.动态顺序表结构体
typedef struct SeqList
{
SLDataType* arr;//指向动态数组的指针
int size;//记录数据个数
int capacity;//记录容量
}SL;
void* SLInit(SL* ps);//初始化函数
void SLPint1(SL ps);//打印函数1(传值)
void SLPint2(SL* ps);//打印函数2(传址)
void SLCheckCapacity(SL* ps);//检查函数（检查容量是否已满）
void SLDestory(SL* ps);//销毁函数
void* SLPushBack(SL* ps, SLDataType x);//尾插
void* SLPushFrant(SL* ps, SLDataType x);//头插
void* SLPopBack(SL* ps);//尾删
void* SLPopFrant(SL* ps);//头删
void* SLInsert(SL* ps, int pos, int x);//在指定位置插入数据。
void* SLErase(SL* ps, int pos);//在指定位置删除数据。
int SLFind(SL* ps, int x);//查找函数（找到指定数字的下标）
void* SLModify(SL* ps, int pos, int x);//修改函数
2.SeqList.c
#include"SeqList2.h"
void* SLInit(SL* ps)//初始化函数
{
assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLPint1(SL ps)//打印函数1(传值)
{
for (int i = 0; i < ps.size; i++)
{
printf("%d ", ps.arr[i]);
}
printf(" capacity:%d\n", ps.capacity);
putchar(10);//换行
}
void SLPint2(SL* ps)//打印函数2(传址)
{
assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf(" capacity:%d\n", ps->capacity);
putchar(10);
}
void SLCheckCapacity(SL* ps)//检查函数（检查容量是否已满）
{
assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
if (ps->size == ps->capacity)//检查容量空间
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//确定新容量大小（考虑容量为0的情况）
SLDataType* tmp = realloc(ps->arr, newcapacity * sizeof(SLDataType));//使用realloc函数开辟扩容后的新空间
//当容量满时用realloc函数扩容有可能失败
if (tmp == NULL)//如果扩容失败
{
printf("realloc fail!\n");
exit(-1);//退出程序
}
ps->arr = tmp;
ps->capacity = newcapacity;
//使用realloc函数完全有可能原地扩容，故这里没有使用free释放原空间。
}
}
void SLDestory(SL* ps)//销毁函数
{
assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
if (ps->arr)
{
free(ps->arr);//释放空间
ps->arr = NULL;//置空防止野指针
ps->capacity = ps->size = 0;
}
}
void* SLPushBack(SL* ps, SLDataType x)//尾插
{
//assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
//SLCheckCapacity(ps);
//ps->arr[ps->size] = x;
//ps->size++;
SLInsert(ps, ps->size, x);
}
void* SLPushFrant(SL* ps, SLDataType x)//头插
{
//assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
//SLCheckCapacity(ps);
//int end = ps->size - 1;//确定最后一个数据
//while (end >= 0)
//{
// ps->arr[end + 1] = ps->arr[end];//从最后一个数据开始，向后移动一位。
// end--;
//}
//ps->arr[0] = x;
//ps->size++;
SLInsert(ps, 0, x);
}
void* SLPopBack(SL* ps)//尾删
{
//assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
暴力检查
//assert(ps->size > 0);//条件为假，报警告。
温柔检查
///*if (ps->size <= 0)
//{
// printf("有效数据个数为0，无法删除！\n");
// return;
//}*/
//ps->size--;
SLErase(ps, ps->size - 1);
}
void* SLPopFrant(SL* ps)//头删
{
//assert(ps != NULL);//当形参为指针时，要防御恶意传递空指针
检查有效数据个数是否为0
//assert(ps->size > 0);
//int begin = 1;
//while (begin < ps->size)
//{
// ps->arr[begin - 1] = ps->arr[begin];
// ++begin;
//}
//ps->size--;//删除后，有效数据个数要减少1
SLErase(ps, 0);
}
void* SLInsert(SL* ps, int pos, int x)//在指定位置插入数据。
{
assert(ps != NULL);//只要形参为指针，就要进行防御性检查
assert(pos >= 0 && pos <= ps->size);//检查数据的插入位置是否合理(pos == 0时为头插，pos == size时为尾插)
SLCheckCapacity(ps);
int end = ps->size - 1;//顺序表插入只要是非尾插，就要从最后一个数据开始，向后挪动一位
while (end >= pos)//挪动数据，直到挪完pos位置上的数据
{
ps->arr[end + 1] = ps->arr[end];
--end;
}
ps->arr[pos] = x;
//插入完数据后，有效数据个数size一定要加1
ps->size++;
}
void* SLErase(SL* ps, int pos)//在指定位置删除数据。
{
assert(ps != NULL);//传址要进行防御性检查
assert(pos >= 0 && pos < ps->size);//检查pos的范围（和插入时的pos的范围不同）
//从pos位置开始
/*int begin = pos;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin + 1];
++begin;
}*/
//从pos+1位置开始
int begin = pos + 1;
while (begin < ps->size)
{
ps->arr[begin - 1] = ps->arr[begin];
++begin;
}
--ps->size;
}
int SLFind(SL* ps, int x)//查找函数（找到指定数字的下标）
{
assert(ps != NULL);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;//找到后返回该数字的下标
}
return -1;//找不到返回-1
}
void* SLModify(SL* ps, int pos, int x)//修改函数
{
assert(ps != NULL);
assert(0 <= pos && pos < ps->size);
ps->arr[pos] = x;
}3.SeqListTest.c（测试用例）
#include"SeqList2.h"
int main()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPint1(s);
SLPushBack(&s, 5);
SLPushFrant(&s, 0);
SLPushFrant(&s, -1);
SLPushBack(&s, 6);
SLPint2(&s);
SLPushFrant(&s, -2);
SLPint2(&s);
SLPopBack(&s);
SLPint2(&s);
SLPopFrant(&s);
SLPopFrant(&s);
SLPint2(&s);
SLInsert(&s, 0, -1);
SLInsert(&s, s.size, 6);
SLPint2(&s);
SLErase(&s, 0);
SLErase(&s, s.size-1);
SLPint2(&s);
printf("请输入你要修改的数字：\n");
int n = 0;
scanf("%d", &n);
int x = SLFind(&s, n);
printf("请输入修改后的数字：\n");
int y;
scanf("%d", &y);
SLModify(&s, x, y);
SLPint2(&s);
SLDestory(&s);
return 0;
}今天的文章数据结构顺序表是什么_数据结构拓扑排序分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：http://bianchenghao.cn/89262.html
