数据结构之线性表-顺序存储结构

分手后的思念是犯贱 2022-05-31 08:55 404阅读 0赞

线性表，顾名思义，所谓线性表就是零个或者多个数据元素的有序序列。  
今天我们一起来看一下线性表中的顺序存储结构。所谓的顺序存储结构其实是存储结构的一种，它的原理是把逻辑相邻的结构存储在物理位置相邻的存储单元中。节点之间的关系由存储关系直接体现的。

首先，我们先来简单了解一下顺序结构下的线性表的优缺点，最后我们对其进行代码实现。

由于其存储在相邻的存储单元，我们可以很容易的计算出其内每个节点的实际位置，从而实现对其的快速访问。还有一点是，这种结构其逻辑结构的关系不需要额外的空间来进行存储，所以节约存储空间也是其优点之一。  
![这里写图片描述][70]  
但是，也是因为这种物理存储位置相邻的缘故导致如果对其进行增删移动等操作的时候，需要移动一系列的节点才能达到我们想要的结果。

作为顺序结构的线性表，它应该满足以下的条件：  
1.首节点只有后继节点，没有前驱结点  
2.尾部节点只有前驱节点，没有后继节点  
3.中间元素既有前驱节点，同时拥有后继节点（有且只有一个）

![这里写图片描述][70 1]

上面这张图就是一个典型的顺序存储结构的示意图。我们呢通过这张图在对其进行仔细的分析。

首先，顺序存储结构的线性表在我们所知的编程语言中是通过数组来进行实现的。这里我们将线性表的一些内容都通过数组这个概念来解释。

数组是具有固定大小的，我们通常所说的数组长度就是指数组的存储空间长度，而这个值必须在申明数组的时候进行指定。有时候你会在一些资料中也称为数据长度。

另外，这里再说一下线性表的长度，所谓线性表长度指的是线性表中数据元素的个数，而这个值是会随着用户操作而变动的，但是有一点大家一定要注意：线性表长度一定不能超过数组长度。否则会出现大家熟知的内存溢出问题。

在来看下用数组存储顺序线性表中的地址计算。下面先上一张图，帮助大家有一个直观的映像。  
![这里写图片描述][70 2]

我们都知道在计算机中存储器中的每个存储单元都有属于自己的编号，这个我们称之为地址。  
这个就像我们大学时候去自习室占座一样，假定我们占了第一排的六个座位，那么第一个人在第一排的第一个座位，那么剩下的自然是第一排第二个座位，第三个。。。很容易就知道后续的同学的位置了。

在大多数编程语言中，数组的第一位是从0开始计算的，所以每一个同学对应的座位编号就是n-1，第一个同学是0，第二个同学是1。。。。

知道了数组中是怎么为我们的同学进行编号的，那么我们就可以很容易计算其他同学的位置了。

比如每一个座位的宽度是50cm，那么第二个同学的位置是多上呢？很简单，（n-1)\*50,第一个同学的起始位置是0，那么第二个同学的起始位置就是50cm处的座位。当然了，这个比喻可能不太适当，大家将就着看把。

到这里我们引出一个我们第一个要实现的东西，查找线性表中的元素。当然了，这里我们的知道线性表的起始地址，如果没有起始地址，我们就是两眼摸黑，啥都不知道了。

在这里我们需要注意的是在返回指定索引的元素时，首先应该判断索引的正确性，然后进行取值操作。这里给出c++代码实现。

int LinearTab::GetLinearValueByIndex(int index)
    {
        if (index < 0 || index > GetLinearCount())
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() << std::endl;
            return -1;
        }
        return this->linear[index];
    }

查找元素使我们的基本功，接下来我们就要实现线性表的插入和删除操作，这里我们就不再叙述其相关的时间复杂度了。

![这里写图片描述][70 3]

插入操作的基本思想是：  
1.判断插入位置是否合理，不合理则抛出异常  
2.如果线性表的长度大于数组长度，则抛出异常或者为数组动态增加容量  
3.从插入位置开始，之后的每一个元素均向后移动一位  
4.将插入元素写入插入位置中

int LinearTab::InsertLinearValue(int index, int values)
    {
        if (index < 0 || index > GetLinearCount() - 1)
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() - 1 << std::endl;
            return -1; 
        }
    
        this->linear = (int *)realloc(this->linear, (GetLinearCount() + 1) * sizeof(int));
    
        for (int i = GetLinearCount() - 1;  i > index; i--)
        {
            this->linear[i] = this->linear[i - 1];
        }
    
        this->linear[index] = values;
    
        printLinear();
    
        return 0;
    }

删除操作过程可以参考下图：  
![这里写图片描述][70 4]

同样的，删除操作的基本思想如下：  
1.判断索引是否越界  
2.从删除元素开始后面依次向前移动一位  
3.重新分配空间，线性表长度减少一位

这里又可以分为两种情况进行，一种是通过索引方式进行删除元素，另外一种是通过值进行删除元素。值得注意的是如果数组内存在值相同元素，我这里的处理是匹配第一个查找到的元素然后进行删除。如果想删除所有指定值的元素，大家可以通过循环进行处理，当然了还有更好的办法，大家可以自己进行发散。

