2023-2024-1 20231419 《计算机基础与程序设计》第七周学习总结

作业信息

教材学习内容总结

《计算机科学概论》第八章：抽象数据类型与子程序

1. 抽象数据类型（ADT）

概念：属性（数据和操作）明确地与特定实现分离的容器。

观察数据的方面：应用（用户）层、逻辑层（数据值、操作）、实现层（存放数据项的结构、编码）（数据域、子程序）；

栈

特点：后进先出（LIFO),即删除的项总是在栈中时间最短的项目。

操作名称：插入（推进Push),删除（弹出Pop)。

没有长度属性，只需确定栈是否为空。

队列

特点：先进先出（FIFO)，即删除的总是在队列中时间最长的项目。

操作名称：插入（Enque,Enqueue,Enq,Enter,Insert),删除（Deque,Dequeue,Deq,Delete,Remove);

列表

属性特征：项目是同构的，线性的，列表是变长的。

操作：插入（Insert），删除（Delete），检索是否存在（Isthere），报告列表中项目数量（GetLength），查看每一项（Reset,GetNext,Moreitems）；

区别：数组是内嵌结构，列表是抽象结构。列表应用于数组中。

• 链式结构：将数据项和找到下一项位置的信息保存到同一容器的实现方法。

一个节点由用户的数据和指向列表的下一个节点的链接或指针构成。最后一个节点的指针变量存放的是表示列表结束的符号（null）。

树

• 二叉树

每个节点有两个以内的后继节点（子女），起始节点叫做<根>，没有子女的节点叫做<树叶>。

——>二叉检索树：

搜索，构造（按插入的先后顺序创建），输出（左子女->根->右子女，递归），节点数。

图

概念：由节点和把节点连接起来的边构成的数据结构。

无向图与有向图；邻顶点；

创建图：顶点、边、权值；

图算法：

• 深度优先搜索：利用栈从一个顶点不断向下走直到到达目的地，只有在无路可走的时候才会向上一个节点进行回溯；

• 广度优先搜索：利用队列，将所有可能的节点列出，尽可能用最少的停顿到达目的地；

• 单源最短路搜索：使权值相加最少。

2. 子程序

• 参数传递；

参数列表：子程序要使用的标识符或值的列表；形参（定义）与实参（调用）。

替代机制：列表，相对位置。位置形参；

• 值参（传递副本），引用参数（传递地址，会改变原来的值）；

有返回值、无返回值。

《C语言程序设计》第六章：循环控制结构

1. 循环控制结构：

   三种循环语句：while,do-while,for;

   计数控制的循环：一般用for语句；

   条件控制的循环：while与do-while的区别；（补充：scanf的返回值；

   嵌套循环：一个循环体在另一个循环体中。

2. 流程的转移控制

   goto->跳转到语句标号所标识的语句；（慎用）

   break->跳出该层循环；

   continue->跳出本次循环；

   适合用goto的情况：需要快速跳出多重循环；跳向共同的出口位置，进行退出前的错误处理工作。（一般是往后面的语句跳）

   穷举法；

3. 结构化程序设计

   特性：只有一个入口和一个出口；无不可达语句；无死循环；

   补充：程序调试的注意与方法；类型溢出的情况。

基于AI的学习

学习进度条