投稿
  1. 高性能架构探索首页
  2. C/C++

顺序表（C++）

admin • • C/C++ • 阅读 134

可动态拓展大小的顺序表

//header.h
//#pragma once
#ifndef _HEADER_H_
#define _HEADER_H_


#include<iostream>
#include<stdlib.h>
using namespace std;

//enum bool{false, true};

template <class T>
class LinearList
{
    public:
        //LinearList();//构造函数
        //virtual ~LinearList();//析构函数
        virtual int Size()const = 0;//求表最大体积，返回体积
        virtual int Length()const = 0;//求表长度，返回长度
        virtual int Search(T& x)const = 0;//查找元素x，返回位置
        virtual T * getData(int i)const = 0;//查找i位置的元素，返回元素值
        //virtual LinearList<T>& operator=(LinearList<T> &L) = 0;//复制,这里不知道为啥不能将其声明为纯虚函数，一旦声明就会报错
        //virtual LinearList<T> operator+(LinearList<T> &L) = 0;
        virtual int Locate(int i)const = 0;//定位表中第i个元素
        virtual void setData(int i, T& x) = 0;//修改表内第i个元素为x
        virtual void Sort() = 0;
        virtual bool IsEmpty()const = 0;
        virtual void push(T x) = 0;//向表尾部增加元素x
        virtual void print() = 0;//将线性表打印出来
        virtual bool IsFull()const = 0;
        virtual bool Insert(int i, T& x) = 0;//在第i位置插入x
        virtual bool Remove(size_t i, T& x) = 0;//删除第i位置的元素，将值返回给x
};


#endif

 

使用纯虚函数，

 

 
//main.cpp
#include<iostream>
#include"header.h"
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList:public LinearList<T>
{
    private:
        T *data;//存放数组
        int maxSize;//最大可容纳表项的项数
        int last;//当前表项最后位置
    protected:
        void reSize(int newSize);//改变data数组空间大小
    public:
        SeqList(int sz = defaultSize);
        SeqList(SeqList<T>& L);//复制构造
        ~SeqList(){delete[] data;}
        int Size()const{return this->maxSize;}//返回表的大小
        int Length()const{return this->last+1;}//返回表元素的个数
        int Search(T& x)const;//查找元素x
        T* getData(int i)const{return (i>0 && i<=this->last+1) ? &this->data[i-1] : NULL;}//找线性变第i个元素
        bool IsEmpty()const{return (this->last==-1) ? true : false;}//判断线性表是否满了
        bool IsFull()const{return (this->last+1==this->maxSize) ? true : false;}
        void print();//将表打印出来
        void push(T x);//在表尾部追加元素
        SeqList<T>&operator=(SeqList<T> &L);//运算符“=”的重载
        //SeqList<T>operator+(const SeqList<T> &L)const;
        int Locate(int i)const;//判断表i位置是否有元素，有返回i,否则返回0
        void setData(int i, T& x);//将i位置的元素重置为x
        void Sort();//排序
        bool Insert(int i, T& x);//在第i个位置插入元素x
        bool Remove(size_t i , T& x);//将i所在的元素传给x后删除i所在元素

};
template<class T>
bool SeqList<T>::Insert(int i, T& x)
{
        if(i<=this->last+2)
        {
                if(this->IsFull())
                        this->reSize(defaultSize);
                if(i!=this->last+2)
                {
                        int a = this->last;
                        for(a; a>=i-1; --a)
                        {
                                this->data[a+1] = this->data[a];
                        }
                }
                        this->data[i-1] = x;
                        ++this->last;
                        return true;
        }
        else
                return false;
}
template<class T>
bool SeqList<T>::Remove(size_t i, T& x)
{
    if(i>0 && i<=this->last+1)
    {
        x = this->data[i-1];
        int L = last+1-i;
        while(L)
        {
            this->data[i-1] = this->data[i];
            ++i;
            --L;
        }
        --this->last;
        return true;
    }
    else
        return false;
}
template<class T>
void SeqList<T>::Sort()
{
    if(!IsEmpty() && this->last!=0)
    {
        int i = 0, j = 0;
        for(j; j<this->last; ++j)//冒泡排序
        {
            for(i=0; i<this->last-j; ++i)
            {
                if(this->data[i]>this->data[i+1])
                {
                    this->data[i] = this->data[i]+this->data[i+1];
                    this->data[i+1] = this->data[i]-this->data[i+1];
                    this->data[i] = this->data[i]-this->data[i+1];
                }

            }
        }
    }
    return;
}
template<class T>
void SeqList<T>::setData(int i, T& x)
{
    if(i>=1 && i<=last+1)
        this->data[i-1] = x;
}
template<class T>
int SeqList<T>::Locate(int i)const
{
    if(i>=1 && i<=this->last+1)
        return i;
    else
        return 0;
}

