学海网

数据结构复习提纲（共18页）
第1章 概述
1．概念和术语
数据：是能输入到计算机中并能被计算机程序处理的符号的总称。
数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。
数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。
数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。
数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。
数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。
算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。
......
第2、3章 线性表、栈、队列
1．线性表的定义
线性表是n个数据元素的有限序列，其中n（n≥0）为线性表的长度。
线性表中各个元素的类型相同。对于线性表（a1，a2，…，ai，…，an）而言，数据元素a1没有直接前趋，an没有直接后继，表中的其它元素ai（2≤i≤n-1）有且仅一个直接前趋ai-1和直接后继ai+1。
2．顺序表
顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。在C语言中可用一维数组来表示。在顺序表中，以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。
顺序表是一种随机存储结构，只要确定了存储顺序表的起始位置，则表中任一元素都可以随机存取。所以在顺序表中可以方便的进行数据元素的查找及存取。但是在进行插入和删除操作时，将会引起元素的大量移动，因而效率比较低，并且易产生空间浪费或“上溢”现象。
顺序表的操作还应注意元素的存储位置，即数组下标（C语言中下标从0开始）。
......