第一章 绪论
1、 数据结构是计算机中存储、组织数据的方式。精心选择的数据
结构可以带来最优效率的算法。 2、 程序设计= 算法 +数据结构 3、 解决问题方法的效率： ? 跟数据的组织方式有关 ? 跟空间的利用效率有关 ? 跟算法的巧妙程度有关
4、 数据：所有能输入到计算机中,且被计算机处理的符号的集合，
是计算机操作对象的总称；
是计算机处理的信息的某种特定的符号表示形式。 5、 数据元素：数据中的一个“个体”,数据结构中讨论的基本单
位。 相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。
6、 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,
如学号。数据元素是数据项的集合。 7、 数据对象：性质相同的数据元素的集合. 例如: 所有运动员的记录集合
8、 数据结构：是相互间存在某种关系的数据元素集合。 9、 数据结构是带结构的数据元素的集合。 10、 不同的关系构成不同的结构。 11、 次序关系：
{
12、 对每种数据结构，主要讨论如下两方面的问题：
1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现； 13、 数据的逻辑结构：
数据之间的结构关系，是具体关系的抽象。 数据结构的基本操作： 指对数据结构的加工处理。 14、 数据的存储结构 (物理结构)： 数据结构在计算机内存中的表示。
数据结构基本操作的实现：
基本操作在计算机上的实现（方法)。 15、 数据结构的有关概念 16、数据元素的4类的基本结构：
1集合； ○
2 线性结构：结构中数据元素之间存在一对一的关系； ○
3 树形结构：结构中数据元素之间存在一对多的关系； ○
4 图状结构或网状结构：结构中数据元素之间存在多对多○的关系。
17、 C语言的优点：C语言可以直接操作内存。 18、 每个节点都由两部分组成：数据域和指针域。 19、 链接存储结构特点：
? 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。 ? 逻辑上相邻的节点物理上不必相邻。 ? 插入、删除灵活
(不必移动节点，只要改变节点中的指针)。
20、 数据类型 是一个值的集合和定义在此集合上的一组操作的
总称。
21、 ADT 有两个重要特征:数据抽象和数据封装。
22、 抽象数据类型 (Abstract Data Type 简称ADT)：是指一个数
学模型以及定义在此数学模型上的一组操作。
23、 抽象数据类型有： 数据对象〈数据对象的定义〉、数据关
系〈数据关系的定义〉、 基本操作〈基本操作的定义〉。 24、 数据类型的定义和含义。
定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
含义：将数据按一定次序与形式存放的结构。 24、算法空间复杂度S(n) 算法的存储量包括：
① 输入数据所占的空间； ② 程序本身所占的空间； ③ 辅助变量所占的空间。
25、 算法具有有穷性、确定性、可行性、输入和输出五大特性。
26、 抽象数据类型具有数据抽象、数据封装的特点。 27、 数据的储存结构分为：顺序存储结构和链式存储结构。
第二章 线性表
1、线性结构的特点：在数据元素中的非空有限集中。 （1）存在唯一的一个被称作“第一”的数据元素； （2）存在唯一的一个被称作“最后一个”的数据元素； （3）除第一个外，集合中的每一个数据元素均只有一个前驱； （4）除最后一个外，集合中的每一个数据元素均只有一个后继。 2、线性表(Linear List) ：一个线性表是n个数据元素的有限序列。 3、线性表的顺序存储实现： typedef struct {
ElementType Data[MAXSIZE]; } List; List L, *PtrL;
4、初始化（建立空的顺序表）
List *MakeEmpty( ) { List *PtrL;
PtrL = (List *)malloc( sizeof(List) ); PtrL->Last = -1; return PtrL; }
int Last;
5、查找
int Find( ElementType X, List *PtrL ) { int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X ) i++;
if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */ else return i; /* 找到后返回的是存储位置 */ }
6、插入算法
void Insert( ElementType X, int i, List *PtrL ) { int j;
if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不能插入*/ printf(＂表满＂); return; }
if ( i < 1 || i > PtrL->Last+2) { /*检查插入位置的合法性*/ printf(＂位置不合法＂); return; }
for ( j = PtrL->Last; j >= i-1; j-- )
PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai～ an倒序向后移动*/
数据结构 清华大学出版社 严蔚敏吴伟民编著
