当前位置:首页 >> 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 章 线性表 一、选择题 1. 链表不具备的特点是()。 A.可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储...
数据结构第2章习题整理
数据结构第2章习题整理_工学_高等教育_教育专区。中国海洋大学数据结构第魏振刚二章习题,思路,答案 第2 章 习题整理 2.11 设顺序表 va 中的数据元素递增有序...
北理工数据结构第二章实验报告
北理工数据结构第二章实验报告_工学_高等教育_教育专区。第二章作业 1、在什么情况下用顺序表比链表好? 删除,插入操作较少,直接用的时候较多。 2、已知 L 是...
数据结构 陈雁 第2章 自测练习题参考答案
数据结构 陈雁 第4章 算法... 22财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
《数据结构》课程建设报告
第二章 线性表 重点:熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分 析,双向链表,循环链表; 2 北京化工大学高职高专《数据结构》课程建设报告 ...
数据结构课程第二章部分习题解答
数据结构课程第二章部分习题解答数据结构课程第二章部分习题解答隐藏>> 中央电大...试 利用字符串的基本运算实现这个替换操作。 【解答】 String & String :: ...
数据结构课后习题及解析第二章
数据结构课后习题及解析第二章_IT认证_资格考试/认证_教育专区。第二章习题 1. 描述以下三个概念的区别:头指针,头结点,首元素结点。 2. 填空: (1) 在顺序表...
数据结构 第二版 课后答案 (陈雁 著) 高等教育出版社
结构和算法 解:数据元素 数据 数据对象 数据结构 存储结构 算法 :数据的基本...(n2) 第二章习 题 1、描述以下三个概念的区别:头指针、头结点、首元结点 ...
第六章习题2数据结构
数据结构练习题2 2页 1下载券第​六​章​习​题​2​数​据​...(2)设深度为 d 的二叉树上只有度为 0 和度为 2 的结点,则此二叉树中所...
《数据结构》课后习题答案(第2版)
数据结构》课后习题答案(第2版) - 第一章 1 填空题 (1)数据元素 (2)数据项 数据元素 (3)集合 线性结构 树结构 图结构 (4)顺序存储 链接存储 数据元素...
更多相关标签: