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

作业信息

教材学习内容总结

数组

数组是一种数据结构，它可以存储多个相同类型的数据元素。在许多编程语言中，数组具有以下特点：

一、存储方式

数组在内存中通常是连续存储的，这使得可以通过简单的数学运算快速访问特定位置的元素。例如，如果知道数组的起始地址和每个元素的大小，就可以通过索引快速计算出特定元素的内存地址。

二、特点

固定大小：
在创建数组时，通常需要指定数组的大小，一旦确定，在程序运行过程中这个大小一般不能改变。
如果尝试向一个已满的数组添加元素，可能会导致错误。
相同类型元素：
数组中的元素必须是相同类型的，例如都是整数、字符或其他特定的数据类型。
这有助于确保内存的高效使用和统一的操作方式。

三、访问和操作

索引访问：
可以通过索引来访问数组中的元素，索引通常从 0 开始。
例如，对于一个名为arr的整数数组，arr[0]表示第一个元素，arr[1]表示第二个元素，以此类推。
遍历：
可以使用循环结构遍历数组中的所有元素。例如，在 C、C++、Java 等语言中，可以使用for循环来遍历数组。
遍历数组可以进行各种操作，如查找特定元素、计算总和、修改元素值等。
插入和删除：
由于数组的固定大小特性，插入和删除元素可能比较复杂。
在某些情况下，可能需要创建一个新的更大或更小的数组，并将原数组中的元素复制到新数组中，以实现插入或删除操作。

四、应用场景

存储大量相同类型的数据：
例如存储学生的成绩、员工的工资等。
可以方便地进行批量操作和统计。
实现算法：
许多算法和数据结构，如排序算法（冒泡排序、快速排序等）、查找算法（线性查找、二分查找等）都可以使用数组来实现。
数组的快速随机访问特性使得这些算法能够高效地运行。
图形和图像处理：
在图形和图像处理中，数组可以用来存储像素值、颜色信息等。
可以对图像进行各种操作，如旋转、缩放、滤波等。

链表

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针（在双向链表中还有指向前一个节点的指针）。以下是关于链表的详细介绍：

一、结构特点

1. 动态大小：

   • 与数组不同，链表的大小可以在程序运行过程中动态地增加或减少。
   • 这使得链表在处理数据量不确定或需要频繁插入、删除元素的情况下非常有用。

2. 节点组成：

   • 每个节点包含两部分：数据部分和指针部分。
   • 数据部分用于存储实际的数据值，指针部分用于指向下一个节点（在双向链表中还有指向前一个节点的指针）。

二、类型

1. 单向链表：

   • 节点中只有一个指向下一个节点的指针。
   • 只能沿着指针的方向遍历链表，从链表的头部开始，依次访问每个节点，直到到达链表的末尾。

2. 双向链表：

   • 节点中有两个指针，一个指向前一个节点，一个指向下一个节点。
   • 可以在双向链表中进行双向遍历，既可以从链表的头部向尾部遍历，也可以从尾部向头部遍历。

三、操作

1. 插入节点：

   • 在链表中插入节点相对比较容易。
   • 对于单向链表，可以在链表的头部、尾部或中间位置插入节点。插入操作只需要修改相应节点的指针，使其指向新插入的节点即可。
   • 对于双向链表，插入节点时需要同时修改新节点的前向指针和后向指针，以及相邻节点的指针。

2. 删除节点：

   • 删除链表中的节点也比较简单。
   • 对于单向链表，删除一个节点只需要修改其前一个节点的指针，使其指向下一个节点即可。
   • 对于双向链表，删除节点时需要同时修改被删除节点的前向指针和后向指针，以及相邻节点的指针。

3. 遍历链表：

   • 遍历链表是链表的基本操作之一。
   • 对于单向链表，只能从链表的头部开始，依次访问每个节点，直到到达链表的末尾。
   • 对于双向链表，可以从链表的头部或尾部开始进行双向遍历。

四、应用场景

1. 实现栈和队列：

   • 链表可以很方便地实现栈和队列的数据结构。
   • 对于栈，可以使用单向链表，在链表的头部进行插入和删除操作。
   • 对于队列，可以使用单向链表或双向链表，在链表的尾部进行插入操作，在头部进行删除操作。

2. 动态内存分配：

   • 在一些需要动态分配内存的情况下，链表可以有效地管理内存。
   • 例如，当需要存储大量动态生成的数据时，可以使用链表来避免数组的固定大小限制。

