本文主要是介绍408计算机学科专业基础综合——数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第1章 绪论
1.1 数据结构的基本概念
数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据类型是一个值的集合和定义在此集合上一组操作的总称。
- 原子类型：其值不可再分的数据类型
- 结构类型：其值可以再分解为若干成分（分量）的数据类型
- 抽象数据类型：抽象数据组织和与之相关的操作
抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。
数据结构的三要素：
- 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。
- 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。
- 数据的运算：包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
选择题
1.可以用（抽象数据类型）定义一个完整的数据结构。
3.以下属于逻辑结构的是（有序表）
A 顺序表 B 哈希表 C 有序表 D 单链表
4.以下与数据的存储结构无关的术语是（栈）
A 循环队列 B 链表 C 哈希表 D 栈
6.在存储数据时，通常不仅要存储各数据元素的值，还要存储（数据元素之间的关系）
7.链式存储设计时，结点内的存储单元地址（一定连续），不同结点间可以（不连续）
1.2 算法和算法评价
算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。一个算法有零个或多个的输入，有一个或多个的输出。
时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。
空间复杂度定义为该算法所耗费的存储空间。算法原地工作是指算法所需辅助空间是常量，即O(1)。
第2章 线性表
2.1 线性表的定义和基本操作
线性表是具有相同数据类型的n个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构。两者属于不同层面的概念，因此不要混淆。
选择题
2.以下（由100个字符组成的序列）是一个线性表。
A 由n个实数组成的集合 B 由100个字符组成的序列
C 所有整数组成的序列（无穷） D 邻接表（存储结构）
2.2 线性表的顺序表示
线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
顺序表最主要的特点是随机访问（随机存取），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。但插入和删除操作需要移动大量元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表插入操作：
最好情况：在表尾插入，元素后移语句不执行，时间复杂度为O(1)
最坏情况：在表头插入，元素后移语句将执行n次，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
顺序表删除操作：
最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)
最坏情况：删除表头元素，需要移动除第一个元素外的所有元素，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
顺序表按值查找（顺序查找）：
最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)
最坏情况：查找的元素在表尾或不存在时，需要比较n次，时间复杂度为O(n)
平均情况：平均时间复杂度为O(n)
选择题
4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（顺序表）的存储方式。
5.一个线性表最常用的操作是存取任一指定序号的元素和在最后进行插入删除操作，则利用（顺序表）存储方式可以节省时间。
10.若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（1 ≤ i ≤ n+1）
2.3 线性表的链式表示
链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，对线性表的插入和删除不需要移动元素，只需要修改指针。
单链表是非随机存储的存储结构，即不能直接找到表中某个特定的结点。
头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。
采用头插法建立单链表：从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
读入数据的顺序与生成的链表中元素的顺序是相反的。
每个结点插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)。
采用尾插法建立单链表：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
时间复杂度和头插法相同。
按序号查找结点值：在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
时间复杂度为O(n)。
按值查找表结点：从单链表第一个结点出发，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针，否则返回NULL。
时间复杂度为O(n)。
插入结点操作：先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
删除结点操作：先检查删除位置的合法性，然后找到待删除位置的前驱结点，即第i-1个结点，再将其删除。
时间复杂度为O(n)。
双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。双链表中执行按值查找和按位查找的操作和单链表相同，但双链表插入、删除操作的时间复杂度仅为O(1)。
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。故表中没有指针域为NULL的结点。
循环双链表 L中，某结点*p为尾结点时，p->next=L；当循环双链表为空表时，其头结点的prior域和next域都等于L。
静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标），又称为游标。
顺序表和链表的比较：
- 存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
- 逻辑结构与物理结构：采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻。
- 查找、插入和删除操作：对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可采用折半查找，时间复杂度为O(logn)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。链表插入、删除较优，只需修改相关结点的指针域即可。
- 空间分配：链式存储的结点空间只在需要的时候申请分配。
- 通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。
选择题
2.对于一个线性表即要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用链式存储方式。
4.下列关于线性表说法正确的是（D）
I. 顺序存储方式只能用于存储线性结构（同样适合图和树的存储，如满二叉树的顺序存储）
II. 取线性表的第i个元素的时间与i的大小有关（无关，顺序存储）
III. 静态链表需要分配较大的连续空间，插入和删除不需要移动元素
IV. 在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)
V. 若用单链表来表示队列，则应该选用带尾指针的循环链表
A I、II B I、III、IV、V C IV、V D III、IV、V
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（O(nlogn)）
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度为O(m)
9.单链表中，增加一个头结点的目的是为了（方便运算的实现）。
10.在一个长度为n的带头结点的单链表h上，设有尾指针r，则执行（删除单链表中最后一个元素）操作与链表的表长有关。
11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（head->next==NULL）；对于不带头结点的单链表，则判定空表的条件是（head == NULL）
13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（仅有尾指针的单循环链表）存储方式最省时间。
18.与单链表相比，双链表的优点之一是（访问前后相邻结点更灵活）。
19.带空结点的双循环链表L为空的条件是（L->prior==L && L->next == L）
20.一个链表最常用的操作是在末尾插入结点和删除结点，则选用（带头结点的双循环链表）最节省时间。
21.设对n个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（只有头结点指针没有尾结点指针的循环双链表）。
22.一个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（不带头结点且有尾指针的单循环链表）最节省时间。
25.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（静态链表）。
第3章 栈和队列
3.1 栈
栈：后进先出（LIFO），又称为后进先出的线性表
顺序栈的实现：
栈顶指针：S.top，初始时设置S.top=-1；栈顶元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。S.data[++S.top]=x。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。x=S.data[S.top–]。
栈空条件：S.top==-1；栈满条件：S.top==Maxsize-1；栈长：S.top+1
注意：如果栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为S.data[S.top++]=x；出栈操作变为x=S.data[–S.top]。相应的栈空、栈满条件也会发生变化。
共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=Maxsize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时刚好相反，0号栈先出栈再减1，1号栈先出栈再加1.
共享栈是为了更有效地利用存储空间，其存取数据的时间复杂度均为O(1)。
链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规
这篇关于408计算机学科专业基础综合——数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
