数据结构,清华大学出版社,严蔚敏吴伟民编著

《数据结构,清华大学出版社,严蔚敏吴伟民编著》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论1、数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。2、程序设计=算法+数据结构3、解决问题方法的效率：l跟数据的组织方式有关l跟空间的利用效率有关l跟算法的巧妙程度有关4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。6、数据项:相当于记录的“域”,是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。7、数据对象：性质相同的数据元素的集合.例

2、如:所有运动员的记录集合8、数据结构：是相互间存在某种关系的数据元素集合。9、数据结构是带结构的数据元素的集合。10、不同的关系构成不同的结构。11、次序关系：{

3、i=1,2,3,4,5,6}1、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；2、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理。14、数据的存储结构(物理结构)：数据结构在计算机内存中的表示。数据结构基本操作的实现：基本操作在计算机上的实现（方法)。15、数据结构的有关概念16、数

4、据元素的4类的基本结构：集合；线性结构：结构中数据元素之间存在一对一的关系；树形结构：结构中数据元素之间存在一对多的关系；图状结构或网状结构：结构中数据元素之间存在多对多的关系。17、C语言的优点：C语言可以直接操作内存。18、每个节点都由两部分组成：数据域和指针域。19、链接存储结构特点：l比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。l逻辑上相邻的节点物理上不必相邻。l插入、删除灵活(不必移动节点，只要改变节点中的指针)。20、数据类型是一个值的集合和定义在此集合上的一组操作的总称。21、ADT有两个重要特征:数据抽象和数据封装。22、抽象数据类型(AbstractDa

5、taType简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。23、抽象数据类型有：数据对象〈数据对象的定义〉、数据关系〈数据关系的定义〉、基本操作〈基本操作的定义〉。24、数据类型的定义和含义。定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。含义：将数据按一定次序与形式存放的结构。24、算法空间复杂度S(n)算法的存储量包括：①输入数据所占的空间；②程序本身所占的空间；③辅助变量所占的空间。17、算法具有有穷性、确定性、可行性、输入和输出五大特性。18、抽象数据类型具有数据抽象、数据封装的特点。19、数据的储存结构分为：顺序存储结构和链式存储结构。第二章线性

6、表1、线性结构的特点：在数据元素中的非空有限集中。（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。2、线性表(LinearList)：一个线性表是n个数据元素的有限序列。3、线性表的顺序存储实现：typedefstruct{ElementTypeData[MAXSIZE];intLast;}List;ListL,*PtrL;4、初始化（建立空的顺序表）List*MakeEmpty(){List*PtrL;PtrL=(List*)m

7、alloc(sizeof(List));PtrL->Last=-1;returnPtrL;}5、查找intFind(ElementTypeX,List*PtrL){inti=0;while(i<=PtrL->Last&&PtrL->Data[i]!=X)i++;if(i>PtrL->Last)return-1;/*如果没找到，返回-1*/elsereturni;/*找到后返回的是存储位置*/}6、插入算法voidInsert(ElementTypeX,inti,List*PtrL){intj;if(PtrL->Last==MAXSIZE-1){/*表空间已满，不能插入*/printf(＂表

8、满＂);return;}if(i<1

9、

10、i>PtrL->Last+2){/*检查插入位置的合法性*/printf(＂位置不合法＂);return;}for(j=PtrL->Last;j>=i-1;j--)PtrL->Data[j+1]=PtrL->Data[j];/*将ai～an倒序向后移动*/PtrL->Data[i-1]=X;/*新元素插入*/PtrL->Last++;/*Last仍指向最后元素*/return;}7