# 顺序表的基本操作

## 初始化

``````void SeqListInit(SeqList* ps, size_t inite_capicity)
{
assert(ps);
ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
if (NULL == ps->arr)
{
exit(1);
}
ps->capicity = inite_capicity;
ps->size = 0;
}
``````

## 清空

``````void SeqListDestory(SeqList* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
ps->arr = NULL;
ps->capicity = 0;
ps->size = 0;
}
}

``````

## 打印

``````void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("n");
}
``````

## 扩容

``````static void SeqListRealloc(SeqList* ps)
{
SLDataType* temp = ps->arr;
temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
if (temp != NULL)
{
// 若申请则将扩容后的地址赋给ps->size
// 这样做的目的是防止空间申请失败后原有空间的地址无法找回
ps->arr = temp;
}
ps->capicity *= 2;
}
``````

## 尾插法

``````void SeqListPushBack(SeqList* ps, SLDataType data)
{
assert(ps);
//先判断是否已满，如果已满则需要扩容
if (ps->size == ps->capicity)
{
SeqListRealloc( ps);//调用扩容函数
}
ps->arr[ps->size] = data;//将数据放到顺序表的结尾
ps->size++;//有效元素增加一个
}
``````

## 判空

``````static int IsSeqListEmpty(SeqList* ps)
{
assert(ps);
if (0==ps->size)
{
return 1;
}
else
{
return 0;
}
}
``````

## 尾删法

``````void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
ps->size--;
}
}
``````

## 头插法

``````void SeqListPushFront(SeqList* ps, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
}
//***将ps->size强转成int类型，否则计算时会发生类型提升***
for (int i = (int)ps->size - 1; i >= 0; i--)
{
ps->arr[i + 1] = ps->arr[i];//所有元素向后移动一个单位
}
ps->arr[0] = data;//将元素插入顺序表头部
ps->size ++;//元素个数加1
}
``````

## 头删法

``````void SeqListPopFront(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = 0; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素个数减1
}
}
``````

## 查询

``````int SeqListFind(SeqList* ps, SLDataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == data)
{
return i;
}
}
return -1;//未找到返回-1
}
``````

## 任意位置插入

``````void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
}

for (int i = (int)ps->size - 1; i >= pos; i--)
{
ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移动一个单位
}
ps->arr[pos] = data;//将元素插入顺序表头部
ps->size++;//元素个数加1
}
``````

## 任意位置删除

``````void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = (int)pos; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素个数减1
}
}
``````

## 完整代码

• 其中work.h头文件主要完成包含头文件和结构体、各个函数的声明
• main.c源文件是程序的入口，并在这里实现测试用例，具体使用时，结构体变量在main.c中定义
• work.c源文件是各个操作的具体函数的实现

work.h

``````#pragma once
#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<assert.h>
#define MAXSIZE 50

typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//起始地址
size_t capicity;//容量
size_t size;//有效数据

}SeqList;

//下面这些都是函数声明
void SeqListInit(SeqList* ps,size_t inite_capicity);//初始化
void SeqListDestory(SeqList* ps);//空间释放
void SeqListPushBack(SeqList* ps, SLDataType data);//尾插
void SeqListPopBack(SeqList* ps);//尾删
void SeqListPushFront(SeqList* ps,SLDataType data);//头插法
void SeqListPopFront(SeqList* ps);//头删法
int SeqListFind(SeqList* ps, SLDataType data);//查找
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//任意位置插入
void SeqListErase(SeqList* ps, size_t pos);//任意位置删除
void SeqListPrint(SeqList* ps);//顺序表打印

``````

main.c

``````#include"work.h"

//测试用例
void TestSeqList()
{
SeqList s;
SeqList* ps = &s;
SeqListInit(ps, MAXSIZE);

SeqListPushBack(ps, 1);//尾插法增加5个元素
SeqListPushBack(ps, 2);
SeqListPushBack(ps, 3);
SeqListPushBack(ps, 4);
SeqListPushBack(ps, 5);
SeqListPrint(ps);//打印输出

SeqListPopBack(ps);//尾删法删除一个元素
SeqListPrint(ps);//打印输出

SeqListPushFront(ps, 0);	//头插法增加一个元素
SeqListPrint(ps);	//打印输出

SeqListPopFront(ps);//头删法删除一个元素
SeqListPrint(ps);	//打印输出

//调用查找函数并返回下标，若不存在返回值为-1
printf("%dn", SeqListFind(ps, 2));
printf("%dn", SeqListFind(ps, 10));

SeqListInsert(ps, 4, 5);//第4个位置插入
SeqListPrint(ps);

SeqListErase(ps, 5);//第5个位置删除
SeqListPrint(ps);

SeqListDestory(ps);
}

int main()
{
TestSeqList();//调用测试函数
system("pause");
return 0;
}
``````

work.c

``````#include"work.h"

//初始化函数
void SeqListInit(SeqList* ps, size_t inite_capicity)
{
assert(ps);
ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
if (NULL == ps->arr)
{
exit(1);
}
ps->capicity = inite_capicity;
ps->size = 0;
}

//堆空间释放释放函数
void SeqListDestory(SeqList* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
ps->arr = NULL;
ps->capicity = 0;
ps->size = 0;
}

}

//顺序表打印函数
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("n");
}

//扩容函数
static void SeqListRealloc(SeqList* ps)
{
SLDataType* temp = ps->arr;
temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
if (temp != NULL)
{
// 若申请则将扩容后的地址赋给ps->size
// 这样做的目的是防止空间申请失败后原有空间的地址无法找回
ps->arr = temp;
}
ps->capicity *= 2;
}

//尾插法
void SeqListPushBack(SeqList* ps, SLDataType data)
{
assert(ps);
//先判断是否已满，如果已满则需要扩容
if (ps->size == ps->capicity)
{
SeqListRealloc( ps);//调用扩容函数
}
ps->arr[ps->size] = data;//将数据放到顺序表的结尾
ps->size++;//有效元素增加一个

}

//判空函数
static int IsSeqListEmpty(SeqList* ps)
{
assert(ps);
if (0==ps->size)
{
return 1;
}
else
{
return 0;
}
}

//尾删法
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
ps->size--;//尾删只需要将实际元素个数减一即可
}
}

//头插法
void SeqListPushFront(SeqList* ps, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
}
//***将ps->size强转成int类型，否则计算时会发生类型提升***
for (int i = (int)ps->size - 1; i >= 0; i--)
{
ps->arr[i + 1] = ps->arr[i];//所有元素向后移动一个单位
}
ps->arr[0] = data;//将元素插入顺序表头部
ps->size ++;//元素个数加1
}

//头删法
void SeqListPopFront(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = 0; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素个数减1
}
}

//查询
int SeqListFind(SeqList* ps, SLDataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == data)
{
return i;
}
}
return -1;//未找到返回-1
}

//任意位置插入
void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
}

for (int i = (int)ps->size - 1; i >= pos; i--)
{
ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移动一个单位
}
ps->arr[pos] = data;//将元素插入顺序表头部
ps->size++;//元素个数加1
}

//任意位置删除
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = (int)pos; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素个数减1
}
}

``````

THE END