顺序表的算法

顺序表

要点

顺序表是在计算机内存中以数组的形式保存的线性表,是指使用一组地址连续的存储单元依次存储数据元素的线性结构。

顺序表的存储结构可表示如下:

#define MAXSIZE 10 typedef int ElemType; typedef struct { // 顺序表的结构类型     ElemType data[MAXSIZE];     int length; } SqList;

基本算法

插入数据元素

在顺序表的第 pos(0≤pos≤length) 个位置上插入新的元素e。

如果 pos 值不正确,则返回ERROR;

否则,讲顺序表中原来第 pos 个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,并且顺序表长度增1。

STATU insertElem(SqList *pList, int pos, ElemType elem) {     int i = 0;       // 判断要插入的位置是否合理     if (pos < 0 || pos > pList->length)        return ERROR;       // 将data[pos]及后面的元素都向后移动一个位置     for (i = pList->length - 1; i > pos; i--) {        pList->data[i] = pList->data[i-1];     }     pList->data[pos] = elem;     pList->length++; // 顺序表长度加1     return OK; }

删除数据元素

删除顺序表中的第 pos(0≤pos≤length-1) 个元素。

如果 pos 值不正确,则返回ERROR;

否则,将顺序表中的第 pos 个元素以后的元素均向前移动一个位置,这样覆盖了原来的第 pos个元素,并且顺序表长度减1。

STATU removeElem(SqList *pList, int pos, ElemType *pElem) {     int i = 0;       // 判断要删除的位置是否合理     if (pos < 0 || pos > pList->length)        return ERROR;       *pElem = pList->data[pos];     // 将data[pos]后面的元素都向前移动一个位置     for (i = pos; i < pList->length; i++) {        pList->data[i] = pList->data[i+1];     }     pList->length--; // 顺序表长度减1       return OK; }

参考代码

以下为本人实现的顺序表的基本操作。欢迎指正。本人的编译环境为Visual Studio2010,C语言。

基本操作 

/*********************************************************************************************************************** [顺序表操作] [1] initList, 初始化一个空的顺序表 [2] createList, 根据数组 elems 构建一个顺序表 [3] insertElem, 在顺序表中第 pos 个位置插入元素 elem [4] removeElem, 在顺序表中移除第 pos 个元素,并由 pElem 返回其值 [5] getElem, 获取顺序表上位置为 pos 的元素,并由 pElem 返回其值 [6] locateElem, 获取元素 elem 在顺序表上第一次出现的位置,如果不存在返回 -1 [7] printList, 打印整个顺序表 ***********************************************************************************************************************/ #include "stdafx.h" #include <stdio.h> #include <stdlib.h>   /*********************************************************************************************************************** 第一部分,数据结构、宏定义 ***********************************************************************************************************************/ #define MAXSIZE 10   typedef enum {          // 状态码     OK = 0,     ERROR = 1 } STATU;   typedef enum {          // C语言中没有bool型,为方便,自定义一个BOOL型     TRUE = 0,     FALSE = -1 } BOOL;   typedef int ElemType;    // 元素类型 typedef struct {     // 顺序表的结构类型     ElemType data[MAXSIZE];     int length; } SqList;   /*********************************************************************************************************************** 第二部分,函数实现 ***********************************************************************************************************************/ /*******************************************************************************  Funtion      : initList  Description  : 初始化一个空的顺序表  Input        : SqList *pList  Output       : SqList *pList  Return Value : void  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ void initList(SqList *pList) {     pList->length = 0; }   /*******************************************************************************  Funtion      : createList  Description  : 根据数组 elems 构建一个顺序表  Input        : SqList *pList,               ElemType elems[],               int size  Output       : SqList *pList  Return Value : STATU(OK/ERROR)  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ STATU createList(SqList *pList, ElemType elems[], int size) {     int i = 0;       // 判断数组大小是否超过最大限制     if (size > MAXSIZE)        return ERROR;         for (i = 0; i < size; i++) {        pList->data[i] = elems[i];     }     pList->length = size;     return OK; }   /*******************************************************************************  Funtion      : insertElem  Description  : 在顺序表中第 pos 个位置插入元素 elem  Input        : SqList *pList,               int pos,               ElemType elem  Output       : SqList *pList  Return Value : STATU(OK/ERROR)  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ STATU insertElem(SqList *pList, int pos, ElemType elem) {     int i = 0;       // 判断要插入的位置是否合理     if (pos < 0 || pos > pList->length)        return ERROR;       // 将data[pos]及后面的元素都向后移动一个位置     for (i = pList->length - 1; i > pos; i--) {        pList->data[i] = pList->data[i-1];     }     pList->data[pos] = elem;     pList->length++; // 顺序表长度加1     return OK; }   /*******************************************************************************  Funtion      : removeElem  Description  : 在顺序表中移除第 pos 个元素,并由 pElem 返回其值  Input        : SqList *pList,               int pos,               ElemType *pElem  Output       : SqList *pList,               ElemType *pElem  Return Value : STATU(OK/ERROR)  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ STATU removeElem(SqList *pList, int pos, ElemType *pElem) {     int i = 0;       // 判断要删除的位置是否合理     if (pos < 0 || pos > pList->length)        return ERROR;       *pElem = pList->data[pos];     // 将data[pos]后面的元素都向前移动一个位置     for (i = pos; i < pList->length; i++) {        pList->data[i] = pList->data[i+1];     }     pList->length--; // 顺序表长度减1       return OK; }   /*******************************************************************************  Funtion      : getElem  Description  : 获取顺序表上位置为 pos 的元素,并由 pElem 返回其值  Input        : SqList list,               int pos,               ElemType *pElem  Output       : ElemType *pElem  Return Value : STATU(OK/ERROR)  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ STATU getElem(SqList list, int pos, ElemType *pElem) {     // 判断位置是否合理     if (pos < 0 || pos > list.length - 1)        return ERROR;       *pElem = list.data[pos];     return OK; }   /*******************************************************************************  Funtion      : locateElem  Description  : 获取元素 elem 在顺序表上第一次出现的位置,如果不存在返回 -1  Input        : SqList list, ElemType elem  Output       : N/A  Return Value : int  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ int locateElem(SqList list, ElemType elem) {     int pos = 0;     for (pos = 0; pos < list.length; pos++) {        if (elem == list.data[pos])            return pos;     }     return -1; }   /*******************************************************************************  Funtion      : printList  Description  : 打印整个顺序表  Input        : SqList list  Output       : N/A  Return Value : N/A  Author       : VictorZhang  Date         : 2015-04-10 *******************************************************************************/ void printList(SqList list) {     int i = 0;     if (0 == list.length) {         printf("SqList is empty\n");         return;     }       printf("SqList:");     for (i = 0; i < list.length; i++) {        printf(" %d", list.data[i]);     }     printf("\n"); }

测试例部分 

顺序表测试例代码

/***********************************************************************************************************************
第三部分,测试例
***********************************************************************************************************************/
void testCase0() {
    printf("================== testCase0 ==================\n");
    
    ElemType A[MAXSIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    SqList list = {0};

    // 初始化链表
    initList(&list);
    printf("Init DList\n");
    printList(list);
    
    // 根据一个数组来创建顺序表
    int size = sizeof(A)/sizeof(ElemType);
    createList(&list, A, size);
    printf("Create List:\n");
    printList(list);

    // 再次初始化链表
    initList(&list);
    printf("Init DList\n");
    printList(list);
}

void testCase1() {
    printf("================== testCase1 ==================\n");
    STATU statu;
    ElemType A[5] = {0, 1, 2, 3, 4};
    SqList list = {0};

    // 初始化链表
    initList(&list);
    printf("Init DList\n");
    printList(list);
    
    // 根据一个数组来创建顺序表
    int size = sizeof(A)/sizeof(ElemType);
    createList(&list, A, size);
    printf("Create List:\n");
    printList(list);

    // 在尾部位置尝试插入元素
    statu = insertElem(&list, 5, 5);
    printf("Insert element:\n");
    if (OK != statu) {
        printf("Insert failed!\n");
    } else {
        printList(list);
    }

    // 在头部位置尝试插入元素
    statu = insertElem(&list, 0, -1);
    printf("Insert element:\n");
    if (OK != statu) {
        printf("Insert failed!\n");
    } else {
        printList(list);
    }

    // 在中间位置尝试插入元素
    statu = insertElem(&list, 3, 11);
    printf("Insert element:\n");
    if (OK != statu) {
        printf("Insert failed!\n");
    } else {
        printList(list);
    }

    // 尝试在不合理的位置上插入元素
    statu = insertElem(&list, 99, 15);
    if (OK != statu) {
        printf("Insert failed!\n");
    } else {
        printList(list);
    }
}

void testCase2() {
    printf("================== testCase2 ==================\n");
    STATU statu;
    ElemType elem;
    ElemType A[5] = {0, 1, 2, 3, 4};
    SqList list = {0};

    // 初始化链表
    initList(&list);
    printf("Init DList\n");
    printList(list);
    
    // 根据一个数组来创建顺序表
    int size = sizeof(A)/sizeof(ElemType);
    createList(&list, A, size);
    printf("Create List:\n");
    printList(list);

    // 尝试移除尾部位置的元素
    statu = removeElem(&list, 4, &elem);
    printf("Remove element pos(%d)\n", 4);
    if (OK != statu) {
        printf("Remove failed!\n");
    } else {
        printList(list);
    }

    // 尝试移除头部位置的元素
    statu = removeElem(&list, 0, &elem);
    printf("Remove element pos(%d)\n", 0);
    if (OK != statu) {
        printf("Remove failed!\n");
    } else {
        printList(list);
    }

    // 尝试移除中间位置的元素
    statu = removeElem(&list, 1, &elem);
    printf("Remove element pos(%d)\n", 1);
    if (OK != statu) {
        printf("Remove failed!\n");
    } else {
        printList(list);
    }

    // 尝试移除不合理位置的元素
    statu = removeElem(&list, 11, &elem);
    printf("Remove element pos(%d)\n", 11);
    if (OK != statu) {
        printf("Remove failed!\n");
    } else {
        printList(list);
    }
}

void testCase3() {
    printf("================== testCase3 ==================\n");
    STATU statu;
    ElemType elem;
    ElemType A[5] = {0, 1, 2, 3, 4};
    SqList list = {0};

    // 初始化链表
    initList(&list);
    printf("Init DList\n");
    printList(list);
    
    // 根据一个数组来创建顺序表
    int size = sizeof(A)/sizeof(ElemType);
    createList(&list, A, size);
    printf("Create List:\n");
    printList(list);

    // 获取指定位置上的元素
    int pos = 3;
    statu = getElem(list, pos, &elem);
    if (OK != statu) {
        printf("Get element failed!\n");
    } else {
        printf("The elem in pos(%d) is %d\n", pos, elem);
    }

    // 查找元素在双链表中第一次出现的位置
    elem = 4;
    pos = locateElem(list, elem);
    printf("%d is in pos(%d) of SqList\n", elem, pos);
    elem = 9;
    pos = locateElem(list, elem);
    printf("%d is in pos(%d) of SqList\n", elem, pos);
}

int _tmain(int argc, _TCHAR* argv[])
{
    testCase0();
    testCase1();
    testCase2();
    testCase3();
    return 0;
}

参考资料 《数据结构》(C语言版) ,严蔚敏、吴伟民

《数据结构习题与解析》(B级第3版),李春葆、喻丹丹

相关阅读

欢迎阅读 程序员的内功——数据结构和算法 系列

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

8-玩转数据结构-堆

前面我们介绍了二分搜索树,以及通过二分搜索树实现的集合和映射这两个更加高层次的数据结构。

1201
来自专栏偏前端工程师的驿站

PLT:说说Evaluation strategy

Brief                                 在学习方法/函数时,我们总会接触到 按值传值 和 引用传值 两个概念。像C#是按值传...

1916
来自专栏一名合格java开发的自我修养

storm 1.0版本滑动窗口的实现及原理

滑动窗口在监控和统计应用的场景比较广泛,比如每隔一段时间(10s)统计最近30s的请求量或者异常次数,根据请求或者异常次数采取相应措施。在storm1.0版本之...

743
来自专栏生信宝典

network3D: 交互式桑基图

桑基图(Sankey diagram),即桑基能量分流图,也叫桑基能量平衡图。它是一种特定类型的流程图,图中延伸的分支的宽度对应数据流量的大小,通常应用于能源、...

42613
来自专栏和蔼的张星的图像处理专栏

数据结构栈队列链表树二叉查找树

这学期刚回到所里的时候把c++数据结构看了一遍,基本的数据结构照着视频也敲了一遍,不过那个时候自己对c++的了解只限于一些基本的语法,c++primer也还没有...

984
来自专栏java工会

编程题1-6答案

1574
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day01-代码题

Java基础day01-代码题巩固 ? ? 第一题:分析以下需求,并用代码实现 1.定义一个HelloWold类 2.在类中定义主方法 3.在主方法中使用输出语...

3175
来自专栏技术沉淀

Numpy 求100以内质数和

1145
来自专栏AI星球

如何实现大数据集查询?Bloom Filter或许是你想要的

虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大,如果有500万条记录...

1455
来自专栏静默虚空的博客

[算法题] 字节流解析

字节流解析 题目标题: 根据数值占用BIT数,按顺序从输入字节流中解析出对应数值,解析顺序按输入数组astElement索引升序。 详细描述: 接口说明...

2265

扫码关注云+社区