顺序表（更新版）——“数据结构与算法”

2023-05-18

amp void size

各位CSDN的uu们你们好呀，今天小雅兰又来更新新专栏啦，其实之前我就已经写过了顺序表的内容，只是之前的内容不是最新版的顺序表，现在，我来更新一下最新版的顺序表，下面，就让我们进入更新版的顺序表的世界吧顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样，分为三个文件：https://xiaoyalan.

各位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;
}