数据结构小结——顺序表（数组版）

77 阅读 0 评论 51 点赞

我是靠谱客的博主愤怒康乃馨，最近开发中收集的这篇文章主要介绍数据结构小结——顺序表（数组版），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

何为顺序表，引用百度百科中的一段话来说

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

假设存储的数据类型位int型，则线性表的顺序存储类型可以用结构体表示为：

#define MAX 64;

typedef int SeqData;

typedef struct _seqlist
{
    SeqData data[MAX];
    int len;
}SeqList;

这种数据是由数组来存储的，数组的内存属于静态分配，大小固定，不可以改变，所以一旦数组存满，再继续存储会内存溢出，导致程序崩溃。
当然凡是都有例外，C99中支持了柔性数组这种东西，不过此篇不做介绍。

顺序表具体怎么操作呢，其实很简单。下面将简单介绍，代码均只有片段。需要完整代码请直接下载（免积分）顺序表（数组版）代码

第一步肯定是创建表初始化。由于用的是数组，所以操作都在栈内存上，系统自动分配内存，表直接创建就好了SeqList sqlist;初始化其实只需要令表的长度为0即sqlist.len = 0;

第二步由于数组存在越界风险，所以在进行一些操作之前需要判断表是否满或空。

sqlist.len == MAX    //表为满
sqlist.len == 0      //表为空

第三步进行数据插入，插入前一定要判断表是否已满，表满则无法继续插入，插入有头插法，尾插法，中间插法。

//头插法
//将所有元素向后移一位
int i;
for(i = s->len; i > 0; i--)
{
    s->data[i] = s->data[i-1];
}
//在头部插入数据
s->data[0] = data;
//表长度加一
s->len++;

尾插法比较简单，只要表不满，就能直接插入

//尾插法
//在尾部插入数据
s->data[s->len] = data;
//表长度加一
s->len++;

中间插法即通过下标选择插入的地点，此方法可以模拟头插和尾插

//中间插法
//数组从下标为pos位，所有元素后移一位
int i;
for(i = s->len; i > pos; i--)
{
    s->data[i] = s->data[i-1];
}
//在下标pos处插入数据
s->data[pos] = data;
//表长度加一
s->len++;

第四步删除数据，同理，在删除数据之前要先判断顺序表是否为空，删除就不要搞什么头删尾删了。在此给两个例子

//删除下标为pos的数据，原理差不多。
int i;
for(i = pos; i < s->len; i++)
{
    s->data[i] = s->data[i+1];
}
s->len--;

//删除所有值为data的数据
int i = 0;
int j;
int len = s->len;
while(len--)
{
    //找到一个删除一个
    if(s->data[i] == data)
    {
        for(j = i; j < s->len-1; j++)
        {
            s->data[j] = s->data[j+1];
        }
        s->len--;
    }    
    i++;
}