第2章 简单数据结构ppt课件.ppt

《第2章 简单数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零基础学算法第2章：简单数据结构课程安排2.1最简单的结构：线性表什么叫线性表操作顺序表操作链表实例：用链表制作通信录2.2先进先出结构：队列什么是队列操作队列循环队列的操作实例：银行排号程序2.3后进先出结构：栈什么是栈操作栈实例：算术表达式求值2.1最简单的结构：线性表2.1.1什么叫线性表2.1.2操作顺序表2.1.3操作链表2.1.4实例：用链表制作通信录2.1最简单的结构：线性表线性表数据结构具有以下特征：有且只有一个“首元素”；有且只有一个“末元素”；除末元素之外，其余元素均有惟一的后继元素；除首元素之外，其余元素

2、均有惟一的前驱元素。对于线性表，主要可进行以下操作：添加结点；插入结点；删除结点；查找结点；遍历结点；统计结点数。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．编写添加联系人模

3、块4．编写查找联系人模块5．编写删除联系人模块6．编写主模块2.1最简单的结构：线性表2.2.1什么是队列2.2.2操作队列2.2.3循环队列的操作2.2.4实例：银行排号程序2.2先进选出结构：队列2.2先进选出结构：队列队列是一种特殊的线性表，只允许在表的前端进行删除操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。当队列中没有元素时，称为空队列。对于队列这种结构，其操作很简单，主要有以下几种：初始化队列：创建一个队列。进队列：将一个元素添加到队尾（相当于到队列最后排队等候）。出队列：将队

4、头的元素取出，同时删除该元素，使后一个元素成为队头。获取队列第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实例：算术表达式求值栈是一种线性表的特殊表现形式，与队列的“先进先出”不同，栈是按照“后进先出”

5、（LastInFirtOut，LIFO）的原则处理数据。栈的基本操作只有两个：入栈（Push）：即将数据保存到栈顶。进行该操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。出栈（Pop）：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。2.3.1什么是栈2.3后进先出结构：栈1．定义顺序栈的结构2．初始化栈3．判断栈的状态4．入栈操作5．出栈操作6．获取栈顶元素7．测试栈的操作2.3.2操作栈2.3后进先出结构：栈对于算术表达式的求值，主要就是解决算术运算符的优先级问题，有以下

6、规则：先进行乘除运算，再进行加减运算（乘除优先级大于加减）；对于相同优先级的运算符，从左向右计算；若要改变优先级，可使用括号。对有括号的表达式，先计算括号内，再计算括号外。在表达式的计算过程中，既要保存操作数，又要保存运算符。这时，可定义两个栈，一个用来保存操作数，一个用来保存运算符。2.3.3实例：算术表达式求值2.3后进先出结构：栈性格决定命运,专注成就人生