1.1 数据结构的基本概念
<strong>数据类型与抽象数据类型</strong>
重要程度：7 分
<h2>数据类型与抽象数据类型</h2>
<h3>数据类型</h3>
<p>在计算机科学中，<strong>数据类型</strong>是用来定义程序中变量的种类。它规定了变量可以存储的数据形式以及在这个数据上允许进行的操作。例如，在C语言中，基本的数据类型包括整型（int）、浮点型（float）、字符型（char）等。</p>
<h3>抽象数据类型</h3>
<p><strong>抽象数据类型 (Abstract Data Type, ADT)</strong> 是指一种数学模型以及定义在此模型上的一组操作。与具体实现无关，只关注数据对象集和相关操作集。ADT提供了一种方法来封装数据和功能，使得用户只需知道如何使用这些功能而不需要了解其内部工作原理。</p>
<p>ADT通常包含以下几个部分：</p>
<ul>
<li>数据对象：ADT所管理的数据集合。</li>
<li>操作：对数据对象执行的操作或方法。</li>
<li>约束条件：对数据对象及操作的限制。</li>
</ul>
<h4>示例 - 栈(Stack)作为ADT</h4>
<p>栈是一种典型的ADT，具有后进先出(LIFO)的特点。它的主要操作包括：</p>
<ul>
<li>Push(压入)：向栈顶添加一个元素。</li>
<li>Pop(弹出)：移除栈顶元素，并返回该元素值。</li>
<li>Peek/Top(查看顶部)：获取但不移除栈顶元素。</li>
<li>IsEmpty(是否为空)：判断栈是否为空。</li>
</ul>
<p>下面是一个简单的栈ADT的伪代码表示：</p>
<pre>
ADT Stack {
数据对象：D = { ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0 }
操作：
Push(item)
前提：item是合法的元素
结果：将item加入到栈顶
Pop()
前提：栈非空
结果：移除并返回栈顶元素
Peek()
前提：栈非空
结果：返回栈顶元素而不移除
IsEmpty()
结果：如果栈为空则返回true，否则返回false
}
</pre>
<h4>练习题</h4>
<p>设计一个队列(Queue)的ADT描述，包括至少四个基本操作。</p>
<pre>
ADT Queue {
数据对象：D = { ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0 }
操作：
Enqueue(item)
前提：item是合法的元素
结果：将item加入队尾
Dequeue()
前提：队列非空
结果：移除并返回队首元素
Front()
前提：队列非空
结果：返回队首元素而不移除
IsEmpty()
结果：如果队列为空则返回true，否则返回false
}
</pre>
<p>通过上述例子，我们可以看到如何使用ADT来定义数据结构的行为特征，而无需关心具体的实现细节。</p>