作业信息
这个作业属于哪个课程 <班级的链接>(如2024-2025-1-计算机基础与程序设计)
这个作业要求在哪里 <作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)
这个作业的目标 数组与链表 基于数组和基于链表实现数据结构 无序表与有序表 树 图 子程序与参数
作业正文
教材学习内容总结
1.数组与链表
数组和链表是两种常见的数据结构,各有特点:
数组
- 定义:是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。
- 优点:
- 随机访问:通过下标能快速定位元素,时间复杂度为O(1)。比如数组arr[5],要访问arr[3]可直接获取。
- 内存连续:空间利用效率相对较高,数据存储紧凑。
- 缺点:
- 插入删除不便:在中间插入或删除元素时,需移动后面的元素,时间复杂度最坏为O(n),n是数组长度。
- 大小固定:创建时需指定大小,后期若要扩容可能开销较大。
链表
- 定义:由一系列节点组成,每个节点包含数据域和指向下一节点的指针域(单向链表),通过指针将节点串联起来。
- 优点:
- 插入删除灵活:只需调整相关节点的指针,时间复杂度在最好情况下为O(1),比如在链表头部插入节点。
- 动态扩展:可随时添加或删除节点,无需事先确定大小。
- 缺点:
- 随机访问慢:要访问链表中某个节点,需从头节点开始遍历,时间复杂度为O(n)。
- 额外空间开销:每个节点除数据外还需存储指针,相比数组占用更多内存空间。
2.基于数组和基于链表实现数据结构
基于数组实现的数据结构
1. 栈:
- 特点:遵循后进先出原则。
- 实现方式:利用数组来存储栈中的元素。可以用一个变量记录栈顶元素的索引。入栈操作就是在数组末尾添加元素并更新栈顶索引;出栈操作则是取出栈顶元素并将栈顶索引减1。
2. 队列: - 特点:遵循先进先出原则。
- 实现方式:同样可以用数组实现。通过两个指针,一个指向队首,一个指向队尾。入队操作在队尾添加元素并移动队尾指针;出队操作取出队首元素并移动队首指针。不过,用数组实现队列时,可能会遇到队首指针移动后数组前端空间闲置的问题,需要一些处理技巧,比如循环队列的实现。
基于链表实现的数据结构
1. 链表本身:
- 特点:由一系列节点组成,节点间通过指针相连,可灵活地进行插入和删除操作。
- 实现方式:定义节点结构体,包含数据域和指针域(指向下一节点)。通过创建节点并连接它们来构建链表。
2. 栈: - 特点:与基于数组实现的栈一样遵循LIFO原则。
- 实现方式:用链表实现栈时,通常可以将链表的头部作为栈顶。入栈操作就是在链表头部插入新节点;出栈操作就是删除链表头部节点。
3. 队列: - 特点:遵循FIFO原则。
- 实现方式:可以用链表构建队列,一般需要维护头指针和尾指针。入队操作在链表尾部添加节点(更新尾指针);出队操作在链表头部删除节点(更新头指针)。
4. 双向链表: - 特点:节点除了有指向下一节点的指针,还有指向前一节点的指针,使得在链表中双向遍历成为可能。
- 实现方式:在节点结构体中增加一个指向前一节点的指针域,在插入和删除操作时,需要同时处理前后两个方向的指针连接。
5. 循环链表: - 特点:链表最后一个节点的指针指向链表的第一个节点(单向循环链表),或者双向循环链表中头节点的前一个节点指向尾节点,尾节点的后一个节点指向头节点,形成一个循环结构。
- 实现方式:在创建和操作链表时,注意让节点的指针形成循环指向关系。比如单向循环链表,在插入新节点时,要正确连接新节点与链表中已有节点的指针,使其构成循环。
3.无序表与有序表
无序表
- 定义:是一种数据集合,其中的元素没有特定的顺序排列。也就是说,元素在表中的存储位置与其值之间没有固定的对应关系。
- 常见实现方式:
- 基于数组:可以用一个数组来存储元素,通过遍历数组来查找、插入或删除元素等操作。但插入和删除操作可能需要移动其他元素来维持数组的结构,查找操作通常需要遍历数组逐个比较,时间复杂度在最坏情况下可能为O(n),n是元素个数。
- 基于链表:以链表形式存储元素,每个节点包含数据和指向下一节点的指针(单向链表情况)。插入和删除操作相对灵活,只需调整相关节点的指针,时间复杂度在最好情况下可以是O(1),但查找操作同样一般需遍历链表,时间复杂度为O(n)。
- 操作特点:
- 查找:通常要逐个元素进行比较,效率相对较低,平均时间复杂度一般为O(n)。
- 插入:可在任意位置插入新元素,基于数组实现时可能要移动元素,基于链表实现相对简单些。
- 删除:找到要删除的元素后,基于数组可能要移动后续元素,基于链表只需调整指针。
有序表
- 定义:表中的元素按照某种特定的规则(如数值大小、字母顺序等)进行了有序排列。
- 常见实现方式:
- 基于数组:同样用数组存储元素,由于元素有序,查找操作可利用二分查找等高效算法,时间复杂度可降低到O(log n)。插入和删除操作依然可能面临移动元素的问题,不过在合适的插入点插入可利用元素的有序性稍作优化。
- 基于链表:以链表存储有序元素,查找操作还是需遍历链表,时间复杂度为O(n),但插入和删除操作在找到合适插入点或删除点后,可根据元素的有序性更方便地调整指针。
- 操作特点:
- 查找:如果基于数组且采用高效算法,查找效率较高;基于链表查找效率相对低些。
- 插入:需要先找到合适的插入位置以维持表的有序性,基于数组可能要移动元素,基于链表要调整指针。
- 删除:找到要删除的元素后,基于数组可能要移动后续元素,基于链表要调整指针,同时要注意维持表的有序性。
4.树 图
树
- 定义:树是一种非线性的数据结构,它由节点和边组成,有一个特定的节点称为根节点,其余节点通过边连接形成层次关系。除根节点外,每个节点都有且仅有一个父节点,节点可以有零个或多个子节点。
- 特点:
- 具有层次结构,根节点在最顶层,往下依次为不同层次的子节点。
- 树的深度是从根节点到叶节点(没有子节点的节点)的最长路径上的节点数。
- 常见类型:
- 二叉树:每个节点最多有两个子节点,分别称为左子节点和右子节点。又可细分为满二叉树(除最后一层外,每层节点数都达到最大,且最后一层节点都在最左边)、完全二叉树(除最后一层外,每层节点数都达到最大,最后一层节点从左到右依次排列)等。
- 多叉树:节点可以有多于两个的子节点,比如三叉树、四叉树等,常用于表示具有多种分支情况的数据关系。
图
- 定义:图也是一种非线性的数据结构,由顶点和边组成。顶点表示对象,边表示对象之间的关系,可以是有向的(有向图,边有方向,从一个顶点指向另一个顶点),也可以是无向的(无向图,边没有方向,两个顶点之间的边可双向通行)。
- 特点:
- 图的结构比树更松散,没有像树那样严格的层次关系和根节点的概念(但在某些应用中也可指定一个特殊顶点作为类似根节点的存在)。
- 图中顶点之间的连接情况可以很复杂,边的数量和分布各不相同。
- 常见类型:
- 有向图:如社交网络中,用户A关注用户B,这就是一个有向的关系,可以用有向图来表示,边从A指向B。
- 无向图:比如城市之间的公路连接,如果只考虑城市间是否有公路相连,而不考虑方向,就可以用无向图来表示。
5.子程序与参数
子程序
- 定义:子程序也叫子过程、函数等,是程序中相对独立的一段代码,它完成特定的任务或功能。当程序中多处需要执行相同或相似的操作时,就可以把这些操作封装成一个子程序,以便重复调用,提高代码的复用性和程序的可读性。
- 示例:比如在一个计算程序中,经常需要计算一个数的平方。那么就可以编写一个子程序来实现这个功能,每次需要计算平方时就调用这个子程序即可。
参数
- 定义:参数是在调用子程序时传递给它的数据。通过参数,主程序可以向子程序传递必要的信息,让子程序根据这些信息来完成特定的任务。
- 类型:
- 形式参数(形参):是在子程序定义时声明的参数,它规定了子程序期望接收的数据类型和格式等。比如在定义一个计算两个数之和的子程序时,声明两个形参用于接收要相加的两个数。
- 实际参数(实参):是在调用子程序时实际传递给它的数据。例如调用上述计算两数之和的子程序时,实际传入的两个具体数字就是实参。实参要与形参在数据类型、数量等方面匹配,这样子程序才能正确运行。
- 作用:参数使得子程序更加灵活通用,不同的实参传入可以让同一个子程序处理不同的数据,实现不同的具体功能。比如上述计算两数之和的子程序,通过传入不同的实参,可以计算任意两个数的和。