第2章 简单数据结构.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,零基础学算法,第,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,后进先出结构：栈,性格决定命运,专注成就人生,