《数据结构与算法分析》C语言描述

目录

表、栈、队列

本章讨论最简单和最基本三种数据结构——表、栈、队列

本章内容

• 介绍抽象数据类型（ADT）的概念
• 阐述如何对表进行有效的操作
• 介绍栈ADT及其实现递归方面的应用
• 介绍队列ADT及其在操作系统和算法设计中的应用

抽象数据类型

模块化

• 描述
  • 程序设计的基本法则之一是例程不应超过一页，这可以通过分割模块（module）来实现
• 优点
  • 调试小程序比调试大程序容易得多
  • 多个人同时对一个模块化程序编程要更容易
  • 一个写得好的模块化程序把某些依赖关系只局限在一个例程中，修改起来更容易

抽象数据类型（Abstract Data Type，ADT）

• 描述
  • 是一些操作的集合，是数学的抽象

表ADT

表模型

概念

• 空表（empty list）：大小为0的表
• 除空表以外的任何表
  • 表中第一个元素是$A_i$，最后一个元素是$A_N$
  • $A_{i+1}$后续$A_i$，或说$A_{i+1}$续$A_i$之后，并称$A_{i-1}$前驱$A_i$
  • $A_i$没有前驱元，$A_N$没有后驱元

表ADT常用的操作集合

• MakeEmpty
• PrintList，打印表
• Find，返回关键字首次出现的位置
• FindKth，返回某个位置上的元素
• Insert，从表的某个位置插入某个关键字
• Delete，从表的某个位置删除某个关键字

实现

数组实现（表的简单实现）

数组

• 对表的所有操作都可以使用数组实现

性能

• PrintList，线性时间
• Find，线性时间
• FindKth，常数时间
• Insert，线性时间$O(N)$
• Delete，线性时间$O(N)$

不足

• 可以看到插入和删除需要线性时间，当N次相继插入/删除时需要二次时间（如删除所有元素a），运行会非常慢
• 且表的大小必须事先已知
• 所以简单数组一般不用来实现表这种结构

链表实现（linked list）

链表与原理

• 为了避免插入和删除的线性开销，可以允许表不连续存储。用链表来实现
• 每一个结构有表元素和指向后续元的结构的指针（称为Next指针），其中最后一个单元的Next指向NULL

性能

• PrintList，线性时间，（比数组实现稍慢）
• Find，线性时间，（比数组实现稍慢）
• FindKth，线性时间$O(i)$，（不如数组实现）
• Insert，（寻址过程还是线性，但连续插入/删除时仍是线性时间）
• Delete，（寻址过程还是线性，但连续插入/删除时仍是线性时间）

程序实现细节

• 起始端插入和删除是特殊情况，需要注意
• 除了重载特殊情况外还有个解决方法：留出一个标志节点，称为表头（header）或哑节点（dummy node）
• 删除算法需要记住被删除元素前面的表元

程序

• 略，学C++时写过一次了，懒得再写一次

单链表（singly linked list）

略，就是普通链表

双链表（doubly linked list）

有时需要倒序扫描链表，解决方法是在数据结构上增加一个指向前一个单元的指针

但该方法有额外的空间和性能开销

循环链表

让最后的单元反过来直指第一个单元。这种结构可以有表头也可以没有表头，并且还可以是双向链表

这种结构在某些应用程序中很流行

游标实现

BASIC和FORTRAN等许多语言都不支持指针，若需要链表又不能使用指针，则需要使用其他实现方法——游标实现法（cursor ...）

思路

• 在链表中指针实现中有两个重要特性，游标法需要模仿实现这两套特性
  • 数据存储在一组结构体中。每个结构体包含数据以及指向下一个结构体的指针
  • 一个新的结构体可以通过调用malloc而从系统全局内存（golbal memory）中得到，并可通过调用free而释放

具体思路

• 略

实现

• 略

应用

表示一元多项式

• 这个例子是说对于非稠密多项式，单链表比数组实现更优
• 个人感觉这个例子不好，他数组的实现本来就很差，弄结构体列表应该性能差不多吧，又不需要删除和添加多项式中的元素
• 反正挺迷惑的？？？

基数排序（radix sort）

桶式排序（bucket sort）

