一、顺序表

概念：

是一种线性结构（1对1的关系），每一个数据元素都有一个前驱（除了第一个元素）和一个后继（除了最后一个元素）
在逻辑上数据元素都是连续的，在物理存储上数据也是连续的

顺序表提供两个内容：

1、对于数据元素的存储 
2、对于顺序表的操作

顺序表在存储数据元素时，必须连续存储，而且必须从最左边开始存储

二、定长顺序表

只能存储固定个数的数据元素

1、定长顺序表的结构声明

//以int类型为例，后期可以修改成任意类型
typedef int ElemType;
#define SQSIZE 100
typedef struct SqList
{ElemType data[SQSIZE]; // 存储数据元素的空间，固定大小的int length; // 记录当前已经存储的数据元素的个数
}FixedSqList;

2、定长顺序表的操作声明

//初始化
void InitFixedSqList(FixedSqList *sqlist);
//插入元素: 头插（将新元素插入第一个位置） 尾插(将新元素插入到当前的最后一个位置)
// 按位置插入（插入到指定位置）
bool InsertOfHead(FixedSqList *sqlist, ElemType val);//头插
bool InsertOfTail(FixedSqList *sqlist, ElemType val);//尾插
bool InsertOfPos(FixedSqList *sqlist, ElemType val, int pos);//按位置插bool DeleteOfHead(FixedSqList *sqlist);//头删
bool DeleteOfTail(FixedSqList *sqlist);//尾删
bool DeleteOfPos(FixedSqList *sqlist, int pos);//按位删bool DeleteOfValue(FixedSqList *sqlist, ElemType val);
bool DeleteOfValue2(FixedSqList *sqlist, ElemType val);void ClearSqList(FixedSqList *sqlist);
void DestroySqList(FixedSqList *sqlist);ElemType FindValue(FixedSqList *sqlist, ElemType val, Compare cp)

3、定长顺序表的方法实现

初始化

C代码中变量的分类： 全局变量 局部变量 堆区变量 静态变量(全局、局部) 字符常量区
C程序（.exe ELF格式a.out）中： .rodata .data (初始化不为0的变量) .bss（未初始化或初始化为0的变量） .heap（堆区）
.stack（栈区 – 局部变量）

1、追求代码的健壮性
2、精益求精 – 代码的效率

void InitFixedSqList(FixedSqList *sqlist)
{if(sqlist == NULL) exit(0);sqlist->length = 0;
}

插入元素

bool InsertOfHead(FixedSqList *sqlist, ElemType val)
{if(sqlist == NULL) exit(0);return InsertOfPos(sqlist, val, 0);
}
bool InsertOfTail(FixedSqList *sqlist, ElemType val)
{if(sqlist == NULL) exit(0);return InsertOfPos(sqlist, val, sqlist->length);
}
bool InsertOfPos(FixedSqList *sqlist, ElemType val, int pos)
{if(sqlist == NULL) exit(0);if(sqlist->length == SQSIZE) return false;if(pos < 0 || pos > sqlist->length) return false;int index = sqlist->length;while(index > pos){sqlist->data[index] = sqlist->data[index - 1];index--;}sqlist->data[pos] = val;sqlist->length++;
}

删除元素

bool DeleteOfHead(FixedSqList *sqlist)
{if (sqlist == NULL) exit(0);return DeleteOfPos(sqlist, 0);}// 内联函数bool DeleteOfTail(FixedSqList *sqlist){if (sqlist == NULL) exit(0);if (sqlist->length == 0) return false;sqlist->length--;return true;}bool DeleteOfPos(FixedSqList *sqlist, int pos){if (sqlist == NULL) exit(0);if (sqlist->length == 0) return false;if (pos < 0 || pos > sqlist->length - 1) return false;for (int i = pos; i < sqlist->length - 1; ++i){sqlist->data[i] = sqlist->data[i + 1];}sqlist->length--;return false;}// 时间复杂度 O(n^2)bool DeleteOfValue(FixedSqList *sqlist, ElemType val){if (sqlist == NULL) exit(0);if (sqlist->length == 0) return false;for (int i = 0; i < sqlist->length; ){if (sqlist->data[i] == val){DeleteOfPos(sqlist, i);}else{i++;}}return true;}// 时间复杂度 O(n)bool DeleteOfValue2(FixedSqList *sqlist, ElemType val){if (sqlist == NULL) exit(0);if (sqlist->length == 0) return false;int i = 0, int j = 0;for (; j < sqlist->length;){if (sqlist->data[j] == val) j++;else sqlist->data[i++] = sqlist->data[j++];}sqlist->length = i;return true;}

