csdn推荐
目录
前言:
数据结构是由“数据”和“结构”两词组合而来。
什么是数据?
常见的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息(姓名、性别、年龄、学历等
等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据
什么是结构?
当我们想要使⽤大量使⽤同⼀类型的数据时,通过⼿动定义⼤量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起,结构也可以理解为组织数据的方式
简而言之
能够存储数据(如顺序表、链表等结构) 存储的数据能够方便查找
那么为什么需要数据结构呢?
假定数组有10个空间,已经使用了5个,向数组中插入数据步骤:
求数组的长度,求数组的有效数据个数,向下标为数据有效个数的位置插入数据(注意:这里是
否要判断数组是否满了,满了还能继续插⼊吗).....
假设数据量非常庞大,频繁的获取数组有效数据个数会影响程序执行效率。
结论:
最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。
顺序表
线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串等
线性表在了逻辑上是线性结构,也就是说是一条直线。但是在物理结构上并不一定是连续的,线性表在物理结构上存储时,通常以数组和链式结构的形式存储。
知识补充:
逻辑结构和物理结构
1.逻辑结构:
所谓逻辑结构就是数据与数据之间的关联关系,准确的说是数据元素之间的关联关系。
注:所有的数据都是由数据元素构成,数据元素是数据的基本构成单位。而数据元素由多个数据项构成。
逻辑结构有四种基本类型:集合结构、线性结构、树状结构和网络结构。也可以统一的分为线性结构和非线性结构。
2.物理结构:
数据的物理结构就是数据存储在磁盘中的方式。官方语言为:数据结构在计算机中的表示(又称映像)称为数据的物理结构,或称存储结构。它所研究的是数据结构在计算机中的实现方法,包括数据结构中元素的表示及元素间关系的表示。
而物理结构一般有四种:顺序存储,链式存储,散列,索引
顺序表
顺序表的底层结构就是数组,对数组的封装,实现了常用的增删改查等接口
顺序表可以分为静态顺序表和动态顺序表
静态顺序表
静态顺序表是使用定长的数组来存储元素
#define N 10
typedef int Type;
//静态顺序表
struct SeqList
{
Type arr[N];//定长数组
int size;//有效数据个数
};
使用动态顺序表缺陷:空间给小了不够用,空间给多了造成空间浪费
动态顺序表
动态顺序表的实现
静态顺序表是定长数组,而动态顺序表是可增容的,不会浪费空间也不会出现空间不够的场景,这里来实现动态顺序表存储整形数据:
首先就是顺序表的一些功能
这里将其写入SeqList.h 的头文件中
SeqList.h头文件
#pragma once
#include
#include
#include
typedef int Type;
typedef struct SeqList//动态顺序表
{
Type* arr;
int size;
int num;
}SL;
//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
int SLFind(SL* p, Type f);
要存储一些数据,顺序表具备以上功能(对于整型)
顺序表初始化
顺序表初始化,其实就是将动态顺序表中指针置为NULL,有效数据和空间容量置为0;
代码如下:
// 初始化
void SLInit(SL* p)
{
p->arr = NULL;
p->size = 0;
p->num = 0;
}
在初始化完成后s中的数据。
顺序表销毁
在使用完顺序表后,就要销毁顺序表,因为动态顺序表内存是动态开辟的,所以需要对动态内存进行释放,并将有效数据和空间容量个数置为0;
代码如下:
//销毁
void SLDesTroy(SL* p)
{
if (p->arr != NULL)
{
free(p->arr);
p->arr = NULL;
}
p->size = 0;
p->num = 0;
}
顺序表销毁之后,指针置为NULL,有效数据和空间容量的为0;
顺序表输出
现在如果顺序表中有数据,我们需要查看数据,就要用到顺序表的输出
代码如下:
//输出
void SLPrint(SL* p)
{
for (int i = 0; i size; i++)
{
printf("%d ", p->arr[i]);
}
printf("n%d %dn", p->size, p->num);
}
测试看一下输出
这里将有效数字和空间容量也输出出来以便查看,下面插入数据以后就不在进行输出了
顺序表扩容
我们要像顺序表中插入数据,这必然会涉及到扩容的问题
代码如下:
//顺序表扩容
void SLExps(SL* p)
{
int num = (p->num == 0) ? 4 : 2 * p->num;
Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));
assert(tmp);
p->arr = tmp;
p->num = num;
}
如果首次扩容,即p->num等于0,这样习惯给它赋值成4,以后每次扩容以倍数增加(这里使用2倍,也可以使用3倍)。
扩容以后再测试看一下输出结果(查看有效数据和空间容量)
这里首次扩容,空间容量为4。
注:扩容主要使用在插入数据判断空间大小不够时
顺序表头插
现在需要从顺序表头部(起始位置)插入数据,这里就需要将有效数据向后移动一位,再进行插入数据以防数据丢失。
当然,再插入数据之前需要判断空间是否足够
代码如下:
//从头部插入数据
void SLAddHand(SL* p, Type x)
{
if (p->size >= p->num)
{
SLExps(p);
}
for (int i = p->size; i > 0; i--)
{
p->arr[i] = p->arr[i - 1];
}
p->arr[0] = x;
p->size++;
}
测试以下代码是否正确
顺序表头删
从起始位置删除数据,就需要把有效数据向前移动一位,并且有效数据个数-1;
代码如下:
//从头部删除数据
void SLDelHand(SL* p)
{
for (int i = 0; i size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
p->size--;
}
测试:
顺序表尾插
现在从尾部插入数据,很简单直接在数据末尾插入数据,然后有效数据+1;
当然,也需要进行判断空间是否足够
代码如下:
//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{
if (p->size >= p->num)
{
SLExps(p);
}
p->arr[p->size] = x;
p->size++;
}
测试:
顺序表尾删
从尾部删除数据很简单马,可以直接让有效数据个数-1;
代码如下:
//从尾部删除数据
void SLDelEnd(SL* p)
{
p->size--;
}
测试:
顺序表任意位置插入
从任意位置插入数据,需要将指定位置数据以后的有效数据向后移动一位,再进行插入
代码:
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{
if (p->size >= p->num)
{
SLExps(p);
}
for (int i = p->size; i > t; i--)
{
p->arr[i] = p->arr[i - 1];
}
p->arr[t] = x;
p->size++;
}
这里就不输出有效数字个数和空间容量了
测试:
顺序表任意数据删除
从任意位置删除数据,将该位置后的数据向前移动一位
代码如下:
//从任意位置删除数据
void SLDeleve(SL* p, int t)
{
for (int i = t; i size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
p->size--;
}
测试:
顺序表查找
现在我们需要在顺序表中查找数据
这里也可以写函数返回数据的下标
代码:
//查找数据
void SLFind(SL* p, Type f)
{
for (int i = 0; i size; i++)
{
if (p->arr[i] == f)
{
printf("查找的数据下标为:%dn", i);
return;
}
}
printf("所查找的数据不存在n");
}
测试:
到这里,顺序表的知识就完成了,学完这些,我们也要写顺序表的实践,就是通讯录——在下一篇进行实现。
代码总览:
SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
typedef int Type;
typedef struct SeqList//动态顺序表
{
Type* arr;
int size;
int num;
}SL;
//动态顺序表
// 初始化
void SLInit(SL* p);
//销毁
void SLDesTroy(SL* p);
//输出
void SLPrint(SL* p);
//顺序表扩容
void SLExps(SL* p);
//从头部插入数据
void SLAddHand(SL* p, Type x);
//从头部删除数据
void SLDelHand(SL* p);
//从尾部插入数据
void SLAddEnd(SL* p, Type x);
//从尾部删除数据
void SLDelEnd(SL* p);
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t);
//从任意位置删除数据
void SLDeleve(SL* p, int t);
//查找数据
void SLFind(SL* p, Type f);
SeqList.c
#include"SeqList.h"
// 初始化
void SLInit(SL* p)
{
p->arr = NULL;
p->size = 0;
p->num = 0;
}
//销毁
void SLDesTroy(SL* p)
{
if (p->arr != NULL)
{
free(p->arr);
p->arr = NULL;
}
p->size = 0;
p->num = 0;
}
//输出
void SLPrint(SL* p)
{
for (int i = 0; i size; i++)
{
printf("%d ", p->arr[i]);
}
printf("n");
//printf("%d %dn", p->size, p->num);
}
//顺序表扩容
void SLExps(SL* p)
{
int num = (p->num == 0) ? 4 : 2 * p->num;
Type* tmp = (Type*)realloc(p->arr, num * sizeof(Type));
assert(tmp);
p->arr = tmp;
p->num = num;
}
//从头部插入数据
void SLAddHand(SL* p, Type x)
{
if (p->size >= p->num)
{
SLExps(p);
}
for (int i = p->size; i > 0; i--)
{
p->arr[i] = p->arr[i - 1];
}
p->arr[0] = x;
p->size++;
}
//从头部删除数据
void SLDelHand(SL* p)
{
for (int i = 0; i size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
p->size--;
}
//从尾部插入数据
void SLAddEnd(SL* p, Type x)
{
if (p->size >= p->num)
{
SLExps(p);
}
p->arr[p->size] = x;
p->size++;
}
//从尾部删除数据
void SLDelEnd(SL* p)
{
p->size--;
}
//从任意位置插入数据
void SLAddeve(SL* p, Type x, int t)
{
if (p->size >= p->num)
{
SLExps(p);
}
for (int i = p->size; i > t; i--)
{
p->arr[i] = p->arr[i - 1];
}
p->arr[t] = x;
p->size++;
}
//从任意位置删除数据
void SLDeleve(SL* p, int t)
{
for (int i = t; i size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
p->size--;
}
//查找数据
void SLFind(SL* p, Type f)
{
for (int i = 0; i size; i++)
{
if (p->arr[i] == f)
{
printf("查找的数据下标为:%dn", i);
return;
}
}
printf("所查找的数据不存在n");
}
测试代码(test.c)
#include"SeqList.h"
void Test()
{
SL s;
//初始化
SLInit(&s);
//SLPrint(&s);//打印
//扩容
//SLExps(&s);
//SLPrint(&s);//打印
头插
//SLAddHand(&s, 520);
//SLAddHand(&s, 1314);
//SLPrint(&s);//打印
头删
//SLDelHand(&s);
//SLPrint(&s);
尾插
//SLAddEnd(&s, 1314);
//SLAddEnd(&s, 520);
//SLPrint(&s);
尾删
//SLDelEnd(&s);
//SLPrint(&s);
//头插
SLAddHand(&s, 1);
SLAddHand(&s, 2);
SLAddHand(&s, 3);
SLAddHand(&s, 4);
//4 3 2 1
//任意位置插入
SLAddeve(&s, 9, 2);
//4 3 9 2 1
SLPrint(&s);
//任意位置删除
SLDeleve(&s, 2);
SLPrint(&s);
//4 3 2 1
SLFind(&s, 9);
SLFind(&s, 2);
//销毁
SLDesTroy(&s);
}
int main()
{
Test();
return 0;
}
制作不易,感到有帮助的可以一键三连支持一下,如果有错误的地方,也请指出!!!
文章来源:https://blog.csdn.net/LH__1314/article/details/140085584
微信扫描下方的二维码阅读本文
暂无评论内容