当前位置：首页 > news >正文

day18-数据结构引言

news 来源：原创 2025/7/20 17:59:51

一、概述

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

1.1 特定关系：

1. 逻辑结构 2.物理结构（在内存当中的存储关系）

逻辑结构	物理结构
集合，所有数据在同一个集合中，关系平等	顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
线性，数据和数据之间是一对一的关系	顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
树，一对多	链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续
图，多对多	链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续

1.2 基本概念

1.数据：具有输入输出特性；具有一定的操作

2.数据项：给变量赋予一定的含义

3.数据对象：数据元素的集合

4.数据的类型，ADT(abstract datatype) 抽象化数据类型：数学模型（如，结构体）+ 操作
        是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
       原子类型，int，char，float
       结构类型，sturct， union，
5. 程序 = 数据 + 算法
（1）算法，是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。
   （2）算法的特征，
            1，输入，输出特性，输入时可选的，输出时必须的。
            2，有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
            3，确定性，同一个输入，会得到唯一的输出。
            4，可行性，每一个步骤都是可以实现的。
        （3）算法的设计，
            1，正确性，
a.语法正确
b.合法的输入能得到合理的结果。
c.对非法的输入，给出满足要求的规格说明
d.对精心选择，甚至刁难的测试都能正常运行，结果正确
           2，可读性，便于交流，阅读，理解
           3，健壮性，输入非法数据，能进行相应的处理，而不是产生异常
           4，高效，存储低，效率高

1.3 时间复杂度

定义：算法时间复杂度：即执行这个算法所花时间的度量

计算方法：

        1，用常数1 取代运行时间中的所有加法常数
       2，在修改后的运行函数中，只保留最高阶项。
       3，如果最高阶存在且不是1，则取除这个项相乘的常数。

如：2n+3, O(n)

二、线性表

定义：零个或多个数据元素的有限序列
元素之间是有顺序的。如果存在多个元素，第一个元素无前驱，最后一个没有后继，其他的元素只有一个前驱和一个后继。
当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

2.1 线性表的常规操作 ADT

2.1.1 顺序表

表头结构：

typedef struct list {DATATYPE *head;int tlen;int clen;
}SeqList//顺序表;

其中，Tlen(total length) 为总长度 clen(current length)为现长度

sudo reboot;//重启虚拟机

在虚拟机中安装vscode：首先，下载安装包；其次，进行解压，输入命令：

sudo dpkg -i cod按Tab自动补全；

一、 概述