目录

前言

1.什么是顺序表

2.顺序表的静态存储表示

1.初始化

2.长度

3.数据元素

4.长度

5.获取元素下标

6.前驱节点

7.后继节点

8.插入

9.删除

10.遍历

11.测试代码

---

前言

    这篇文章讲的是顺序表的两种实现方式。

1.什么是顺序表

        线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

        顺序表有以下性质：

图1.线性表中数据元素之间的关系

图2.线性表的顺序存储结构示意图

2.顺序表的静态存储表示

        我们使用数组来实现顺序表的静态表示，数组中的数据元素在存储中是连续的，但是使用数组表示顺序表有个缺点就是数组的长度不可变。

        顺序表的静态表示定义如下：

#define MAX_SIZE 10           //定数顺序表的最大表长
typedef int ElementType;
typedef int Status;
typedef struct StaticSqList {
    ElementType data[MAX_SIZE]; // 数据元素存储区
    int length; // 当前长度
}StaticSqList;

1.初始化

        初始化的时候，表长为空

// 初始化
void initStaticSqList(StaticSqList * sqList){
    sqList->length = 0;
}

2.长度

        返回静态顺序表的长度

// 长度
int staticSqListLength(StaticSqList *sqList){
    return sqList->length;
}

3.数据元素

        遍历数组

// 获取元素
Status getElemForStaticSqList(StaticSqList *sqList,int location,ElementType * element){
    if (location < 0 || location > sqList->length - 1) {
        return 0;
    }
    *element = sqList->data[location];
    return 1;
}

4.长度

// 长度
int staticSqListLength(StaticSqList *sqList){
    return sqList->length;
}

5.获取元素下标

// 获取元素
Status getElemForStaticSqList(StaticSqList *sqList,int location,ElementType * element){
    if (location < 0 || location > sqList->length - 1) {
        return 0;
    }
    *element = sqList->data[location];
    return 1;
}

6.前驱节点

// 前驱节点
Status priorElemForStaticSqList(StaticSqList *sqList,ElementType currentElement,ElementType * priorElement){
    for (int i = 0 ; i< sqList->length; i++) {
        if (sqList->data[i] == currentElement) {
            if (i - 1 > 0) {
                * priorElement = sqList->data[i-1];
                return 1;
            }
        }
    }
    return 0;
}

7.后继节点

// 后继节点
Status nextElemForStaticSqList(StaticSqList *sqList,ElementType currentElement,ElementType * nextElement){
    for (int i = 0 ; i< sqList->length; i++) {
        if (sqList->data[i] == currentElement) {
            if (i <= MAX_SIZE - 1) {
                * nextElement = sqList->data[i+1];
                return 1;
            }
        }
    }
    return 0;
}

8.插入

// 插入
Status insertStaticSqList(StaticSqList *sqList,int pos,ElementType element){
    if (pos < 0 || pos > sqList->length+1 || sqList->length == MAX_SIZE) {
        return 0;
    }
    for (int i = sqList->length; i > pos -1; i --) {//插入位置之后的元素后移
        sqList[i] = sqList[i-1];
    }
    sqList->data[pos-1] = element;
    sqList->length++;
    return 1;
}

9.删除

