线性表的实现及其功能的拓展

data_structure

返回目录

本文目的在于，对线性表实现的描述，以及代码的简单实现

线性表概况描述

下面是函数的头文件部分

template <class dataType, int MaxSize>class SeqList {
    dataType *data;                     //用于存放数据元素的数组
    int length;                         //顺序表中的元素个数
public:
    SeqList();                          //无参构造函数
    SeqList(dataType a[], int n);       //有参构造函数
    ~SeqList();
    int ListLength();                   //求线性表的长度
    void SetLength(int length);
    dataType Get(int pos);              //按位查找，取顺序表的第pos个元素
    int Locate(dataType item);          //按值查找，求顺序表中值为item的元素序号
    void PrintSeqList();                //遍历顺序表，按序号一次输出各元素
    void Insert(int i, dataType item);  //在顺序表第i个位置插入值为item的元素
    dataType Delete(int i);             //删除顺序表的第i个元素‘
    *****
    扩展部分
    *****
    void quicksort(const int &first, const int &last );//快速排序
    void Merge(SeqList & LA, SeqList & LB);           //合并有序表
    bool IsOrder();                                  //判断表是否有序
    dataType DeleteMinData();                       //删除最小元素，空位后值填补
    void DeleteStoT(dataType S,dataType T);         //删除S-T的元素
    void DeleteXitem(dataType X);                   //删除元素X
    void Deleterepeated();                          //删除重复元素
    bool IsExited(dataType &x,dataType *record,int length);//查看元素是否已存在
    void DevidedBya_1();                            //按照键值A1分开数组
    bool cmp(const dataType&, const dataType&);     //用于比较
};

一、基本功能

1.1无参构造函数

这个函数，适用于无参的构造函数，实现对空间的申请，以及长度置0；

/**
* 无参数构造函数
* 仅设置长度为0
* @param[in] 无
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::SeqList()
{
    data=new dataType[MaxSize];
    length = 0;
}

1.2有参构造函数

此函数用来，带有参数的赋值,做合法性检查，申请空间，置线性表长度。

/**
* 构造函数
* 设置线性表的初始值，长度
* @param[in] 数据源a，数量n
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::SeqList(dataType *a, int n)
{   
    data=new dataType[MaxSize];
    if (n > MaxSize)            //数据合法性检查
    {
        cerr << "error";
        system("pause");
        exit(1);
    }
    for (int i=0; i <n; i++)
    {
        data[i] = a[i];             //需要重载运算符‘=’
    }
    length = n;
    cout << "\ncreate list success,length is " << length << endl;
}

1.3析构函数

用于在程序结束后，对申请空间进行销毁，做后续处理。

* 析构函数
* @param[in] 无
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::~SeqList()
{
    if(data) delete[]data;
    data=NULL;
}

1.4求表长

/**
* 返回线性表返回当前元素个数
* @param[out] 表长length
*/
template<class dataType, int MaxSize>
int SeqList<dataType, MaxSize>::ListLength()
{
    return length;
}

1.5其他基本功能

还有一些基本功能，不在此贴出，详细请见源程序

二、扩展功能

2.1快速排序

本函数采用快速排序的方法，对成员进行排序，目前采用的是运用cmp函数，以后可考虑用‘<’重载

/**
* 按照CMP的方式进行快速排序
* @param[in] 起始位置first，终止位置last，比较函数cmp
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::quicksort(const int &first, const int &last)
{
    int i = first, j = last;
    const dataType m = *(data + ((first + last) >> 1));
    dataType temp;
    do
    {
        while (cmp(data[i], m)) i++;
        while (cmp(m, data[j])) j--;
        if (i <= j)
        {
            temp = data[i]; 
            data[i] = data[j]; 
            data[j] = temp;
            i++; j--;
        }
    } while (i < j);
    if (i < last) quicksort( i, last);
    if (first < j) quicksort(first, j);
}

2.2归并有序表

通过比较方法，取各数组较大值，最后把多余的附载在后面即可
其中，做了关于合法性的检测，还包含了先判断所给的数据是否有序的操作。

/**
* 合并两个有序表，并存在第一个中，
* @param[in] 表1LA，表2LB， 比较方法，cmp
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::Merge(SeqList &LA,SeqList &LB)
{
    int i = 0; int  j = 0;int k = 0;
    SeqList C;
    if (LA.ListLength() + LB.ListLength() > MaxSize) {
        cerr << "溢出";
        system("pause");
        return;
    }
    C.length = LA.ListLength() + LB.ListLength();
    if(!LA.IsOrder(cmp)){LA.quicksort(0,LA.ListLength()-1,cmp);}//若A无序，先排序
    if(!LB.IsOrder(cmp)){LA.quicksort(0,LB.ListLength()-1,cmp);}
    while (i<LA.ListLength() && j<LB.ListLength()) {
        //循环，两两比较，小者存入结果表
        if (LA.data[i]<=LB.data[j])
            C.data[k++] = LA.data[i++];
        else
            C.data[k++] = LB.data[j++];
    }
    if(i==LA.ListLength()) {
        while (j< LB.ListLength()) {
            C.data[k++] = LB.data[j++];
        }
    }
    else{
        while (i<LA.ListLength()) {
            C.data[k++] = LA.data[i++];
        }
    }
    for (i=0;i<C.ListLength();i++)
    {
        LA.data[i]=C.data[i];
    }
    LA.SetLength(C.ListLength());
}

/*
*检查元素是否有序
*/
template<class dataType, int MaxSize>
bool SeqList<dataType, MaxSize>::IsOrder()
{
    for (int j = 0; j <ListLength()  ; j++) {
        if (cmp(data[j], data[j + 1])) {
            return false;
        }
    }
    return true;
}

