基础数据结构

数据结构的基本概念

数据元素

数据对象

数据关系

抽象数据类型

抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，用（数据对象，数据关系，基本操作集）三元组来表示，从而构成一个完整的数据结构的定义。

定义补充：

数据类型：

1）原子类型，其值不可再分的数据类型

2）结构类型，其值可以再分解为若干成分（分量）的数据类型

3）抽象数据类型，抽象数据组织（包括数据对象，数据关系）及与之相关的操作（即数据操作集）

数据结构：

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，这些关系称为结构。数据结构包括三方面内容：逻辑结构、存储结构和数据的运算。

提问：为什么抽象数据类型可以定义完整的数据结构？数据结构的三要素包括逻辑结构和存储结构，抽象数据类型也定义了存储结构吗？比如说堆，堆是一个抽象数据结构，但是堆既可以在顺序结构上实现，也可以在链式结构上实现，定义一个堆需要定义它在什么结构上实现吗？

顺序表

哈希表

有序表

单链表

数据结构的三要素是：逻辑结构，存储结构，数据运算

逻辑结构：元素之间的逻辑关系，与存储结构无关，是独立于计算机的。

常见的逻辑结构有：一般线性表，栈，队列，串，数组，广义表，一般树，二叉树，有向图，无向图

存储结构：数据结构在计算机中的表示，包括数据元素的表示和关系的表示。

常见的存储结构有：顺序存储，链式存储，索引存储和散列存储。

选项中顺序表，哈希表和单链表都是既规定了逻辑结构又规定了存储结构，是数据结构，不能只看作逻辑结构。只有有序表，仅描述元素之间的逻辑关系。

循环队列

链表

哈希表

栈

数据的存储结构有顺序存储，链式存储，索引存储和散列存储。循环队列使用顺序表表示的队列，是一种数据结构。

提问：这是否与P3，1矛盾？题目解释中，栈是抽象数据类型，与存储结构无关，即数据关系中只定义了逻辑结构，独立于存储结构。

循环队列的定义依赖于存储结构吗？循环链表可以用顺序存储实现，也可以用链式存储实现，其定义依赖于存储结构吗？

数据的逻辑结构独立于其存储结构

数据的存储结构独立于其逻辑结构

数据的逻辑结构唯一决定了其存储结构

数据结构仅由其逻辑结构和存储结构决定

数据的逻辑结构采用抽象的表达方式，独立于存储结构。

数据的操作方法

数据元素的类型

数据元素之间的关系

数据的存取方法

完整的数据结构包括数据元素之间的关系以及在这些数据上的运算，按照优先级来选择，应该优先选数据元素之间的关系

程序

问题求解步骤的描述

要满足五个基本特性

A和C

算法：

算法是对特定问题求解步骤的一种描述。

算法具有五个重要特性：1）有穷性，2）确定性，3）可行性，4）输入，5）输出

程序不一定满足有穷性，但是算法必须有穷

五个特性只是算法的必要条件，而不是算法的定义

n(n+1)

n

n+1

n^2

2+4+8+...+2n=2*(1+...+n)=n(n+1)

线性表

由n个实数组成的集合

由100个字符组成的序列

所有整数组成的序列

邻接表

线性表的特点如下：

1）元素个数有限

2）元素具有逻辑上的顺序性

3）每个元素都是数据元素

4）所有元素的数据类型相同

访问第i个节点和求第i个节点的直接前驱

在最后一个节点后插入一个新节点

删除第一个节点

在第i个节点后插入一个节点

不要读错题目，题目中已经给出了——数组表示

1<=i<=n

1<=i<=n+1

0<=i<=n-1

0<=i<=n

线性表中元素起始序号是1，末尾序号是n

顺序存储方式只能用于存储线性结构

取顺序表的第i个元素的时间与i的大小有关

静态链表需要分配较大的连续空间，插入和删除不需要移动元素

在长度为n的有序单链表保序插入一个元素时间复杂度为O(n)

用单链表表示队列需要带尾指针

静态链表借助数组来描述线性表的链式存储结构，每个表项都有数据域和指针域，需要预先分配一块连续内存空间，插入删除元素只需要修改指针不需要移动元素

提问：如何用单链表实现队列——尾进头出

O(1)

O(n)

O(n^2)

O(nlog_2(n))

数组排序最好的时间复杂度为O(nlog_2(n))

使单链表至少有一个节点

标识表节点中首节点的位置

方便运算的实现

说明单链表是线性表的链式存储

目的是方便运算的实现——统一空表和非空表的处理：1）插入删除操作的处理统一，无需再判断是否是再第一个元素之前插入或者删除第一个元素；2）不论链表是否非空，链表的头指针不变。

栈和队列

抽象数据类型

逻辑结构

存储结构

运算

栈和队列的逻辑结构都是相同的，都属于线性结构中的受限线性表，只是它们对数据的运算不同

4

5

3

6

C语言标识符由大小写字母、数字以及下划线构成，但是数字不能放在首位

递归

进制转换

迷宫求解

缓冲区

栈的应用：括号匹配，表达式转换，递归，迷宫求解

括号匹配

迷宫求解

页面替换算法

递归

队列的应用：层序遍历，缓冲区，页面替换算法

递归算法通常更高效

非递归算法通常更高效

两者相同

无法比较

通常情况下递归算法在实际执行过程中包含很多重复计算，所以效率更低。比如用递归求斐波那契数列，但是可以通过记录已经求出的项来剪枝

rear=rear+1

rear=(rear+1) mod (n-1)

rear=(rear+1) mod n

rear=(rear+1) mod (n+1)

入队时，队尾指针的操作为Q.rear=(Q.rear+1)%Maxsize，本题中Maxsize=n+1

提问：循环队列用数组如何实现？

仅修改头指针

仅修改尾指针

头尾指针都要修改

头尾指针可能都要修改

特殊情况是，队列中只有一个元素时，删除后队列为空，需将尾指针修改为rear=NULL

提问：链式存储方式如何实现队列？

队列的链式存储方式中，头指针和尾指针都是指向元素的，尤其是尾指针，在队列非空的时候是指向最后一个元素而不是空节点的！所以对仅含有一个元素的队列进行出队操作后，要修改的指针有front=front->link;rear=NULL;

类似地，front在队列为空时指向NULL，在队列非空的时候是指向第一个元素的！所以向空队列中插入一个元素，需要进行的修改的指针有rear=new LinkNode (x);front=rear;

O(n)

O(1)

O(n^2)

O(nlog_2(n))

队头固定在表尾，只有头指针，即没有尾指针指向队头，出队需要遍历链表到队尾，时间复杂度为O(n)

提问：循环单链表如何实现队列？队列是头进尾出还是尾进头出？

尾进头出，而且对于下标、maxsize有严格对应关系：maxsize=n则下下标从0到n-1；注意下标一定是从0开始的

0123

0112

0231

1211

不要粗心错