C++語言實現(xiàn)順序表

順序表的定義及其特點

順序表的定義是:把線性表中的所有表項按照其邏輯順序依次存儲到從計算機存儲中指定存儲位置開始的一塊連續(xù)的存儲空間中效斑。 這樣,線性表中第一個表項的存儲位置就是被指定的存儲位置,第i個表項(2 i n)的存儲位置緊接在第i一1個表項的存儲位置的后面。假設(shè)順序表中每個表項的數(shù)據(jù)類型為T,則每個表項所占用存儲空間的大小(即字節(jié)數(shù))大小相同,均為 sizeof(T),整個順序表所占用存儲空間的大小為n sizeof(T),其中n表示線性表的長度。

順序表的特點是:

(1)在順序表中,各個表項的邏輯順序與其存放的物理順序一致,即第i個表項存儲于
第i個物理位置(1 i n).
(2)對順序表中所有表項,既可以進行順序訪問,也可以進行隨機訪問苗踪。 也就是說,既可以從表的第一個表項開始逐個訪問表項,也可以按照表項的序號(亦稱為下標(biāo))直接訪問表項捂襟。

順序表類定義及其主要操作

順序表的類聲明

class SeqList
{
    private:
        T *data;//存放數(shù)據(jù)的動態(tài)數(shù)組
        int maxSize;//最大可容納表項的項數(shù)
        int last; //當(dāng)前已存表項的最后位置（從0開始）
        void reSize(int newSize);   //改變數(shù)組空間大小
        
    public:
        SeqList(int sz);          //構(gòu)造函數(shù)
        SeqList(SeqList<T>& L);            //復(fù)制構(gòu)造函數(shù)
        ~SeqList() {delete[ ] data;}            //析構(gòu)函數(shù)
        int Size(){//求表最大容量
            return maxSize;
            }    
        int Length() {//計算表長度
            return last+1;
            }        
        int Search(T x);//搜索x在表中位置，函數(shù)返回表項序號 
        int Locate(int i);//定位第i個表項趴酣，函數(shù)返回表項序號
        bool Insert(int i, T& x);//插入x在第i個表項之后
        bool Remove(int i, T& x);//刪除第i個表項之后梨树，通過x返回表項的值
        bool GetData(int i,T& x);//取第i個表項的值，以x引用返回
        bool SetData(int i,T& x);//用x修改第i個表項的值
        bool IsEmpty(){//判斷表是否空否岖寞，是返回true抡四，否返回false
            return (last==-1) ? true : false;
        }
        bool IsFull(){//判讀表是否滿否，是返回true，否返回false
            return (last = maxSize - 1) ? true : false;
        }
        void input();//輸入數(shù)據(jù)
        void output();//打印數(shù)據(jù)
};

構(gòu)造函數(shù)和復(fù)制構(gòu)造函數(shù)

template <class T>
inline SeqList<T>::SeqList(int sz)
{
    if (sz > 0) {
        maxSize = sz;  last = -1;
        data = new T[maxSize];     //創(chuàng)建表存儲數(shù)組
        if (data == NULL)          //動態(tài)分配失敗
        { 
            cout<<"儲存分配錯誤指巡！"<<endl;
        }
    }
}
template <class T>
inline SeqList<T>::SeqList(SeqList<T>& L)
{
    //復(fù)制構(gòu)造函數(shù)淑履，用參數(shù)表中給出的已有順序表初始化新建的順序表
    maxSize = L.Size();
    last = L.Length()-1;
    T value;
    data = new T[maxSize];//創(chuàng)建順序表儲存數(shù)組
    if(data == NULL){
        cout<<"動態(tài)分配錯誤！"<<endl;
    }
    for(int i =1;i<=last-1;i++){
        L.GetData(i, value);
        data[i-1] = value;
    }
    
}

調(diào)整順序表空間大小

template <class T>
inline void SeqList<T>::reSize(int newSize){
    //私有函數(shù)藻雪，擴充順序表的儲存數(shù)組空間的大小秘噪，新數(shù)組的元素個數(shù)為newSize.
    if(newSize <= 0){
        cout<<"無效數(shù)組的大小勉耀！"<<endl;
    }
    if(newSize != maxSize){
        T *newarray = new T[newSize];
        if(newarray == NULL){
            cout<<"儲存分配錯誤指煎！"<<endl;
        }
        int n = last+1;
        T *srcptr = data;//源數(shù)組的首地址
        T *desptr = newarray;//目的數(shù)組的首地址
        while(n--){//復(fù)制
            *desptr++ = *srcptr++;
        }
        delete []data;//刪除老數(shù)組
        data = newarray;
        maxSize = newSize;//復(fù)制新數(shù)組
    }
}

搜索和定位操作

template <class T>
inline int SeqList<T>::Search(T x)
{
    //搜索函數(shù)：在表中順序搜索與給定值x匹配的表項，找到則函數(shù)返回該表項是第幾個元素
    //否則返回0便斥，表示搜索失敗
    for(int i=0;i<=last;i++){
        if(data[i] == x)
        return i+1;
    }
    return 0;
}
template <class T>
inline int SeqList<T>::Locate(int i)
{
    //定位函數(shù):返回第i(1<=i<=lat+1)個表項的位置至壤，否則函數(shù)返回0，表示定位失敗
    if(i>=1 && i<last+1){
        return i;
    }
    else return 0;
}

