数据结构期末复习资料

《数据结构期末复习资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构期末复习材料第一章1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构(DataStructure)：相互之间存在一种或多种特定关系的数据元素的集合。2、数据结构的形式定义：二元组Data_Structure=(D,S)其中，D是数据元素的有限集，S是D上关系的有限集。3、数据元素之间关系的映像：１、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于数据(逻辑)结构，其实现取决

2、于物理结构。4、算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性：有穷性、确定性、可行性、输入、输出5、算法的评价——衡量算法优劣的标准正确性(correctness):满足具体问题的需求可读性(readability)：易读、易理解健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理效率与低存储量:执行时间短、存储空间小第二章1、线性表是一种最简单的线性结构。线性结构是一个数据元素的有序（次序）关系特点：存在唯一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素

3、；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继2、线性表类型的实现——顺序映像定义：用一组地址连续的存储单元依次存放线性表中的数据元素。以“存储位置相邻”表示有序对，则有：LOC(ai)=LOC(ai-1)+l其中l是一个数据元素所占存储量LOC(ai)=LOC(a1)+(i-1)×l特点：1、实现逻辑上相邻—物理地址相邻2、实现随机存取3、若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：4、线性表类

4、型的实现——链式映像线性链表特点：用一组地址任意的存储单元存放线性表中的数据元素。5、在单链表中第i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;p->next=s;//插入在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。q=p->next;p->next=q->next;e=q->data;free(q);5、循环链表：最后一个结点的指针域

5、的指针又指回第一个结点的链表。和单链表的差别仅在于：判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。6、双向链表的操作特点：1、“查询”和单链表相同；2、“插入”和“删除”时需要同时修改两个方向上的指针“插入”：s->next=p->next;p->next=s;s->next->prior=s;s->prior=p;（s是插入的结点）删除：p->next=p->next->next;p->next->prior=p;（要删除的是p的下一个结点）课后作业P13:2.3、2.5P15:2.8、2.9(2)第三章1、栈、队列的

6、特点：¨从数据元素间的逻辑关系看à是线性表¨从操作方式与种类看à不同于线性表：栈与队列是操作受限的线性表2、栈的基本概念栈---是限制仅在线性表的一端进行插入和删除运算的线性表。栈顶（TOP）--允许插入和删除的一端。栈底（bottom)--不允许插入和删除的一端。空栈--表中没有元素。栈--又称为后进先出的线性表3、栈中元素的特性：1、具有线性关系2、后进先出4、栈的进栈出栈规则：a)按序进栈：有n个元素1，2，…,n，它们按1,2,…,n的次序进栈(i进栈时，1~(i-1)应该已经进栈)；b)栈顶出栈：栈底最后出栈；c)时进时出：元素未完全进栈时，

7、即可出栈。5、栈的表示与实现顺序栈即栈的顺序存储结构：一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。1、附设一个栈底指针base，总是指向栈底。2、附设一个栈顶指针top。空栈时，top=base；非空栈时，总是指向栈顶元素＋1的位置。¨插入一个栈顶元素，指针top增1；¨删除一个栈顶元素，指针top减1；¨非空栈中的栈顶指针始终在栈顶元素的下一个位置上链栈：注意:链栈中指针的方向指向前驱结点！6、队列n队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。¨队尾(rear)——允许插入的一端¨队头(front)——允许删除的一端n队

8、列特点：先进先出(FIFO)7、队列类型的实现n链队列——队列的链式表示和实现n顺序队列——队