【数据结构】之顺序表（C语⾔描述）
  顺序表是线性表的⼀种，它将元素存储在⼀段连续的内存空间中，表中的任意元素都可以通过下标快速的获取到，因此，顺序表适合查询操作频繁的场景，⽽不适合增删操作频繁的场景。
  下⾯是使⽤ C语⾔编写的顺序表的代码：
  顺序表的头⽂件SeqList.h中的代码如下：
/**
* 顺序表（线性存储）
* 注意：添加数据时，先判断容量是否存满，存满才扩容，⽽不是添加元素后判断扩容！
*/
#include <stdio.h>
#include <stdlib.h>
// 定义常量
#define SEQLIST_INITIAL_SIZE 5    // 顺序表的初始长度
#define SEQLIST_INCREMENT_SIZE 5  // 顺序表的递增长度
// 类型定义
typedef int seqElemType;
// 定义顺序表（线性存储）的数据结构
typedef struct MySeqList {
seqElemType* data; // 存储所有数据的数组
int currentLength; // 当前长度
int totalLength;  // 总长度
} MySeqList;
// 0.⽐较两个元素数据是否相等
int isEqual(seqElemType a, seqElemType b) {
return a == b;
}
// 1.初始化顺序表L，即进⾏动态存储空间分配并置L为⼀个空表
void initSeqList(MySeqList* L, int ms) {
if(ms <= 0) {
printf("顺序表的初始长度⾮法！\n");
exit(1);
}
L->data = (seqElemType*)malloc(ms * sizeof(seqElemType));
if(L->data != NULL) {
L->currentLength = 0;
L->totalLength = ms;
printf("顺序表初始化成功！当前总长度：%d\n", L->totalLength);
} else {
printf("顺序表初始化失败！\n");
exit(1);
}
}
// 2.清除顺序表L中的所有元素，释放动态存储空间，使之成为⼀个空表
void clearList(MySeqList* L) {
if(L->data == NULL || L->totalLength < 1) {
printf("顺序表不存在，清空失败！\n");
exit(1);
}
free(L->data);
L->data = 0;
L->currentLength = L->totalLength = 0;
printf("顺序表清空成功！\n");
}
// 3.返回顺序表L的长度，若L为空则返回0
int getListSize(MySeqList* L) {
if(L->data == NULL) {
return0;
}
return L->currentLength;
}
// 4.判断顺序表L是否为空，若为空则返回1，否则返回0
int isListEmpty(MySeqList* L) {
if(L->data == NULL) {
return1;
}
return L->currentLength == 0;
}
/
/ 5.返回顺序表L中第pos个元素的值，若pos超出范围，则停⽌程序运⾏
seqElemType getElemAtPos(MySeqList* L, int pos) {
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
if(pos < 0 || pos >= L->currentLength) {
printf("下标⽆效！\n");
exit(1);
}
return L->data[pos - 1];
}
// 6.顺序扫描（即遍历）输出顺序表L中的每个元素
void traverseList(MySeqList* L) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
printf("顺序遍历顺序表：");
for(i = 0; i < L->currentLength; i++) {
printf("%-4d", L->data[i]);
}
printf("\n");
}
// 7.从顺序表L中查值与x相等的元素（第⼀个），若查成功则返回其位置（下标），否则返回-1
int getPositionOfElem(MySeqList* L, seqElemType x) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
for(i = 0; i < L->currentLength; i++) {
if(isEqual(L->data[i], x)) {
break;
}
}
if(i == L->currentLength) {
i = -1;
}
return i;
}
// 8.把顺序表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0
int setElemValue(MySeqList* L, int pos, seqElemType x) {
if(L->data == NULL) {
printf("顺序表不存在！\n");
return0;
}
if(pos < 0 || pos >= L->currentLength) {
printf("下标⽆效！\n");
return0;
}
L->data[pos] = x;
return1;
}
/
/ 9.0.判断顺序表是否需要扩容，如果需要则扩容
void expandWhenShould(MySeqList* L) {
if(L->currentLength == L->totalLength) {
L->data = (seqElemType*)realloc(L->data, (L->totalLength + SEQLIST_INCREMENT_SIZE) * sizeof(seqElemType));        L->totalLength += SEQLIST_INCREMENT_SIZE;
if(L->data == NULL || L->totalLength <= 0) {
printf("顺序表重分配空间失败，插⼊元素失败！\n");
exit(1);
}
printf("扩容成功，顺序表容量扩⼤到%d！\n", L->totalLength);
}
}
// 9.向顺序表L的表头插⼊元素x
void insertElemAtStart(MySeqList* L, seqElemType x) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
if(L->totalLength > 0) {
expandWhenShould(L);
L->currentLength++;
for(i = L->currentLength; i > 0; i--) {
L->data[i] = L->data[i - 1];
}
L->data[0] = x;
printf("成功将元素%d插⼊到表头！\n", x);
} else {
printf("顺序表长度不合法，插⼊元素失败！\n");
exit(1);
}
}
// 10.向顺序表L的表尾插⼊元素x
void insertElemAtEnd(MySeqList* L, seqElemType x) {
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
if(L->totalLength > 0) {
expandWhenShould(L);
L->data[L->currentLength++] = x;
printf("成功将元素%d插⼊到表尾！\n", x);
} else {
printf("顺序表长度不合法，插⼊元素失败！\n");
exit(1);
}
}
// 11.向顺序表L中第pos个元素位置插⼊元素x，若插⼊成功返回1，否则返回0 int insertElemAtPos(MySeqList* L, int pos, seqElemType x) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
return0;
}
if(pos < 0 || pos > L->currentLength) {
printf("下标不合法，插⼊元素失败！\n");
return0;
}
if(L->totalLength > 0) {
expandWhenShould(L);
L->currentLength++;
for(i = L->currentLength; i > pos; i--) {
L->data[i] = L->data[i - 1];
}
L->data[pos] = x;
printf("成功添加%d到顺序表第%d个位置！\n", x, pos);
} else {
printf("顺序表长度不合法，插⼊元素失败！\n");
return0;
}
return1;
}
// 12.向有序（递增）顺序表L中插⼊元素x，使得插⼊后仍然有序
void insertOrderly(MySeqList* L, seqElemType x) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
if(L->totalLength > 0) {
expandWhenShould(L);
L->currentLength++;
for(i = L->currentLength; i > 0; i--) {
if(x < L->data[i - 1]) {
L->data[i] = L->data[i - 1];
} else {
L->data[i] = x;
printf("成功将%d插⼊到顺序表的%d位置！\n", x, i);
break;
}
}
if(i == 0) {
L->data[i] = x;
printf("成功将%d插⼊到顺序表的%d位置！\n", x, i);
}
} else {
printf("顺序表长度不合法，插⼊元素失败！\n");
exit(1);
}
}
// 13.从顺序表L中删除表头元素并返回它，若删除失败则停⽌程序运⾏seqElemType deleteFirstElem(MySeqList* L) {
int i = 0;
int result = -1;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
result = L->data[0];
for(i = 1; i < L->currentLength; i++) {
L->data[i - 1] = L->data[i];
}
L->currentLength--;
printf("删除表头元素成功，返回表头元素：%d\n", result);
return result;
}
// 14.从顺序表L中删除表尾元素并返回它，若删除失败则停⽌程序运⾏seqElemType deleteLastElem(MySeqList* L) {
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
L->currentLength--;
printf("删除表尾元素成功，返回表尾元素：%d\n", L->data[L->currentLength]); return L->data[L->currentLength];
}
// 15.从顺序表L中删除第pos个元素并返回它，若删除失败则停⽌程序运⾏seqElemType deleteElemAtPos(MySeqList* L, int pos) {
int i = 0;
int result = -1;
if(L->data == NULL) {
printf("顺序表不存在！\n");
exit(1);
}
if(pos < 0 || pos >= L->currentLength) {
printf("下标⽆效，删除元素失败！");
exit(1);
}
result = L->data[pos];
for(i = pos + 1; i < L->currentLength; i++) {
L->data[i - 1] = L->data[i];
}
L->currentLength--;
printf("成功将%d从顺序表的%d位置删除！\n", result, pos);
return result;
}
// 16.从顺序表L中删除值为x的第⼀个元素，若删除成功返回1否则返回0
int deleteElemByValue(MySeqList* L, seqElemType x) {
int i = 0;
if(L->data == NULL) {
printf("顺序表不存在！\n");
return0;
}
for(i = 0; i < L->currentLength; i++) {
if(isEqual(L->data[i], x)) {
deleteElemAtPos(L, i);
printf("成功删除%d在顺序表中出现的第⼀个数据（%d位置）！\n", x, i);
return1;
}
}
printf("%d没有在顺序表中出现过，删除失败！\n");
return0;
}
// 测试⽅法
void testMySeqList() {
// 声明顺序表变量
MySeqList list;
// 初始化顺序表
initSeqList(&list, SEQLIST_INITIAL_SIZE);
// 清空顺序表
/
/ clearList(&list);
// 获取顺序表的当前长度
printf("顺序表当前长度：%d\n", getListSize(&list));
// 判断顺序表是否为空
printf("顺序表是否为空？%s\n", isListEmpty(&list) ? "是" : "否");
// 向表头插⼊数据
insertElemAtStart(&list, 6);
insertElemAtStart(&list, 5);
insertElemAtStart(&list, 4);
insertElemAtStart(&list, 3);
insertElemAtStart(&list, 2);
insertElemAtStart(&list, 1);
// 顺序遍历顺序表
traverseList(&list);
// 向表尾插⼊数据
insertElemAtEnd(&list, 6);
insertElemAtEnd(&list, 7);
insertElemAtEnd(&list, 7);
insertElemAtEnd(&list, 7);
insertElemAtEnd(&list, 8);
// 顺序遍历顺序表
traverseList(&list);
/
/ 向顺序表指定位置插⼊数据
insertElemAtPos(&list, 9, 7);
insertElemAtPos(&list, 9, 7);
insertElemAtPos(&list, 9, 7);
insertElemAtPos(&list, 9, 7);
insertElemAtPos(&list, 9, 7);
// 顺序遍历顺序表
traverseList(&list);
// 有序表插⼊元素
insertOrderly(&list, 7);
insertOrderly(&list, 0);
/
/ 顺序遍历顺序表
traverseList(&list);
// 删除表头元素
deleteFirstElem(&list);
deleteFirstElem(&list);
deleteFirstElem(&list);
deleteFirstElem(&list);
// 顺序遍历顺序表
traverseList(&list);
// 删除表尾元素
deleteLastElem(&list);
deleteLastElem(&list);
deleteLastElem(&list);
deleteLastElem(&list);
// 顺序遍历顺序表
traverseList(&list);
// 删除指定位置的元素
deleteElemAtPos(&list, 3);
deleteElemAtPos(&list, 3);
deleteElemAtPos(&list, 3);
// 顺序遍历顺序表
traverseList(&list);
/
/ 删除某元素的⾸次出现
deleteElemByValue(&list, 7);
deleteElemByValue(&list, 10);
// 顺序遍历顺序表c语言listinsert函数
traverseList(&list);
}
  主⽂件main.c中的代码：
#include <SeqList.h>
//主函数
int main() {
testMySeqList(); // 顺序表（顺序存储）顺序结构的测试return0;
}
  运⾏结果如下：
顺序表初始化成功！当前总长度：5
顺序表当前长度：0
顺序表是否为空？是
成功将元素6插⼊到表头！
成功将元素5插⼊到表头！
成功将元素4插⼊到表头！
成功将元素3插⼊到表头！
成功将元素2插⼊到表头！
扩容成功，顺序表容量扩⼤到10！
成功将元素1插⼊到表头！
顺序遍历顺序表：1  2  3  4  5  6
成功将元素6插⼊到表尾！
成功将元素7插⼊到表尾！
成功将元素7插⼊到表尾！
成功将元素7插⼊到表尾！
扩容成功，顺序表容量扩⼤到15！
成功将元素8插⼊到表尾！
顺序遍历顺序表：1  2  3  4  5  6  6  7  7  7  8
成功添加7到顺序表第9个位置！
成功添加7到顺序表第9个位置！
成功添加7到顺序表第9个位置！
成功添加7到顺序表第9个位置！
扩容成功，顺序表容量扩⼤到20！
成功添加7到顺序表第9个位置！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。