线性表的定义及实现

2016-05-19  本文已影响134人  代号027

线性表的逻辑结构

线性表是由n个类型相同的数据元素组成的有限序列,记为(a1,a2,…,ai-1,ai,ai+1,…,an)。其中,这里的数据元素可以是原子类型,也可以是结构类型。线性表的数据元素存在着序偶关系,即数据元素之间具有一定的次序。在线性表中,数据元素ai-1在ai的前面,ai又在ai+1的前面,可以把ai-1称为ai的直接前驱元素,ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素,ai+1称为ai的直接后继元素。

image

在线性表中,除了第一个元素a1,每个元素有且仅有一个直接前驱元素;除了最后一个元素an,每个元素有且只有一个直接后继元素。

顺序表的插入:

image

线性表中顺序表的实现(C++语言描述):

#include <iostream>
#include <cstring>
using namespace std;

//自定义顺序表类Vector
class Vector {

//设置顺序表的size和length
//其中size是指顺序表的最大尺寸
//length是指顺序表中data的长度
private:
    int size, length;
    int *data;

public:

    Vector(int input_size) {
        size = input_size;
        length = 0;
        data = new int[size];
    }
    ~Vector() {
        delete[] data;
    }

    //在插入操作中,根据下标loc,插入value
    //插入后为保顺序,loc后的元素挨个向后偏移一个位置,切顺序表长度增加
    bool insert(int loc, int value) {
        if (loc < 0 || loc > length) {
            return false;
        }
        if (length >= size) {
            return false;
        }
        for (int i = length; i > loc; --i) {
            data[i] = data[i - 1];
        }
        data[loc] = value;
        length++;
        return true;
    }

    
    int search(int value) {
        for (int i = 0; i < length; ++i) {
            if (data[i] == value) {
                return i;
            }
        }
        return -1;
    }
    
    //删除操作,删除某一个元素时,后面的元素一次向前偏移一个位置,顺序表长度减少
    bool remove(int index) {
        if (index < 0 || index >= length) {
            return false;
        }
        for (int i = index + 1; i < length; ++i) {
            data[i - 1] = data[i];
        }
        length = length - 1;
        return true;
    }
    
    void print() {
        for(int i=0; i<length; i++)
        {
            if(i > 0)
            {
                cout << " ";
            }
            cout << data[i];
        } 
        cout << endl;
    }
};

int main() {
    Vector a(2);
    cout << a.insert(0, 1) << endl;
    cout << a.insert(0, 2) << endl;
    a.print();
    cout << a.remove(1) << endl;
    a.print();
    cout << a.search(0) << endl;
    cout << a.search(1) << endl;
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读