// 测试函数
void testStaticSqList(){
    StaticSqList sqList;
    cout<<"顺序表初始化......"<<endl;
    initStaticSqList(&sqList);
    cout<<"顺序表判空和长度计算......"<<endl;
    if (emptyStaticSqList(&sqList)) {
        cout<<"顺序表为空,长度为"<<staticSqListLength(&sqList)<<endl;
    }
    cout<<"顺序表插入测试......"<<endl;
    for (int i = 1; i <=11 ; i++) {
        if (insertStaticSqList(&sqList, sqList.length + 1, i)) {
            cout<<"数据元素"<<i<<"插入成功"<<endl;
        }else{
            cout<<"数据元素"<<i<<"插入失败"<<endl;
        }
    }
    cout<<"插入之后的静态顺序表"<<endl;
    traverseStaticSqList(&sqList);
    cout<<"顺序表删除测试......"<<endl;
    ElementType element;
    if (deleteStaticSqList(&sqList, 10, &element)) {
        cout<<"数据元素"<<element<<"删除成功"<<endl;
    }
    cout<<"删除之后的静态顺序表"<<endl;
    traverseStaticSqList(&sqList);
    //后继节点测试
    ElementType nextElement;
    if (nextElemForStaticSqList(&sqList, 8, &nextElement)) {
        cout<<"数据元素8"<<"后继节点为："<<nextElement<<endl;
    }else{
        cout<<"后继节点不存在"<<endl;
    }
    //后继节点测试
    ElementType priorElement;
    if (priorElemForStaticSqList(&sqList, 8, &priorElement)) {
        cout<<"数据元素8"<<"前驱节点为："<<priorElement<<endl;
    }else{
        cout<<"前驱节点不存在"<<endl;
    }
    cout<<"顺序表数据元素下标测试......"<<endl;
    for (int i = -1; i <= 12; i++) {
        int location;
        if (locationElemForStaticSqList(&sqList, i, &location)) {
            cout<<"数据元素"<<i<<"下标为:"<<location<<endl;
        }else{
            cout<<"数据元素不存在"<<endl;
        }
    }
    
}

// 删除
Status deleteStaticSqList(StaticSqList *sqList,int pos,int * element){
    if (pos < 1 || pos > sqList->length|| sqList->length == 0) {
        return 0;
    }
    for (int i = pos - 1; i < sqList->length - 1; i ++) {//插入位置之后的元素后移
        sqList[i] = sqList[i+1];
    }
    * element = sqList->data[pos-1];
    sqList->length--;
    return 1;
}

10.遍历

// 遍历
void traverseStaticSqList(StaticSqList *sqList){
    for (int i = 0; i<sqList->length; i++) {
        cout<<sqList->data[i]<<"\t";
    }
    cout<<endl;
}

11.测试代码

// 测试函数
void testStaticSqList(){
    StaticSqList sqList;
    cout<<"顺序表初始化......"<<endl;
    initStaticSqList(&sqList);
    cout<<"顺序表判空和长度计算......"<<endl;
    if (emptyStaticSqList(&sqList)) {
        cout<<"顺序表为空,长度为"<<staticSqListLength(&sqList)<<endl;
    }
    cout<<"顺序表插入测试......"<<endl;
    for (int i = 1; i <=11 ; i++) {
        if (insertStaticSqList(&sqList, sqList.length + 1, i)) {
            cout<<"数据元素"<<i<<"插入成功"<<endl;
        }else{
            cout<<"数据元素"<<i<<"插入失败"<<endl;
        }
    }
    cout<<"插入之后的静态顺序表"<<endl;
    traverseStaticSqList(&sqList);
    cout<<"顺序表删除测试......"<<endl;
    ElementType element;
    if (deleteStaticSqList(&sqList, 10, &element)) {
        cout<<"数据元素"<<element<<"删除成功"<<endl;
    }
    cout<<"删除之后的静态顺序表"<<endl;
    traverseStaticSqList(&sqList);
    //后继节点测试
    ElementType nextElement;
    if (nextElemForStaticSqList(&sqList, 8, &nextElement)) {
        cout<<"数据元素8"<<"后继节点为："<<nextElement<<endl;
    }else{
        cout<<"后继节点不存在"<<endl;
    }
    //后继节点测试
    ElementType priorElement;
    if (priorElemForStaticSqList(&sqList, 8, &priorElement)) {
        cout<<"数据元素8"<<"前驱节点为："<<priorElement<<endl;
    }else{
        cout<<"前驱节点不存在"<<endl;
    }
    cout<<"顺序表数据元素下标测试......"<<endl;
    for (int i = -1; i <= 12; i++) {
        int location;
        if (locationElemForStaticSqList(&sqList, i, &location)) {
            cout<<"数据元素"<<i<<"下标为:"<<location<<endl;
        }else{
            cout<<"数据元素不存在"<<endl;
        }
    }
    
}