作业信息
作业课程 2024-2025-1-计算机基础与程序设计
作业要求 2024-2025-1计算机基础与程序设计第七周作业
作业目标 数组与链表，基于数组和基于链表实现数据结构，无序表与有序表，树，图，子程序与参数
作业正文 2024-2025-1 20241328 《计算机基础与程序设计》第七周学习总结
教材学习内容总结
一、数组与链表
（一）数组
1.概念
数组是一种线性数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。（根据首地址来找）这使得数组的“随机访问”相对高效，因为可以根据离首地址的偏移量直接存取相应位置上的数据。
2.操作特点
增删操作：数组的增删操作效率很低。因为为了保证连续性，在进行增删操作时需要做大量的数据搬移工作。例如在数组中间插入一个元素，需要将插入位置后面的元素集体向后移一位为新元素空出存储空间。
（二）链表
3.概念
链表与数组不同，它不使用连续的内存空间，而是通过“指针”将一组零散的内存块串联起来。链表由节点组成，常见的链表有单链表、双向链表和循环链表等。[1]
4.操作特点
（1）单向链表
结构：单向链表中的每个节点包含两部分，即数据部分和后继节点指针部分。节点的链接方向是单向的。
访问与操作：相对于数组来说，单链表的随机访问速度较慢，但是单链表删除/添加数据的效率很高。例如在单向链表中删除一个节点，只需要修改相关节点的指针指向即可。添加节点时，也是修改指针指向来完成操作。[1]
双向链表
结构：双向链表中的每个节点由三部分组成，即前驱节点指针、数据、后继节点指针。所以从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
操作：双向链表的删除节点和插入节点跟单向链表基本一致，只是在删除和插入节点时要加上对前驱节点指针的修改。[1]
循环链表：是一种特殊的链表，它将链表的结尾节点的后继指针指向头节点。循环链表的添加与删除主要是要重点考虑结尾节点和头结点的前继节点指针和后继节点指针问题。
二、基于数组和基于链表实现数据结构
1.队列实现（示例）
可以通过数组对数据进行操作来实现队列功能。例如在队列末尾添加数据时，可以实例化一个新数组对象，其长度比原数组大一，然后将原数组数据复制到新数组中，并将新元素添加到新数组末尾。[2]
2.以链表实现队列
可以利用链表的特性，如添加和删除元素效率高的特点来构建队列。在链表头部进行删除操作（出队），在链表尾部进行添加操作（入队）较为方便。
三．向函数传递一维和二维数组
-
向函数传递一维数组
基本方法：在C语言中，传递一维数组时只传递数组的首地址，不传递整个数组。函数的参数可以用指针、固定大小数组或未定义大小的数组表示。这些方式在编译时被解释为指向数组首元素的指针
2.向函数传递二维数组当传递二维数组时，函数形参需要包含第二维的大小；第一维可以省略
使用指针：将二维数组作为指向一维数组的指针来处理。在这种情况下，参数可以被定义为指向一维数组的指针，同时在计算时需转化为对应的偏移量。这种方法利用了数组在内存中是行优先存储的特性，通过计算偏移量直接访问每个元素。