第一章绪论
数据结构与算法c++版 pdf
1、数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以
带来最优效率的算法。
2、程序设计= 算法+数据结构
3、解决问题方法的效率：
跟数据的组织方式有关
跟空间的利用效率有关
跟算法的巧妙程度有关
4、数据：所有能输入到计算机中，且被计算机处理的符号的集合，是计算机
操作对象的总称；
是计算机处理的信息的某种特定的符号表示形式。
5、数据元素：数据中的一个“个体” ，数据结构中讨论的基本单位。相当于
“记录” ，在计算机程序中通常作为一个整体考虑和处理。
6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位如学号。数
据元素是数据项的集合。
7、数据对象：性质相同的数据元素的集合.
例如: 所有运动员的记录集合
8、数据结构：是相互间存在某种关系的数据元素集合。
9、数据结构是带结构的数据元素的集合。
10、不同的关系构成不同的结构。
11、次序关系：
{vai,ai+1>|i=1,2,3,4,5,6}
12、 对每种数据结构，主要讨论如下两方面的问题：
1） 数据的逻辑结构，数据结构的基本操作；
2） 数据的存储结构，数据结构基本操作的实现；
13、 数据的逻辑结构：
数据之间的结构关系，是具体关系的抽象。
数据结构的基本操作：
指对数据结构的加工处理。
14、 数据的存储结构（物理结构）:
数据结构在计算机内存中的表示。
数据结构基本操作的实现：
基本操作在计算机上的实现（方法）。
15、数据结构的有关概念
|线性表
「上线性结构!栈
［队
（仁数据的逻辑结构=
i  B.非彌結构I 树形结构 J I 图形结构
木数据的存储结枸I A 噸序行储 B 链式存储 < 3、数据的运算：檢索.插入.删除*烽改等
16、数据元素的 4 类的基本结构 ：
① 集合； 数
£结构
的三
个
方廁
②线性结构：结构中数据元素之间存在一对一的关系；
③树形结构：结构中数据元素之间存在一对多的关系；
②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];
int Last;
} List;
List L, *PtrL;
4、初始化(建立空的顺序表)
List *MakeEmpty( )
{ List *PtrL;
PtrL = (List *)malloc( sizeof(List) );
PtrL->Last = -1;
return PtrL;
}
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;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。