三个问题:

  • 数据结构和数据类型有什么区别?
  • 什么是算法?算法的特性有哪些?
  • 若逻辑结构相同但存储结构不同则为不同的数据结构。这样说法对吗?

逻辑结构相同但存储不同,可以是不同的数据结构。例如,线性表的逻辑结构属于线性结构,采用顺序存储结构为顺序表,而采用链式存储结构称为线性链表。

为什么要有数据结构?

计算机想要解决一个具体的问题一般需要三步

  • 寻找数学模型(实质为分析问题),提取操作对象,用数学语言描述 PS:数据结构在这一层
  • 设计对应算法
  • 编写程序,运行调试

大部分的现实情况是所需解决的问题没办法用数学方程解决问题,这些复杂的问题以及复杂的数据关系就需要用数据结构间的关系来解决问题。
在课程中主要所说的 数据 指的是数据元素的集合, 数据元素的集合也叫数据对象数据元素 是数据的最 基本单位 ,如一个班每个学生的基本信息就是数据元素,这个班学生的信息的详细内容就是 数据项,例如一个学生的年龄、性别等。

  • 数据对象
  • 数据元素
  • 数据项

    而 数据元素 之间的关系就叫 数据结构
    有了数据结构,一些很难用数学方程来分析的问题就可以用数据间的关系进行解决。

    数据结构的概念

    数据结构包括逻辑结构存储结构数据运算三部分。

    逻辑结构

    逻辑结构指的是单纯数据中的逻辑关系,这种关系是独立于计算机的,是单纯的从现实中发现的数据关系。

    表示

  • 图标表示

    1. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/1530465/1611891485275-65ef1011-3fc7-4a7e-8d0b-74d7ed6b72d9.png#align=left&display=inline&height=225&margin=%5Bobject%20Object%5D&name=image.png&originHeight=449&originWidth=983&size=73278&status=done&style=none&width=491.5)
  • 二元组表示

B=(D,R) B代表是一种数据逻辑结构,由数据元素集合D以及D上二元关系的集合R组成
D={di|1≤i≤n,n≥0}
R={r|1≤j≤m,m≥0}

  • 集合

    类型

    逻辑结构的类型又很多种,但归总下来有以下三种

  • 线性结构

线性结构是指数据间一对一的关系,特点是:

  1. 1. 开始元素 以及 结束元素 **唯一**,
  2. 1. 除开始和结尾元素外,其余元素都仅有 一个 前驱、后继元素。

例如上图的学生表数据,每个学号仅有一个前驱后继,且

  • 树形结构

树形结构是指数据见 一对多 的关系,特点是:

  1. 1. 除了开始元素外,每个元素仅有 一个 前驱元素
  2. 1. 除了终端元素外,每个元素又 一个 或者 多个 后继元素,如下图

image.png

  • 图形结构

图形结构是 多对多 关系,特点是每个元素的前驱和后继元素的个数是 任意的
树形结构和图形结构统称为 非线性结构 ,线性结构是树形结构的 特殊情况 ,树形结构是图形结构的 特殊情况

存储结构

数据的逻辑结构在计算机中表示出来就叫数据的 存储结构 ,通常要求不仅把数据内容存起来,还要把数据间的逻辑关系存下来。常用的数据结构有4种存储结构类型。

  • 顺序存储

