[数据结构与算法]基础数据结构：顺序表

定义

使用一组连续的存储单元依次存放数据，是最简单一种数据结构。

静态顺序表

一旦定义该表，其大小始终固定不变。数组就是一种静态顺序表。

静态顺序表定义：

const int maxSize = 100;//最多存放元素个数
elemType sequenceTable [maxSize];
int len;//已存放元素个数

动态顺序表

定义在堆内存，以便元素个数可变。

动态顺序表定义：

const int defaultSize = 100;//初始分配空间
const int incrementSize = 50;//当空间不足时分配的元素个数

template <typename T> class dynamicSequenceList
{
public:
    dynamicSequenceList()
    {
        elem = static_cast<T*>(malloc(sizeof (T) * defaultSize));
        len = 0;
        listSize = defaultSize;
    }
    ~dynamicSequenceList()
    {
        free(elem);
    }

private:
    T * elem{nullptr};//头指针，指向顺序表的第一个元素
    unsigned int len;//已存放元素个数（已使用空间）
    unsigned int listSize;//已申请空间个数
};

动态顺序表示例

1、在末尾插入

//在末尾插入
template <typename T> void dynamicSequenceList<T>::append(T data)
{
    if(length >= listSize)//内存不够，重新申请
    {
        elem = static_cast<T*>(realloc(elem,sizeof (T) * (listSize + incrementSize)));
        listSize += incrementSize;
    }
    T * p = &(elem[length]);
    *p = data;
    ++length;
}

2、遍历

//遍历
template <typename T> void dynamicSequenceList<T>::traverseSequenceList()
{
    for(int i = 0;i < length;++i)
    {
        qDebug()<<i<<" "<< (*&elem[i]);
    }
}

3、在中间插入

//在中间插入
template <typename T> void dynamicSequenceList<T>::insert(unsigned int index, T data)
{
    if(index >= length)
    {
        return;
    }
    if(length >= listSize)//内存不够，重新申请
    {
        elem = static_cast<T*>(realloc(elem,sizeof (T) * (listSize + incrementSize)));
        listSize += incrementSize;
    }

    for(int i = length;i > index;--i)//后移部分数据
    {
        *&elem[i] = *&elem[i-1];
    }
    *&elem[index] = data;
    ++length;
}

效果：

    dynamicSequenceList<int> list;
    list.append(22);
    list.append(333);
    list.append(567);
    list.insert(1,8888);

    list.traverseSequenceList();

4、逆置

//逆置
template <typename T> void dynamicSequenceList<T>::inverted()
{
    int hafrLen = length / 2;
    for(int i = 0;i < hafrLen;++i)
    {
        T temp = *&elem[i];
        *&elem[i] = *&elem[length - 1 - i];
        *&elem[length - 1 - i] = temp;
    }
}

5、删除index处的的数据

//删除index处的数据
template <typename T> void dynamicSequenceList<T>::removeOne(unsigned int index)
{
    if(index >= length)
    {
        return;
    }

    for(int i = index;i < length;++i)//前移部分数据
    {
        *&elem[i] = *&elem[i+1];
    }
    --length;
}

6、删除重复数据

思路：遍历一次，找到重复的数据，地址存入一个列表，再删除列表中的元素。

//删除重复数据
template <typename T> void dynamicSequenceList<T>::removeDuplicate()
{
    int noDuplicateSize{0};//非重复数目
//    T ** tempArrayPtr = new T*[length];//T*类型的数组，遍历时如果数据第一次出现，则储存其地址
    T** tempArrayPtr = static_cast<T**>(malloc(sizeof (T *) * length));

//    int * duplicateArray = new int[length];//标识第i个数据是否是重复的，重复设未888
    int * duplicateArray = static_cast<T*>(malloc(sizeof (int) * length));

    for(int i = 0;i < length;++i)
    {
        T c = *&elem[i];
        bool isDuplicate{false};//是否重复
        for(int j = 0;j < noDuplicateSize;++j)
        {
            if(c == *tempArrayPtr[j])
            {
                isDuplicate = true;
                break;
            }
        }
        if(isDuplicate)
        {
            qDebug()<<"重复"<<i;
            duplicateArray[i] = 888;
        }
        else
        {
            tempArrayPtr[noDuplicateSize] = &elem[i];
            ++noDuplicateSize;
        }
    }
//    delete[] tempArrayPtr;
    free(tempArrayPtr);

    int removeSize{0};
    int duplicateArrayLength = length;
    for(int i = 0;i < duplicateArrayLength;++i)
    {
        if(duplicateArray[i] == 888)
        {
            removeOne(i - removeSize);
            ++removeSize;
        }
    }
//    delete[] duplicateArray;
    free(duplicateArray);
}

