数据结构(c语言版)复习知识点2017

《数据结构(c语言版)复习知识点2017》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论1.1数据、数据元素、数据项、数据结构等基本概念1.数据（data）：客观事物的符号表示，在计算机科学中指所有能输入计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声音、图像。2.数据元素（dataelement）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3.一个数据元素可能由若干个数据项（dataitem）组成。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段）。故不是组成数据的最小单位。数据项是构成数据的最小单位。4.数据对象（dataobject）：性质相同

2、的数据元素的集合，是数据的一个子集。5.数据结构（datastructure）：数据元素以及数据元素之间存在的关系。6.数据结构主要描述：数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算，即数据的逻辑结构、存储结构和数据的操作集合1.2数据结构的逻辑结构、存储结构的含义及其相互关系1.数据的逻辑结构：用形式化方式描述数据元素间的关系。数据的逻辑结构独立于计算机，是数据本身所固有的。用于算法的设计。两大类逻辑结构：线性结构（线性表、栈、队列、数组和串），非线性结构（树和图）。2.数据的物理结构（也称存储结构）：数据在计算机中

3、的具体表示。包括数据元素的表示和关系的表示。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。用于算法的实现。数据的存储方式可分为如下两类：顺序存储、链接存储。1.3算法1.算法的定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列。2.算法的特性：有穷性——算法必须在执行有穷步之后结束，而且每一步都可在有穷时间内完成确定性——每条指令无二义性。并且，相同的输入只能得到相同的输出；可行性——算法中描述的每一操作，都可以通过已实现的基本运算来实现。输入——算法有零至多个输入。输出——算法有一个至多个输出3.算法效率的度量：时

4、间复杂度和空间复杂度及计算。第二章线性表2.1线性表的逻辑结构特征存在唯一的一个被称作第一个的数据元素；存在唯一的一个被称作最后一个的数据元素；除第一个元素之外，集合中的每个数据元素均只有一个前驱；除最后一个元素之外，集合中的每个数据元素均只有一个后继。2.2线性表的顺序存储结构1.用一组连续的存储单元依次存储线性表的数据元素。在线性表的顺序存储表示中，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的顺序存储结构是一种随机存取的存储结构。LOC(ai+1)=LOC(ai)+1LOC(ai+1)=LOC(a1)+i*1

5、LOC(ai)表示元素ai的存储位置；LOC(a1)表示第一个数据元素的存储位置，通常称为线性表的起始位置或基地址每个数据元素占用1个存储单元。2.线性顺序表上的插入是指在第i(1≤i≤n+1)个位置插入一个新的数据元素，需将第i至第n共(n-i+1)个元素后移注意：Ø顺序表中数据区域有listSize个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。Ø要检验插入位置的有效性，这里i的有效范围是：1<=i<=n+1，其中n为原表长。Ø注意数据的移动方向算法时间复杂度移动元素个数：n-i

6、+1平均移动元素个数：n/2T（n）=O（n）；3.线性顺序表上的删除是指第i(1≤i≤n)个数据元素删除掉，需将第i+1至第n共（n-i)个元素前移注意：Ø删除第i个元素，i的取值为1<=i<=n,否则第i个元素不存在，因此，要检查删除位置的有效性。Ø当表空时不能做删除。Ø删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。算法时间复杂度：移动元素个数：n-i平均移动元素个数：（n-1）/2T（n）=O（n）；4.线性表的顺序存储。优点：逻辑相邻，物理相邻可以实现数据元素的随机存取；缺点：在作插入或是删除操作时，需要移动大量数

7、据元素2.3线性表的链式存储结构1.线性表链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素。在线性表的链式存储中，在进行插入或是删除操作时，不需要进行数据元素的移动，但不能实现数据元素的随机存取。2.线性链表的表示：数据元素、数据元素之间的关系；数据域存储数据元素，指针域存储数据元素之间的关系：直接后继的存储位置，线性链表：每个节点只包含一个指针域3.假定指针p指向线性链表中的第i个数据元素，则p->next为指向线性链表中第i+1个数据元素的指针。即p->data为ai，p->next->data为ai+1。(*p)表示p所

8、指向的结点(*p).dataÛp->data表示p指向结点的数据域(*p).nextÛp->next表示p指向结点的指针域4.在单链表中查找第i个元素StatusgetElem_L(LinkL