插入與刪除操作

template <class T>
inline bool SeqList<T>::Insert(int i, T& x)//插入x在第i個表項之后
{
    //將新元素x插入到第i（0<=i<=last+1）個表項之后枢纠。函數(shù)返回插入成功的信息像街，若插入成功返回true,否則返回false.
    //i=0時虛擬的，實際上是插入到第1個元素的位置晋渺。
    if(last == maxSize - 1){
        return false;//表滿镰绎，不能插入
    }
    if(i<0 || i > last+1)
    {
        return false;//參數(shù)i不合理，不能插入
    }
    for(int j=last;j>=i;j--)
    {
        data[j+1]=data[j];//一次后移木西，空出第i號位置
    }
    data[i] = x;//插入
    last++;//最后位置加一
    return true;
}
template <class T>
inline bool SeqList<T>::Remove(int i, T& x)//刪除第i個表項之后畴栖，通過x返回表項的值
{
    //從表中刪除第i（0<=i<=last+1）個表項，通過引用型參數(shù)x返回刪除的元素值户魏。函數(shù)返回刪除成功的信息驶臊，刪除成功返回true,刪除失敗返回false
    if(last == -1){
        return false;//表空，不能刪除
    }
    if(i<1 || i>last+1){
        return false;//參數(shù)i不合理叼丑，不能刪除
    }
    x=data[i];//儲存刪除的元素
    for(int j=i;j<=last;j++)
    {
        data[j-1] = data[j];//依次前移关翎，填補
    }
    last--;//最后位置減一
    return true;
}

順序表的性能分析

順序表所有操作的實現(xiàn)中,最復(fù)雜、最耗時的就是搜索鸠信、插入和刪除運算的實現(xiàn)代碼纵寝。分析順序表的性能,主要是分析這3個操作的實現(xiàn)代碼的時間復(fù)雜性。
int search(T& x)是順序表的順序搜索算法星立。 其主要思想是:

從表的開始位置起,根據(jù)給定值x,逐個與表中各表項的值進行比較爽茴。 若給定值與某個表項的值相等,則算法報告搜索成功的信息并返回該表項的位置;若查遍表中所有的表項,沒有任何一個表項滿足要求,則算法報告搜索不成功的信息并返回0(必要的話,可改一下算法,返回新表項應(yīng)插人的位置)。

搜索算法的時間代價用數(shù)據(jù)比較次數(shù)來衡量绰垂。 在搜索成功的情形下,順序搜索的數(shù)據(jù)比較次數(shù)可做如下分析室奏。 若要找的正好是表中第1個表項,數(shù)據(jù)比較次數(shù)為1,這是最好情況;若要找的是表中最后的第n個表項,數(shù)據(jù)比較次數(shù)為n(設(shè)表的長度為n),這是最壞的情況 。若要計算平均數(shù)據(jù)比較次數(shù),需要考慮各個表項的搜索概率p及找到該表項時的數(shù)據(jù)比較次數(shù).搜索的平均數(shù)據(jù)比較次數(shù)ACN(average comparing number)為
ACN=

計算平均數(shù)據(jù)比較次數(shù)是為了了解對表操作的整體性能劲装。若考慮相等概率的情形胧沫。搜索各表項的可能性相同,有==...==,且搜索第1個表項的數(shù)據(jù)比較次數(shù)為1,搜計算平均值是為了解算法對表操作的整體性能昌简。 若僅考慮相等概率的情形。搜索各表索第2個表項的數(shù)據(jù)比較次數(shù)為2,,搜索第i號表項的數(shù)據(jù)比較次數(shù)為i,則
ACN=
即平均要比較個表項绒怨。

分析順序表的插入和刪除的時間代價主要看循環(huán)內(nèi)的數(shù)據(jù)移動次數(shù)
在將新表項插入到第i個表項(0 i n)后面時,必須從后向前循環(huán),逐個向后移動n-i個表項纯赎。 因此,最好的情形是在第n個表項后追加新表項,移動表項個數(shù)為0;最差情形是在第1個表項位置插人新表項(視為在第0個表項后面插入),移動表項個數(shù)為n;平均數(shù)據(jù)移動次數(shù)AMN(average moving number)在各表項插入概率相等時為
AMN=
即就整體性能來說,在插入時有n+1個插入位置,平均移動個表項!

在刪除第i個表項(1 i n)時,必須從前向后循環(huán),逐個移動n一i個表項。 因此,最好的情形是刪去最后的第n個表項,移動表項個數(shù)為0;最差情形是刪去第1個表項,移動項個數(shù)為n-1;平均數(shù)據(jù)移動次數(shù)AMN在各表項刪除概率相等時為
AMN=
就整體性能來說,在刪除時有n個刪除位置,平均移動(n-1)/2個表項南蹂。

以上是C++順序表使用過程中最常用的主要操作犬金，相關(guān)完整代碼已經(jīng)push到GitHub，需要的小伙伴自行clone六剥，如果覺得還不錯的話晚顷，歡迎Star,這里是傳送門C++順序表，除此之外仗考，想要了解更多的C,C++,Java,Python等相關(guān)知識的童鞋音同，歡迎來我的博客相逢的博客词爬，我們一起討論秃嗜！接下來我會更新C語言鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)線性表，敬請期待顿膨！