时间复杂度：Ο (n2)

效果：

    dynamicSequenceList<int> list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(2);
    list.append(5);
    list.append(6);
    list.append(5);
    list.append(8);
    list.append(5);
    list.removeDuplicate();

    list.traverseSequenceList();

?7、汇总

#include <stdlib.h>
#include <QDebug>

const int defaultSize = 100;//初始分配空间
const int incrementSize = 50;//当空间不足时分配的元素个数

template <typename T> class dynamicSequenceList
{
public:
    dynamicSequenceList()
    {
        elem = static_cast<T*>(malloc(sizeof (T) * defaultSize));
        length = 0;
        listSize = defaultSize;
    }
    ~dynamicSequenceList()
    {
        free(elem);
    }
    void append(const T &data);
    void insert(const unsigned int index, const T &data);
    void traverseSequenceList();
    void inverted();
    void removeOne(const unsigned int index);
    void removeDuplicate();

private:
    T * elem{nullptr};//头指针，指向顺序表的第一个元素
    unsigned int length;//已存放元素个数（已使用空间）
    unsigned int listSize;//已申请空间个数
};

//在末尾插入
template <typename T> void dynamicSequenceList<T>::append(const T & data)
{
    if(length >= listSize)//内存不够，重新申请
    {
        elem = static_cast<T*>(realloc(elem,sizeof (T) * (listSize + incrementSize)));
        listSize += incrementSize;
    }
    T * p = &(elem[length]);
    *p = data;
    ++length;
}

//在中间插入
template <typename T> void dynamicSequenceList<T>::insert(const unsigned int index, const T & data)
{
    if(index >= length)
    {
        return;
    }
    if(length >= listSize)//内存不够，重新申请
    {
        elem = static_cast<T*>(realloc(elem,sizeof (T) * (listSize + incrementSize)));
        listSize += incrementSize;
    }

    for(int i = length;i > index;--i)//后移部分数据
    {
        *&elem[i] = *&elem[i-1];
    }
    *&elem[index] = data;
    ++length;
}

//遍历
template <typename T> void dynamicSequenceList<T>::traverseSequenceList()
{
    for(int i = 0;i < length;++i)
    {
        qDebug()<<i<<" "<< (*&elem[i]);
    }
}

//逆置
template <typename T> void dynamicSequenceList<T>::inverted()
{
    int hafrLen = length / 2;
    for(int i = 0;i < hafrLen;++i)
    {
        T temp = *&elem[i];
        *&elem[i] = *&elem[length - 1 - i];
        *&elem[length - 1 - i] = temp;
    }
}

//删除index处的数据
template <typename T> void dynamicSequenceList<T>::removeOne(const unsigned int index)
{
    if(index >= length)
    {
        return;
    }

    for(int i = index;i < length;++i)//前移部分数据
    {
        *&elem[i] = *&elem[i+1];
    }
    --length;
}

//删除重复数据
template <typename T> void dynamicSequenceList<T>::removeDuplicate()
{
    int noDuplicateSize{0};//非重复数目
//    T ** tempArrayPtr = new T*[length];//T*类型的数组，遍历时如果数据第一次出现，则储存其地址
    T** tempArrayPtr = static_cast<T**>(malloc(sizeof (T *) * length));

//    int * duplicateArray = new int[length];//标识第i个数据是否是重复的，重复设未888
    int * duplicateArray = static_cast<T*>(malloc(sizeof (int) * length));

    for(int i = 0;i < length;++i)
    {
        T c = *&elem[i];
        bool isDuplicate{false};//是否重复
        for(int j = 0;j < noDuplicateSize;++j)
        {
            if(c == *tempArrayPtr[j])
            {
                isDuplicate = true;
                break;
            }
        }
        if(isDuplicate)
        {
            qDebug()<<"重复"<<i;
            duplicateArray[i] = 888;
        }
        else
        {
            tempArrayPtr[noDuplicateSize] = &elem[i];
            ++noDuplicateSize;
        }
    }
//    delete[] tempArrayPtr;
    free(tempArrayPtr);

    int removeSize{0};
    int duplicateArrayLength = length;
    for(int i = 0;i < duplicateArrayLength;++i)
    {
        if(duplicateArray[i] == 888)
        {
            removeOne(i - removeSize);
            ++removeSize;
        }
    }
//    delete[] duplicateArray;
    free(duplicateArray);
}