前言
顺序表是在计算机内存中以数组的形式保存的线性表，是指使用一组连续分配存储单元有序的存储数据元素的线性结构。
顺序表还有后面讲的单链表、循环链表、双链表都是链表，根本区别是在内存中存储数据的方式不同，每种方式都有优劣点，这也根据应用场景的不同，决定用什么方式存储数据。基本算法
在线性表中算法操作中，异常判断很重要，包括链表是否为空，插入位置是否正确等等。
- 插入数据元素 在顺序表中第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;}
同理删除元素也是这样的操作。
插入操作： 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#include /***********************************************************************************************************************第一部分，数据结构、宏定义***********************************************************************************************************************/#define MAXSIZE 10typedef 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\n"); return; } printf("SqList:"); for (i = 0; i < list.length; i++) { printf(" %d", list.data[i]); } printf("\n");}
综述
顺序的创建的初始化就是相当于对数组的初始化，获取元素和位置，也和数组相同，关键是在删除和插入的时需要元素进行移动。在插入操作时，不能超过最大长度，如果超过需要扩容。
后面讲详细讲解线性表和链表的应用场景版权声明：本文为博主原创文章，未经博主允许不得转载。