3. 缓存管理：

   • 在缓存管理中，链表可以用来实现最近最少使用（LRU）算法等缓存替换策略。
   • 通过将最近使用的元素放在链表的头部，最近最少使用的元素放在链表的尾部，可以方便地进行缓存替换。

基于数组和基于链表实现数据结构
以下分别介绍基于数组和基于链表实现一些常见数据结构的方式：

一、基于数组实现

1. 栈

   • 可以使用数组来实现栈。将数组的一端作为栈顶，另一端作为栈底。
   • 入栈操作就是在栈顶位置插入元素，可以通过将元素放置在数组当前索引最大的位置实现。出栈操作则是移除栈顶元素，即移除数组当前索引最大的元素。
   • 优点是实现简单，随机访问速度快。缺点是需要事先确定栈的最大容量，可能会造成空间浪费或栈溢出。

2. 队列

   • 同样可以用数组实现队列。使用两个指针分别指向队头和队尾。
   • 入队操作将元素添加到队尾指针所指位置，然后队尾指针向后移动一位。出队操作移除队头元素，队头指针向后移动一位。
   • 优点是实现相对容易，随机访问方便。缺点是可能存在假溢出问题，即当队尾指针到达数组末尾时，即使数组前面还有空间也无法继续入队。

二、基于链表实现

1. 栈

   • 对于链表实现的栈，将链表的头部作为栈顶。
   • 入栈操作就是在链表头部插入一个新节点。出栈操作则是删除链表头部节点。
   • 优点是动态分配空间，不会出现栈溢出问题。缺点是需要额外的指针操作，实现相对复杂一些。

2. 队列

   • 用链表实现队列时，链表的头部作为队头，尾部作为队尾。
   • 入队操作在链表尾部添加新节点，出队操作移除链表头部节点。
   • 优点是可以动态调整大小，不会出现假溢出。缺点是指针操作可能导致错误，且随机访问不如数组方便。

总的来说，基于数组实现数据结构简单直接，随机访问速度快，但在动态性方面有所不足；基于链表实现则具有更好的动态性，但实现相对复杂，随机访问效率较低。具体选择哪种实现方式取决于具体的应用场景和需求。

教材学习中的问题和解决过程

问题1:使用数组有什么优缺点？
问题1解决：使用数组有以下优点和缺点：

一、优点

1. 随机访问快速：

   • 由于数组在内存中是连续存储的，可以通过索引在常数时间内访问特定位置的元素。例如，如果知道数组的起始地址和每个元素的大小，通过索引可以快速计算出特定元素的内存地址，从而实现高效的随机访问。
   • 这使得在需要频繁访问特定元素的情况下，数组非常高效。

2. 简单直观：

   • 数组的概念相对简单，易于理解和使用。对于熟悉编程语言的开发者来说，创建和操作数组通常是比较容易的事情。
   • 可以通过简单的语法来声明、初始化和访问数组元素，这使得代码更加简洁和易读。

3. 高效的存储和访问局部性：

   • 因为数组中的元素在内存中是连续存储的，所以在访问数组元素时，处理器可以利用存储和访问局部性原理，提高缓存命中率。
   • 这意味着当访问一个数组元素时，处理器可能会将相邻的元素也加载到缓存中，从而在后续访问相邻元素时可以更快地获取数据，提高程序的性能。

二、缺点

1. 固定大小：

   • 在创建数组时，通常需要指定数组的大小，一旦确定，在程序运行过程中这个大小一般不能改变。这意味着如果在运行时需要存储更多的数据，可能会出现数组已满的情况，而如果数组的大小设置得过大，又可能会浪费内存空间。
   • 当需要动态调整数组大小时，通常需要创建一个新的更大或更小的数组，并将原数组中的元素复制到新数组中，这是一个相对耗时的操作。

2. 插入和删除元素效率低：

   • 由于数组的连续存储特性，插入和删除元素可能比较复杂。如果要在数组中间插入一个元素，需要将插入位置后面的所有元素向后移动一位，以腾出空间插入新元素。同样，删除一个元素时，需要将删除位置后面的所有元素向前移动一位。
   • 这种操作的时间复杂度为 O(n)，其中 n 是数组的长度。因此，在频繁进行插入和删除操作的情况下，数组不是一个理想的数据结构。

3. 内存浪费：

   • 如果数组的大小设置得过大，而实际存储的数据量较少，就会浪费内存空间。另一方面，如果数组的大小设置得过小，可能会出现数组已满的情况，需要进行动态调整，这也会带来一定的性能开销。
   • 对于一些内存受限的系统，或者需要高效利用内存的应用场景，数组的固定大小特性可能会成为一个问题。

基于AI的学习