0、前要：线性表的概念

（1）线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有 ：顺序表、链表、栈、队列、字符串等

（2）线性表在逻辑上是线性结构，也就说是连续的一条直线。

（3）线性表在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

简单来说就是其数据存储后看起来就是一条线

1、顺序表（sequence list）的概念

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
• 顺序表一般可以分为：
  • 静态顺序表：使用定长数组存储
  • 动态顺序表：使用动态开辟的数组存储

2、顺序表的实现

一般情况下我们使用动态顺序表，而不使用静态顺序表

（1）顺序表结构体

typedef int SLDataType;
typedef struct SeqList
{SLDataType* array;//存储数据size_t size;//当前已存储的数量size_t capicity;//当前最大容量
}SeqList;

（2）顺序表初始化

void SeqListInit(SeqList* psl)
{assert(psl);//避免空指针SLDataType* cache = (SLDataType*)malloc(sizeof(SLDataType) * INITIAL_NUMBER);//初始化就给INITIAL_NUMBER个数据空间if (!cache){perror("malloc fail");return;}psl->array = cache;//申请成功就将这块可用空间给顺序表psl->size = 0;psl->capicity = INITIAL_NUMBER;
}

（3）顺序表销毁

void SeqListDestory(SeqList* psl)
{assert(psl);free(psl->array);psl->array = NULL;psl->capicity = psl->size = 0;
}

（4）顺序表打印

void SeqListPrint(SeqList* psl)
{assert(psl);if (psl->size == 0){printf("空顺序表\\n");return;}for (int i = 0; i < psl->size; i++){printf("%d ", psl->array[i]);}printf("\\n");
}

（5）检查空间，如果满了，进行增容

void CheckCapacity(SeqList* psl)
{assert(psl);if (psl->capicity == psl->size){SLDataType* cache = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capicity * 2);if (!cache){perror("malloc fail");return;}psl->array = cache;psl->capicity *= 2;//容量倍增}
}

（6）顺序表尾插

void SeqListPushBack(SeqList* psl, SLDataType x)
{assert(psl);CheckCapacity(psl);//检查是否已满，满则增容psl->array[psl->size++] = x;//psl->size++;
}

（7）顺序表尾删

void SeqListPopBack(SeqList* psl)
{//直接操控size就可以assert(psl);assert(psl->size > 0);//直接使用较为暴力的检查，这样就会直接报错//if (psl->size > 0)//{psl->size--;//}//else//{//    printf("删除失败\\n");//比较柔和的检查//}
}

（8）顺序表头插

void SeqListPushFront(SeqList* psl, SLDataType x)
{assert(psl);CheckCapacity(psl);//if (psl->size > 0)//这个判断没有必要//{for (int i = psl->size - 1; i >= 0; i--){psl->array[i + 1] = psl->array[i];}//}psl->array[0] = x;psl->size++;//实际上还有另外一种简单的方式就是使用mommove库函数
}

（9）顺序表头删

void SeqListPopFront(SeqList* psl)
{assert(psl);assert(psl->size > 0);//暴力检查//if (psl->size > 0)//{for (int i = 0; i < psl->size - 1; i++){psl->array[i] = psl->array[i + 1];}psl->size--;//}//else//{//    printf("删除失败\\n");//}
}

（10）顺序表查找

int SeqListFind(SeqList* psl, SLDataType x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->array[i] == x){return i;//返回x的下标}}return -1;//下标不可能是负数
}

（11）顺序表在pos位置的值前插入x

void SeqListInsert(SeqList* psl, int pos, SLDataType x)
{assert(psl);//避免解引用空指针CheckCapacity(psl);//避免容量不够//if (pos == 0 && psl->size == 0)//这一串代码是多余的，后面的代码足以完成头插和尾插//{//    psl->array[0] = x;//    psl->size++;//    return;//}assert(pos <= psl->size && pos >= 0);//检查pos的合法性，等号代表头插和尾插for (int i = psl->size - 1; i >= pos; i--)//如果是头插和尾插就不会进入循环{psl->array[i + 1] = psl->array[i];}psl->array[pos] = x;psl->size++;
}

（12）顺序表在pos位置的值删除

void SeqListErase(SeqList* psl, int pos)
{assert(psl);assert(pos < psl->size && pos >= 0);//检查pos的合法性，注意有了这个语句就不需要加上assert(psl->size > 0);这条语句，因为被这条语句间接检查了for (int i = pos; i < psl->size - 1; i++){psl->array[i] = psl->array[i + 1];}psl->size--;
}

（13）顺序表在pos位置的值被修改

void SeqListAmend(SeqList* psl, int pos, SLDataType x)
{assert(psl);assert(pos < psl->size && pos >= 0);//检查pos的合法性psl->array[pos] = x;
}

（14）顺序表的测试用例