下面给出代码：

int LinearTab::DeleteLinearByIndex(int index)
    {
        if (index < 0 || index > GetLinearCount() - 1)
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() - 1 << std::endl;
            return -1;
        }
    
        for (int i = index; i < GetLinearCount() - 1; i++)
        {
            this->linear[i] = this->linear[i + 1];
        }
    
        this->linear = (int *)realloc(this->linear, (GetLinearCount() - 1) * sizeof(int));
    
        printLinear();
    
        return 0;
    }
    
    int LinearTab::DeleteLinearByValue(int values)
    {
        int deleteIndex = -1;
        for (int i = 0; i < GetLinearCount(); i++)
        {
            if (this->linear[i] == values)
            {
                deleteIndex = i;
                break;
            }
        }
    
        if (deleteIndex == -1)
        {
            std::cout << "数组内没有该值，请检查输入。"<< std::endl;
            return -1;
        }
        DeleteLinearByIndex(deleteIndex);
    }

完整的类实现：

#pragma once
    #include <iostream>
    class LinearTab { 
    public:
        LinearTab();
        LinearTab(int count);
        ~LinearTab();
    
        //获取数组长度
        int GetLinearCount();
    
        //打印数组元素
        void printLinear();
    
        //通过索引获取指定位置的元素
        //获取成功返回该元素
        //获取失败返回 -1
        int GetLinearValueByIndex(int index);
    
        //在指定位置插入元素
        //插入成功返回 0 
        //插入失败返回 -1
        int InsertLinearValue(int index, int values);
    
        //删除指定位置元素
        //删除成功返回 0 
        //删除失败返回 -1
        int DeleteLinearByIndex(int index);
    
    
        //删除指定元素,匹配第一个元素
        //删除成功返回 0 
        //删除失败返回 -1
        int DeleteLinearByValue(int values);
    private:
        //数组长度
        int count;
    
        //数组
        int *linear;
    };

#include "stdafx.h"
    #include "LinearTab.h"
    
    LinearTab::LinearTab()
    {
    }
    
    
    LinearTab::LinearTab(int count)
    {
        this->count = count;
    
        this->linear = new int[this->count];
    
        for (int i = 0; i < this->count; i++)
        {
            this->linear[i] = i + 1;
        }
    }
    
    LinearTab::~LinearTab()
    {
        delete[]this->linear;
    }
    
    
    int LinearTab::GetLinearCount()
    {
        return _msize(this->linear) / sizeof(int);
    }
    
    void LinearTab::printLinear()
    {
        for (int i = 0; i < GetLinearCount(); i++)
        {
            std::cout << "当前是第" << (i + 1) << "个元素,Value=" << this->linear[i] << std::endl;
        }
    }
    
    int LinearTab::GetLinearValueByIndex(int index)
    {
        if (index < 0 || index > GetLinearCount() -1)
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() - 1 << std::endl;
            return -1;
        }
        return this->linear[index];
    }
    
    int LinearTab::InsertLinearValue(int index, int values)
    {
        if (index < 0 || index > GetLinearCount() - 1)
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() - 1 << std::endl;
            return -1; 
        }
    
        this->linear = (int *)realloc(this->linear, (GetLinearCount() + 1) * sizeof(int));
    
        for (int i = GetLinearCount() - 1;  i > index; i--)
        {
            this->linear[i] = this->linear[i - 1];
        }
    
        this->linear[index] = values;
    
        printLinear();
    
        return 0;
    }
    
    int LinearTab::DeleteLinearByIndex(int index)
    {
        if (index < 0 || index > GetLinearCount() - 1)
        {
            std::cout << "索引越界，请检查输入。有效索引范围：0 -" << GetLinearCount() - 1 << std::endl;
            return -1;
        }
    
        for (int i = index; i < GetLinearCount() - 1; i++)
        {
            this->linear[i] = this->linear[i + 1];
        }
    
        this->linear = (int *)realloc(this->linear, (GetLinearCount() - 1) * sizeof(int));
    
        printLinear();
    
        return 0;
    }
    
    int LinearTab::DeleteLinearByValue(int values)
    {
        int deleteIndex = -1;
        for (int i = 0; i < GetLinearCount(); i++)
        {
            if (this->linear[i] == values)
            {
                deleteIndex = i;
                break;
            }
        }
    
        if (deleteIndex == -1)
        {
            std::cout << "数组内没有该值，请检查输入。"<< std::endl;
            return -1;
        }
        DeleteLinearByIndex(deleteIndex);
    }

[70]: /images/20220531/75c793f212ef46629a5b9d107eba72bd.png
[70 1]: /images/20220531/950dbd19fec34dbcb17bc51a0d2ce243.png
[70 2]: /images/20220531/0b21f47ca0ba467caf5874de278d3599.png
[70 3]: /images/20220531/25464cdc53c9457384c52640f1120a08.png
[70 4]: /images/20220531/2c23584d73e349768661f0dff5c7ed55.png