数据结构.ppt

IT Education & TrainingDate:2016年11月5日星期六数据结构IT Education & TrainingDate:2016年11月5日星期六第一部分数据结构基础知识IT Education & TrainingDate:2016年11月5日星期六数据结构?数据结构:是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。IT Education & TrainingDate:2016年11月5日星期六基本概念?数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。?数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。?数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。IT Education & TrainingDate:2016年11月5日星期六数据的逻辑结构数据的存储结构数据的运算:检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面:IT Education & TrainingDate:2016年11月5日星期六主要内容? 线性表以及其应用? 栈、队列? 排序、查找IT Education & TrainingDate: 线性表以及其应用(1)?线性表–分为静态线性表和动态线性表–静态线性表?特征:表中节点的存储是连续的,占用一块连续存储区,一般节点的数量是固定的;?存储表示如下图?数据结构如下图数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedef struct { Data_t data; //数据域 int next; //后继域}Node_t, *PNode_t;//提供的操作有:初始化、插入、删除等。IT Education & TrainingDate:2016年11月5日星期六线性表?顺序存储结构特定:借助元素在存储器中的相对位置(即,物理位置相邻)来表示数据元素之间的逻辑关系。缺点:插入、删除时,需移动大量数据。一次性分配内存空间。表的容量难以扩充。IT Education & TrainingDate:2016年11月5日星期六图顺序存储结构内存结构示意图IT Education & TrainingDate: 线性表以及其应用(2)–动态线性表?特征:表中节点的存储是不连续的,一般节点的数量是不固定的;?存储表示如下图?数据结构如下图typedef struct { Data_t data; //数据域 Node_t* next; //后继域}Node_t, *PNode_t;//提供的操作有:初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nend