顺序表
要点
顺序表是在计算机内存中以数组的形式保存的线性表，是指使用一组地址连续的存储单元依次存储数据元素的线性结构。
顺序表的存储结构可表示如下：
| #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"); } |
测试例部分
顺序表测试例代码
本文转自静默虚空博客园博客，原文链接：http://www.cnblogs.com/jingmoxukong/p/4415323.html，如需转载请自行联系原作者