template<class T>
SeqList<T>& SeqList<T>::operator=(SeqList<T> &L)
{
    if(this->maxSize < L.Size())
        this->reSize(L.Size());
    this->last = L.last;
    this->maxSize = L.maxSize;
    int i = 0;
    while(i<=this->last)
    {
        this->data[i] = L.data[i];
        ++i;
    }
}
/*
这里本来是打算重载运算符“+”，使对象之间可以相加，但是不知道什么原因一直报错，查了很久也没找到原因，从报错类型上看多半不是代码内部的原因
再学学再尝试解决（烂尾。。。。。）
template<class T>
SeqList<T> SeqList<T>::operator+(const SeqList<T> &L)const
{
    if(this->last>=L.last)
    {
        if(!this->IsEmpty())
        {
            int i = 0;
            SeqList<T> tmp;
            tmp.reSize(this->maxSize);
            tmp.last = this->last;
            while(i!=L.last+1)
            {
                tmp.data[i] = this->data[i]+L.data[i];
                ++i;
            }
            while(i!=this->last+1)
            {
                tmp.data[i] = this->data[i];
            }
            return tmp;
        }
    }
    else
    {
        int i = 0;
        SeqList<T> tmp;
        tmp.reSize(L.maxSize);
        tmp.last = L.last;
        while(i!=this->last+1)
        {
            tmp.data[i] = this->data[i]+L.data[i];
            ++i;
        }
        while(i!=L.last+1)
        {
            tmp.data[i] = L.data[i];
            ++i;
        }
        return tmp;

    }
}*/
template<class T>
int SeqList<T>::Search(T &x)const
{
    if(this->last!=-1)
    {
        int i = 0;
        while(i!=this->last+1)
        {
            if(this->data[i]==x)
                return i;
            ++i;
        }
    }
    return -1;
}
template<class T>
SeqList<T>::SeqList(int sz)
{
    if(sz > 0)
    {
        this->maxSize = sz;
        this->last = -1;
        this->data = new T[this->maxSize];
        if(this->data == NULL)
        {
            cerr<<"内存分配错误！"<<endl;
            exit(1);
        }
    }
}
template<class T>
SeqList<T>::SeqList(SeqList<T> &L)
{
    this->maxSize = L.Size();
    this->last = L.Length()-1;
    this->data = new T[maxSize];
    if(this->data == NULL)
    {
        cerr<<"内存分配错误！"<<endl;
        exit(1);
    }
    for(int i=0; i<=last; ++i)
        this->data[i] = L.data[i];
}
template<class T>
void SeqList<T>::reSize(int newSize)
{
    if(newSize <= 0)
    {
        cerr<<"无效的数组大小！"<<endl;
        return;
    }
    if(newSize != maxSize)
    {
        T *newarray = new T[newSize];
        if(newarray == NULL)
        {
            cerr<<"存储分配错误！"<<endl;
            exit(1);
        }
        int n = this->last+1;
        T *srcptr = this->data;
        T *destptr = newarray;
        while(n--)
        {
            *destptr++ = *srcptr++;
        }
        delete[]data;
        this->data = newarray;
        this->maxSize = newSize;
    }
}

template<class T>
void SeqList<T>::print()
{
    int i = 0;
    if(this->last != 0)
    {
        while(i!=last+1)
        {
            cout<<" ["<<this->data[i++]<<"] ";
        }
        cout<<endl;
    }
}
template<class T>
void SeqList<T>::push(T x)
{
    if(!this->IsFull())
    {
        this->data[last+1] = x;
        ++this->last;
    }
    else
    {
        this->reSize(defaultSize);
        this->data[last+1] = x;
        ++this->last;
    }
}
int main()
{
    int a = 777, b = 1000, c;
    SeqList<int> shu_zu0, shu_zu1;
    for(int i = 0; i<=10; ++i)
        shu_zu0.push(i);
    shu_zu0.print();
    cout<<shu_zu0.Search(a)<<endl;
    shu_zu1 = shu_zu0;
    shu_zu1.print();
    cout<<shu_zu1.Locate(10)<<endl;
    cout<<shu_zu1.Locate(14)<<endl;
    shu_zu1.setData(7, a);
    shu_zu1.print();
    shu_zu1.Sort();
    shu_zu1.print();
    shu_zu1.Insert(11, b);
    shu_zu1.print();
    shu_zu1.Remove(11, c);
    shu_zu1.print();
    cout<<c<<endl;
    //shu_zu1 = shu_zu1+shu_zu1;
    //shu_zu1.print();
    return 0;
}

 

运行结果

顺序表（C++）

 

这里分析一下线性表的性能，从三个主要功能分析：查找、删除和插入

①查找

 因为每个元素被查找的可能性是相同的，因此对于有n个元素的线性表平均查找次数为

ACN = (1+n)/2

所以要平均比较（1+n）/2个元素才能查到所查元素

顺序表（C++）

 

注：在所查询的元素不在表内的情况时，算法中负担检测的循环实际执行了n+1，只是在n+1次时没有进行数据比较

②删除

当删除元素存在时，需要对所删除位置后的元素向前移动，因为删除的元素均等概，所以平均移动次数为

AMN = (n-1 + 0)/2 = (n-1)/2

顺序表（C++）

 

③插入

当插入位置合法时，需要对所插入位置后的元素向后移动，因为插入位置等概，所以平均移动次数为

AMN = (n+0)/2 = n/2

 

原文链接: https://www.cnblogs.com/area-h-p/p/10822135.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    顺序表（C++）

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/294750

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月15日 下午4:12
下一篇 2023年2月15日 下午4:13

相关推荐