第2章简单数据结构.ppt

零基础学算法,第2章：简单数据结构,课程安排,2.1 最简单的结构：线性表 什么叫线性表 操作顺序表 操作链表 实例：用链表制作通信录 2. 2 先进先出结构：队列 什么是队列 操作队列 循环队列的操作 实例：银行排号程序 2.3 后进先出结构：栈 什么是栈 操作栈 实例：算术表达式求值,2.1 最简单的结构：线性表,2.1.1 什么叫线性表 2.1.2 操作顺序表 2.1.3 操作链表 2.1.4 实例：用链表制作通信录,2.1 最简单的结构：线性表,线性表数据结构具有以下特征： 有且只有一个“首元素”； 有且只有一个“末元素”； 除末元素之外，其余元素均有惟一的后继元素； 除首元素之外，其余元素均有惟一的前驱元素。 对于线性表，主要可进行以下操作： 添加结点； 插入结点； 删除结点； 查找结点； 遍历结点； 统计结点数。,2.1.1 什么叫线性表,1定义顺序队列结构 2初始化队列 3获取队列状态 4入队操作 5出队操作 6获取队头元素,2.1.2 操作顺序表,2.1 最简单的结构：线性表,2.1.3 操作链表,1定义链表的结构 2添加结点至尾部 3添加结点至首部 4插入结点,2.1 最简单的结构：线性表,5查找结点 6删除结点 7链表的长度 8测试链表操作,2.1.4 实例：用链表制作通信录,1定义通信录结构 2编写显示联系人信息模块 3编写添加联系人模块 4编写查找联系人模块 5编写删除联系人模块 6编写主模块,2.1 最简单的结构：线性表,2.2.1 什么是队列 2.2.2 操作队列 2.2.3 循环队列的操作 2.2.4 实例：银行排号程序,2.2 先进选出结构：队列,2.2 先进选出结构：队列,队列是一种特殊的线性表，只允许在表的前端进行删除操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。当队列中没有元素时，称为空队列。 对于队列这种结构，其操作很简单，主要有以下几种： 初始化队列：创建一个队列。 进队列：将一个元素添加到队尾（相当于到队列最后排队等候）。 出队列：将队头的元素取出，同时删除该元素，使后一个元素成为队头。 获取队列第1个元素：将队头的元素取出，不删除该元素（队头仍然是该元素）。 获取队列长度：根据队头、队尾计算出队列中元素的数量。,2.2.1 什么是队列,2.2 先进选出结构：队列,1定义顺序队列结构 2初始化队列 3获取队列状态 4入队操作 5出队操作 6获取队头元素,2.2.2 操作队列,2.2 先进选出结构：队列,2.2.3 循环队列,2.3 后进先出结构：栈,2.3.1 什么是栈 2.3.2 操作栈 2.3.3 实例：算术表达式求值,栈是一种线性表的特殊表现形式，与队列的“先进先出”不同，栈是按照“后进先出”（Last In Firt Out，LIFO）的原则处理数据。 栈的基本操作只有两个： 入栈（Push）：即将数据保存到栈顶。进行该操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。 出栈（Pop）：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。,2.3.1 什么是栈,2.3 后进先出结构：栈,1定义顺序栈的结构 2初始化栈 3判断栈的状态 4入栈操作 5出栈操作 6获取栈顶元素 7测试栈的操作,2.3.2 操作栈,2.3 后进先出结构：栈,对于算术表达式的求值，主要就是解决算术运算符的优先级问题，有以下规则： 先进行乘除运算，再进行加减运算（乘除优先级大于加减）； 对于相同优先级的运算符，从左向右计算； 若要改变优先级，可使用括号。对有括号的表达式，先计算括号内，再计算括号外。 在表达式的计算过程中，既要保存操作数，又要保存运算符。这时，可定义两个栈，一个用来保存操作数，一个用来保存运算符。,2.3.3 实例：算术表达式求值,2.3 后进先出结构：栈,性格决定命运, 专注成就人生,