数据结构--顺序表（实现增删改查）

三个文件（Mytest.c 、MySeqList.c 、 MySeqList.h）

Mytest.c测试函数

MySeqList.c 函数定义

MySeqList.h函数声明

增删改查的步骤：

初始化

增加元素

• 尾插：先检查顺序表空间是否足够，若不足则进行扩容，然后将新元素插入到顺序表末尾，更新元素个数。

• 头插：先检查空间是否足够，然后将顺序表中已有元素依次向后移动一位，再将新元素插入到表头，更新元素个数。

• 任意位置插入：先检查插入位置是否合法以及空间是否足够，然后将插入位置及之后的元素依次向后移动一位，再将新元素插入到指定位置，更新元素个数。

删除元素

• 尾删：直接将顺序表的元素个数减1，逻辑上删除了最后一个元素。

• 头删：将顺序表中除第一个元素外的其他元素依次向前移动一位，覆盖原来的第一个元素，然后更新元素个数。

• 任意位置删除：先检查删除位置是否合法，然后将删除位置之后的元素依次向前移动一位，覆盖要删除的元素，更新元素个数。

修改元素

• 检查要修改的位置是否合法，然后直接将指定位置的元素值修改为新的值。

查询元素

• 遍历顺序表中的元素，将每个元素与要查找的值进行比较，若找到相等的元素，则返回该元素的位置；若遍历完整个顺序表都未找到，则返回 -1。

一、MySeqList.h

1、首先创建一个结构体（剩下的就是函数声明）

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLdatatype;
#define INIT_CAPCITY 3  //初始化空间大小
#define ADD_CAPCITY 2  //增容大小typedef struct SLSeqList
{SLdatatype* arr;//让a在初始化函数中初始化，让a指向一块空间int size;//用于记录顺序表中当前已经存储的元素个数int capcity;  //最多能存储几个数量（不够大可以扩容）当size达到capcity.
}SL;void SLInit(SL* p);
void SLpushBack(SL* p, SLdatatype x);
void SLpopBack(SL* p);
void SLPrint(SL* p);void SLPushFront(SL* p , SLdatatype x);
void SLPopFront(SL* p);
void SLInsert(SL* p, int pos, SLdatatype x);
void SLErase(SL* p, int pos);
void SLModify(SL* p, int pos, SLdatatype newVal);
int SLFind(SL* p, SLdatatype x);
void SLDestroy(SL* p);

二、MySeqList.c实现

#define _CRT_SECURE_NO_WARNINGS
#include"my_SeqList.h"//初始化
void SLInit(SL *p)
{assert(p);p->arr = (SLdatatype*)calloc(INIT_CAPCITY,sizeof(SLdatatype));if (p->arr == NULL){perror("calloc");return;}p->size = 0;p->capcity = INIT_CAPCITY;// 初始化为3 在 my_SeqList.h中定义 #define INIT_CAPCITY 3
}//判断是否需要扩容
void SLCapaty(SL* p)
{if (p->size == p->capcity){SLdatatype* tmp = (SLdatatype*)realloc(p->arr,sizeof(SLdatatype) * p->capcity * 2);if (p->arr == NULL){perror("calloc");return;}p->arr = tmp;p->capcity += ADD_CAPCITY;}
}//尾插
void SLpushBack(SL* p , SLdatatype x)
{assert(p);//增加内容前判断空间是否够用？SLCapaty(p);p->arr[p->size++] = x;
}//尾删
void SLpopBack(SL* p)
{assert(p->size > 0);//温柔检查/*if (p->size == 0)return;*/p->size--;
}//头插
void SLPushFront(SL *p , SLdatatype x)
{assert(p);SLCapaty(p);int end = p->size-1;while (end >= 0){p->arr[end + 1] = p->arr[end];end--;}p->arr[0] =x;p->size++;
}
//头删
void  SLPopFront(SL* p)
{assert(p);assert(p->size > 0); //元素个数size如果不大于0（即没有数据，就不需要往西执行了）int begin = 1;while (begin < p->size){p->arr[begin - 1] = p->arr[begin];++begin;}p->size--;
}
//任意位置插入数据
//传入一个结构体 ， pos位置（要插入的位置），int x
void SLInsert(SL* p , int pos , SLdatatype x)
{assert(p);//这里已经进行了判断：<=p->size，所以不会越界assert(pos >= 0 && pos <=p->size);SLCapaty(p);int end = p->size - 1;while (end >= pos){p->arr[end + 1] = p->arr[end];--end;}p->arr[pos] = x;//如果在插入元素之前就将  p->size  // 加 1，那么在插入元素时， p->size  // 的值就会比实际的元素个数多 1p->size++;
}
//任意位置删除数据
void SLErase(SL* p, int pos)
{assert(p);//这里已经进行了判断：<=p->size，所以不会越界assert(pos >= 0 && pos < p->size);//pos 位置的元素即将被删除，不需要参与移动操作。int begin = pos + 1;//只能从后往前挪，从前完后挪会被覆盖while (begin < p->size){//eg:1,2,3,4,5,6 删除3//pos=2  下标[2+1]  , 4,5,6往前挪p->arr[begin -1] = p->arr[begin];++begin;}p->size--;
}
//查找数据
int SLFind(SL *p , SLdatatype x)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){if (p->arr[i] == x){return i;}		}return -1;
}
// 修改顺序表中指定位置的元素值
void SLModify(SL* p, int pos, SLdatatype newVal){assert(p);// 检查位置是否合法，pos 必须在 0 到 p->size - 1 之间assert(pos >= 0 && pos < p->size);// 直接将指定位置的元素修改为新值p->arr[pos] = newVal;
}
void SLPrint(SL* p)
{assert(p);int i = 0;for (i = 0; i < p->size; i++){printf("%d ",p->arr[i]);}printf("\n");
}
void SLDestroy(SL* p)
{assert(p);free(p->arr);p->arr = NULL;p->capcity = p->size = 0;//p = NULL; //结构体p是全局  所以不需要释放，程序结束会销毁
}

