数据结构线性表之顺序存储 类的封装

点击上方蓝字可直接关注！方便下次阅读。如果对你有帮助，可以点个在看，让它可以帮助到更多同志

自己编程也挺久的了，然而数据结构这块是很弱的部分，然而这个东西对编程又异常重要，虽然这么久我一直没感受到。所以最近集中学习一下。正好手里有一本大话数据结构，就按照该书的顺序往下学习。

开始学习之前，要了解几个概念，如时间复杂度和空间复杂度，具体概念就不罗列，大家可直接百度。

下面是线性表的定义：零个或多个数据元素的有限序列。

顺序存储：用一段地址连续的存储单元依次存储线性表的数据元素。

也就是这次说的顺序存储，大家自然就会想到数组。Ok，接下来我们就使用 C++ 来封装一个类，实现线性表的一些操作。

一般对数据操作都是增删改查，我们以这几个操作为核心，再扩充几个其他操作，如初始化线性表、线性表是否为空、判断某一元素的位置等操作。其实这里面这些操作主要就是插入与删除，其他的都很好理解。

开发环境：Ubuntu Qt

类的组成：common.h  一些宏定义、数据结构、

SeqList类的头文件与源文件

1. common.h

namespace  seqlist_namespace
{

#define OK 0
#define ERROR 1

#define MAXSIZE 100      /* 存储空间初始分配量 */

typedef int ElemType;     /* ElemType类型根据实际情况而定，这里假设为int */

typedef struct
{
    ElemType data[MAXSIZE];        /* 数组，存储数据元素 */
    int length;                    /* 线性表当前长度 */
}SqList;

}

2. 头文件

class SeqList
{
public:
    SeqList();
    ~SeqList();

public:
    int initList(seqlist_namespace::SqList *L);
    int isListEmpty(const seqlist_namespace::SqList& L);
    int clearList(seqlist_namespace::SqList *L);
    int listLength(const seqlist_namespace::SqList& L);

    //list existed, return element by position i,
    //first element means array cursor is 0
    int getElem(const seqlist_namespace::SqList& L, const int i, seqlist_namespace::ElemType *e);
    //list existed,search first is e element
    int locateElem(const seqlist_namespace::SqList& L, const seqlist_namespace::ElemType e);
    //
    int listInsert(seqlist_namespace::SqList *L, const int i, const seqlist_namespace::ElemType e);
    //
    int listDelete(seqlist_namespace::SqList *L, const int i, seqlist_namespace::ElemType *e);

    int listTraverse(seqlist_namespace::SqList& L);
};

3. 源文件

int SeqList::listInsert(seqlist_namespace::SqList *L, const int i,
                        const seqlist_namespace::ElemType e)
{
    if(MAXSIZE == L->length)
        return ERROR;
    if(i < 1 || i > L->length+1)
        return ERROR;


    if(i <= L->length)
    {
        for(int j=L->length-1; j>=i-1; j--)
            L->data[j+1] = L->data[j];
    }

    L->data[i-1] = e;
    L->length++;

    return OK;
}

int SeqList::listDelete(seqlist_namespace::SqList *L, const int i,
                        seqlist_namespace::ElemType *e)
{
    if(0 == L->length)
        return ERROR;
    if(i < 1 || i > L->length)
        return ERROR;

    if(i < L->length)
    {
        for(int j=i-1; j!=L->length-1; j++)
        {
            L->data[j] = L->data[j+1];
        }
    }

    *e = L->data[i-1];
    L->length--;

    return OK;
}

当需要修改元素时，传入线性表指针；如果不需要修改则传入线性表引用变量。

简单说下插入和删除。

插入数据时，涉及到数据元素向后移动，所以找到元素最大下标(L.length - 1)的数据，之后将其后移一个位置，以此类推，直到移动完所有元素。之后进行插入操作。

删除数据时，找到要删除元素的下标(i -1)，将它后继元素 (i-1+1) 前移，以此类推。

4. 主函数中测试程序

seqlist_namespace::SqList sqlist;
    seqlist_namespace::ElemType element;

    SeqList L;

    L.initList(&sqlist);
    for(int i = 0; i < 5; i++)
        L.listInsert(&sqlist, 1, i);

    L.listTraverse(sqlist);


    int ret = 0;
    ret = L.locateElem(sqlist,4);
    std::cout << "locate " << ret << std::endl;

    ret = L.isListEmpty(sqlist);
    std::cout << "isEmpty" << ret << std::endl;

    L.getElem(sqlist, ret, &element);
    std::cout << "getElement" << element << std::endl;

    L.listDelete(&sqlist, 1, &element);

    L.listTraverse(sqlist);

效果图：

5.  小结

从实现上讲，主要是插入、删除部分的标准以及线性表的一些状态的判断，如表是否为空、表是否为满、插入数据位置的合理性等。

从重要性 讲 ，它很重要，虽然现在还没感觉出来。

学习贵在坚持和不断总结。

程序中还有很多不足，希望大家不吝指正，需要整个Qt的工程的同志可在公众号后台留言。

这是一个记录自己学习的公众号，希望对你也有一丢丢的帮助。