顺序表的算法

顺序表


要点

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

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

#define MAXSIZE 10

typedef int ElemType;

typedef struct { // 顺序表的结构类型

    ElemType data[MAXSIZE];

    int length;

} SqList;

 

基本算法


插入数据元素

在顺序表的第 pos(0poslength) 个位置上插入新的元素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(0poslength-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");

}

测试例部分 

顺序表的算法 顺序表测试例代码

 本文转自静默虚空博客园博客,原文链接:http://www.cnblogs.com/jingmoxukong/p/4415323.html,如需转载请自行联系原作者

上一篇:Java 第8章 循环结构进阶


下一篇:windows 10 下的linux子系统用法 -- tmux分屏工具用法