3. 堆栈和队列
阅读信息
约 965 个字 3 分钟 本页总访问量：加载中... 次
Class Three
引言
- Taylor 展开本质是多项式逼近复杂函数,神经网络本质也是逼近,用数据训练求出权重,得到数据结构.
- 能量转化为结构(关系).通过不断改进数据结构,获得智能.
- 均摊代价分析:将代价与结构结合.
有序的序列是线性表
多项式(The Polynomial ADT)
- 用数组表示多项式.为了防止稀疏数组浪费空间,只表示非零项.使用结构数组或链表.
多重线性表
- e.g. 表示很多学生选几门课.列出学生为列,课程为行的稀疏矩阵.只表示选的节点并按纵向,横向连成链表.
- 每个节点都在纵向,横向两个链表中.
内存管理
- 怎么管空闲位置?操作系统管怎么分配,释放内存.用链表管理
- 编译器编译时分配相对位置(相对地址),等代码运行时操作系统分配存储空间(绝对地址)
内存管理过程
- 理想情况下,申请释放的内存大小都相同,内存中利用一小块作为指针表示地址,将不同地址串成链表,每个指针指向下一个空闲空间.
- malloc 申请空间时,分配头上的空闲空间的指针.修改链表,将头指针指向下一个空闲位置.
- free 释放空间时,将释放的空间连到头指针.
- 使用时间长后,内存的链表更无序,但头节点始终维持头.
- 实际情况中,申请和释放的内存大小任意,每个节点大小不同.此时每个节点中包含这个节点大小,下一个空闲空间位置,标记该空间是否被占用的标记 flag 这三个信息.
- 每次申请时,先看该节点大小是否满足.若节点小,看下一个节点;若节点满足,从该节点中切一块.
- 防止多次使用后内存碎片化,释放内存时尽量使下一块或上一块连续.根据该节点大小找到下一节点,检查下一节点的 flag.
- 为了能和前一节点,需要在节点末尾加 size,next,flag 信息.
堆栈(The Stack ADT)
后缀表达式计算
- 每次遇到运算符号,计算前两个数,并压入计算结果.
- 怎么把中缀表达式变为后缀表达式?
- 遇到数,放入;遇到符号,记住.如果已有的符号优先级高,高的出去;如果已有的符号优先级低,记住新符号;如果已有的和新的优先级一样,先读到的出去.
- 由括号怎么办?将括号视为运算.左括号优先级低.遇到右括号抛出之前的符号,直到左括号.
堆栈与函数调用
- 连续多次调用函数,函数执行后回答上一个调用它的函数.
- 利用堆栈:先放 main 函数,再每次调用一次压入函数名.每次返回时栈顶的函数为调用它的函数.
- 解决递归调用的问题.
队列(The Queue ADT)
- 用链表实现时,front 删除元素,rear 插入元素(front 指向 next,删除后可以直接找到下一个).
- 指针指向右,则从右插入,从左删除
- 队列空间用满后怎么办?循环队列.
- 循环队列空和满:front==rear+1(取余)
- 为什么无法判断?队列中 n 个位置,共有 n+1 中情况,但 front 和 rear 的状态共有 n 种(信息量不够)
- 怎么增加信息?加入 tag,插入时设置为 1,删除时设置为 0.无法判断时看 tag.
- 或者使队列状态一共 n 种.空时 rear+1==front,一个元素时 front==rear,满时 front==rear+2.
- 一般使用 rear 不指实际的位置,而是指下一个要放的位置.空:
front\==rear,满:front\==rear+1. - 或者 front 指向第一个元素的前一个位置(哑头),空:front==rear,满:front==rear+1.