线性表--顺序表

目录

1.什么是顺序表

2.动态顺序表实现

2.1动态顺序表结构体

2.2初始化

2.3打印验证函数

2.4判断是否扩容，按需扩容

2.5头插/尾插

 2.6头删/尾删

 2.7指定位置插入数据/指定位置删除数据

3.动态顺序表代码

---

1.什么是顺序表

线性表是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等，在逻辑结构上呈线性，在物理结构（存储）上不一定线性。顺序表是线性表的一种，在逻辑结构上呈线性，在物理结构（存储）也是线性的，因为底层结构是数组，加上增删查改等功能封装在一起形成顺序表，顺序表分成静态顺序表和动态顺序表。

2.动态顺序表实现

2.1动态顺序表结构体

 SLDataType是类型重命名，便于替换类型；

size是有效数据个数，也是一种重要下标，即为最后一个有效数据的下一个下标；

capacity是arr空间容量；

2.2初始化/销毁

 要初始化后才能后续使用该结构体，用完后进行销毁；

2.3打印验证函数

 便于后续验证直接使用；

2.4判断是否扩容，按需扩容

 当空间容量不够时（即空间容量与有效数据值相等），就需要扩容，起始空间容量扩容4，后面的扩容按原空间容量的2倍或者1.5倍的原则扩容；

使用中间指针判断是否扩容成功，失败退出程序，成功就将原指针更新为中间指针，并更新扩容后的空间容量；

2.5头插/尾插

 头插分为三种情况：

 注意后移形式，避免覆盖到后续后移数据；

尾插分三种情况：

 2.6头删/尾删

 头删分两种情况：

 

 尾删：

 2.7指定位置插入数据/指定位置删除数据

pos是插入下标:

 

 

 2.8查找数据

 2.9改变指定下标的数据

3.动态顺序表代码

具体代码如下：

//头文件 SeqList.h#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;//便于类型替换//动态顺序表
typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int size;     //有效数据个数int capacity; //空间容量
}SL;静态顺序表
//#define N 10
//typedef struct SeqList
//{
//	SLDataType arr[N];//定长数组
//	int size;       //有效数据个数
//}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印验证
void SLPrint(SL* ps);//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表尾插
void SLPushBack(SL* ps, SLDataType x);//判断是否需要扩容，需要进行扩容
void SLCheckCapacity(SL* ps);//顺序表的头删
void SLPopFront(SL* ps);
//顺序表的尾删
void SLPopBack(SL* ps);//指定位置插入数据，后面数据存在就后移
void SLInsert(SL* ps, int pos, SLDataType x);
//删除指定位置数据,后面数据存在就前移
void SLErase(SL* ps, int pos);//改变指定下标的数据
void SLChange(SL* ps, int pos, SLDataType x);//查找
int SLFind(SL* ps, SLDataType x);

//SeqList.c#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//初始化和销毁
void SLInit(SL* ps)
{ps->arr = NULL;              //初始化为空指针 ps->size = ps->capacity = 0; //初始化什么都没有，所以为0
}
void SLDestory(SL* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
//打印验证
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//判断是否需要扩容，需要进行扩容
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity)//有效数据个数与空间容量相等的时候，要插入需要先扩容{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//起始空间容量为0，则第一次扩容4个，扩容原则扩容原空间容量的2倍或1.5倍SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//中间指针接收扩容后的地址if (tmp == NULL)//扩容失败{perror("Realloc Fail!");exit(1);//意外退出}ps->arr = tmp;//扩容成功ps->capacity = newCapacity;//更新扩容后的空间容量}
}//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//或者if(ps == NULL) { return; }//若空间不够，需要扩容SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//若空间不够，需要扩容SLCheckCapacity(ps);ps->arr[ps->size] = x;ps->size++;
}//顺序表的头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//顺序表为空不能再删了for (int i = 0; i < ps->size - 1; i++)//向前覆盖{ps->arr[i] = ps->arr[i + 1];}ps->size--;//有效数据减1
}
//顺序表的尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表为空不能再删了ps->size--;//直接减去最后一位的有效数据
}//指定位置插入数据，后面数据存在就后移
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
//删除指定位置数据,后面数据存在就前移
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//改变指定下标的数据
void SLChange(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}//查找
int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

//测试，project.c#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void test()
{SL ps;SLInit(&ps);SLPushFront(&ps, 5);SLPushFront(&ps, 4);SLPushFront(&ps, 3);SLPushFront(&ps, 2);SLPushFront(&ps, 1);SLPrint(&ps);SLPushBack(&ps, 6);SLPushBack(&ps, 7);SLPushBack(&ps, 8);SLPushBack(&ps, 9);SLPushBack(&ps, 10);SLPrint(&ps);SLPopFront(&ps);SLPopFront(&ps);SLPrint(&ps);SLPopBack(&ps);SLPopBack(&ps);SLPrint(&ps);SLInsert(&ps, 0, 1);SLInsert(&ps, 1, 2);SLInsert(&ps, 8, 9);SLInsert(&ps, 9, 10);SLPrint(&ps);SLErase(&ps, 4);SLErase(&ps, 7);SLPrint(&ps);SLInsert(&ps, 4, 5);SLInsert(&ps, 7, 9);SLChange(&ps, 0, 10);SLChange(&ps, 1, 11);SLPrint(&ps);int ret = SLFind(&ps, 3);if (ret != -1){printf("找到了，在下标为%d的位置\n", ret);}else{printf("不存在数据，查找失败\n");}SLDestory(&ps);
}int main()
{test();return 0;
}