【数据结构】顺序表---C语言版(数据结构开篇小菜,全网最详细!小白看一遍就学会!!!)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
文章目录
一、前言
停更了一个月限时返场啦从本篇文章开始就进入了我们数据结构的学习喽本篇文章也是《数据结构与算法》 专栏的第一篇文章本篇的内容是顺序表的学习也是数据结构的开胃小菜希望烙铁们可以理解消化哦
在我们学习顺序表之前呢我们大家肯定会有疑问什么是数据结构为什么要去学习数据结构顺序表在数据结构里面代表什么呢这里我来给大家一次解惑让大家真正的搞懂数据结构学习起来才更加有动力
1. 什么是数据结构
简单地说数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的而对于其他操作则是低效的。首先我们需要理解各种数据结构才能在处理实际问题时选取最合适的数据结构。
数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构其中的逻辑关系是指数据元素之间的前后间关系而与他们在计算机中的存储位置无关。逻辑结构分为以下几种
集合结构数据元素同属一个集合单个数据元素之间没有任何关系。
线性结构数据结构中的元素存在一对一的相互关系。
树形结构数据结构中的元素存在一对多的相互关系。
图形结构数据结构中的元素存在多对多的相互关系。
数据的物理结构是指数据的逻辑结构在计算机存储空间的存放形式它包括数据元素的机内表示和关系的机内表示。物理结构又叫存储结构分为以下几种
顺序存储结构一段连续的内存空间。优点随机访问缺点插入删除效率低大小固定。
链式存储结构不连续的内存空间。优点大小动态扩展插入删除效率高缺点不能随机访问。
索引存储结构为了方便查找整体无序但索引块之间有序需要额外空间存储索引表。优点对顺序查找的一种改进查找效率高缺点需额外空间存储索引。
散列存储结构选取某个函数数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置引起地址冲。优点查找基于数据本身即可找到查找效率高存取效率高缺点存取随机不便于顺序查找。
二、顺序表的概念----线性表
1. 什么是线性表
本次我们要来介绍第一种数据结构也是数据结构中最简单的一部分线性表
此时此刻肯定会有烙铁会有疑问为什么难道他会像一条线一样一次连接吗
没错当数据首尾依次相连接这种数据结构就被叫做线性表。
注意 相连接是逻辑上的连接不是空间上的连接。
此时可能还会有烙铁站出来说你说的这不就是数组嘛小意思我会
其实 数组只是一种线性表可是线性表还有很多种形式哦
线性表的形式 数组、链表、顺序表、队列等 其中数组我们在C语言已经学过不再提及 。
官方解释线性表linear list是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
2. 顺序表与数组的区别
顺序表顺序表是用 一段物理地址连续存储单元 依次存储数据元素的线性结构
顺序表就是将数据连着存放存放的数据空间也是连着的
数组数据不用按顺序的存放可以随意的存放
区别数组不按空间顺序随意地存放数据但是顺序表的数据是要按照空间的的顺序存放
说的这里估计有些烙铁已经开始有点 晕晕的状态了我来给大家画图解释一下
三、顺序表详解
静态顺序表
静态顺序表使用定长数组存储
优点操作简单代码实现容易
缺点定长数组很受限制数组开小了不够用开大了又浪费
//静态顺序表
#define N 10;
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype a[N];
int size;
}SL;
动态顺序表
动态顺序表使用动态开辟的数组进行数据的存储
优点数组大小可以根据自己的需求进行调节
缺点代码比较复杂
//动态顺序表
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype* a; //指向动态开辟的数组
int size; //存储的有效数据的个数
int capacity; //当前容量
}SL;
创建动态顺序表
这里先创建三个文件
1️⃣SeqList.h文件用于函数的声明
2️⃣SeqList.c文件用于函数的定义
3️⃣Test.c文件用于测试函数
建立三个文件的目的 将顺序表作为一个项目来进行书写方便我们的学习与观察。
⭕接口1定义结构体SL
请看代码与注释
typedef int SLDatatype; //数据类型
typedef struct SeqList
{
SLDatatype* a; //指向动态开辟的数组
int size; //存储的有效数据的个数
int capacity; //当前容量
}SL;
⭕接口2初始化结构体SLInit
请看代码与注释
void SLInit(SL* psl)
{
assert(psl);
psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
if (psl->a == NULL)
{
perror("malloc fail");
return;
}
psl->capacity = 4;
psl->size = 0;
}
⭕接口3检查结构体中的数组是否需要扩容(SLCheckCapacity)
请看代码与注释
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
if (tmp == NULL);
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity *= 2;
}
}
⭕接口4结构体销毁SLDestroy
销毁顺序表所开辟的空间防止内存泄漏
请看代码与注释
void SLDestroy(SL* psl)
{
assert(psl);
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
⭕接口5打印SLPrint
请看代码与注释
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
⭕接口6尾插SLPushBack
请看代码与注释
void SLPushBack(SL* psl, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);//检查是否需要扩容
psl->a[psl->size] = x;
psl->size++;
}
⭕接口7头插SLPushFront
1从第一个数据开始向后挪动会发生覆盖----不可取❌
2从最后一个数据开始向后挪动理想状态✅
请看代码与注释
void SLPushFront(SL* psl, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);
//挪动数据
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size++;
}
⭕接口8尾删SLPopBack
请看代码与注释
void SLPopBack(SL* psl)
{
//暴力检查
assert(psl->size > 0);
//温柔的检查
//if (psl->size == 0)
// return;
psl->size--;
}
⭕接口9头删SLPopFront
1从最后一个数据开始向前挪动会发生覆盖----不可取❌
1先从下标为 1 的数据开始向前挪动理想状态✅
请看代码与注释
void SLPushFront(SL* psl, SLDatatype x)
{
assert(psl);
SLCheckCapacity(psl);
//挪动数据
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size++;
}
⭕接口10在指定位置pos插入SLInsert
要实现这一功能我们依然需要一个end下标数据从后往前依次后挪直到pos下标移动完毕。另外别忘了检查容量。
请看代码与注释
void SLInsert(SL* psl, int pos, SLDatatype x)
{
assert(0 <= pos && pos <= psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[pos] = x;
psl->size++;
}
拓展了解了以上在指定位置插入的代码之后我们就可以在头插和尾插中复用该功能
请看代码
//尾插
void SLPushBack(SL* psl, SLDatatype x)
{
SLInsert(psl, psl->size, x);
}
//头插
void SLPushFront(SL* psl, SLDatatype x)
{
SLInsert(psl, 0, x);
}
这样写是不是非常滴香
⭕接口11在指定位置pos删除SLErase
要实现这一功能我们依然需要一个start下标数据从前往后依次前挪直到移动完毕。
请看代码与注释
void SLErase(SL* psl, int pos)
{
assert(0 <= pos && pos < psl->size);
int start = pos + 1;
while (start < psl->size)
{
psl->a[start - 1] = psl->a[start];
start++;
}
psl->size--;
}
拓展同样的了解了以上在指定位置删除的代码之后我们就可以在头删和尾删中复用该功能
请看代码
//尾删
void SLPopBack(SL* psl)
{
SLErase(psl, psl->size - 1);
}
//头删
void SLPopFront(SL* psl)
{
SLErase(psl, 0);
}
⭕接口12查找某一个数据的位置SLFind
找到返回下标没找到返回-1
请看代码与注释
int SLFind(SL* psl, SLDatatype x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
⭕接口13查找某一个数据的位置SLFind
请看代码与注释
void SLModify(SL* psl, int pos, SLDatatype x)
{
assert(0 <= pos && pos < psl->size);
psl->a[pos] = x;
}
⭕菜单
数据结构阶段不建议写菜单不便于调试本篇文章菜单写在下面的完整代码中的 Test.c文件和 main主函数中了需要的烙铁自行学习查看
四、完整代码
SeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
#include<assert.h>
//动态顺序表
typedef int SLDatatype; //数据类型
typedef struct SeqList
{
SLDatatype* a; //指向动态开辟的数组
int size; //存储的有效数据的个数
int capacity; //当前容量
}SL;
//初始化
void SLInit(SL* psl);
//销毁
void SLDestroy(SL* psl);
//检查是否需要扩容
void SLCheckCapacity(SL* psl);
//打印
void SLPrint(SL* psl);
//尾插
void SLPushBack(SL* psl, SLDatatype x);
//头插
void SLPushFront(SL* psl, SLDatatype x);
//尾删
void SLPopBack(SL* psl);
//头删
void SLPopFront(SL* psl);
//在pos位置插入
void SLInsert(SL* psl, int pos, SLDatatype x);
//在pos位置删除
void SLErase(SL* psl, int pos);
//查找找到返回下标没找到返回-1
int SLFind(SL* psl, SLDatatype x);
//修改
void SLModify(SL* psl, int pos, SLDatatype x);
SeqList.c
#include"SeqList.h"
//初始化
void SLInit(SL* psl)
{
assert(psl);
psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
if (psl->a == NULL)
{
perror("malloc fail");
return;
}
psl->capacity = 4;
psl->size = 0;
}
//销毁
void SLDestroy(SL* psl)
{
assert(psl);
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
//检查是否需要扩容
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
if (tmp == NULL);
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity *= 2;
}
}
//打印
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
//尾插
void SLPushBack(SL* psl, SLDatatype x)
{
//SLCheckCapacity(psl);
//psl->a[psl->size] = x;
//psl->size++;
SLInsert(psl, psl->size, x);
}
//头插
void SLPushFront(SL* psl, SLDatatype x)
{
//SLCheckCapacity(psl);
//挪动数据
//int end = psl->size - 1;
//while (end >= 0)
//{
// psl->a[end + 1] = psl->a[end];
// end--;
//}
//psl->a[0] = x;
//psl->size++;
SLInsert(psl, 0, x);
}
//尾删
void SLPopBack(SL* psl)
{
//暴力检查
//assert(psl->size > 0);
//温柔的检查
//if (psl->size == 0)
// return;
//psl->size--;
SLErase(psl, psl->size - 1);
}
//头删
void SLPopFront(SL* psl)
{
//暴力检查
//assert(psl->size > 0);
//int start = 1;
//while (start < psl->size)
//{
// psl->a[start - 1] = psl->a[start];
// start++;
//}
//psl->size--;
SLErase(psl, 0);
}
//在pos位置插入
void SLInsert(SL* psl, int pos, SLDatatype x)
{
assert(0 <= pos && pos <= psl->size);
SLCheckCapacity(psl);
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[pos] = x;
psl->size++;
}
//在pos位置删除
void SLErase(SL* psl, int pos)
{
assert(0 <= pos && pos < psl->size);
int start = pos + 1;
while (start < psl->size)
{
psl->a[start - 1] = psl->a[start];
start++;
}
psl->size--;
}
//查找找到返回下标没找到返回-1
int SLFind(SL* psl, SLDatatype x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SLModify(SL* psl, int pos, SLDatatype x)
{
assert(0 <= pos && pos < psl->size);
psl->a[pos - 1] = x;
}
Test.c
#include"SeqList.h"
//尾插测试
void TestSeqList1()
{
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);
SLPrint(&s);
SLDestroy(&s);
}
//头插测试
void TestSeqList2()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPrint(&s);
SLDestroy(&s);
}
//尾删测试
void TestSeqList3()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLDestroy(&s);
}
//头删测试
void TestSeqList4()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPushFront(&s, 8);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPrint(&s);
SLPopFront(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestroy(&s);
}
//指定位置插入测试
void TestSeqList5()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushFront(&s, 6);
SLPushFront(&s, 7);
SLPrint(&s);
SLInsert(&s, 2, 30);
SLPrint(&s);
SLDestroy(&s);
}
//指定位置删除测试
void TestSeqList6()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPushBack(&s, 6);
SLPrint(&s);
SLInsert(&s, 2, 30);
SLPrint(&s);
SLErase(&s, 2);
SLPrint(&s);
SLDestroy(&s);
}
//菜单
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("%d", &option);
int sum = 0;
int x = 0;
int y = 0;
int z = 0;
int pos = 0;
int w = 0;
int o = 0;
int p = 0;
switch (option)
{
case 1:
printf("请依次输入你要尾插的数据以-1结束\n");
scanf("%d", &sum);
while (sum != -1)
{
SLPushBack(&s, sum); // 1.尾插
scanf("%d", &sum);
}
break;
case 2:
SLPopBack(&s); // 2.尾删
break;
case 3:
scanf("%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("%d", &z);
y = SLFind(&s, z); // 7.查找某个数字的位置
printf("%d的位置在%d处 \n", z, y);
break;
case 9:
SLPrint(&s);
break;
case 8:
printf("请输入要修改序列的中的某个数据的下标>\n");
scanf("%d", &o);
printf("请输入要修改成什么>\n");
scanf("%d", &p);
SLModify(&s, o, p);
break;
default:
if (option == -1)
{
exit(0); // 退出程序
}
else
{
printf("输入错误请重新输入\n");
}
break;
}
} while (option != -1); // 退出程序
SLDestroy(&s);
return 0;
}
✅运行界面
这期内容些许复杂需要慢慢理解消化哦
总结
以上就是 【数据结构】顺序表—C语言版 的全部内容啦
本文章所在【数据结构与算法】专栏感兴趣的烙铁可以订阅本专栏哦
前途很远也很暗但是不要怕不怕的人面前才有路。
小的会继续学习继续努力带来更好的作品
创作写文不易还多请各位大佬uu们多多支持哦
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |