顺序表是在计算机内存中以数组的形式保存的线性表，是指使用一组地址连续的存储单元依次存储数据元素的线性结构。
顺序表的存储结构可表示如下：
#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; } 顺序表测试例代码
参考资料
《数据结构习题与解析》（B级第3版），李春葆、喻丹丹
欢迎阅读 程序员的内功——数据结构和算法 系列