• 说明
  • 有N个整数，范围从1到M（或从0到M-1），利用该前提可以得到一种快速的排序——桶式排序
• 思路
  • 留置一个大小为M的数组，称为Count，初始化为0
  • 当$A_i$被读入时$Count[A_i]$增1，读入所有输入后
  • 扫描数组Count，打印输出排好序的表
• 性能：$O(M+N)$，如果$M=\Theta(N)$，则为$O(N)$

基数排序（radix sort）

• 说明
  • 也称卡式排序（card sort），因为以前用于老式穿孔卡的排序
  • 是桶式排序的的推广
• 思路
  • 排序10个数，范围在0到999之间
  • 这时不能用桶式排序了，桶会太大。策略是使用多趟桶式排序
  • 依次对最低（有效）“位”优先的方式进程桶式排序（不能从高位到低位，排序一次就知道为什么了）
• 性能
  • 时间线性，空间需求$\Theta(N^2)$

多重表（大学课程注册例子）

多重表（大学课程注册例子）

• 应用
  • 大学的课程注册，40000个学生和2500门课程
  • 要生成两种报告：每个班的注册者、每个学生注册的班级
• 二维数组实现
  • 常用的实现是二维数组，但这样的数组会有1亿项，空间需求太大
  • 若一个学生注册3门课程，则有意义的数据有120000项，仅占0.1%，空间利用率低
• 多重表实现
  • 每个项既在学生链表中又在课程链表中（每个项两个链表指针）
• 性能
  • 循环表节省空间但花费时间

栈ADT

栈模型

概念

• 栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（top）
• 有时也叫LIFO（后进先出）表

操作集合

• Push，进栈
• Pop，出栈
• Top，检查最后插入的元素
• 对空栈进行Pop或Top被认为是栈ADT的错误
• Push时空间用尽是实现错误，但不是ADT错误

实现

链表实现

链表实现

• 程序：略
• 性能：较差，对于malloc和free的调用的开销是昂贵的

数组实现

（更流行，一般应用程序中栈元素的实际个数不会太大）

• 程序：略
• 性能：较好

应用

平衡符号

• 说明：编译器检查程序语法时，可以检验每个符号是否都成对出现
• 例如：[()]合法，[(])错误
• 实现：这个很容易就能想明白了，略
• 性能：线性，且是“在线”的（联机算法）

后缀表达式

• 说明
  • 科学计算器需要先算乘除再算加减，如4.99*1.06 + 5.99 + 6.99*1.06
• 实现
  • 后缀记法
    • 可以将上面的操作顺序书写为：4.99 1.06 * 5.99 + 6.99 1.06 * +
    • 这种记法叫做后缀（postfix）或逆波兰（reverse Polish）记法
    • 可以用栈来实现后缀记法的计算
    • 当遇到数就推入栈，遇到符号就弹出两个数运算并将结果推回栈
  • 中缀到后缀的转换
    • 标准形式的表达式（也叫作中缀式（infix））转换成后缀式
    • 可以用栈来实现中缀到后缀的转换，规则多且繁琐。此处略，详见书
• 性能
  • 后缀计算：线性
  • 转换到后缀：线性

函数调用

这个就很经典了

尾递归（tail recursion）应当被优化以消除，可使用goto语句进行消除，而有些编译器还能自动完成尾调用优化

队列ADT（queue）

队列模型

操作集合

• Enqueue，入队，表末端（也叫队尾，rear ）插入元素
• Dequeue，出队，表开头（也叫队头，front）删除元素

实现（数组实现）

数组实现

• 一般是使用循环数组（circular array）实现

注意点

• 检验队列是否为空很重要。队列为空时出队操作会返回一个不确定的值
• 某些程序设计人员使用不同的方式来表示队列的队头和队尾

程序

• 略

应用

应用

• 送往行式打印机的作业
• 实际生活中的排队
• 计算机网络中的文件服务器
• 接线员较忙时对大公司的传呼
• 大学时学生等待使用终端
• 餐馆拿票排队

其他

• 有一个叫排队论（queueing theory）的完整数学分支
• 处理用概率的方法计算用户排队预计等待时间、等待服务的队列能排多长，以及其他一些诸如此类的问题