Learning Log. [數(shù)據(jù)結(jié)構(gòu)] 順序表(c++實(shí)現(xiàn))

  • 源碼
#define ERROR -1
#define OVERMEMORY -2

#include <iostream>

using namespace std;

template<class T>
class List{
    T *elem;    //存儲(chǔ)空間的基址
    int length; //當(dāng)前順序表長(zhǎng)度
    int listsize; //當(dāng)前分配空間的大小

public:
    List(){
        InitList(1);
    }
    List(int size){
        InitList(size);
    }
    List(const List &l){
        elem = new T[l.listsize];
        length = l.length;
        listsize = l.listsize;
        for (int i = 0; i < l.listsize; i++){
            elem[i] = l.elem[i];
        }
    }//拷貝構(gòu)造函數(shù)

    ~List(){
        delete elem;
    }

    void InitList(int L){
        elem = new T[L];
        if (!elem){
            cout << "Over Memory!" << endl;
            exit(OVERMEMORY);
        }
        length = 0;
        listsize = L;
    }// 初始化鏈表

    void ListInsert(int i,const T &e){
        if (i < 0 || i > length)    return;
        if (length >= listsize)
            resize(listsize*2);
        
        T *p = &elem[i];
        for (T *q = &elem[length]; q > p; q--){
            *q = *(q-1);
        }
        *p = e;
        length++;
    }// 在下標(biāo)為i的位置插入元素e

    void push_back(const T &e){
        ListInsert(length, e);
    }//在表末添加元素e

    void ListDelete(int i){
        if (i < 0 || i >= length)    return;

        T *end = &elem[length-1];
        for (T *p = &elem[i]; p != end; p++){
            *p = *(p+1);
        }
        length--;

        if (listsize / length >= 4){
            resize(listsize / 2);
        }//如果分配的空間太大,調(diào)整大小

    }//刪除下標(biāo)為i的元素
    void resize(int size){
        T *newelem = new T[size];
        if (!newelem){
            cout << "Over Memory!" << endl;
            exit(OVERMEMORY);
        }

        int count = 0;
        for (int i = 0; i < size; i++){
            if (i < length){
                newelem[i] = elem[i];
                count++;
            }
            else
                break;
        }
        delete elem;
        elem = newelem;
        listsize = size;
        length = count;
    }// 重新設(shè)置順序表存儲(chǔ)空間大小
    
    int LocateElem(const T &e){
        int i = 0;
        T *p = elem;
        while (i < length && *p != e){
            p++;
            i++;
        }
        if (i == length)
            return -1;
        return i;
    }//獲取元素e的下標(biāo)肋僧,如果有多個(gè)則返回下標(biāo)最小的一個(gè)

    void MergeList(List &b){
        List c;

        T *pa = elem;
        T *pb = b.elem;

        c.resize(listsize+b.listsize);
        c.length = length + b.length;

        T *pc = c.elem;
        T *pa_last = &elem[length-1];
        T *pb_last = &b.elem[b.length-1];

        //歸并
        while (pa <= pa_last && pb <= pb_last){
            if (*pa <= *pb){
                *pc = *pa;
                pa++;
                pc++;
            }
            else{
                *pc = *pb;
                pc++;
                pb++;
            }
        }
        while (pa <= pa_last){
            *pc = *pa;
            pc++;
            pa++;
        }//插入La剩余元素
        while (pb <= pb_last){
            *pc = *pb;
            pc++;
            pb++;
        }//插入Lb剩余元素

        *this = c;
    }// 與一個(gè)順序表歸并

    void print(){
        for (int i = 0; i < length; i++){
            cout << elem[i];
            if (i != length-1)
                cout << " ";
        }
        cout << endl;
    }

    T& operator[] (int i){
        return elem[i];
    }// 重載[]

    void operator= (const List &l){
        if (listsize)
            delete elem;
        elem = new T[l.listsize];
        length = l.length;
        listsize = l.listsize;
        for (int i = 0; i < l.listsize; i++){
            elem[i] = l.elem[i];
        }
    }// 重載賦值(深拷貝)

};//順序表類, 下標(biāo)從0開(kāi)始


int main(){
    List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.ListInsert(0, 0);
    l.print();

    List<int> a;
    a.push_back(4);
    a.push_back(5);
    a.push_back(6);
    a.ListDelete(1);
    a.print();
    
    a.MergeList(l);
    a.print();
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末功蜓,一起剝皮案震驚了整個(gè)濱河市芒率,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌俩檬,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,561評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異篮灼,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)徘禁,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,218評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門诅诱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人送朱,你說(shuō)我怎么就攤上這事娘荡。” “怎么了驶沼?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,162評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵炮沐,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我回怜,道長(zhǎng)大年,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,470評(píng)論 1 283
  • 正文 為了忘掉前任玉雾,我火速辦了婚禮翔试,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘复旬。我一直安慰自己垦缅,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,550評(píng)論 6 385
  • 文/花漫 我一把揭開(kāi)白布驹碍。 她就那樣靜靜地躺著壁涎,像睡著了一般凡恍。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上粹庞,一...
    開(kāi)封第一講書(shū)人閱讀 49,806評(píng)論 1 290
  • 那天咳焚,我揣著相機(jī)與錄音,去河邊找鬼庞溜。 笑死革半,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的流码。 我是一名探鬼主播又官,決...
    沈念sama閱讀 38,951評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼漫试!你這毒婦竟也來(lái)了六敬?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,712評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤驾荣,失蹤者是張志新(化名)和其女友劉穎外构,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體播掷,經(jīng)...
    沈念sama閱讀 44,166評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡审编,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,510評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了歧匈。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片垒酬。...
    茶點(diǎn)故事閱讀 38,643評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖件炉,靈堂內(nèi)的尸體忽然破棺而出勘究,到底是詐尸還是另有隱情,我是刑警寧澤斟冕,帶...
    沈念sama閱讀 34,306評(píng)論 4 330
  • 正文 年R本政府宣布口糕,位于F島的核電站,受9級(jí)特大地震影響宫静,放射性物質(zhì)發(fā)生泄漏走净。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,930評(píng)論 3 313
  • 文/蒙蒙 一孤里、第九天 我趴在偏房一處隱蔽的房頂上張望伏伯。 院中可真熱鬧,春花似錦捌袜、人聲如沸说搅。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,745評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)弄唧。三九已至适肠,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間候引,已是汗流浹背侯养。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,983評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留澄干,地道東北人逛揩。 一個(gè)月前我還...
    沈念sama閱讀 46,351評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像麸俘,于是被迫代替她去往敵國(guó)和親辩稽。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,509評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容