查找元素

ElemType FindValue(FixedSqList *sqlist, ElemType val)//返回下标
{if (sqlist == NULL) exit(0);for (int i = 0; i < sqlist->length; ++i){if (val == sqlist->data[i])){return sqlist->i;}}return -1;
}typedef bool(*Compare)(ElemType, ElemType);ElemType FindValue2(FixedSqList *sqlist, ElemType val, Compare cp)
{if (sqlist == NULL) exit(0);for (int i = 0; i < sqlist->length; ++i){if (cp(val, sqlist->data[i])){return sqlist->data[i];}}return -1;
}

清空销毁

void ClearSqList(FixedSqList *sqlist)
{if (sqlist == NULL) exit(0);sqlist->length = 0;
}
void DestroySqList(FixedSqList *sqlist)
{if (sqlist == NULL) exit(0);sqlist->length = 0;
}

三、不定长顺序表 – 动态数组 Go 切片 Python 列表

存储的数据元素的空间大小是不固定，可以随着用户的操作动态扩充存储空间

1、结构声明

typedef int ElemType;typedef struct SqList
{ElemType *data; // 指向申请的堆区空间首地址int length; // 记录当前存储的数据元素个数int size; // 存储当前空间的大小
}SqList;

2、操作方法声明

//初始化
void InitSqList(SqList *sqlist);
//插入元素: 头插（将新元素插入第一个位置） 尾插(将新元素插入到当前的最后一个位置)
// 按位置插入（插入到指定位置）
bool InsertOfHead(SqList *sqlist, ElemType val);
bool InsertOfTail(SqList *sqlist, ElemType val);
bool InsertOfPos(SqList *sqlist, ElemType val, int pos);bool DeleteOfHead(SqList *sqlist);
bool DeleteOfTail(SqList *sqlist);
bool DeleteOfPos(SqList *sqlist, int pos);bool DeleteOfValue(SqList *sqlist, ElemType val);
bool DeleteOfValue2(SqList *sqlist, ElemType val);void ClearSqList(SqList *sqlist);
void DestroySqList(SqList *sqlist);ElemType FindValue(SqList *sqlist, ElemType val, Compare cp);

3、操作实现

扩容方法

//static 加在函数上，此函数只能在本文件中使用，其他问题没办法访问
static bool AppendSpace(SqList *sqlist)
{int newsize = 0;if (sqlist->size < 1000) newsize = sqlist->size * 2;else newsize = sqlist->size + INITSIZE;ElemType *s = (ElemType *)malloc(sizeof(ElemType) * newsize);if (s == NULL) return false;// 数据复制： 将原来sqlist->data中的数据全部复制到s中for (int i = 0; i < sqlist->length; ++i){s[i] = sqlist->data[i];}free(sqlist->data);sqlist->data = s;sqlist->size = newsize;return true;
}

初始化

#define INITSIZE 1
void InitSqList(SqList *sqlist)
{if (sqlist == NULL) exit(0);//这里使用宏定义INISIZE，一次性初始化多个sqlist->data = (ElemType *)malloc(sizeof(ElemType) * INITSIZE);if (sqlist->data == NULL) exit(0);sqlist->length = 0;sqlist->size = INITSIZE;
}

插入元素

bool InsertOfHead(SqList *sqlist, ElemType val)
{if (sqlist == NULL) exit(0);return InsertOfPos(sqlist, val, 0);
}
bool InsertOfTail(SqList *sqlist, ElemType val)
{if (sqlist == NULL) exit(0);return InsertOfPos(sqlist, val, sqlist->length);
}
bool InsertOfPos(SqList *sqlist, ElemType val, int pos)
{if (sqlist == NULL) exit(0);if (pos < 0 || pos > sqlist->length) return false;if (sqlist->length == sqlist->size){// 扩容操作if (!AppendSpace(sqlist)) return false;}for (int i = sqlist->length; i > pos; --i){sqlist->data[i] = sqlist->data[i - 1];}sqlist->data[pos] = val;sqlist->length++;return true;
}

清空、销毁

void ClearSqList(SqList *sqlist)
{if (sqlist == NULL) exit(0);sqlist->length = 0;
}
void DestroySqList(SqList *sqlist)
{if (sqlist == NULL) exit(0);free(sqlist->data);sqlist->data = NULL;sqlist->length = sqlist->size = 0;
}