【實(shí)現(xiàn)類】

const int maxSize=100;//存儲(chǔ)空間初始分配量 template <class T> class SeqList{ private:T data[maxSize];//存放數(shù)據(jù)元素的數(shù)組int length;//順序表的長度 public:SeqList();//無參構(gòu)造函數(shù)SeqList(T a[],int n);//有參構(gòu)造函數(shù)~SeqList(){};//析構(gòu)函數(shù)空int getLength();//獲取順序表的長度T getElement(int i);//獲取順序表的第i個(gè)元素int getPosition(T x);//獲取順序表中值為x的元素序號(hào)void insertElement(int i,T x);//在順序表中第i個(gè)位置插入值為x的元素T deleteElement(int i);//刪除順序表的第i的元素void print();//按序號(hào)依次輸出順序表各元素 };

【構(gòu)造函數(shù)與析構(gòu)函數(shù)】

1.無參構(gòu)造函數(shù)與析構(gòu)函數(shù)

無參構(gòu)造函數(shù)創(chuàng)建一個(gè)空的順序表，將表長置為 0，析構(gòu)函數(shù)使用默認(rèn)析構(gòu)函數(shù)即可。

template<class T> SeqList<T>::SeqList(){length=0;//長度為0 }

2.有參構(gòu)造函數(shù)

有參構(gòu)造函數(shù)將給定數(shù)組元素作為順序表的數(shù)據(jù)元素，傳入元素個(gè)數(shù) n 作為順序表長度。

template<class T> SeqList<T>::SeqList(T a[], int n){if(n>maxSize) throw "參數(shù)非法";for(int i=0;i<n;i++)//給定元素作為順序表數(shù)據(jù)元素data[i]=a[i];length=n;//傳入元素個(gè)數(shù)作為順序表長度 }

【獲取順序表長度】

求順序表的長度只需返回成員變量 length 的值

template<class T> SeqList<T>::getLength(){return length; }

【查找元素】

1.按位查找

按位查找時(shí)，順序表中第 i 個(gè)元素存儲(chǔ)在數(shù)組中下標(biāo)為 i-1 的位置，時(shí)間復(fù)雜度為 O(1)

template<class T> T SeqList<T>::getElement(int i){if(i<1&&i>length)throw "查找位置非法";elsereturn data[i-1]; }

2.按值查找

按值查找時(shí)，需要對(duì)順序表中元素依次進(jìn)行比較，查找成功則返回元素的序號(hào)，查找失敗則返回 0，時(shí)間復(fù)雜度為 O(n)

template<class T> int SeqList<T>::getPosition(T x){for(int i=0;i<length;i++)if(data[i]==x)return i+1;//返回元素序號(hào)return 0;//查找失敗 }

【插入操作】

在順序表中的第 i 個(gè)位置插入值元素，需要先將第 n 個(gè)元素到第 i 個(gè)元素后移 1 位，再將元素插入位置 i，使長度為 n 的順序表變?yōu)?n+1，其時(shí)間復(fù)雜度為 O(n)

需要注意的是，在插入之前需要進(jìn)行異常判斷，如果表滿，則引發(fā)上溢異常；如果插入位置不合理，則引發(fā)位置異常。

template<class T> void SeqList<T>::insertElement(int i,T x){if(length>=maxSize)throw "上溢";if(i<1||i>length+1)throw "位置異常";for(int j=length;j>=i;j--)//第n個(gè)到第i個(gè)元素依次后移data[j]=data[j-1];data[i-1]=x;//位置i插入元素length++;//長度+1 }

【刪除操作】

在順序表中的第 i 個(gè)元素刪除，需要先取出被刪除的元素，然后將第 i+1 個(gè)元素到第 n 個(gè)元素前移 1 位，最后將順序表的長度變?yōu)?n-1，其時(shí)間復(fù)雜度為 O(n)

需要注意的是，在刪除之前需要進(jìn)行異常判斷，如果表空，則引發(fā)下溢異常；如果刪除位置不合理，則引發(fā)位置異常。

T SeqList<T>::deleteElement(int i){if(length==maxSize)throw "下溢";if(i<1||i>length)throw "位置異常";T x=data[i-1];//取出刪除元素for(int j=i;j<=length-1;j++)//第i個(gè)到第n個(gè)元素依次前移data[j]=data[j+1];length--;//長度-1return x; }

7.遍歷輸出

遍歷輸出即按照下標(biāo)依次輸出各元素

template<class T> void SeqList<T>::print(){for(int i=0;i<length;i++)cout<<data[i]<<endl; } 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 线性表 —— 顺序表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。