顺序表和链表

1.线性表：

• 线性表是n个具有相同特性（相同逻辑结构，物理结构）的数据元素的有限序列。常见的线性表有：顺序表，链表，栈，队列，字符串…
• 线性表在逻辑上是线性结构，也就说是连续的一条直线。但在物理结构上不一定是连续的，线性表在屋里上存储时，通常以数组和链式结构的形式存储。
• 逻辑结构：抽象结构，人为想象。比如数组里有五个数据，我们抽象为一个长方形框；比如把排队买东西的人抽象为一条直线
• 物理结构：存储时分配的物理空间（数组物理结构是连续的，因为分配的空间是连续的）

2.顺序表（逻辑结构：线性；物理结构：线性）

2.1 概念与结构

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储

2.2 顺序表与数组的区别：

顺序表底层是数组，对数组实现封装，实现了常用的增删查改操作的接口（可以直接调用顺序表中增删查改相关方法）

2.3 顺序表的分类

2.3.1 静态顺序表

• 使用定长数组存储数据

//静态顺序表
typedef int SLDataType;
#define N 6
typedef struct SeqList
{SLDataType a[N];//定长数组int size;//有效数据个数,下图有效数据个数为4，指向a[4]
}SL;

2.3.2 动态顺序表

//动态顺序表--运行时按需申请空间
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间容量
}SL;

//头文件--SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;//存储数据int size;//有效数据个数int capacity;//空间容量大小
}SL;
void SLInit(SL* ps);void SLPrint(SL* ps);
void SLInit(SL* ps);
void SLDestroy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);//查找
int SLFind(SL* ps, SLDataType x);
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDataType x);
//删除pos位置的数据
void SLErase(SL* ps, int pos);

//实现文件--SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;}
void CheckCapacity(SL* ps)
{int Newcapacity = ps->capacity == 0?4 : 2 * ps->capacity;//如果空间大小为0，就分配四个字节空间if (ps->capacity == ps->size){SLDataType* tmp = (SLDataType*)realloc( ps->arr, Newcapacity * sizeof(SLDataType));//realloc分配成功返回void*//realloc的第二个参数是字节数，可以给数字，比如12，就代表十二个字节//若用来存储12个int类型的数据，需要12*sizeof（int）//malloc(15)if (tmp == NULL){perror("error");exit(1);}ps->capacity = Newcapacity;ps->arr = tmp;;}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);//ps为指针变量，检查指向的地址是否为空，与初始化ps->arr=NULL无关CheckCapacity(ps);//检查空间是否足够ps->arr[ps->size] = x;//不可以直接写成size，访问指针变量的结构体成员必须用箭头ps->size++;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);CheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i-1];}ps->arr[0] = x;ps ->size++; } 
void SLPopBack(SL* ps)//尾删
{assert(ps && ps->size);ps->size--;//这就是删除方法，之间减少数据的数量}
void SLPopFront(SL* ps)//头删
{for (int i = 1; i<ps->size; i++){ps->arr[i - 1] = ps->arr[i];}ps->size--;
}
int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;//即没找到
}
void SLInsert(SL* ps, int pos, SLDataType x)//在指定位置之前插入数据
{assert(ps&&ps->size);CheckCapacity(ps);for (int i = ps->size; i >pos; i--){ps->arr[i] =ps-> arr[i - 1];}ps->arr[pos] = x;ps->size++;}
void SLInsertAfter(SL* ps, int pos, SLDataType x)//在指定位置之后插入数据
{assert(ps->size && ps);CheckCapacity(&ps);for (int i = ps->size; i > pos+1; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos + 1] = x;ps->size++;
}void SLPrint(SL* ps)//可以不用指针 ，用指针可以减少拷贝提高效率
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}
void SLErase(SL* ps, int pos)//删除指定位置的数据
{assert(ps && ps->size);if (pos >= ps->size){perror("该位置不存在");return 1;}for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
void SLDestroy(SL*ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

//测试文件--test.c
#include"SeqList.h"
void test01()
{SL sl;SLInit(&sl); SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushFront(&sl, 8);SLPushFront(&sl, 9);SLPushFront(&sl, 10);/*SLPopBack(&sl);SLPopFront(&sl);SLPopFront(&sl);*//*int c=SLFind(&sl, 10);printf("%d\n", c);*/SLInsert(&sl, 1, 5);SLInsertAfter(&sl, 2, 7);/*SLErase(&sl, 2);*/SLPrint(&sl);SLDestroy(&sl);
}
int main()
{test01();return 0;}