目录

前言:        

顺序表

动态顺序表的实现

代码总览:


前言:
        

数据结构是由“数据”和“结构”两词组合而来。

        什么是数据?

常见的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息(姓名、性别、年龄、学历等

等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据

        什么是结构?

当我们想要使⽤大量使⽤同⼀类型的数据时,通过⼿动定义⼤量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起,结构也可以理解为组织数据的方式

简而言之

  1. 能够存储数据(如顺序表、链表等结构)
  2. 存储的数据能够方便查找

那么为什么需要数据结构呢?

假定数组有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<stdio.h>
#include<stdlib.h>
#include<assert.h>
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 < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("\n%d %d\n", 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 < p->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 < p->size - 1; i++)
	{
		p->arr[i] = p->arr[i + 1];
	}
	p->size--;
}

测试:

顺序表查找

现在我们需要在顺序表中查找数据

这里也可以写函数返回数据的下标

代码:

//查找数据
void SLFind(SL* p, Type f)
{
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == f)
		{
			printf("查找的数据下标为:%d\n", i);
			return;
		}
	}
	printf("所查找的数据不存在\n");
}

测试:

到这里,顺序表的知识就完成了,学完这些,我们也要写顺序表的实践,就是通讯录——在下一篇进行实现。

代码总览:

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
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 < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("\n");
	//printf("%d %d\n", 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 < p->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 < p->size - 1; i++)
	{
		p->arr[i] = p->arr[i + 1];
	}
	p->size--;
}
//查找数据
void SLFind(SL* p, Type f)
{
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == f)
		{
			printf("查找的数据下标为:%d\n", 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;
}

制作不易,感到有帮助的可以一键三连支持一下,如果有错误的地方,也请指出!!!

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部