1. 数据结构初始化SLInit(SL *p)：分配初始内存，初始化元素个数为0、空间容量

2. 判断是否需要扩容 SLCapaty(SL* p)

什么时候需要判断呢？  插入数据数据之前判断空间是否够大

3. 数据插入操作SLpushBack(SL* p , SLdatatype x)：插入前都会调用SLCapaty检查是否需要扩容，插入时会相应移动元素并更新size。

p->arr[p->size++] = x;：它的作用是将新元素 x 赋值给顺序表数组 p->arr 中当前元素个数 p->size 所对应的位置（因为 p->size 作为下标使用后才自增），然后 p->size 的值会自动增加 1，从而实现了在顺序表的尾部插入一个新元素的功能。

4. 数据删除操作：尾删SLpopBack，直接size--，就不会访问到最后一个元素了，这样就实现了尾删。

头删SLPopFront(SL* p)：

 int begin = 1;：定义一个整型变量 begin 并初始化为 1，用于从顺序表的第二个元素（下标为 1）开始遍历。因为要删除第一个元素（下标为 0），所以从第二个元素开始处理。

while (begin < p->size)：只要 begin 小于顺序表当前的元素个数 p->size，就会继续循环。

循环的目的是将后续元素依次向前移动一位，覆盖掉前面的元素。

 p->arr[begin - 1] = p->arr[begin];：在循环体中，将下标为 begin 的元素的值赋给下标为 begin - 1 的位置。这样就实现了将当前元素向前移动一位，覆盖掉原来前一个位置的元素。例如，原本 p->arr[1] 的值会覆盖 p->arr[0] 的值，p->arr[2] 的值会覆盖 p->arr[1] 的值，以此类推。

5. 查找与修改：SLFind函数遍历顺序表查找指定元素，返回其下标，未找到则返回-1；SLModify函数用于修改指定位置的元素值。

6. 打印：SLPrint函数用于打印顺序表中的所有元素；

7、SLDestroy函数释放顺序表占用的内存，并将相关成员变量置为0和NULL 。

三、Mytest.c

#define _CRT_SECURE_NO_WARNINGS
#include"my_SeqList.h"//SLpushBack();头插
//SLpopBack();尾删void test1()
{SL s;SLInit(&s);
//---------------尾插---尾删----------------SLpushBack(&s , 1); //尾插,插入数字1SLpushBack(&s , 2);//尾插SLpushBack(&s , 3);//尾插SLpushBack(&s , 4);//尾插SLpushBack(&s , 5);//尾插SLpushBack(&s , 6);//尾插SLpushBack(&s , 7);//尾插SLpushBack(&s , 8);//尾插SLpushBack(&s , 9);//尾插SLPrint(&s);SLpopBack(&s);//尾删一个SLpopBack(&s);//尾删一个SLpopBack(&s);//尾删一个//----------头插---头删-------------SLPushFront(&s,10); //头插入一个数据SLPushFront(&s,20); //头插入一个数据SLPushFront(&s,30); //头插入一个数据SLPrint(&s);SLPopFront(&s);//头部删除一个数据SLPopFront(&s);//头再删除一个数据SLPrint(&s);//----------任意位置插入/删除------------SLInsert(&s, 2,6);SLPrint(&s);SLErase(&s,3);SLPrint(&s);//查找int ret = SLFind(&s, 6);//查6 在哪个位置printf("%d\n", ret);//打印位置SLModify(&s,0, 200);//从0位置开始的SLPrint(&s);SLDestroy(&s);
}
int main()
{test1();	return 0;
}