顺序表

前言

顺序表是在计算机内存中以数组的形式保存的线性表，是指使用一组连续分配存储单元有序的存储数据元素的线性结构。
顺序表还有后面讲的单链表、循环链表、双链表都是链表，根本区别是在内存中存储数据的方式不同，每种方式都有优劣点，这也根据应用场景的不同，决定用什么方式存储数据。

基本算法

在线性表中算法操作中，异常判断很重要，包括链表是否为空，插入位置是否正确等等。
- 插入数据元素
在顺序表中第n个位置插入新的元素e。

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;

}

View Code

同理删除元素也是这样的操作。
插入操作：
1. 如果插入位置不合理，抛出异常
2. 如果超过容量，跑出异常或者动态增加容量。
3. 如果从最后一个元素开始向前遍历到第i元素位置，其后面元素都向后移动一个位置。
4. 将元素插入在位置i处
5. 表长加1.
6. 删除工作和插入很相似。关键是前面的异常判断。

在上面顺序表的插入和删除操作中，最快的就是在表尾插入，为时间复杂度为1，最坏的情况是在表头插入，时间复杂度为n-1，所以插入和删除的时间复杂度为O(n),平均复杂度为：O((n-1)/2))

优点	缺点
无须为表中逻辑关系增加额外的存储空间	插入和删除需要移动大量元素
可以快速存取表中任意位置元素	当线性表长度变化较大时，难以确定存储空间的容量
	造成存储空间的“碎片”，释放内存时

顺序表代码实现

以c语言实现顺序表的基本操作

序号	函数名称	函数说明
1	InitList	创建一个为空的顺序表
2	CreateList	根据数组elems构建一个顺序表
3	InsertElem	在顺序表中第pos位置插入元素elem
4	DeleteElem	在顺序表中第pos位置删除元素elem
5	GetElem	获取在位置为Pos位置元素，并返回pelem
6	GetElemLocation	获取元素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  : 初始化一个空的顺序表

*******************************************************************************/

void initList(SqList *pList) {

    pList->length = 0;

}

/*******************************************************************************

 Funtion      : createList

 Description  : 根据数组 elems 构建一个顺序表

*************************************************/

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

*******************************************************************************/

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 返回其值

*******************************************************************************/

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 返回其值


*******************************************************************************/

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


*******************************************************************************/

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  : 打印整个顺序表



*******************************************************************************/

void printList(SqList list) {

    int i = 0;

    if (0 == list.length) {

        printf("SqList is empty
");

        return;

    }



    printf("SqList:");

    for (i = 0; i < list.length; i++) {

       printf(" %d", list.data[i]);

    }

    printf("
");

}

View Code

综述

顺序的创建的初始化就是相当于对数组的初始化，获取元素和位置，也和数组相同，关键是在删除和插入的时需要元素进行移动。在插入操作时，不能超过最大长度，如果超过需要扩容。
后面讲详细讲解线性表和链表的应用场景