首页 > 编程语言 >2024-2025 20241308 《计算机基础与程序设计》第七周学习总结

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

时间:2024-11-10 10:30:38浏览次数:5  
标签:链表 元素 子程序 2024 2025 20241308 数组 节点 指针

作业信息
这个作业属于哪个课程 <班级的链接>(如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.子程序与参数
子程序

  • 定义:子程序也叫子过程、函数等,是程序中相对独立的一段代码,它完成特定的任务或功能。当程序中多处需要执行相同或相似的操作时,就可以把这些操作封装成一个子程序,以便重复调用,提高代码的复用性和程序的可读性。
  • 示例:比如在一个计算程序中,经常需要计算一个数的平方。那么就可以编写一个子程序来实现这个功能,每次需要计算平方时就调用这个子程序即可。

参数

  • 定义:参数是在调用子程序时传递给它的数据。通过参数,主程序可以向子程序传递必要的信息,让子程序根据这些信息来完成特定的任务。
  • 类型:
  • 形式参数(形参):是在子程序定义时声明的参数,它规定了子程序期望接收的数据类型和格式等。比如在定义一个计算两个数之和的子程序时,声明两个形参用于接收要相加的两个数。
  • 实际参数(实参):是在调用子程序时实际传递给它的数据。例如调用上述计算两数之和的子程序时,实际传入的两个具体数字就是实参。实参要与形参在数据类型、数量等方面匹配,这样子程序才能正确运行。
  • 作用:参数使得子程序更加灵活通用,不同的实参传入可以让同一个子程序处理不同的数据,实现不同的具体功能。比如上述计算两数之和的子程序,通过传入不同的实参,可以计算任意两个数的和。

标签:链表,元素,子程序,2024,2025,20241308,数组,节点,指针
From: https://www.cnblogs.com/babythbreaths/p/18537694

相关文章

  • 2024-2025-1 20241417 《计算机基础与程序设计》第七周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第七周作业这个作业的目标<数组与链表,基于数组和基于链表实现数据结构,无序表与有序表,树,图,子程序与参数>作业正文https://www.cnblogs.com/lry......
  • 十大最佳数据恢复软件——2024-2025年10款最佳数据恢复软件
    我们将数据存储在我们的计算机和其他设备上。我们可能拥有与我们工作的公司或我们的个人信息相关的机密信息。有时系统可能会得到维修,或者可能会发生一些事情。所以数据会丢失。在硬盘驱动器,硬盘等数据存储设备中可能会损坏。为了取回数据,我们有数据恢复软件。10款最佳数据恢......
  • 中文大模型基准测评2024年10月报告
    背景自2023年以来,AI大模型在全球范围内掀起了有史以来规模最大的人工智能浪潮。进入2024年,全球大模型竞争态势日益加剧,随着Sora、GPT-4o、o1的发布,国内大模型在2024年进行了波澜壮阔的大模型追逐赛。中文大模型测评基准SuperCLUE持续对国内外大模型的发展趋势和综合效果进......
  • 还在搞传统爬虫吗?2025年用人工智能轻松抓取几乎所有网站
    今天,我将介绍一种简单的方法,帮助大家从各种网站上收集数据,搭建一个能够像人在浏览器中操作的网页爬虫。这种爬虫甚至可以在Upwork等平台上独立完成一些网页抓取的自由职业任务。自2024年以来,随着AI的发展,网页抓取发生了巨大的变化。以前,大公司如亚马逊或沃尔玛为了保持价格......
  • 华为OD机试2024年E卷-MVP争夺战[100分]( Java | Python3 | C++ | C语言 | JsNode | Go
    题目描述在星球争霸篮球赛对抗赛中,最大的宇宙战队希望每个人都能拿到MVP,MVP的条件是单场最高分得分获得者。可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场,并且让所有得分的选手得分都相同,然而比赛过程中的每1分钟的得分都只能由某一个人包揽。输入描述输入第一行......
  • 华为OD机试2024年E卷-AI识别面板[100分]( Java | Python3 | C++ | C语言 | JsNode | Go
    题目描述AI识别到面板上有N(1≤N≤100)个指示灯,灯大小一样,任意两个之间无重叠。由于AI识别误差,每次别到的指示灯位置可能有差异,以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1,右下角x2,y2),请输出先行后列排序的指示灯的编号,排序规则:每次在尚未排序的灯中挑选最高的......
  • #2024-2025-1学号20241309《计算机基础与程序设计》第七周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第七周作业这个作业的目标作业正文2024-2025-1学号20241309《计算机基础与程序设计》第七周学习总结教材学习内容总结《计算机科学概论......
  • 2024-11-9 栈的应用--括号匹配问题
    一、括号匹配问题(最后出现的左括号最先被匹配,每出现一个右括号就会消耗一个左括号)二、算法演示1.遇到左括号就入栈,遇到右括号就“消耗”一个左括号。(判断括号是否匹配,不匹配就失败。右括号存在,栈空,则也失败。若左括号有剩余,则也失败。)2.算法实现 初始化栈,扫描到左括号,就......
  • Toyota Programming Contest 2024#11(AtCoder Beginner Contest 379)题解
    总体情况A-Cyclic题意给你一个三位整数\(N\),其中每个数字都是介于\(1\)和\(9\)之间的整数。设\(a\),\(b\),\(c\)分别是\(N\)的百位、十位和个位数。打印一个按此顺序排列\(b\),\(c\),\(a\)所组成的整数,以及一个按此顺序排列\(c\),\(a\),\(b\)所组成......
  • 国内 ChatGPT中文版镜像网站整理合集(2024/11/10)
    一、GPT中文镜像网站① www.yixiaai.com 支持GPT4、4o以及o1,支持通用全模型② chat.lify.vip 支持GPT3.5/4,4o以及AI绘画,支持AI文件、AI插件、AI绘画、AIPPT③ AIPlus支持GPT3.5/4,4o以及AI绘画1.什么是镜像站镜像站(MirrorSite)是指通过复制原始网站内容和结构,创......