《C语言序设计》第一章 数据结构（冯毅）

Date: 24 February 2021 IT Education Training 数据结构 Neusoft

Date:24 February 2021 IT Education & Training 数据结构

Date: 24 February 2021 IT Education Training 第一部分数据结构 基础知识

Date:24 February 2021 IT Education & Training 第一部分 数据结构 基础知识

Date: 24 February 2021 IT Education Training 数据结构 数据结构:是一门研究非数值计算的程序设计问题 中计算机操作对象以及它们之间的关系和操作等等 的学科

Date:24 February 2021 IT Education & Training 数据结构 • 数据结构：是一门研究非数值计算的程序设计问题 中计算机操作对象以及它们之间的关系和操作等等 的学科

Date: 24 February 2021 IT Education Training 基本概念 数据:是对客观事物的符号表示,在计算机科学中 是指所有能输入到计算机中并被计算机程序处理的 符号的总称。 数据元素:是数据的基本单位,在计算机程序中通 常作为一个整体进行考虑和处理。 数据结构:是相互之间存在一种或多种特定关系的 数据元素的集合

Date:24 February 2021 IT Education & Training 基本概念 • 数据：是对客观事物的符号表示，在计算机科学中 是指所有能输入到计算机中并被计算机程序处理的 符号的总称。 • 数据元素：是数据的基本单位，在计算机程序中通 常作为一个整体进行考虑和处理。 • 数据结构：是相互之间存在一种或多种特定关系的 数据元素的集合

Date: 24 February 2021 IT Education Training 数据结构的三个方面: 线性表 线性结构栈 队 数据的逻辑结构 树形结构 非线性结构 图形结构 顺序存储 数据的存储结枘 链式存储 数据的远犷:检索、排序、插入、删除、修改等

Date:24 February 2021 IT Education & Training 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面：

Date: 24 February 2021 IT Education Training 主要内容 1线性表以及其应用 1.2栈、队列 1.3排序、查找

Date:24 February 2021 IT Education & Training 主要内容 • 1.1 线性表以及其应用 • 1.2 栈、队列 • 1.3 排序、查找

Date: 24 February 2021 IT Education Training 1.1线性表以及其应用(1) 线性表 分为静态线性表和动态线性表 静态线性表 特征:表中节点的存储是连续的,占用一块连续存储区,一般节 点的数量是固定的 数据1|数据2数据3 数据n1|数据n 后继2后继:3后继4 后继nend typedef struct Data t data;∥数据域 Int next;∥后继域 i Node t, *PNode t ∥提供的操作有 :初始化、插入、删除等

Date:24 February 2021 IT Education & Training 1.1 线性表以及其应用（1） • 线性表 –分为静态线性表和动态线性表 –静态线性表 • 特征：表中节点的存储是连续的，占用一块连续存储区，一般节 点的数量是固定的； • 存储表示如下图 • 数据结构如下图 数据1 后继:2 数据2 后继:3 数据3 后继:4 …… …… 数据n-1 后继:n 数据n end typedef struct { Data_t data; //数据域 int next; //后继域 }Node_t, *PNode_t; //提供的操作有 ：初始化、插入、删除等

Date: 24 February 2021 IT Education Training 线性表 顺序存储结构 特定:借助元素在存储器中的相对位置(即,物理位 置相邻)来表示数据元素之间的逻辑关系。 缺点 插入、删除时,需移动大量数据。 次性分配内存空间。 表的容量难以扩充

Date:24 February 2021 IT Education & Training 线性表 • 顺序存储结构 特定：借助元素在存储器中的相对位置（即，物理位 置相邻）来表示数据元素之间的逻辑关系。 缺点： 插入、删除时，需移动大量数据。 一次性分配内存空间。 表的容量难以扩充

Date: 24 February 2021 IT Education Training 0 5 MaxSize -1 da ata a a a a a 5 size= 6 图顺序存储结构内存结构示意图

Date:24 February 2021 IT Education & Training 图顺序存储结构内存结构示意图

Date: 24 February 2021 IT Education Training 1.1线性表以及其应用(2) 动态线性表 特征:表中节点的存储是不连续的,一般节点的数量是不固定的; 存储表示如下图 数据1数据2数据3 后继H后继十后继 r 数据n-1-数据n 后继 en 数据结如下图 typedef struct i Data t data;∥数据域 Node t*next;∥后继域 , Node t, "PNode t ∥提供的操作有 初始化、插入、删除等

Date:24 February 2021 IT Education & Training 1.1 线性表以及其应用（2） –动态线性表 • 特征：表中节点的存储是不连续的，一般节点的数量是不固定的； • 存储表示如下图 • 数据结构如下图 typedef struct { Data_t data; //数据域 Node_t* next; //后继域 }Node_t, *PNode_t; //提供的操作有 ：初始化、插入、删除等。 数据1 后继 数据2 后继 数据3 后继 …… …… 数据n-1 后继 数据n end