顺序表（更新版）——“数据结构与算法”
各位CSDN的uu们你们好呀，今天小雅兰又来更新新专栏啦，其实之前我就已经写过了顺序表的内容，只是之前的内容不是最新版的顺序表，现在，我来更新一下最新版的顺序表，下面，就让我们进入更新版的顺序表的世界吧
顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样，分为三个文件：
https://xiaoyalan.blog.csdn.net/article/details/128705747?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/128717749?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/129788167?spm=1001.2014.3001.5502
https://xiaoyalan.blog.csdn.net/article/details/129896970?spm=1001.2014.3001.5502
test.c——测试代码功能
SeqList.c——顺序表的实现
SeqList.h——顺序表的声明
https://xiaoyalan.blog.csdn.net/article/details/129380414?spm=1001.2014.3001.5502
这是小雅兰之前写的顺序表的知识，有兴趣的可以去看看
我们写的是一个动态版的顺序表：
typedef struct SeqList {SLDataType* a;int size;//存储的有效数据的个数int capacity;//容量 }SL;把struct SeqList这个结构体重命名为SL
typedef int SLDataType;把int重命名为SLDataType
写成这样的形式是因为：如果以后想要修改类型，那就直接改int就可以了，如果不这样写， 要改很多个地方，就很麻烦
顺序表的初始化：
//初始化 void SLInit(SL* ps1) {ps1->a = malloc(sizeof(SLDataType) * 4);if (ps1 == NULL){perror("malloc fail");return;}ps1->size = 0;ps1->capacity = 4; }动态开辟出4个SLDataType类型的大小的空间
顺序表的销毁：也就是把空间还给操作系统
//销毁 //把空间还给操作系统 void SLDestroy(SL* ps1) {free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0; }
打印顺序表的内容：
//打印 void SLPrint(SL* ps1) {int i = 0;for (i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\\n"); }
尾插：
ps1->a[ps1->size] = x; ps1->size++;在这里，我们需要想一个问题：在尾插的过程中，如果空间不够了该怎么办呢？？？所以在这里，我们还需要一个检查容量的函数，如果容量不够就扩容
//检查容量，容量不够就扩容 void SLCheckCapacity(SL* ps1) {if (ps1->size == ps1->capacity){SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);//扩上一个二倍大小的容量//这个数值可以自己设定，扩多了不好，扩少了也不好//所以扩上二倍是最合理的选择if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = ps1->capacity * 2;} }//尾插 void SLPushBack(SL* ps1, SLDataType x) {SLCheckCapacity(ps1);ps1->a[ps1->size] = x;ps1->size++; }
下面，我们来测试一下尾插的功能，看是否成功
int main()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPushBack(&s, 7);SLPushBack(&s, 8);SLPushBack(&s, 9);SLPushBack(&s, 10);SLPrint(&s);SLDestroy(&s);return 0;
}
结果发现，尾插的功能非常成功！！！
头插：
需要从后往前挪动数据！！！
若是从前往后挪动数据，就会覆盖，这是绝对不行的
//头插 void SLPushFront(SL* ps1, SLDataType x) {SLCheckCapacity(ps1);//挪动数据int end = ps1->size - 1;while (end >= 0){ps1->a[end + 1] = ps1->a[end];//把数据往后挪end--;}ps1->a[0] = x;ps1->size++; }
来测试一下头插的功能：
//头插测试
void TestSeqList2()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPushFront(&s, 7);SLPushFront(&s, 8);SLPushFront(&s, 9);SLPrint(&s);SLDestroy(&s);
} 
尾删：
直接把size--就可以了
//尾删 void SLPopBack(SL* ps1) {ps1->size--; }
来测试一下尾删的功能：
//尾删测试
void TestSeqList3()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPushFront(&s, 7);SLPushFront(&s, 8);SLPushFront(&s, 9);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLDestroy(&s);
}
但是这个尾删仍然有点问题，需要检查一下：
//尾删 void SLPopBack(SL* ps1) {//温柔的检查if (ps1->size == 0){return;}ps1->size--; }//尾删 void SLPopBack(SL* ps1) {//暴力的检查assert(ps1->size > 0);ps1->size--; }
头删：
//头删 void SLPopFront(SL* ps1) {//暴力检查assert(ps1->size > 0);int start = 0;while (start < ps1->size - 1){ps1->a[start] = ps1->a[start + 1];start++;}ps1->size--; }
来测试一下头删的功能：
//头删测试
void TestSeqList4()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPushFront(&s, 7);SLPushFront(&s, 8);SLPushFront(&s, 9);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SLDestroy(&s);
} 
在中间位置插入数据：
//在中间位置(pos)插入数据 void SLInsert(SL* ps1, int pos, SLDataType x) {SLCheckCapacity(ps1);int end = ps1->size - 1;while (end >= pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++; }
写了这个函数的功能之后，我们就可以把之前写的头插和尾插修改一下：
//尾插 void SLPushBack(SL* ps1, SLDataType x) {SLInsert(ps1, ps1->size, x); }//头插 void SLPushFront(SL* ps1, SLDataType x) {SLInsert(ps1, 0, x); }
但是，这个在中间插入数据的代码还是有点问题;
//中间插数据测试
void TestSeqList5()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPushFront(&s, 7);SLPushFront(&s, 8);SLPushFront(&s, 9);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 2, 30);SLPrint(&s);SLInsert(&s, 20, 300);SLPrint(&s);SLDestroy(&s);
}
从此运行结果可知：越界是不会报错的！！！但是它的的确确越界了！！！
所以把代码改进为：
//在中间位置(pos)插入数据 void SLInsert(SL* ps1, int pos, SLDataType x) {assert(pos >= 0 && pos <= ps1->size);SLCheckCapacity(ps1);int end = ps1->size - 1;while (end >= pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++; }
在中间位置删除数据：
//在中间位置(pos)删除数据 void SLErase(SL* ps1, int pos) {assert(pos >= 0 && pos < ps1->size);assert(ps1->size > 0);//可有可无int start = pos + 1;while (start <= pos + 1){ps1->a[start - 1] = ps1->a[start];start++;}ps1->size--; }
同样，有了这个功能之后，可以把头删和尾删修改一下：
//头删 void SLPopFront(SL* ps1) {SLErase(ps1, 0); }//尾删 void SLPopBack(SL* ps1) {SLErase(ps1, ps1->size - 1); }
测试一下从中间删除数据的功能：
//中间删数据测试
void TestSeqList6()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPushFront(&s, 7);SLPushFront(&s, 8);SLPushFront(&s, 9);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 2, 30);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);SLDestroy(&s);
} 
查找：
//查找 //找到了返回下标，找不到返回-1 int SLFind(SL* ps1, SLDataType x) {int i = 0;for (i = 0; i < ps1->size; i++){if (ps1->a[i] == x){return i;}}return -1; }
修改：
//修改 void SLModify(SL* ps1, int pos, SLDataType x) {assert(pos >= 0 && pos < ps1->size);ps1->a[pos] = x; }
下面，浅浅附上一波源代码：
SeqList.c的内容
#include"SeqList.h"
//初始化
void SLInit(SL* ps1)
{assert(ps1);ps1->a = malloc(sizeof(SLDataType) * 4);if (ps1 == NULL){perror("malloc fail");return;}ps1->size = 0;ps1->capacity = 4;
}
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1)
{assert(ps1);free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}
//打印
void SLPrint(SL* ps1)
{assert(ps1);int i = 0;for (i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\\n");
}
//检查容量，容量不够就扩容
void SLCheckCapacity(SL* ps1)
{assert(ps1);if (ps1->size == ps1->capacity){SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);//扩上一个二倍大小的容量//这个数值可以自己设定，扩多了不好，扩少了也不好//所以扩上二倍是最合理的选择if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = ps1->capacity * 2;}
}
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{assert(ps1);assert(pos >= 0 && pos <= ps1->size);SLCheckCapacity(ps1);int end = ps1->size - 1;while (end >= pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++;
}
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos)
{assert(ps1);assert(pos >= 0 && pos < ps1->size);assert(ps1->size > 0);//可有可无int start = pos + 1;while (start <= pos + 1){ps1->a[start - 1] = ps1->a[start];start++;}ps1->size--;
}
//尾插
void SLPushBack(SL* ps1, SLDataType x)
{assert(ps1);/*SLCheckCapacity(ps1);ps1->a[ps1->size] = x;ps1->size++;*/SLInsert(ps1, ps1->size, x);
}
//头插
void SLPushFront(SL* ps1, SLDataType x)
{assert(ps1);//SLCheckCapacity(ps1);挪动数据//int end = ps1->size - 1;//while (end >= 0)//{// ps1->a[end + 1] = ps1->a[end];//把数据往后挪// end--;//}//ps1->a[0] = x;//ps1->size++;SLInsert(ps1, 0, x);
}
//尾删
void SLPopBack(SL* ps1)
{assert(ps1);温柔的检查//if (ps1->size == 0)//{// return;//}//ps1->size--;//暴力的检查/*assert(ps1->size > 0);ps1->size--;*/SLErase(ps1, ps1->size - 1);
}
//头删
void SLPopFront(SL* ps1)
{assert(ps1);//暴力检查assert(ps1->size > 0);int start = 0;while (start < ps1->size - 1){ps1->a[start] = ps1->a[start + 1];start++;}ps1->size--;//SLErase(ps1, 0);
}
//查找
//找到了返回下标，找不到返回-1
int SLFind(SL* ps1, SLDataType x)
{assert(ps1);int i = 0;for (i = 0; i < ps1->size; i++){if (ps1->a[i] == x){return i;}}return -1;
}
//修改
void SLModify(SL* ps1, int pos, SLDataType x)
{assert(ps1);assert(pos >= 0 && pos < ps1->size);ps1->a[pos] = x;
}
SeqList.h的内容
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size;//存储的有效数据的个数int capacity;//容量
}SL;
//初始化
void SLInit(SL* ps1);
//销毁
//把空间还给操作系统
void SLDestroy(SL* ps1);
//打印
void SLPrint(SL* ps1);
//尾插
void SLPushBack(SL* ps1,SLDataType x);
//尾删
void SLPopBack(SL* ps1);
//头插
void SLPushFront(SL* ps1, SLDataType x);
//头删
void SLPopFront(SL* ps1);
//在中间位置(pos)插入数据
void SLInsert(SL* ps1, int pos, SLDataType x);
//在中间位置(pos)删除数据
void SLErase(SL* ps1, int pos);
//查找
//找到了返回下标，找不到返回-1
int SLFind(SL* ps1, SLDataType x);
//修改
void SLModify(SL* ps1, int pos, SLDataType x);test.c的内容
void menu()
{printf("*\\n");printf("1、尾插数据 2、尾删数据\\n");printf("\\n");printf("3、头插数据 4、头删数据\\n");printf("\\n");printf("5、在任意位置插入数据（位置3插入20）\\n");printf("\\n");printf("6、在任意位置删除数据 \\n");printf("\\n");printf("7、查找某个数据的位置，并删除它 \\n");printf("\\n");printf("8、删除顺序表中有的 某个数据 \\n");printf("\\n");printf("9、打印数据 \\n");printf("\\n");printf("-1、退出 \\n");printf("\\n");printf("*\\n");}int main()
{printf("* 欢迎大家来到动态顺序表的测试 \\n");int option = 0;SL s;SLInit(&s);do{menu();printf("请输入你的操作：>");scanf_s("%d", &option);int sum = 0;int x = 0;int y = 0;int z = 0;int pos = 0;int w = 0;switch (option){case 1:printf("请依次输入你要尾插的数据：，以-1结束\\n");scanf_s("%d", &sum);while (sum != -1){SLPushBack(&s, sum); // 1.尾插scanf_s("%d", &sum);}break;case 2:SLPopBack(&s); // 2.尾删break;case 3:scanf_s("%d", &x);SLPushFront(&s, x); // 3.头插break;case 4:SLPopFront(&s); // 4.头删break;case 5:SLInsert(&s, 3, 20); // 5.在任意位置插入数据break;case 6:SLErase(&s, 3); // 6.在任意位置删除数据break;case 7:printf("请输入要删除序列的中的某个数字\\n");scanf_s("%d", &z);y = SLFind(&s, z); // 7.查找某个数字的位置，并且删除它printf("%d的位置在%d处： \\n", z, y);if (y != -1){SLErase(&s, y);}break;case 8:printf("请输入要删除序列的中的数字\\n"); //8.删除顺序表中 所有的 某个数据 scanf_s("%d", &w);pos = SLFind(&s, w, 0);while (pos != -1){SLErase(&s, pos);pos = SLFind(&s, w, pos);}break;case 9:SLPrint(&s);break;default:if (option == -1){exit(0); // 退出程序 }else{printf("输入错误，请重新输入\\n");}break;}} while (option != -1); // 退出程序SLDestroy(&s);return 0;
}好啦，小雅兰今天的顺序表的更新版的内容就到这里啦，继续加油刷题和学习算法噢！！！
