大学计算机—基于计算思维知识点
- 格式:doc
- 大小:136.55 KB
- 文档页数:11
计算机基础与计算思维知识点
计算机技术正快速发展,不仅对于我们的日常应用而言重要,也正在成为当今社会的重要组成部分。
随着技术的发展,我们对计算机的基础知识和计算思维也变得越来越重要。
首先,我们需要了解计算机基础知识,这也是计算机技术学习的基础。
当我们开始学习计算机技术时,应该要了解什么是计算机、计算机的结构、如何构建和运行程序、计算机网络技术等等。
另外,还需了解计算机的常用操作系统以及如何使用常用软件。
这些知识可以帮助我们更加深入的理解计算机技术,并有效地应用它们。
接下来,计算思维也是一个重要知识点。
计算思维具有构建和解决问题的能力,也可以被用来理解、分析、提出、解决问题和设计系统的能力。
它是人们表达、传达、理解和利用计算机技术的方式。
在现代社会中,计算思维的重要性日益凸显,因为它可以帮助我们更好的利用计算机技术解决问题。
计算机思维也可以帮助我们更好的理解计算机语言,如C/C++、Java/Python/PHP等,以及扩展其他计算机相关知识,如数据库技术、Web开发等。
正确的学习方法包括观察、模拟、演示、试验、调试、推理等步骤。
在学习计算机有关知识时,可以使用这些方法获得更多的收获。
最后,计算机技术以及计算思维都是当今社会发展的基础,它们的重要性可以说是无可替代的。
因此,我们应该充分珍惜这些有趣的技术内容,并努力深入学习,以进一步提升自己的计算机技术水平。
大一计算机思维知识点计算机思维是指运用计算机科学的原理和方法,处理和解决现实世界问题的一种思维方式。
作为计算机专业的大一新生,了解计算机思维的基本知识点对于理解计算机科学的基本概念和方法具有重要意义。
本文将介绍大一计算机思维的主要知识点,以帮助大家更好地理解和应用计算机科学。
一、算法与程序设计1. 算法的定义和特性算法是解决问题的一系列有序步骤。
它具有输入、输出、确定性、有穷性和可行性等特性。
了解算法的基本概念和特性有助于我们设计高效的程序。
2. 程序设计的基本步骤程序设计的基本步骤包括问题分析、算法设计、程序编写、调试和测试等。
熟悉这些步骤和方法可以帮助我们编写出正确、高效的程序。
二、数据结构与算法分析1. 常见数据结构线性结构包括数组、链表、堆栈和队列等;非线性结构包括树和图等。
了解这些数据结构及其特点有助于我们选择合适的数据结构来组织和管理数据。
2. 算法的时间复杂度和空间复杂度算法的时间复杂度和空间复杂度是衡量算法效率的重要指标。
学会分析算法的复杂度可以帮助我们优化程序,提高执行效率。
三、计算机组成原理1. 计算机的基本组成部分计算机由硬件和软件两部分组成。
硬件包括中央处理器(CPU)、内存(RAM)、输入输出设备等;软件包括系统软件和应用软件等。
2. 计算机运算原理计算机进行数据处理的基本运算类型包括算术运算、逻辑运算和位运算等。
理解计算机的运算原理有助于我们编写高效的程序。
四、编程语言与开发环境1. 常用编程语言C、C++、Java等是常用的计算机编程语言,每种语言都有其特点和适用范围。
了解这些编程语言有助于我们选择合适的语言来实现程序功能。
2. 开发环境与工具编程开发环境包括编译器、集成开发环境(IDE)等,它们能够提供良好的开发支持和调试功能。
掌握常用的开发环境与工具能够提高我们的编程效率。
五、计算机网络与互联网1. 计算机网络基础了解计算机网络的基本概念和结构对于理解互联网的工作原理和应用具有重要意义。
大一计算思维知识点计算思维是指通过对问题的分析、建模和求解,利用计算机或者人的计算能力来解决问题的一种思维方式。
它是现代社会必备的一种能力,也是大一学生需要掌握的重要知识点。
本文将介绍大一计算思维的三个主要知识点:算法与流程控制、数据结构与算法分析、计算机编程与实现。
一、算法与流程控制1.1 算法概述算法是一种问题求解的方法,它由一系列清晰而有序的步骤组成,可以用来解决特定问题。
算法的设计需要考虑问题的规模、效率和可行性。
1.2 算法的特性算法具有以下几个重要特性:- 输入:算法的输入参数或数据。
- 输出:算法的输出结果。
- 确定性:对于相同的输入,算法必须有相同的输出。
- 可行性:算法的每一步都是可行的,可以通过有限次的操作得到结果。
- 有限性:算法在执行有限的步骤之后终止。
1.3 常用的流程控制结构大一学生需要掌握常见的流程控制结构,包括顺序结构、选择结构和循环结构。
- 顺序结构:按照指定的顺序逐步执行程序。
- 选择结构:根据条件的真假选择不同的执行路径。
- 循环结构:重复执行一段代码,直到满足退出条件。
二、数据结构与算法分析2.1 数据结构概述数据结构是指组织和存储数据的方式,它关注数据的逻辑关系和操作。
常见的数据结构包括数组、链表、栈、队列、树等。
2.2 算法分析在实际应用中,我们需要比较不同算法的效率。
算法分析是对算法运行时间和空间复杂度的评估。
常用的算法分析方法有大O表示法、平均情况复杂度和最坏情况复杂度等。
2.3 常见的算法- 排序算法:包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。
- 查找算法:包括线性查找、二分查找等。
- 图算法:包括深度优先搜索、广度优先搜索等。
三、计算机编程与实现3.1 编程语言大一学生通常学习C、C++、Java等编程语言。
通过学习编程语言,学生可以将算法和数据结构转化为具体的代码实现。
3.2 常见的编程任务- 程序的输入和输出:包括标准输入输出、文件输入输出等。
大学计算机知识点整理.一、选择 201. 计算思维定义:计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及理解人类行为等涵盖计算机科学之广度的一系列思维活动。
本质:抽象和自动化特征、三种思维:理论思维:以推理和演绎为特征,以数学学科为代表实验思维:以观察和总结自然规律为特征,以物理学科为代表计算思维:以设计和构造为特征,以计算机学科为代表2. 冯诺依曼五大部件:运算器、控制器、存储器、输入设备、输出设备①运算器。
计算机中进行算术运算和逻辑运算的主要部件,是计算机的主体。
在控制器的控制下,运算器接收待运算的数据,完成程序指令指定的基于二进制数的算术运算或逻辑运算。
②控制器。
计算机的指挥控制中心。
控制器从存储器中逐条取出指令、分析指令,然后根据指令要求完成相应操作,产生一系列控制命令,使计算机各部分自动、连续并协调动作,成为一个有机的整体,实现程序的输入、数据的输入以及运算并输出结果。
③存储器。
存储器是用来保存程序和数据,以及运算的中间结果和最后结果的记忆装置。
计算机的存储系统分为内部存储器 (简称内存或主存储器和外部存储器 (简称外存或辅助存储器。
主存储器中存放将要执行的指令和运算数据, 容量较小,但存取速度快。
外存容量大、成本低、存取速度慢,用于存放需要长期保存的程序和数据。
当存放在外存中的程序和数据需要处理时,必须先将它们读到内存中,才能进行处理。
④输入设备。
输入设备是用来完成输入功能的部件,即向计算机送入程序、数据以及各种信息的设备。
常用的输入设备有键盘、鼠标、扫描仪、磁盘驱动器和触摸屏等。
⑤输出设备。
输出设备是用来将计算机工作的中间结果及处理后的结果进行表现的设备。
常用的输出设备有显示器、打印机、绘图仪和磁盘驱动器等。
3. 存储系统内 /主存储器 (ROM 、 RAM 、 cache :ROM 是只读存储器 (Read-Only Memory的简称,是一种只能读出事先所存数据的固态半导体存储器。
大学计算机基础-01-计算机与计算思维在当今的数字化时代,计算机已经成为我们生活中不可或缺的一部分。
无论是工作、学习还是娱乐,我们几乎每天都会与计算机打交道。
而要真正理解计算机的运行原理和应用,就必须掌握计算思维。
接下来,让我们一起走进计算机与计算思维的奇妙世界。
计算机,这个看似复杂的设备,实际上是由一系列硬件和软件组成的。
硬件包括中央处理器(CPU)、内存、硬盘、显示器、键盘等组件,它们协同工作,使得计算机能够执行各种任务。
软件则是指安装在计算机上的程序和操作系统,如 Windows、Mac OS、Linux 等。
这些软件为我们提供了与计算机交互的界面和工具,让我们能够轻松地完成文档编辑、图像处理、游戏娱乐等各种活动。
计算机的发展经历了几个重要的阶段。
从最初的大型机到个人电脑的普及,再到如今的智能手机和平板电脑,计算机的体积越来越小,性能却越来越强大。
早期的计算机主要用于科学计算和军事领域,而随着技术的进步,计算机逐渐走进了千家万户,成为了人们日常生活和工作的得力助手。
那么,什么是计算思维呢?简单来说,计算思维是一种运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。
它不仅仅是关于编程和算法,更是一种解决问题的方式和思维模式。
计算思维具有几个重要的特点。
首先是抽象。
在面对复杂的问题时,我们需要将其抽象为简单的模型,以便更好地理解和解决。
例如,在设计一个在线购物系统时,我们可以将用户、商品、订单等元素抽象为数据结构,并通过算法来处理这些数据。
其次是逻辑。
计算思维要求我们遵循严格的逻辑规则,确保我们的解决方案是正确和有效的。
无论是编写程序还是设计系统,逻辑的严密性都是至关重要的。
此外,计算思维还强调分解和组合。
我们可以将一个大问题分解成若干个小问题,分别解决后再将它们组合起来,形成最终的解决方案。
计算思维在各个领域都有着广泛的应用。
在科学研究中,科学家们利用计算思维来模拟自然现象、分析实验数据,从而推动科学的进步。
大学计算机基础知识点第一章计算思维与计算机1、三大科学思维——理论思维(以数学为基础的理论思维)、实验思维以物理为基础的实验思维、计算思维2、计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动.3、计算思维的本质:抽象+自动化4、计算机是一种能存储程序和数据,自动执行程序、快速而精确地完成对各种数字化信息处理的电子设备5、1946年(美)宾夕法尼亚大学第一台数字电子计算机 ENIAC诞生。
6、按照计算机所使用的逻辑部件将计算机的发展分为四代:第一代:(1946-1957) 电子管时代第二代:(1958-1964) 晶体管时代第三代:(1965-1970) 中小规模集成电路第四代:(1971-至今) 大规模、超大规模集成电路(出现网络,使用面日益广泛)7、存储程序的工作原理是:在计算机中设置存储器,将程序和数据存放到存储器中,计算机按照程序指定的逻辑顺序依次取出存储器中的内容进行处理,直到得出结果。
计算机有两个基本能力:一是能够存储程序和数据二是能够自动地执行程序程序(Program) :是指可以连续执行的一条条指令的集合指令(Instruction) :是指计算机完成某一种操作的命令指令是一组二进制代码操作码:指出进行什么操作地址码:是规定操作数的值或地址、操作结果的地址及下一条指令的地址等计算机硬件系统第二章⏹数制(Numbering System)即表示数值的方法,有进位计数制和非进位计数制两种⏹进位计数制的基本特点如下:☐使用固定个数的数码表示数值的大小☐逢R进一☐采用位权表示法数制的转换二进制、八进制、十六进制和十进制之间的转换信息的存储单位(位、字节)除字节外,还有千字节(KB)、兆字节(MB)、吉字节(GB)、太字节(TB),拍字节(PB)。
它们的换算关系原码、反码、补码之间的转换ASCII(American Standard Code for Information Interchange)码,即美国标准信息交换代码。
计算机基础与计算思维知识点
计算机基础与计算思维是计算机科学中一个重要的研究领域。
它主要包括计算机基础、数
学基础和计算机科学逻辑学。
它也是计算机科学应用研究的基础知识。
它以概念、技术和
任务构成了一种系统的、正确的计算机学习和思考的总体框架,对计算机思维、算法及编
程有非常重要的意义。
计算机基础包括计算机构造、编程语言、软件工程原理、数据库、操作系统等基础知识。
这些基础知识将为学习计算机科学、利用计算机解决问题和实现技术创新提供支援。
数学基础是解决计算机问题的基本技能,最少应用数学,包括:数论、集合论、代数、数
值分析、微积分、几何、概率论、统计学等知识。
这部分知识涉及逻辑、证明及系统分析,掌握它将帮助使用者将复杂问题转化为结构化的计算机问题,进而提高解决复杂问题的能力。
计算机科学逻辑学是计算机科学中最基本的,也是最重要的部分。
它研究计算机思维和计
算逻辑,包括证明论、演算论、图论等,以及大量的算法及算法分析知识。
它是计算机基
础设施和计算思维能力的核心,对学习和研究任何计算机方面的问题都具有重要的意义。
计算机基础与计算思维能力是计算机科学领域最基础的部分,也是最重要的部分,它涉及
计算机基础、数学基础、计算机科学逻辑学和算法等多方面的知识,是计算机学习、利用
计算机解决问题和实现技术创新的基础,对计算机思维、算法及编程有非常重要的意义。
计算机基础与计算思维知识点计算机科学与技术作为一门专业,涉及的知识点广泛而且日新月异。
其中最重要而又基础的内容之一就是计算机基础与计算思维。
本文将为大家介绍计算机基础与计算思维的相关知识点。
一、计算机基础知识1. 计算机硬件与软件计算机硬件包括中央处理器(CPU)、内存(RAM)、硬盘、显卡等组成部分,而软件则是指计算机的操作系统、应用程序等。
硬件是计算机的基础,而软件则是实现硬件功能的关键。
2. 二进制与十进制计算机使用的是二进制,即由0和1组成的数字系统。
而人类通常使用的是十进制,即由0到9组成的数字系统。
转换二进制与十进制可以加深对计算机数字表示的理解。
3. 计算机网络计算机网络包括局域网(LAN)、广域网(WAN)等,通过各种设备连接起来,实现信息的传输与共享。
了解计算机网络的基本概念与工作原理对于网络通信有着重要的意义。
4. 数据结构与算法数据结构是组织和存储数据的方式,而算法是解决问题的一系列步骤。
了解不同的数据结构和算法有助于学习编程和解决实际问题。
5. 操作系统操作系统是计算机的核心软件,负责管理计算机的硬件和软件资源,并提供给用户一个友好的界面。
掌握操作系统的基本功能和原理有助于更好地使用计算机。
二、计算思维知识点1. 抽象与模型抽象是将复杂的问题简化为一系列可处理的概念和模型。
模型是对真实世界的一种简化和抽象,通过模型可以更好地理解问题的本质。
2. 分解与组合将一个问题分解为更小的子问题,通过解决各个子问题最终解决整个问题。
同时,将多个简单的问题组合起来也可以解决复杂的问题。
3. 模式识别与建模通过观察和分析,寻找问题的规律和模式,并将其抽象为合适的模型,以便于问题的解决和优化。
4. 自动化与智能化计算机的最大特点就是可以执行自动化任务。
计算思维要求我们将复杂的问题进行自动化处理,同时,利用人工智能等技术实现智能化任务。
5. 算法设计与优化设计高效的算法是解决问题的关键,同时也需要不断地考虑算法的优化和改进,以提升计算效率和解决问题的质量。
《大学计算机-计算思维》主要知识点清单以下须掌握:1.数制及其相互转换2.原码、反码和补码,补码的意义3.定点数与浮点数的概念;浮点数的表示(教材p42图2-4真值的图示纠正,p48浮点数格式参照下图补充)定点数浮点数与定点数的关系IEEE754标准的浮点数4.字符的编码:ASCII码(7位编码,1字节存储即可,忽略教材中的校验位问题),Unicode5.汉字的区位码、GB2312-80国标码、机内码的对应关系与计算(教材中没讲为自学内容,须补充)6.图像与声音的表示原理,数据压缩(须补充)7.矢量图与位图,位图的存储容量计算8.图灵机模型的组成部分以及模型的意义9.冯·诺依曼的“存储程序控制”工作原理。
计算机的五大组成部件及其功能。
(教材p65图3-2只是以运算器为核心的图示,一条指令的执行过程表述不够清楚,补充讲解以下两张图)10.CPU的结构、功能与性能参数。
11.指令,一条指令的执行过程。
12.总线,计算机中通常含有哪几种类型的总线。
13.Cache的作用;内存的结构;ROM、RAM等14.硬盘、光盘的存储原理;磁道、扇区、磁盘块、光道等;存储体系;硬盘存储空间计算15.计算机系统的结构,软件的分类。
16.常用操作系统;操作系统的作用17.图形用户界面GUI、命令行用户界面CUI18.操作系统的进程管理功能,生存期的三态变化19.操作系统的存储管理功能20.操作系统的文件管理,目录,文件分配表,树形目录结构。
21.文件的相对路径与绝对路径22.Windows文件名规则,不能使用哪些字符/ \ “ | < > * ? :23.操作系统的设备管理功能24.计算机网络:分类、拓扑结构25.网络协议3要素26.计算机网络:ISO/OSI参考模型(教材p142只有一张图,并没有讲解分层的思想、各层的功能、虚通信实通信等概念,参照以下层次图补充)27.计算机网络相关概念解释:数字信号与模拟信号、带宽、数据传输率、比特率与波特率及其关系,数据传输方式等。
大学计算机基础知识点第一章计算思维与计算机1、三大科学思维——理论思维(以数学为基础的理论思维)、实验思维以物理为基础的实验思维、计算思维2、计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动.3、计算思维的本质:抽象+自动化4、计算机是一种能存储程序和数据,自动执行程序、快速而精确地完成对各种数字化信息处理的电子设备5、1946年(美)宾夕法尼亚大学第一台数字电子计算机 ENIAC诞生。
6、按照计算机所使用的逻辑部件将计算机的发展分为四代:第一代:(1946-1957) 电子管时代第二代:(1958-1964) 晶体管时代第三代:(1965-1970) 中小规模集成电路第四代:(1971-至今) 大规模、超大规模集成电路(出现网络,使用面日益广泛)7、存储程序的工作原理是:在计算机中设置存储器,将程序和数据存放到存储器中,计算机按照程序指定的逻辑顺序依次取出存储器中的内容进行处理,直到得出结果。
计算机有两个基本能力:一是能够存储程序和数据二是能够自动地执行程序程序(Program) :是指可以连续执行的一条条指令的集合指令(Instruction) :是指计算机完成某一种操作的命令指令是一组二进制代码操作码:指出进行什么操作地址码:是规定操作数的值或地址、操作结果的地址及下一条指令的地址等计算机硬件系统第二章⏹数制(Numbering System)即表示数值的方法,有进位计数制和非进位计数制两种⏹进位计数制的基本特点如下:☐使用固定个数的数码表示数值的大小☐逢R进一☐采用位权表示法数制的转换二进制、八进制、十六进制和十进制之间的转换信息的存储单位(位、字节)除字节外,还有千字节(KB)、兆字节(MB)、吉字节(GB)、太字节(TB),拍字节(PB)。
它们的换算关系原码、反码、补码之间的转换ASCII(American Standard Code for Information Interchange)码,即美国标准信息交换代码。
在这种编码方案中,用八位二进制(一个字节)来存放一个字符,常用字符有128个,编码从0到127ASCII码无需记忆,只要了解0-9依次升高,a-z依次升高就可以汉字的编码:区位码、国标码、机内码的转换字形码所占字节的计算第三章◆微处理器也叫中央处理单元(CPU),主要由运算器和控制器组成,是任何微型计算机系统中必备的核心部件。
◆内存储器◆内存储器按其工作方式的不同,可以分为随机存取存储器(RAM)、只读存储器(ROM) 。
◆ROM是只能读出信息而不能由用户写入信息的存储器,断电后,其中的信息也不会丢失。
◆RAM是指在CPU运行期间既可读出信息也可写入信息的存储器,但断电后,写入的信息会丢失。
◆注意:CPU只能直接对内存进行读写,而不能直接读写外存为了解决主存RAM与CPU工作速度不匹配的问题,在CPU和主存之间设置了一级高速度、小容量的存储器,称之为高速缓冲存储器●外存储器即外存,其主要作用是长期存放计算机工作所需要的系统文件、应用程序、用户程序、文档和数据等。
外存中存储的程序和数据必须先送入内存,才能被计算机执行。
●总线(BUS)是连接微机中各个部件的一组物理信号线,用于各部件之间的信息传输。
●一次传输信息的位数称为总线宽度。
按照总线上传送信息类型的不同,可将总线分为数据总线、地址总线和控制总线。
控制总线(CB):用控制总线来传送控制信号地址总线(AB):通常地址总线是单向的。
地址总线的宽度与所寻址的范围有关,即地址总线的位数决定了CPU可直接寻址的内存空间大小,一般来说,若地址总线为n根,则可寻址空间为2n字节比如8位微机的地址总线为16根,则其最大可寻址空间为216=64KB数据总线(DB):是CPU同各部件交换信息的通路。
数据总线都是双向的。
BIOS:实际上就是微机的基本输入输出系统(Basic Input-Output System),其内容集成在微机主板上的一个ROM芯片上,主要保存着有关微机系统最重要的基本输入输出程序,系统信息设置、开机上电自检程序和系统启动自举程序等。
计算机软件是指为了充分发挥计算机硬件的效能和方便用户使用计算机而设计的各种程序和数据的总和。
软件分为:系统软件、应用软件系统软件是指控制计算机的运行,管理计算机的各种资源,并为应用软件提供支持和服务的一类软件操作系统(operating system),它管理和控制计算机系统中的硬件及软件资源,为用户提供一个功能强大、使用方便且可扩展的工作环境,它是配置在计算机硬件上的第一层软件,是对硬件功能的扩充应用软件是指用户为了解决各种实际问题而开发和研制的软件,它在系统软件的支持下运行第四章算法的特性:确定性、可行性、有穷性、有零个或多个输入、有一个或多个输出算法的描述图形符号符号名称说明起始、终止框表示算法的开始或结束输入、输出框框中标明输入、输出的内容处理框框中标明进行什么处理用自然语言表示:就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来用流程图表示:就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法用程序设计语言表示常量与变量常量:在程序执行过程中,其值不发生改变的量称为常量变量:在程序运行过程中,其值可以改变的量称为变量。
一个变量有一个名字 ,变量通过其名字来访问变量的访问主要有“读”和“写”两种操作运算符 :用于告知计算机对数据进行操作的类型、方式和功能表达式 :用运算符将运算对象(操作数或另一个表达式)连接起来的、符合语法规则的式子称为表达式。
控制语句对应的三种结构:顺序结构、选择结构、循环结构常用算法:极值算法、求和算法、枚举算法、迭代算法第五章数据结构包括以下三方面内容:逻辑结构、存储结构、和对数据的操作❖ 逻辑结构:数据元素之间逻辑上的关系,数据的组织形式。
简称为数据结构.❖ 数据的逻辑结构具体可分为四类:① 集合 ② 线性结构 ③ 树型结构 ④ 图状结构存储结构:数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。
一般地,一个存储结构包括以下两个主要部分存储结点(简称结点),每个结点存放一个数据元素② 数据元素之间关系的表示,也就是逻辑结构的计算机内部表示线性表: 是n(n ≥O)个同类型数据元素(结点)的有穷序列。
其中数据元素的个数n 称为线性表的长度(简称表长)。
表长为O 的线性表称为空表。
表示成:(a 1,a 2 …,a n )线性表逻辑结构的基本特征:① 存在唯一的一个被称为“第一个”的数据元素和唯一的一个被称为“最后一个”的数据元素;② 除第一个数据元素外,其他数据元素有且仅有一个直接前趋元素;③ 除最后一个数据元素外,其他数据元素有且仅有一个直接后继元素判断框 框中标明判定条件并在框外标明判定后的两种结果的流向流程线 表示从某一框到另一框的流向 连接点表示算法流向出口或入口连接点线性表的顺序存储结构顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素特点:逻辑结构中相邻的结点在存储结构中仍相邻在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1) 插入:在表的第i(1≤i≤n+1)个位置上,插入一个新结点x,使线性表的长度加1 。
基本步骤为:①将结点a i…a n各后移一个位置,以便空出第i个位置;②将新结点x置入第i个位置;③表长加l删除:将表的第i(1≤i≤n)个结点删去,使线性表的长度减1。
基本步骤为:①结点a i+1…a n依次前移一个位置(覆盖被删结点a i);②表长减1单链表是用一组任意的存储单元来存放线性表的结点。
单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成;数据域用于存储线性表一个数据元素;指针域用于存放一个指针,该指针指向其直接后继结点。
这样,所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次序不一定相同特点:指针为数据元素之间的逻辑关系的映像栈的逻辑结构和线性表相同,但是,栈(Stack)是仅限在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶,另一端称为栈底,表中无元素时为空栈栈的运算原则是“先进后出”插入运算称为进栈(或入栈)删除运算称为退栈(或出栈)基本运算为:入栈、出栈、取栈顶元素队列(Queue),两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端称为队头(front),允许插入的一端称为队尾(real)队列(Queue),两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端称为队头(front),允许插入的一端称为队尾(real)树是n(n≥0)个结点的有限集合。
在任意一棵非空树中:①有且仅有一个特定的称为根的结点:②当n>l时,其余结点分为m(m>0)个互不相交的非空集合T1,T2,…,Tm,其中每一个集合本身又是一棵树,并称为根的子树。
树是一种“分支层次”结构。
“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;“层次”是指树上所有结点可以按它们的层数划分成不同的“层次度:树上任一结点所拥有的子树的数目称为该结点的度。
叶子或终端结点:度为0的结点称为叶子或终端结点。
非终端结点或分支结点:度大于O的结点称为非终端结点或分支结点。
树的度:一棵树中所有结点的度的最大值称为该树的度。
➢若树中结点A是结点B的直接前趋,则称A为B的双亲或父结点,称B为A的孩子或子结点。
➢父结点相同的结点互称为兄弟。
➢一棵树上的任何结点(不包括根本身)称为根的子孙。
反之,若B是A的子孙,则称A是B的祖先➢(3)结点的层数(或深度)从根开始算起:根的层数为l,其余结点的层数为其双亲的层数加l。
一棵树中所有结点层数的最大值称为该树的高度或深度二叉树:是结点的有穷集合,它或者是空集,或者同时满足下述两个条件:①有且仅有一个称为根的结点;②其余结点分为两个互不相交的集合T1、T2,T1与T2都是二叉树,并且Tl与T2有顺序关系(T1在T2之前),它们分别称为根的左子树和右子树。
二叉树的每个结点至多只有两棵子树,并且这两棵子树之间有次序关系。
二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子二叉树的基本性质①二叉树第i(i≥1)层上至多有2i-1个结点。
②深度为k(k≥1)的二叉树至多有2k-1个结点。
③对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。
❑满二叉树一棵深度为k(k≥1)且有2k -1个结点的二叉树称为满二叉树,这种树的特点是每一层上的结点数都是最大结点数。