《简单数据结构》PPT课件.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.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 后进先出结构：栈,性格决定命运,专注成就人生,