void test_1()
{SeqList a;SeqListInit(&a);//初始化CheckCapacity(&a);//检查空间SeqListPushBack(&a, 1);//尾插SeqListPushBack(&a, 2);//尾插SeqListPushBack(&a, 3);//尾插SeqListPushBack(&a, 4);//尾插SeqListPushBack(&a, 5);//尾插SeqListPrint(&a);SeqListPopBack(&a);//尾删SeqListPopBack(&a);//尾删SeqListPopBack(&a);//尾删SeqListPopBack(&a);//尾删SeqListPrint(&a);SeqListPopBack(&a);//尾删SeqListPrint(&a);//SeqListPopBack(&a);//尾删//SeqListPopBack(&a);//尾删SeqListPushBack(&a, 1);//尾插SeqListPushFront(&a, -1);//头插SeqListPushFront(&a, -2);//头插SeqListPushFront(&a, -3);//头插SeqListPushFront(&a, -4);//头插SeqListPrint(&a);SeqListPopFront(&a);//头删SeqListPopFront(&a);//头删SeqListPopFront(&a);//头删SeqListPopFront(&a);//头删SeqListPrint(&a);SeqListPopFront(&a);//头删//SeqListPopFront(&a);//头删//SeqListPopFront(&a);//头删SeqListPrint(&a);SeqListInsert(&a, 0, 1000);//任意插入SeqListPrint(&a);SeqListInsert(&a, 0, 1000);//任意插入SeqListInsert(&a, 1, -1000);//任意插入SeqListInsert(&a, 2, -800);//任意插入SeqListInsert(&a, 0, 8000);//任意插入SeqListPrint(&a);SeqListErase(&a, 0);//任意删除SeqListErase(&a, 0);//任意删除SeqListPrint(&a);SeqListErase(&a, 2);//任意删除SeqListPrint(&a);SeqListErase(&a, 0);//任意删除SeqListPrint(&a);SeqListErase(&a, 0);//任意删除SeqListPrint(&a);SeqListInsert(&a, 0, 8000);//任意插入SeqListPrint(&a);SeqListInsert(&a, 0, 100);//任意插入SeqListPrint(&a);SeqListInsert(&a, 1, -100);//任意插入SeqListPrint(&a);SeqListAmend(&a, 1, 2);//修改SeqListPrint(&a);SeqListAmend(&a, 0, 1);//修改SeqListPrint(&a);SeqListAmend(&a, 2, 3);//修改SeqListPrint(&a);printf("%d\\n", SeqListFind(&a, 3));//查找printf("%d\\n", SeqListFind(&a, 4));//查找SeqListDestory(&a);//销毁
}
void test_2()
{SeqList sl;//创建顺序表变量SeqListInit(&sl);//初始化顺序表SeqListPushBack(&sl, 1);//尾插SeqListPushBack(&sl, 2);//尾插SeqListPushBack(&sl, 3);//尾插SeqListPushFront(&sl, 0);//头插SeqListPrint(&sl);//打印SeqListPopFront(&sl);//头删SeqListPopBack(&sl);//尾删SeqListPrint(&sl);//打印SeqListDestory(&sl);//销毁顺序表
}
void test_3()
{SeqList sl;//创建顺序表变量SeqListInit(&sl);//初始化顺序表SeqListPushBack(&sl, 1);//尾插SeqListPushBack(&sl, 2);//尾插SeqListPushBack(&sl, 3);//尾插SeqListInsert(&sl, 0, 0);//任意插入SeqListInsert(&sl, 2, 10);//任意插入SeqListErase(&sl, 4);//任意删除SeqListAmend(&sl, 1, 20);//任意修改SeqListPrint(&sl);//打印SeqListDestory(&sl);//销毁
}
void test_4()
{SeqList sl;SeqListInit(&sl);//初始化for (int i = 0; i < 10; i++) {SeqListPushBack(&sl, i);//循环尾插}SeqListPrint(&sl);//打印SeqListPushBack(&sl, 10);//尾插SeqListPrint(&sl);//打印SeqListDestory(&sl);//销毁
}
void test_5()
{SeqList sl;SeqListInit(&sl);//初始化for (int i = 0; i < 10; i++) {SeqListPushFront(&sl, i);//循环尾插}SeqListPrint(&sl);//打印SeqListPushFront(&sl, 10);//头插SeqListPrint(&sl);//打印SeqListDestory(&sl);//销毁
}
void test_6()
{SeqList sl;SeqListInit(&sl);//初始化SeqListPushBack(&sl, 1);//尾插SeqListPushBack(&sl, 2);//尾插SeqListPushBack(&sl, 3);//尾插printf("%d\\n", SeqListFind(&sl, 2));//查找成功printf("%d\\n", SeqListFind(&sl, 4));//查找失败SeqListDestory(&sl);
}