顺序表的实现

#include <iostream>
#include <stdlib.h>
#include <conio.h>

using namespace std;

#define INIT_SIZE 5
#define INCREASE_SIZE 10

typedef int ElemType;

/*
 * 声明此程序中的地址值与数组想象
 * 即首位为0，其余的依次递增
 * 若要使得首位为0，只需稍做修改即可
 */
//自定义一个类型
typedef struct {
    ElemType *eList;   //用于指向相应的存储区
    int length;         //存储区内存储原元素个数
    int listSize;       //存储的容量，为存储元素的大小的倍数
} ArrayList;

//初始化一个ArrayList
void initArrayList(ArrayList &al) {
    //分配一段固定内存
    al.eList = (ElemType *)malloc(INIT_SIZE * sizeof(ElemType));
    //判断内存是否分配成功
    if(!al.eList) {
        exit(0);
    }
    al.length = 0;
    al.listSize = INIT_SIZE;
}

//显示所有的函数值
void showArrayList(ArrayList &al) {
    if(al.length == 0) {
        cout << "There is no element in it!" <<endl;
    }
    ElemType *index = al.eList;
    for(int i = 0; i < al.length; i++) {
        cout << *(index++) << " ";
        if(i == al.length - 1) {
            cout << endl;
        }
    }
}

//添加数据
void addElements(ElemType e[] , int iNumber , ArrayList &al) {
    ElemType *curr = al.eList + al.length;
    for(int i = 0; i < iNumber; i++) {
        *(curr ++) = e[i];
        al.length ++;
    }
}

//插入数据
void insertElement(ElemType e, int index, ArrayList &al) {
    //判断插入的位置是否合法
    if(index > al.length || index < 1) {
        cout << "地址值越界！" << endl;
        return;
    }
    //判断内存空间是否充足，若不充足自动递增
    if(al.length >= al.listSize) {
        int iSize = al.listSize + INCREASE_SIZE;
        ElemType *newbase = (ElemType *)realloc(al.eList , iSize * sizeof(ElemType));
        al.eList = newbase;
        al.listSize = iSize;
    }
    //将index后面的元素向后移动一个单位
    ElemType *p = al.eList + index;
    for(ElemType *q = al.eList + al.length - 1; q >= p; q--) {
        *(q + 1) = *q;
    }
    *p = e;
    al.length++;
    cout << "插入成功！" << endl;
}

//删除元素
ElemType deleteElement(int index , ArrayList &al) {
    //判断元素的下标值是否越界
    if(index < 0 || index > al.length - 1) {
        cout << "要删除的元素不存在！" << endl;
        return -1;
    }
    //记录要删除的下标地址
    ElemType *curr = al.eList + index;
    //记录被删除元素的值，当做返回值
    ElemType eReturn = *(curr);
    //将地址后的所有元素前移一位
    for(ElemType *p = al.eList + al.length - 1; curr < p; curr++) {
        *(curr) = *(curr + 1);
    }
    al.length --;
    return eReturn;
}

//添加元素
void addElement(ElemType e , ArrayList &al) {
    //判断内存空间是否充足，若不充足自动递增
    if(al.length >= al.listSize) {
        int iSize = al.listSize + INCREASE_SIZE;
        ElemType *newbase = (ElemType *)realloc(al.eList , iSize * sizeof(ElemType));
        al.eList = newbase;
        al.listSize = iSize;
    }
    ElemType *curr = al.eList + al.length - 1;
    *(curr + 1) = e;
    al.length++;
    cout << "添加元素成功！" << endl;
}

//获取元素
ElemType getElement(int index , ArrayList &al) {
    if(index < 0 || index > al.length - 1) {
        cout << "您要获取的元素不存在！";
        return -1;
    }
    ElemType eReturn = *(al.eList + index);
    return eReturn;
}

//获取元素的地址值
int getIndex(ElemType e , ArrayList &al) {
    for(int i = 0; i < al.length ; i++) {
        if(e == *(al.eList + i)) {
            return i;
        }
    }
    cout << "您要查找的元素不存在！";
    return -1;
}

void changeElement(int index , ElemType e , ArrayList &al) {
    if(index < 0 || index > al.length - 1) {
        cout << "要修改的元素不存在！" << endl;
        return;
    }
    *(al.eList + index) = e;
    cout << "修改成功！" << endl;
}

//测试函数
int main()
{
    ArrayList al;
    initArrayList(al);

    //初始化ArrayList
    int iNumber;
    cout << "请输入您要创建线性表的长度：" << endl;
    cin >> iNumber;
    cout << "请输入您要给线性表初始化的值：" << endl;
    ElemType elements[iNumber];
    for(int i = 0; i < iNumber ; i++) {
        cin >> elements[i];
    }
    addElements(elements , iNumber, al);
    cout << "线性表中元素值为：" << endl;
    showArrayList(al);

    //添加元素到ArrayList里面
    int index;
    ElemType e;
    cout << "请输入您要插入的地址值，不要大于 " << al.length << " :" << endl;
    cin >> index;
    cout << "请输入您要插入的元素值：" << endl;
    cin >> e;
    insertElement(e , index , al);
    cout << "线性表中元素值为：" << endl;
    showArrayList(al);

    //测试函数deleteElement
    int deleteIndex;
    cout << "请输入您要删除的元素的地址值，不要大于 " << al.length-1 << " :" << endl;
    cin >> deleteIndex;
    ElemType eReturn = deleteElement(deleteIndex , al);
    cout << "删除的元素为：" << eReturn << endl;
    cout << "线性表中元素值为：" << endl;
    showArrayList(al);

    //测试函数addElement
    ElemType eAdd;
    cout << "请输入您要向线性添加的元素值：" << endl;
    cin >> eAdd;
    addElement(eAdd, al);
    cout << "线性表中元素值为：" << endl;
    showArrayList(al);

    //测试函数getElement
    int iGet;
    cout << "请输入您要获取元素的地址值，不要大于 " << al.length-1 << " :" << endl;
    cin >> iGet;
    ElemType eGet = getElement(iGet , al);
    cout << "地址值为" << iGet << "的元素值为：" << eGet << endl;

    //测试函数getIndex
    ElemType eFind;
    cout << "请输入您要查找的元素值：" << endl;
    cin >> eFind;
    cout << "元素值为" << eFind << "的地址值为：" << getIndex(eFind , al) << endl;

    //测试函数changeElement
    int iModify;
    ElemType eModify;
    cout << "请输入您要修改元素的地址值，不要大于 " << al.length - 1 << " :" << endl;
    cin >> iModify;
    cout << "请输入您要修改的元素值 :" << endl;
    cin >> eModify;
    changeElement(iModify, eModify , al);
    cout << "线性表中元素值为：" << endl;
    showArrayList(al);

    return 0;
}