一、线性表

在学习顺序表和链表之前，先要了解什么是线性表：

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

文章所讲述的顺序表和下一篇链表便是线性表的一种。

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

例如：顺序表和链表

顺序表在逻辑结构上是连续的，物理结构上也是连续的；

链表在逻辑结构上是连续的，但是在物理结构上不是连续的

-------------------我是分割线------------------

二、顺序表

2.1 顺序表概念及结构

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

顺序表一般可以分为：静态顺序表、动态顺序表

（1）静态顺序表：使用定长数组存储元素。

#define N 100//对空间大小进行了限定typedefintSLDataType;便于修改存储的数据类型typedefstructSeqList{
SLDataTypearr[N];//定义需要的数组长度intsize;//记录数组的有效个数（已使用）}SL;
//缺陷：空间给小了不够用，给大了可能浪费，不实用

（2）动态顺序表：使用动态开辟的数组存储

typedefintSLDataType;//便于修改存储的数据类型typedefstructSeqList{
SLDataType*arr;//指向动态开辟的数组，用于存放数据。空间不够则增容intsize;//数组的个数intcapacity;//容量大小}SL;

2.2 顺序表接口实现

首先，我们要创建一个顺序表类型，该顺序表类型包括了顺序表的起始位置、记录顺序表内已有元素个数的计数器(size)，以及记录当前顺序表的容量的变量(capacity)，这里实现的是动态顺序表

typedefintSLDataType;//便于修改存储的数据类型//顺序表的动态储存typedefstructSeqList{
SLDataType*arr;//指向动态开辟的数组，用于存放数据intsize;//数组的个数intcapacity;//容量大小}SL;

2.2.1 顺序表初始化

//初始化顺序表voidSeqListInit(SL*ps)
{
ps->arr=NULL;
ps->size=0;
ps->capacity=0;
}

2.2.2 顺序表的销毁

顺序表所用的内存空间是动态开辟在堆区的，所以我们在使用完后需要及时对其进行释放，避免造成内存泄漏。

//销毁顺序表
void SeqListDestroy(SL* ps)
{
  assert(ps);
  if (ps->size)
  {
    free(ps->arr);
    ps->arr = NULL;
    ps->size = 0;
    ps->capacity = 0;
  }
}

2.2.3 顺序表的打印

遍历即可

//打印voidSeqListPrint(SL*ps)
{
assert(ps);
inti=0;
for (i=0; i<ps->size; i++)
    {
printf("%d ", ps->arr[i]);
    }
printf("\n");
}

2.2.4 顺序表增加数据（插入，头插、尾插）

每次需要增加数据的时候，首先都应该先检查顺序表内元素个数是否已达顺序表容量上限。若已达上限，那么我们就需要先对顺序表进行扩容，然后才能增加数据。

