计算机二级考试公共基础知识：数据结构与算法详解

计算机二级考试公共基础知识：数据结构与算法详解

引用

CSDN

1.

https://m.blog.csdn.net/m0_60631827/article/details/144948189

本文主要介绍了计算机二级考试中公共基础知识部分的数据结构与算法相关内容。从算法的概念、特征和复杂度，到数据结构的基本概念、表示方法和分类，再到线性表的详细讲解，内容较为全面且系统。

一、算法

1、算法的概念

• 算法是指解题方案的完整且准确的描述，是一系列解决问题的清晰指令。算法不等于数学上的计算方法，也不等于程序。
• 常见的算法设计方法有列举法、归纳法、递推法和递归法等。
• 在算法设计时，不能只考虑算法的效率，还需要考虑其他因素。

2、算法的特征

• 可行性：算法中的每一个步骤必须能够实现，且执行的结果能够达到预期的目的。
• 确定性：算法中的每一个步骤都有它确定的含义，不存在一个步骤有多个含义的情况。不允许有模棱两可的解释，也不允许有多义性。
• 有穷性：算法必须在有限时间内完成，即算法必须能在执行有限个步骤之后终止。
• 拥有足够的情报：一个有效的算法应该有足够多的、正确的输入信息或初始化信息，并且至少有一个输出结果。

3、算法的复杂度

算法的复杂度主要包括时间复杂度和空间复杂度，但两者之间没有直接的联系。

• 时间复杂度：执行算法所需要的计算工作量，即算法语句的执行次数。
• 空间复杂度：算法在执行过程中所需要的计算机存储空间。包括程序本身所占的存储空间、输入数据所占的存储空间、算法执行过程中所需要的额外空间。如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。

二、数据结构

1、数据结构的概念

• 数据结构，即带有“结构”的数据元素的集合。一般来说，现实世界中客观存在的一切个体都可以是数据元素。
• 在数据处理时，通常把数据元素之间的特殊关系称为前后件关系。

2、数据结构的两种表示方法

（1）二元组表示

B = (D, R)
D = {春, 夏, 秋, 冬}
R = {(春, 夏), (夏, 秋), (秋, 冬)}
# D：即data，表示数据元素
# R：即relationship，表示关系

（2）图形表示

3、数据结构分类

（1）逻辑结构

• 数据的逻辑结构是指反映数据元素之间逻辑关系（前后件关系）的数据结构。
• 数据的逻辑结构分为线性结构和非线性结构。

（2）存储结构

• 数据的逻辑结构在计算机存储空间中的存放形式被称为数据的存储结构，也可以称为数据的物理结构。
• 常见的存储结构有顺序存储、链式存储、索引存储和散列存储等。

三、线性表

1、线性表的概念

• 线性表是一种逻辑结构，它是最简单、最常用的一种数据结构。
• 在线性表中，数据元素之间是一对一的关系。
• 线性表是由n(n≥0)个相同数据类型的数据素组成的一个有限序列，将其表示为(a1,a2,a3,…,an)
• 其中a1,a2,a3,…,an表示n个数据元素，a1为表头元素，也叫根节点，an为表尾元素，叫终端节点。

2、线性表的特性

非空线性表的结构特征：

• 有且只有一个根结点a1，它无前件。
• 有且只有一个终端结点an，它无后件。
• 线性表的结点个数就是该线性表的长度。
  当n=0时，线性表为空表

3、顺序表

3.1 概述

• 将线性表中的数据元素存储在一组地址连续的存储单元里，使得逻辑上相邻的两个元素在物理位置上也相邻，称为线性表的顺序存储，又称为顺序表。
• 在顺序表中可以进行插入、删除、修改和查询数据元素等操作，常用的操作是插入和删除。

3.2 插入操作

• 在顺序表中插入元素时，首先需找到要插入元素的位置。如果该位置上没有元素则直接插入；若该位置上有元素，需要将该位置上的元素及其后面的元素向后移动，空出需要插入元素的位置，最后将新元素插入到指定的位置上
• 当线性表的存储空间已满时，不能再继续插入新元素。若继续插入，则会产生“上溢”。

3.3 删除操作

• 在线性表中删除已有的元素，然后将删除元素之后的所有元素依次向前移动相应个位置并减少线性表的结点数。
• 若线性表为空时，不能再进行数据元素的删除。若继续删除，则会产生“下溢”错误。

4、线性链表

4.1 概述

• 线性表的链式存储结构称为线性链表，用一组地址任意的存储单元存放线性表中的各个数据元素不要求逻辑上相邻的两个元素在物理位置也相邻。
• 链式存储结构中的结点通常由两部分组成，用于存放数据的部分称为数据域，用于存放指针的部分称为指针域。
• 线性链表又分为了单向链表，双向链表，循环链表。

4.2 单向链表

单向链表是链表的一种，它的指向是单向的，对链表的访问是从头部开始顺序读取元素，其每个结点都有指针成员变量指向列表中的下一个结点。单向链表的head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

4.3 双向链表

双向链表有两个指针域，一个指向前件结点，一个指向后件结点。指向前件结点的指针称为左指针 (Llink)，指向后件结点的指针称为右指针 (Rlink)。

4.4 循环链表

• 循环链表是将表中最后一个结点的指针域指向头结点，使整个链表形成一个环。
• 在循环链表中，只要知道任一结点的位置，都可以从该结点位置出发，访问表中所有的结点。
• 循环链表插入和删除元素比单向链表更加简单。表头结点是循环链表中固有的结点，即使表中没有数据，表中至少都还有一个表头结点，这样就实现了空表和非空表运算的统一。

4.5 插入操作

移除要插入位置的指针，然后为要插入的元素加上指针，前一个元素指针域的指针指向后一个元素的地址域。

4.6 删除操作

直接删除元素即可，删除后加上指针，前一个元素指针域的指针指向后一个元素的地址域。

4.7 查找操作

如果要在线性链表中查找指定元素，就需要从队头指针出发，逐个向后搜索，直到找到指定元素或链表尾部为止。当搜索到指定元素时，需要返回该元素的所在位置；若在链表中没有找到指定元素，则返回空。