用一组连** 的存储单元存放所有的数据元素,逻辑上相邻的元素存储中也相连。
优点是效率高,
逻辑关系 没有占用额外的存储空间,可以进行 随机存储**
缺点是不方便数据修改

  1. struct{
  2. int NO; //存储学号
  3. char name[8]; //名字
  4. char sex[2]; //性别
  5. char class[4]; //班级
  6. }Stud[7]={{1,"张三","男","9901"}.....{5,"王平","女","9901"};

image.png

  • 链式存储

链式存储的每个元素用 内存结点 存储,他们不一定连续,不用占用一整块的空间。
但是每个节点都需要附加指针域来存放相邻节点的存储地址。
优点是方便数据修改,增删改查时只用修改相应节点的指针域,不用移动点。
缺点是空间利用率低。同样也不能随机存储。

  1. typedef struct Studenode{
  2. int NO; //存储学号
  3. char name[8]; //名字
  4. char sex[2]; //性别
  5. char class[4]; //班级
  6. struct Studnode *next; //存储指向下一个学生节点的指针
  7. }StudType; //节点类型

image.png

  • 索引存储

该种+存储指除了存储数据元素的信息外还附加建立了一个索引表,索引项是由关键字和地址构成。

  • 哈希存储

用元素的关键字通过哈希函数直接就算出一个值,这个值就是这个元素的储存地址。
优点是查找快,但这种方法只存元素,不存元素间的逻辑关系。

数据运算

数据运算就是对数据实时操作。
常见的有检索、插入、删除、更新、排序等。数据运算最终在对应的 存储结构上 用 算法实现 。因此数据运算分

  • 运算定义

对运算功能描述,是抽象的,基于逻辑结构的

  • 运算实现

程序员完成运算的实现算法,是具体的,基于存储结构
这种定义和实现相互分离的做法体现了软件工程的思想,有利于软件开发。

数据类型抽象数据类型

数据类型

在进行程序设计时需要定义数据类型,例如整形、浮点型。。。
数据类型 是一组性质相同的值的集合,是某种程序设计语言中已经实现的数据结构。
C中有基本数据类型、指针类型、结构体类型、共用体类型。
在使用这些定义时,一般有两种主要的存储空间分配方式,第一种时静态存储空间分配,静态空间分配的存储单元会一直保持不变,一直到程序结束。
第二种为动态的空间分配,用malloc()/free()函数进行分配
使用动态分配时需要及时的free()空间,不然会造成内存泄漏。

抽象数据类型

这是从现实问题种抽象出来的逻辑数据结构及运算,不需要考虑具体的存储结构和运算的具体实现算法。
一般用(D,S,P)表示,D是数据对象、S是D上的关系集,P是D中数据运算的基本运算集。

  1. ADT抽象数据类型名{
  2. 数据对象:数据对象的声明
  3. 数据关系:数据关系的声明
  4. 基本运算:基本运算的声明
  5. }
  6. 基本运算的声明:基本运算名:运算功能描述

❓数据结构和数据类型有什么区别?

数据结构是数据元素之间的关系,而数据类型更是数据项的总称
一、性质不同
1、数据结构:是计算机存储、组织数据的方zhi式;指相互之间存在一种或多种特定关系的数据元素的集合。
2、数据类型:是用一组属性描述其定义、标识、表示和允许值的数据单元。
二、作用不同
1、数据结构:通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。
2、数据类型:若干具有相关性的数据元按一定的次序组成一个整体结构。
三、特点不同
1、数据结构:数据结构往往同高效的检索算法和索引技术有关。
2、数据类型:数据元基本模型中,对象类对应于数据模型中的实体、特性和表示对应于数据模型中的属性

算法

算法是对特定问题求解步骤的描述,是 指令 的有限序列。每个指令表示计算机的一个或者多个操作

算法的五个特性

  • 有穷性
  • 确定性
  • 可行性
  • 有输入
  • 有输出

    算法的设计目标

    • 正确性
    • 可使用性
    • 可读性
    • 健壮性
    • 高效率与低存储量需求

      算法的描述

      balabala

      ❓什么是算法?算法的特性有哪些?

      算法是对特定问题求解步骤的描述,是指令的有限序列,其中每一条指令表示一个或多个操作。算法具有五个重要特性:有穷性、确定性、可行性、输入和输出。

      算法分析

      旨在分析算法占用计算机资源的多少,主要是CPU时间和内存空间,有事后统计法事前估计法

      时间复杂度

      一个算法由3种控制结构原操作构成。执行时间却决于控制结构和原操作的综合效果 。当算法中原操作次数越少,执行时间越少
      所以算法的时间复杂度等同于有关 时间规模 n的函数T(n)。
      求出T(n)后进一步用时间复杂度表示,

      空间复杂度