数据结构-顺序表详解（看这篇就足够了，哈哈哈）

哈喽，everybody!感谢各位同胞的阅览，希望大家在评论区多多发表意见！

本篇代码都是基于VS所写，在其他编译器运行可将#define _CRT_SECURE_NO_WARNINGS该行注释，某些语句或许在某些低版本的GCC编译器上不能运行。

顺序表

1.顺序表的概念及结构

1.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合

顺序表的底层是数组，故顺序表的物理结构是连续的。

顺序表是线性表的一种，逻辑结构是连续的。

2.顺序表分类

•2.1顺序表和数组的区别

◦ 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

• 2.2顺序表分类

◦ 静态顺序表

概念：使用定长数组存储元素

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费.

struct SeqList{//sequence 顺序的 
 int arr[100];//定长数组
 int size;//顺序表当前有效的数据个数
 }SL;

◦ 动态顺序表

struct SeqList{
 int *arr;
 int size;//有效的数据个数
 int capacity;//空间大小
 }SL;

可增容

3.动态顺序表的实现

#define INIT_CAPACITY 4
 typedef int SLDataType;
 // 动态顺序表 -- 按需申请
 typedef struct SeqList
 {
  SLDataType* a;
  int size; // 有效数据个数
  int capacity; // 空间容量
 }SL;
 //初始化和销毁
 void SLInit(SL* ps);
 void SLDestroy(SL* ps);
 void SLPrint(SL* ps);
 //扩容
 void SLCheckCapacity(SL* ps);
 //头部插⼊删除 / 尾部插⼊删除
 void SLPushBack(SL* ps, SLDataType x);
 void SLPopBack(SL* ps);
 void SLPushFront(SL* ps, SLDataType x);
 void SLPopFront(SL* ps);
 //指定位置之前插⼊/删除数据
 void SLInsert(SL* ps, int pos, SLDataType x);
 void SLErase(SL* ps, int pos);
 int SLFind(SL* ps, SLDataType x);

以上为提纲

下面顺序表的实现采用项目格式

项目设计: 1.头文件 .h 顺序表结构 声明顺序表的方法 2 .c文件 实现顺序表的方法

4.顺序表具体实现（主要为动态）

4.1头文件

#pragma once
 //顺序表的创建
 //静态
 /*
 struct seqList{
 int arr[100];定长数组
 int size; 数量
 }
 */
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 typedef int datatype;//方便以后改数据类型
 //动态顺序表--按需申请空间
 typedef  struct seqList {
     datatype* arr;
     int size;
     int capacity;//容量
 }SL;
 //初始化和销毁,数据打印
 void SLInit(SL* ps);
 void SLDestroy(SL* ps);
 void SLPrint(SL s);
 //扩容
 void CheckCapacity(SL* ps);
 //头部插⼊删除 / 尾部插⼊删除 
 void SLPushBack(SL* ps, datatype x);
 void SLPopBack(SL* ps);
 void SLPushFront(SL* ps, datatype x);
 void SLPopFront(SL* ps);
 //指定位置之前插⼊/删除数据/数据查询
 void SLInsert(SL* ps, int pos, datatype x);
 void SLErase(SL* ps, int pos);
 int SLFind(SL* ps, datatype x);

4.2相关函数实现

#define _CRT_SECURE_NO_WARNINGS
 #include"seqList.h"
 //初始化
 void SLInit(SL* ps) {
     ps->arr = NULL;
     ps->size = ps->capacity = 0;//初始化也可赋值，但是后续操作会改变，思路都是一样的。
 }
 //销毁
 void SLDestroy(SL* ps) {
     if (ps->arr) {//等价于if(ps->arr!=NULL)
         free(ps->arr);
         ps->arr = NULL;
     }
     ps->size = ps->capacity = 0;
 }
 //空间检查
 void CheckCapacity(SL* ps) {
     if (ps->size == ps->capacity) {
         int newcapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
         //创建临时数组，判断是否创建为空导致数据丢失
         datatype* tem = (datatype*)realloc(ps->arr, newcapacity * sizeof(datatype));
         if (tem == NULL) {
             perror("realloc fail!");
             exit(1);//直接退出
         }
         ps->arr = tem;
         ps->capacity = newcapacity;
     }
 }
 //尾插
 void SLPushBack(SL* ps, datatype x) {
 ​
     //ps->arr[ps->size] = x;
     //++ps->size;
     //判断空间是否足够
     assert(ps);
     CheckCapacity(ps);
     ps->arr[ps->size++] = x;
 }
 //头插
 void SLPushFront(SL* ps, datatype 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 SLPrint(SL s) {
     for (int i = 0; i < s.size; i++) {
         printf("%d ", s.arr[i]);
     }
     printf("\n");
 }
 //尾删
 void SLPopBack(SL* ps) {
     assert(ps);
     assert(ps->size);
     --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];//arr[size-2]=arr[size-1]
     }
     ps->size--;
 ​
 }
 //指定位置前插入数据
 void SLInsert(SL* ps, int pos, datatype x) {
     assert(ps);
     assert(pos >= 0 && pos <= ps->size);
     CheckCapacity(ps);
     for (int i = ps->size; i > pos; i--) {
         ps->arr[i] = ps->arr[i - 1];//arr[size]=arr[size-1]
     }
     ps->arr[pos] = x;
     ps->size++;
 }
 //指定位置删除
 void SLErase(SL* ps, int pos) {
     assert(ps);
     assert(ps->size);
     for (int i = pos; i < ps->size - 1; i++) {
         ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
     }
     ps->size--;
 ​
 }
 //找寻数据
 int SLFind(SL* ps, datatype x) {
     assert(ps);
     for (int i = 0; i < ps->size; i++) {
         if (ps->arr[i] == x) {
             return i;
         }
     }
     return -1;
 }

4.3代码测试

#define _CRT_SECURE_NO_WARNINGS
 #include"seqList.h"
 void test1() {
     SL sl;
     SLInit(&sl);
     SLPushBack(&sl, 1);
     SLPushBack(&sl, 2);
     SLPushBack(&sl, 3);
     SLPushBack(&sl, 4);
     SLPushBack(&sl, 5);
     SLPrint(sl);//12345
     SLInsert(&sl, 0, 99);
     SLInsert(&sl, sl.size, 66);
     //SLErase(&sl, 3);
     //SLErase(&sl, 0);
     //SLErase(&sl, 4);
     SLPrint(sl);
 ​
     SLPushFront(&sl, 6);
     SLPushFront(&sl, 6);
     SLPrint(sl);
 ​
     SLPopBack(&sl);
     SLPopBack(&sl);
     SLPopBack(&sl);
     SLPrint(sl);
 ​
 ​
     SLPopFront(&sl);
     SLPopFront(&sl);
     //SLPopFront(&sl);
     SLPrint(sl);
     SLPopFront(&sl);
     SLPopFront(&sl);
     SLPrint(sl);
 ​
     int find= SLFind(&sl,4);
     if (find < 0) {
         printf("没有找到!");
     }
     else
         printf("找到了,数组下标为%d.，第%d个元素.", find,find+1);
     SLDestroy(&sl);
 }
 int main() {
     test1();
     return 0;
 }

可根据自己要求进行数据检测处理！