（1）插入：就是从两个数据中间直接直接插入一个新的数据(时间复杂度为O(n)）

//插入voidSeqListInsert(SL*ps, intpos, SLDataTypen)
{
assert(ps);
assert(pos>=0&&pos<=ps->size);
CheckCapacity(ps);//检查顺序表容量，不够则开辟新空间//挪动数据intend=ps->size-1;
while (end>=pos);
    {
ps->arr[end+1] =ps->arr[end];
end--;
    }
ps->arr[pos] =n;
ps->size++;
}

//检查顺序表容量voidCheckCapacity(SL*ps)
{
assert(ps);
//进行扩容，两种情况，1、没有开辟空间  2、空间不足if (ps->size==ps->capacity)
    {
intNewCapacity= (ps->capacity==0?4 : ps->capacity*2);
SLDataType*tmp= (SLDataType*)realloc(ps->arr, NewCapacity*sizeof(SLDataType));
if (tmp==NULL)
        {
printf("realloc fail\n");
//return;exit(-1);
        }
ps->arr=tmp;
ps->capacity=NewCapacity;
    }
}

（2）头插：顾名思义就是从头部插入一个新的数据（时间复杂度为O(n)）

这里有两种写法，推荐可以直接复用插入的代码

//顺序表的头插voidSeqListPushFront(SL*ps, SLDataTypen)
{
/*assert(ps);CheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = n;ps->size++;*///两种都行，下面这种比较方便SeqListInsert(ps, 0, n);
}

（3）尾插：这个比较简单，直接从尾上插入即可（时间复杂度为O(1)）

这里也是有两种写法，推荐可以直接复用插入的代码

//尾插voidSeqListPushBack(SL*ps, SLDataTypen)
{
/*assert(ps);CheckCapacity(ps);ps->arr[ps->size] = n;ps->size++;*///两种都行，下面这种比较方便SeqListInsert(ps, ps->size, n);
}

2.2.5 顺序表删除数据（删除，头删、尾删）

删除数据，其实可以理解为：从某个位置开始，数据依次向前覆盖。这样一来，该位置的数据就相当于删除了。

（1）删除：直接删除 pos 位置的值，向前覆盖（时间复度为O(n)）

//删除数据voidSeqListErase(SL*ps, intpos)
{
assert(ps);
assert(pos>=0&&pos<ps->size);
intbegin=pos;
while (begin<ps->size-1)
    {
ps->arr[begin] =ps->arr[begin+1];
begin++;
    }
ps->size--;
}

（2）头删（时间复杂度为O(n)）

这里也是有两种写法，这里也是有两种写法，推荐可以直接复用删除的代码

//头删， O(n)voidSeqListPopFront(SL*ps)
{
/*assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];begin++;}ps->size--;*///两种都行，下面这种比较方便SeqListErase(ps, 0);
}

（3）尾删（时间复杂度为O(1)）

这里也是有两种写法，推荐可以直接复用删除的代码

//尾删voidSeqListPopBack(SL*ps)
{
/*assert(ps);assert(ps->size > 0);ps->size--;*///两种都行，下面这种比较方便SeqListErase(ps, ps->size-1);
}

2.2.6 顺序表查找数据

查找数据也相对简单，直接遍历一次顺序表即可，若找到了目标数据，则停止遍历，并返回该数据的下标

//查找数据intSeqListFind(SL*ps, SLDataTypen)
{
assert(ps);
inti=0;
for (i=0; i<ps->size; i++)
    {
if (ps->arr[i] ==n)
        {
returnn;//找到了        }
    }
return-1; //找不到}

2.2.7 顺序表修改数据

修改数据，就直接对该位置的数据进行再次赋值即可。

//修改数据voidSeqListModify(SL*ps, intpos, SLDataTypen)
{
assert(ps);
assert(pos>=0&&pos<ps->size);
ps->arr[pos] =n;
}

-------------------我是分割线------------------

三、顺序表完整代码（C语言）

分三个文件写

SeqList.h（类型定义、接口函数声明、引用的头文件）

SeqList.c（接口函数的实现）
Test.c（主函数、测试顺序表各个接口功能）

3.1 SeqList.h

#pragma once//防止头文件被二次引用//声明#define _CRT_SECURE_NO_WARNINGS//vs编译器需要，可自行删去#include <stdio.h>#include <stdlib.h>#include <assert.h>typedefintSLDataType;//便于修改存储的数据类型//顺序表的动态储存typedefstructSeqList{
SLDataType*arr;//指向动态开辟的数组，用于存放数据intsize;//数组的个数intcapacity;//容量大小}SL;
//初始化顺序表voidSeqListInit(SL*ps);
//打印voidSeqListPrint(SL*ps);
//检查顺序表容量voidCheckCapacity(SL*ps);
//销毁顺序表voidSeqListDestroy(SL*ps);
//增//顺序表的头插，O(n)voidSeqListPushFront(SL*ps, SLDataTypen);
//尾插,O(1)voidSeqListPushBack(SL*ps, SLDataTypen);
//插入数据voidSeqListInsert(SL*ps, intpos, SLDataTypen);
//删//头删， O(n)voidSeqListPopFront(SL*ps);
//尾删, O(1)voidSeqListPopBack(SL*ps);
//删除数据voidSeqListErase(SL*ps, intpos);
//查找数据intSeqListFind(SL*ps, SLDataTypen);
//修改数据voidSeqListModify(SL*ps, intpos, SLDataTypen);

3.2 SeqList.c

//函数接口实现#include "SeqList.h"//打印voidSeqListPrint(SL*ps)
{
assert(ps);
inti=0;
for (i=0; i<ps->size; i++)
    {
printf("%d ", ps->arr[i]);
    }
printf("\n");
}
//初始化顺序表voidSeqListInit(SL*ps)
{
ps->arr=NULL;
ps->size=0;
ps->capacity=0;
}
//检查顺序表容量voidCheckCapacity(SL*ps)
{
assert(ps);
//进行扩容，两种情况，1、没有开辟空间  2、空间不足if (ps->size==ps->capacity)
    {
intNewCapacity= (ps->capacity==0?4 : ps->capacity*2);
SLDataType*tmp= (SLDataType*)realloc(ps->arr, NewCapacity*sizeof(SLDataType));
if (tmp==NULL)
        {
printf("realloc fail\n");
//return;exit(-1);
        }
ps->arr=tmp;
ps->capacity=NewCapacity;
    }
}
//销毁顺序表voidSeqListDestroy(SL*ps)
{
assert(ps);
if (ps->size)
    {
free(ps->arr);
ps->arr=NULL;
ps->size=0;
ps->capacity=0;
    }
}
//顺序表的头插voidSeqListPushFront(SL*ps, SLDataTypen)
{
/*assert(ps);CheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = n;ps->size++;*///两种都行，下面这种比较方便SeqListInsert(ps, 0, n);
}
//尾插voidSeqListPushBack(SL*ps, SLDataTypen)
{
/*assert(ps);CheckCapacity(ps);ps->arr[ps->size] = n;ps->size++;*///两种都行，下面这种比较方便SeqListInsert(ps, ps->size, n);
}
//插入voidSeqListInsert(SL*ps, intpos, SLDataTypen)
{
assert(ps);
assert(pos>=0&&pos<=ps->size);
CheckCapacity(ps);//检查顺序表容量，不够则开辟新空间//挪动数据intend=ps->size-1;
while (end>=pos);
    {
ps->arr[end+1] =ps->arr[end];
end--;
    }
ps->arr[pos] =n;
ps->size++;
}
//头删， O(n)voidSeqListPopFront(SL*ps)
{
/*assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->arr[begin - 1] = ps->arr[begin];begin++;}ps->size--;*///两种都行，下面这种比较方便SeqListErase(ps, 0);
}
//尾删voidSeqListPopBack(SL*ps)
{
/*assert(ps);assert(ps->size > 0);ps->size--;*///两种都行，下面这种比较方便SeqListErase(ps, ps->size-1);
}
//删除数据voidSeqListErase(SL*ps, intpos)
{
assert(ps);
assert(pos>=0&&pos<ps->size);
intbegin=pos;
while (begin<ps->size-1)
    {
ps->arr[begin] =ps->arr[begin+1];
begin++;
    }
ps->size--;
}
//查找数据intSeqListFind(SL*ps, SLDataTypen)
{
assert(ps);
inti=0;
for (i=0; i<ps->size; i++)
    {
if (ps->arr[i] ==n)
        {
returnn;//找到了        }
    }
return-1; //找不到}
//修改数据voidSeqListModify(SL*ps, intpos, SLDataTypen)
{
assert(ps);
assert(pos>=0&&pos<ps->size);
ps->arr[pos] =n;
}

3.3 Test.c

//测试函数#include "SeqList.h"voidSeqListTest1()
{
SLs1;//定义一个结构体SeqListInit(&s1);//初始化SeqListPushFront(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPrint(&s1);
SeqListPopFront(&s1);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
voidSeqListTest2()
{
SLs1;
SeqListInit(&s1);
SeqListPushFront(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushFront(&s1, 0);
SeqListPushBack(&s1, 4);
SeqListPrint(&s1);
SeqListPopBack(&s1);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
voidSeqListTest3()
{
SLs1;
SeqListInit(&s1);
SeqListPushFront(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPrint(&s1);
intfind=SeqListFind(&s1, 1);
if (find==-1)
printf("找不到\n");
elseprintf("%d", find);
}
voidSeqListTest4()
{
SLs1;
SeqListInit(&s1);
SeqListPushFront(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListInsert(&s1, 2, 3);
SeqListPrint(&s1);
}
intmain()
{
SeqListTest1();
return0;
}

四、顺序表的优缺点

（1）优点

空间连续，可以按下标进行随机访问

顺序表的 cpu 高速缓存命中率高

（2）缺点

空间不够需要增容，增容有一定的性能消耗，且可能存在一定的空间浪费

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

中间或头部的插入、删除，需要挪动数据，效率低，时间复杂度为O(N)

-------------------我是分割线------------------

文章就到这里

【数据结构初阶】二、顺序表的实现

一、线性表

二、顺序表

2.1 顺序表概念及结构

2.2 顺序表接口实现

2.2.1 顺序表初始化

2.2.2 顺序表的销毁

2.2.3 顺序表的打印

2.2.4 顺序表增加数据（插入，头插、尾插）

2.2.5 顺序表删除数据（删除，头删、尾删）

2.2.6 顺序表查找数据

2.2.7 顺序表修改数据

三、顺序表完整代码（C语言）

3.1 SeqList.h

3.2 SeqList.c

3.3 Test.c

四、顺序表的优缺点

热门文章

最新文章

相关课程

相关电子书