顺序表的实现

编程技术  /  houtizong 发布于 3年前   52

#include <iostream>#include <stdlib.h>#include <conio.h>using namespace std;#define INIT_SIZE 5#define INCREASE_SIZE 10typedef int ElemType;/* * 声明此程序中的地址值与数组想象 * 即首位为0，其余的依次递增 * 若要使得首位为0，只需稍做修改即可 *///自定义一个类型typedef struct {    ElemType *eList;   //用于指向相应的存储区    int length;         //存储区内存储原元素个数    int listSize;       //存储的容量，为存储元素的大小的倍数} ArrayList;//初始化一个ArrayListvoid 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;}