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

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

作业信息

教材学习内容总结

一、数组与链表
（一）数组

1. 概念
   • 数组是一种线性数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。例如存储(10)，(20)，(30)，(40)，(50)的数组，其逻辑结构和存储结构都是连续的，并且顺序是对应的。这使得数组的“随机访问”相对高效，因为可以根据离首地址的偏移量直接存取相应位置上的数据。[1]
2. 操作特点
   • 增删操作：数组的增删操作效率很低。因为为了保证连续性，在进行增删操作时需要做大量的数据搬移工作。例如在数组中间插入一个元素，需要将插入位置后面的元素集体向后移一位为新元素空出存储空间。
   • 动态数组：动态数组是指数组的容量能动态增长的数组。一般当当前数组的容量不够用的时候会自动创建一个新的数组（新数组的容量是当前数组的(x)倍，(x)一般是(1.5)，可以自己设置），然后将当前数组的数据复制到新数组中，这就实现了数组容量的自动增长。在不同编程语言中，(C)语言若要提供动态数组，需要手动实现；(C++)中(STL)提供了(Vector)；(Java)中(Collection)集合中提供了(ArrayList)和(Vector)。[1]
     （二）链表
3. 概念
   • 链表与数组不同，它不使用连续的内存空间，而是通过“指针”将一组零散的内存块串联起来。链表由节点组成，常见的链表有单链表、双向链表和循环链表等。[1]
4. 操作特点
   • 单向链表
     • 结构：单向链表中的每个节点包含两部分，即数据部分和后继节点指针部分。节点的链接方向是单向的。
     • 访问与操作：相对于数组来说，单链表的随机访问速度较慢，但是单链表删除/添加数据的效率很高。例如在单向链表中删除一个节点，只需要修改相关节点的指针指向即可。添加节点时，也是修改指针指向来完成操作。[1]
   • 双向链表
     • 结构：双向链表中的每个节点由三部分组成，即前驱节点指针、数据、后继节点指针。所以从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
     • 操作：双向链表的删除节点和插入节点跟单向链表基本一致，只是在删除和插入节点时要加上对前驱节点指针的修改。[1]
   • 循环链表：是一种特殊的链表，它将链表的结尾节点的后继指针指向头节点。循环链表的添加与删除主要是要重点考虑结尾节点和头结点的前继节点指针和后继节点指针问题。[1]

二、基于数组和基于链表实现数据结构
（一）基于数组实现数据结构

1. 队列实现（示例）
   • 可以通过数组对数据进行操作来实现队列功能。例如在队列末尾添加数据时，可以实例化一个新数组对象，其长度比原数组大一，然后将原数组数据复制到新数组中，并将新元素添加到新数组末尾。[2]
     （二）基于链表实现数据结构
2. 以链表实现队列
   • 可以利用链表的特性，如添加和删除元素效率高的特点来构建队列。在链表头部进行删除操作（出队），在链表尾部进行添加操作（入队）较为方便。

三、无序表与有序表

1. 无序表
   • 无序表中的元素没有特定的顺序排列。可以用数组或者链表来实现无序表。在数组实现的无序表中，元素按照存储顺序存在数组中，没有按照元素大小等规则排序。链表实现的无序表也是类似，元素在链表中的顺序不是按照某种特定顺序排列的。
2. 有序表
   • 有序表中的元素按照一定的顺序（如升序或降序）排列。如果用数组实现有序表，在插入新元素时，可能需要移动其他元素来保持顺序。用链表实现有序表时，插入新元素需要比较元素大小并找到合适的插入位置，这个过程可能需要遍历链表部分节点。

四、树

1. 概念
   • 树是一种非线性的数据结构，它由节点（包括根节点、内部节点和叶节点）和边组成。树有一个根节点，根节点下面可以有多个子节点，每个子节点又可以有自己的子节点，以此类推。
2. 特性
   • 树具有层次结构，不同层次的节点有不同的深度（根节点深度为(0)）。树的高度是从根节点到叶节点最长路径上的节点数。在树中可以定义父节点、子节点、兄弟节点等关系。
3. 常见类型
   • 二叉树：二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树有多种特殊类型，如满二叉树（所有叶节点都在同一层，且每个内部节点都有两个子节点）和完全二叉树（除了最后一层外，其他层的节点数都是满的，最后一层节点从左到右依次排列）。

五、图

1. 概念
   • 图是一种更为复杂的非线性数据结构，由顶点（节点）和边组成。边可以表示顶点之间的关系，如连接关系、权重关系等。
2. 分类
   • 无向图：无向图中的边没有方向，即顶点之间的关系是双向的。例如社交网络中的好友关系可以用无向图表示，(A)是(B)的好友，那么(B)也是(A)的好友。
   • 有向图：有向图中的边有方向，从一个顶点指向另一个顶点。例如在城市交通网络中，道路可能是单向的，就可以用有向图表示。
3. 表示方法
   • 邻接矩阵：用一个二维矩阵来表示图中顶点之间的关系。如果顶点(i)和顶点(j)有边相连，则矩阵中((i, j))位置的值根据图的性质（如无向图为(1)，有向图根据边的方向等）设定，否则为(0)。
   • 邻接表：对于每个顶点，用一个链表（或数组）来存储与该顶点相连的其他顶点。这种表示方法在顶点数较多而边数相对较少的图中比较节省空间。

六、子程序与参数

1. 子程序
   • 子程序也称为函数、方法等，是一段可以被重复调用的代码块。它将一个较大的程序分解成多个较小的、功能相对独立的部分，提高了程序的可读性、可维护性和可复用性。例如在一个计算程序中，可能有一个专门用于计算加法的子程序，在需要进行加法运算的地方就可以调用这个子程序。
2. 参数
   • 参数是在调用子程序时传递给子程序的值或变量。参数可以让子程序更加通用，根据不同的输入值执行不同的操作。例如上述加法子程序，可以接受两个参数，这两个参数就是要进行加法运算的两个数。参数可以有不同的类型，如数值型、字符型等，并且在不同的编程语言中有不同的传递方式，如值传递（将参数的值复制一份传递给子程序）和引用传递（将参数的地址传递给子程序）等。

基于AI的学习