以下为《数据结构笔记》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

栈和队列

栈的定义和特点

是一种特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表，又称为“后进先出”的线性表，简称LIFO结构。表尾成为栈顶（插—入栈push，删—出栈pop）,表头称为栈底。

逻辑结构：同线性表相同，一对一

存储结构：顺序栈和链栈存储均可，但一顺序栈更加常见。

运算规则：只能在栈顶运算，且访问结点时依照先进先出（LIFO）的原则。

实现方式：编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。

链栈：是运算受限的单某某，只能在链表的头部进行操作。

链表的头指针就是栈顶

不需要头结点

基本不存在栈满的情况

空栈相当于头指针指向空

插入和删除仅在栈顶处执行

递归：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的

若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

分治法：对于一个较为负责的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。

递归的优缺点：

优点：结构清晰，程序易读

缺点：每一次调用要生成工作记录，保存状态新消息，入栈；返回时要出栈，恢复状态信息。时间开销大

栈的抽象数据类型定义：

ADT Stack{

数据对象：

数据关系：

基本操作：

}ADT Stack

InitStack（&S）初始化操作

操作结果：构造一个空栈S

DestroyStrack（&S）销毁栈操作

初始条件：栈S已存在

操作结果：栈S被销毁

Sta 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 （FIFO）的线性表。在表的一端插入（表尾），在另一头（表头）删除。

逻辑结构：同线性表相同，一对一

存储结构：顺序队或链队，以循环顺序队列更常见。

运算规则：只能在队首和队尾运算，且结点访问时依照先进先出（FIFO）的原则。

实现方式：关键是掌握入队和出队的操作，具体实现依顺序队或链队的不同而不同。

队列的抽象数据类型定义：

ADT Queue{

数据对象：

数据关系：

基本操作：

}ADT Queue

解决假溢出的办法：引入循环队列

插入元素：

Q.base[Q.rear]=x

Q.rear = (Q.rear+1)%MAXQSIZE

删除元素：

x=Q.base[Q.front]

Q.front = (Q.front+1)%MAXQSIZE

队空&队满解决方案

另外设一个标志以区别队空、队满

另设一个变量，记录元素的个数

少用一个元素空间

队空：front==reat

队满：（rear+1）%MAXQSIZE==front

案例1：舞伴问题

依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

首先构造两个队列，依次从队头元素出队配成舞伴，某队为空，则另一队等待着下一舞曲第一个可获得舞伴的人。

串、数组、广义表

串

零个或多个任意字符组成的有限序列

子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的自串

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

1. 二级公共基础知识复习资料
2. 07.排列与组合
3. 1.1.1 集合的含义与表示（1）
4. 选修课-信息技术应用 Information Technology Application 教学大纲
5. 业务学习目录（模板）
6. 葡萄冬季管理的这几点要牢记
7. 《四则运算》ppt课件
8. 危险化学品购销管理制度
9. 应用统计软件作业结果分析4
10. python学习笔记(字典)
11. L1第1次课知识点总结
12. 提取日志申请表模板
13. 信息技术环境下的课堂教学设计
14. 修改：《加法运算定律》教学设计
15. 黄毛数据结构模拟练习

以上为《数据结构笔记》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。