2.3删除S-T之间元素

本函数比较复杂，目前版本没有实现完全功能，原因是没有重载运算符，对边界的处理不好。

/**
* 删除顺序表S-T之间元素，若S<T报错，
* @param[in] S,T,
* @param[out] 
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DeleteStoT(dataType S,dataType T)
{
    if(!cmp(S,T))
    {
        cout<<"输入有误，删除失败。。"<<endl;
        return;
    }
    if (IsOrder()){
        quicksort(0,ListLength()-1);
    }
    for (int i=0;i<ListLength();i++){   //找到S所在的位置i
        bool flag = !cmp(data[i],S);
        if(flag){
            break;
        }
    }
    for (int j=0;j<ListLength();j++){   //  找到T所在的位置j
        bool flag = !cmp(data[j],T);
        if(flag){
            break;
        }
    }
    if(i>=0&&j<ListLength()){
        for(int k=j-1;k>=i;k--){
            Delete(k+1);    
        }
    }
}

2.3删除X元素

本函数用于删除顺序表中的X元素，未找到，提示消息。

template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DeleteXitem(dataType X){
    int k=0;
    for (int i=0;i<ListLength();i++)
    {
        if (X==data[i])
        {
            Delete(i+1);    
            i=i-1;
            k++;
        }
    }
    if (k==0)cout<<"Not Found!"<<endl;
}

2.4删除重复元素

本函数用于删除重复元素，编写时遍历表，找到第一次出现的元素，放在record数组中，后接受record的值

/**
* 删除重复元素
* @param[in] 
* @param[out] 
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::Deleterepeated(){
    dataType *record=new int[MaxSize];
    int k=0;
    for (int i=0;i<ListLength();i++)
    {
        if (!IsExited(data[i],record,k))
        {
            record[k++]=data[i];
        }
    }
    delete []data;
    data=record;
    SetLength(k);
}

其中用了一个辅助函数，判定是否第一次出现。

/**
* 判定元素是否出现过，辅助函数
* @param[in] 元素X，数组record，长度length
* @param[out] bool flag
* 位置从0开始。
*/
template<class dataType, int MaxSize>
bool SeqList<dataType, MaxSize>::IsExited(dataType &x,dataType *record,int length){
    for (int i=0;i<length;i++)
    {
        if(x==record[i]) return true;
    }
    return false;
}

2.5 划分元素

按照A[0]值，划分数组，要求复杂度为O（n）
思路如下：先遍历一遍，找到小于键值的，放到前面（交换），从这个位置继续开始继续遍历，找到等于的元素放到中间即可。

/**
* 按照a0的值划分，要求时间复杂度为O（N）
* @param[in] 
* @param[out] 
* 位置从1开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DevidedBya_1(){
    dataType v=data[0];//键值V
    int k=0;//递进下标
    for (int i=0;i<ListLength();i++)        //小于v的值归于左侧
    {
        if (data[i]<v)
        {
            int tmp=data[i];
            data[i]=data[k];
            data[k]=tmp;
            k++;
        }
    }
    for (i=k;i<ListLength();i++)        //等于v的值继续归于中间，剩下的自然是大于v的值
    {
        if (data[i]==v)
        {
            int tmp=data[i];
            data[i]=data[k];
            data[k]=tmp;
            k++;
        }
    }
}

三、测试（test.cpp）

下面是完整代码

#include<iostream>
#include<stdlib.h>
#include"SeqList.h"
#include"SeqList.cpp"
using namespace std;
int main() {
    int MaxSize=100;
    int number;
    cout << "请输入数据个数\n";
    cin >> number;
    int *a = new int[number];
    for (int  i = 0; i < number; i++)
    {
        cin>>a[i];
    }
    SeqList<int, 100> lista(a, number);
    cout <<"当前元素个数是："<< lista.ListLength()<< endl;
    lista.quicksort(0,lista.ListLength() - 1);
    cout << "排序后遍历打印："<<endl;
    lista.PrintSeqList();
    system("pause");
    lista.DeleteStoT(70,90);
    cout << "删除S-T后遍历打印："<<endl;
    lista.PrintSeqList();
    lista.Insert(1,3);
    cout << "插入后遍历打印："<<endl;
    lista.PrintSeqList();
    lista.DeleteXitem(100);
    cout<<endl << "删除元素X后遍历打印："<<endl;
    lista.PrintSeqList();
    system("pause");
    cout <<endl<< "按照a0划分遍历打印："<<endl;
    lista.DevidedBya_1();
    lista.PrintSeqList();
    system("pause");
    cout <<endl<< "删除重复元素后遍历打印："<<endl;
    lista.Deleterepeated();
    lista.PrintSeqList();
    system("pause");
    if (a) delete []a;//扫尾
    return 0;
}

3.1测试结果

4、总结

这次编程，还算顺利，但是对于引用对象还是不是很清楚，感谢老师刚刚发的文件，会去仔细看看的。