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