当前位置:首页 >> IT/计算机 >>

第2章 简单数据结构


零基础学算法

第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 什么叫线性表
线性表数据结构具有以下特征: – – – – 有且只有一个“首元素”; 有且只有一个“末元素”; 除末元素之外,其余元素均有惟一的后继元素; 除首元素之外,其余元素均有惟一的前驱元素。 。

对于线性表,主要可进行以下操作: – 添加结点; – 插入结点; – 删除结点; – 查找结点; – 遍历结点; – 统计结点数。

2.1 最简单的结构:线性表 最简单的结构:
2.1.2 操作顺序表
? ? ? ? ? ? 1.定义顺序队列结构 . 2.初始化队列 . 3.获取队列状态 . 4.入队操作 . 5.出队操作 . 6.获取队头元素 .

2.1 最简单的结构:线性表 最简单的结构:
2.1.3 操作链表

? ? ? ?

1.定义链表的结构 . 2.添加结点至尾部 . 3.添加结点至首部 . 4.插入结点 .

? ? ? ?

5.查找结点 . 6.删除结点 . 7.链表的长度 . 8.测试链表操作 .

2.1 最简单的结构:线性表 最简单的结构:
2.1.4 实例:用链表制作通信录 实例:
? ? ? ? ? ? 1.定义通信录结构 . 2.编写显示联系人信息模块 . 3.编写添加联系人模块 . 4.编写查找联系人模块 . 5.编写删除联系人模块 . 6.编写主模块 .

2.2 先进选出结构:队列 先进选出结构:

? ? ? ?

2.2.1 2.2.2 2.2.3 2.2.4

什么是队列 操作队列 循环队列的操作 实例: 实例:银行排号程序

2.2 先进选出结构:队列 先进选出结构:
2.2.1 什么是队列
队列是一种特殊的线性表,只允许在表的前端进行删除操作, 而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删 除操作的端称为队头。当队列中没有元素时,称为空队列。 对于队列这种结构,其操作很简单,主要有以下几种:
– – – – – 初始化队列:创建一个队列。 进队列:将一个元素添加到队尾(相当于到队列最后排队等候)。 出队列:将队头的元素取出,同时删除该元素,使后一个元素成为队头。 获取队列第1个元素:将队头的元素取出,不删除该元素(队头仍然是 该元素)。 获取队列长度:根据队头、队尾计算出队列中元素的数量。

2.2 先进选出结构:队列 先进选出结构:
2.2.2 操作队列 ? ? ? ? ? ?
1 A 2 B

1.定义顺序队列结构 . 2.初始化队列 . 3.获取队列状态 . 4.入队操作 . 5.出队操作 . 6.获取队头元素 .
3 C 4 D 5 6 7 8 …… n
1 2 B 3 C 4 D 5 6 7 8 …… n

head

tail

head

tail

2.2 先进选出结构:队列 先进选出结构:
2.2.3 循环队列

2.3 后进先出结构:栈 后进先出结构:

? ? ?

2.3.1 什么是栈 2.3.2 操作栈 2.3.3 实例:算术表达式求值 实例:

2.3 后进先出结构:栈 后进先出结构:
2.3.1 什么是栈
栈是一种线性表的特殊表现形式,与队列的“先进先出”不同, 栈是按照“后进先出”(Last In Firt Out,LIFO)的原则处理数据。

?

栈的基本操作只有两个:
– 入栈(Push):即将数据保存到栈顶。进行该操作前,先修改 栈顶指针,使其向上移一个元素位置,然后将数据保存到栈顶 指针所指的位置。 – 出栈(Pop):即将栈顶的数据弹出,然后修改栈顶指针,使 其指向栈中的下一个元素。

2.3 后进先出结构:栈 后进先出结构:
2.3.2 操作栈 ? ? ? ? ? ? ? 1.定义顺序栈的结构 . 2.初始化栈 . 3.判断栈的状态 . 4.入栈操作 . 5.出栈操作 . 6.获取栈顶元素 . 7.测试栈的操作 .

2.3 后进先出结构:栈 后进先出结构:
2.3.3 实例:算术表达式求值 实例:
对于算术表达式的求值,主要就是解决算术运算符的优 先级问题,有以下规则: – 先进行乘除运算,再进行加减运算(乘除优先级大于加 减); – 对于相同优先级的运算符,从左向右计算; – 若要改变优先级,可使用括号。对有括号的表达式,先 计算括号内,再计算括号外。

在表达式的计算过程中,既要保存操作数,又要保 存运算符。这时,可定义两个栈,一个用来保存操作数, 一个用来保存运算符。

性格决定命运, 性格决定命运 专注成就人生


相关文章:
第2章 数据结构和算法
第2 章 数据结构和算法本章主要考察的内容是: 1 .算法的基本概念 (1) 算法的定义 (2) 算法的特点 (3) 算法的复杂度 2.数据结构基本概念 3. 线性结构...
第2章 数据结构与算法
第2章 数据结构与算法 三级数据库技术三级数据库技术隐藏>> 数据结构与算法 1.1 基本概念信息---》数据 1.11 数据结构基本概念数据: 数据: 数据就是计算机化...
第2章 数据结构与算法
第2 章 数据结构与算法 本章节内容来自全国计算机等级考试用书《计算机等级考试二级 C 语言考点分析、题解 与模拟》。本章节主要考查算法的基本概念、基本的数据结构...
数据结构1-2章(8页)
第2章至第7章中已经介绍... 40页 免费 第7章 查找 暂无评价 22页 1下载...清华大学出版社 对学习课程的要求 掌握各种数据结构的逻辑特点、存贮方法、基本...
数据结构授课教案-第2章
数据结构授课教案-第1章 7页 免费如要投诉违规内容,请到百度文库投诉中心;如要...2.1 线性表的逻辑结构 ? 线性表是一种最简单数据结构,它是一种线性结构。...
数据结构 第二章自测题答案
《C语言数据结构》第1至... 62页 2下载券 数据结构第3章栈和队列自... ...线性表的每个结点只能是一个简单类型,而链表的每个结点可 以是一个复杂类型。 ...
第2章 C语言数据结构及其运算
C语言数据结构及其运算C语言数据结构及其运算隐藏>> 第二章 数据结构及其运算 考试要求: 考试要求: 1. C 的数据结构及其定义: 的数据结构及其定义: 基本类型, ...
数据结构第2章-习题
数据结构第2章-习题_理学_高等教育_教育专区。一、填空题 01、当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取 线性表中的元素时...
2.数据结构作业答案第2章(线性表)作业答案
第2章 数据结构线性表A 112页 5财富值 数据结构(C++) 第2章 线性... 97...(×)4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂...
数据结构第2章-答案
数据结构第2章-答案_工学_高等教育_教育专区。第 2 章 线性表 数据结构作业答案 一、填空题 01、当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求...
更多相关标签: